How is space from malloc allocated? Whenever we load a process (which consists of object code, static and global variables, stack and heap space) into main memory it would be of fixed size. But, the program doesn't know in advance how much heap memory is it gonna need? Is there some fixed stack and heap space given to each process of some size in advance? But, then wouldn't it be a waste of space to give same amount of stack and heap space for each process ?

There can  be other possibility that whenever we execute malloc, operating system gives us free space (basically holes) from main memory which is not the part of process. So, process size can increase at runtime. Then, Why is stack and heap space given to a process in the first place?

malloc is a library function that makes use the sbrk system call. The manual page of malloc on Linux says:

  Normally,  malloc() allocates memory from the heap, and adjusts the size of the heap as required, using sbrk(2).

If we now look at sbrk manual page:

   brk() and sbrk() change the location of the  program  break,
   which  defines  the end of the process's data segment (i.e.,
   the program break is the first location after the end of the
   uninitialized  data  segment).  Increasing the program break
   has the effect of allocating memory to the process; decreas
   ing the break deallocates memory.


Is selection in genetic algorithm considered to be a genetic operator? It is listed as such in wiki, however my literature never refers to it as such.
My gut tells me to follow papers and monographs on the matter, but my concern is that I will make an easily avoidable mistake, or that I simply misunderstood the text.

One of my first Google hits is a widely-cited article:

Eberhart, Russell C., and Yuhui Shi. "Comparison between genetic algorithms and particle swarm optimization." In International Conference on Evolutionary Programming, pp. 611-616. Springer, Berlin, Heidelberg, 1998.

The third paragraph of the article says:

  Regardless of the specific implementation, it is generally agreed that GAs utilize one form or another of three operators: selection, crossover, and mutation.


Meta Programming Operators I have a basic understanding how operators work (bitwise, logical, unary, ternary, etc.), but I am confused how you define what the operator does so the machine knows how to treat the operator when you use it in your code base. Are operators predefined by the compiler and is there a way for me to access the source code of an operator's definition?

The language specification defines what the operator does, and the compiler produces the appropriate machine instructions to implement this. In general, there's no reason to assume that the operator is implemented as a sequence of statements in the language that's being compiled (e.g., operators in C aren't first translated into longer expressions in C).

In many cases, (e.g., addition and multiplication), the appropriate machine instructions will be just one instruction.


Checking if several sets of pairs covers a given set of pairs Suppose we have $N$ arrays of pairs, e.g. for $N=3$:

$A_1 = [ [3,2], [4,1], [5,1], [7,1], [7,2], [7,3] ]$,

$A_2 = [ [3,1], [3,2], [4,1], [4,2], [4,3], [5,3], [7,2] ]$ and

$A_3 = [ [4,1], [5,1], [5,2], [7,1] ]$.

We can assume that the pairs in every array are sorted by the first number, and then by the second number. Also, the same pair won't appear in the same array more than once (same pair can appear in multiple arrays, as you can see above).

The numbers in every pair are arbitrary integers $\geq 1$.

How could I find all the $k$'s that satisfy:

$\exists \{ p_1, p_2, ... , p_N\}\subseteq [1..N]\ \forall n \in [1..N]: [k,n]\in A_{p_n}$

The expected result for the example above is: $[5, 7]$.

Note: Speed is the most critical factor of the algorithm, then memory. If it helps to optimise for speed/memory, assume that $N\leq 10$. The number of pairs in an array can be ~50000.

Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A_1,\ldots,A_N \subseteq [N]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A_i$.

Given the $A_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A_j$. A permutation $\pi$ such that $\pi(i) \in A_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.


Collection of inference rules viewed itself as a judgment I'm confused about the intended meaning of the following passage from Bob Harper's Practical Foundations for Programming Languages:

  A collection of rules is considered to define the strongest judgment form that is closed under, or respects, those rules.

The author goes on to explain the italicized words.

Is this to be understood as saying that a collection of rules defines a unique judgment which somehow encompasses all judgments derivable from those rules?

If so- of what does this unique judgment consist? Does this necessarily include formal hypothetical judgments? Does it include some kind of union/conjunction of "orthogonal" applications of the rules? (eg $\overline{\text{zero nat}}$ and $\overline{\text{zero even}}$)

If not- what's the correct interpretation?

The interpretation of such paragraph is that rules define judgements. It's more or less the same as saying
closure: the judgment satisfies this rules
strongest: ..and this is all there is

So, for example, if you have the following two rules to define the judgement "to be a nat":

$$\frac{}{\mbox{zero nat}} \quad \frac{x \mbox{ nat}}{\mbox{suc(} x\mbox{) nat}}$$

then you are stating that:

closed:

$\mbox{zero}$ is a $\mbox{nat}$ and
if $x$ is a $\mbox{nat}$, then $\mbox{suc}(x)$ is a $\mbox{nat}$

strongest: no other word is a $\mbox{nat}$


Partitioning a bipartite graph to get disjoint components of same size I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $n$ connected components, each of size $k+1$ and containing one element of $S$. To be clear, $n$ and $k$ are inputs to the problem: it's not a maximisation problem.

The naïve brute force algorithm would consider $\binom{S}{n}$ candidate subsets of $S$, and would do $O(E)$ work for each to identify vertices in $T$ which have an edge to exactly one element of the candidate subset of $S$. For fixed $n$ that's $O(S^n E)$.

I'm not optimistic, because it's an independence problem, but is there an algorithm for fixed $n$ and $k$ whose running time is polynomial in $E$ with exponent independent of $n$ and $k$?

Your problem is NP-hard, even for any fixed $k \geq 3$ by a straight-forward reduction from 3-SET-COVER. Quick explanation: nodes of $S$ are triplets, nodes of $T$ are set elements and each triplet connected to all elements it contains.

I am still thinking about the case when $n$ is fixed.


Convert DFA to Regular Expression In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first.
The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states
$(q_0$,$q_1,q_3)$ such that:

  We go from $q_0$ to $q_1$ with RE $a+ba$
  We go from $q_0$ to $q_3$ with RE $bb$
  We go from $q_1$ to $q_1$ with RE $ba$
  We go from $q_1$ to $q_3$ with RE $a+bb$

I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

:

:

The conversion in each step forms REs that describe

The previous direct edge from one state to another and
the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.


General Approach To Calculate Minimum Number Of Flip-Flops Required In the previous two years of the GATE exams, a question has been asked for finding number of flip flop's for counting sequence $0−1−0−2−0−3$ in 2016 and $0−0−1−1−2−2−3−3−0−0$ in 2015. But still, the approach discussed in these questions hasn't arrived at Common answer (or) solution.

For $0−1−0−2−0−3$, there are $6$ different states, and thus it acts as a mod−6, counter So, 3 FF's are suffice. In another approach it is said that $2$ bits are used to distinguish three $0$′s and $2$ for $1,2,3$. So number of FF's required =2+2=4

Similar is the case in $0−0−1−1−2−2−3−3−0−0$, one approach says setting clock such that output of FF will be sampled at twice the input frequency makes me think 2 FF's would suffice. But on the other-hand using 2 FF's for $1,2,3,4 $ and 1 FF for identifying which 1 out of two 1′s makes me think $3$ is also right.

So, I want to be sure in answering these type of questions as they have been asked in recent past [GATE][3] Exams.Please tell the general approach to solve these type of questions also please comment about minimum number of JK
FF's required for following counting sequence so that i will be able to work out myself using the technique provided by you and evaluate my understanding.

$0−0−0−1−1−2−2−3−3−...$
$0−1−0−2−0−2−0−3−0−2−...$
$1−2−3−0−0−1−0−2−2−...$

The links you have provided (gateoverflow) are themselves quite helpful. However if you want a even more elaborate explanation then read further.

In the very first question you have sequence 0--1--0--2--0--3
now these numbers represented in binary are:  00--01--10-00-10--00-11
So clearly you would need 2 bits to determine each of those number so 2 FF for that. Moreover there are 3 similar states for that are 000,000,000 so in order to differentiate between them you further would require 3 combinations that would need log(3)base2 digits =2 digits. thereby 2 FF would be required here too.

So that is a total of 2+2 Flip flops required.
Let me know if I could help you further.


Why isn't set $\{ \langle i, j \rangle \mid W_i = \overline{W_j}\}$ a recursively enumerated set? Why isn't the set $\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ a r.e. set?

Note: $W_x = L(M_x)$

Hint: Use a reduction for the proof. If your  language $L=\{ \langle i, j \rangle \mid W_i = \overline W_j\}$ is r.e. then of course  every language where the second machine $M_j$ is fixed is also r.e.. Say, you pick for $M_j$ the Turing machine that always accepts, then you are left with showing that the language $L_0=\{ i \mid W_i = \emptyset \}$ is not r.e.. This again can be shown with a reduction (i.e., show that $\overline{\text{HALT}}\le_p  L_0$). Alternatively, show that $L_0$ is not decidable (Rice's Theorem), but $\overline{L_0}$ is Turing-recognizable.


Can a RE language be reduced to a non-RE language? In our lecture notes about many-one reduction we showed that the following statements hold:
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L' \in RE \implies L\in RE$$
$$(II)\space L \notin RE \implies L'\notin RE$$

Now I was wondering if this would also be true if you'd reverse these statements i.e.
$$ L, L' \subseteq \mathbb{N}\space and \space L\leq L'$$
$$(I)\space L \in RE \implies L'\in RE$$
$$(II)\space L' \notin RE \implies L\notin RE$$

First, note that if $p$ and $q$ are any two statements, the implication $p\implies q$ is logically equivalent to $(\lnot q)\implies(\lnot p)$. This equivalence is known as "taking the contrapositive".

Because of this, your statements $(I)$ and $(II)$ are equivalent. That is, the first two properties you mention are equivalent (and they follow from $L \leq_m L'$). The second two properties are also equivalent. Your question then becomes:

$(I)$ If $L \leq_m L'$ and $L \in RE$, can we conclude $L' \not\in RE$ ?

In general, no, we can not conclude that.

For instance, take $L=\{0\}$. This is a decidable language (we can test the input string against $0$, and accept iff they are equal), so it is also a $RE$ language.

Now, note that we can many-one reduce $L$ to absolutely any set $L'$ except the empty set and the full set ($\Sigma^*$). This includes non-$RE$ sets like the complement of the halting problem.

Indeed, to find a reduction, take any word $w\in L'$ and any other word $x\notin L'$. Then, the reduction function behaves as follows: it tests its input, if it is equal to $0$, then it returns $w$, otherwise it return $x$.

By construction, this is a reduction, so $L \leq_m L'$, even if $L\in RE$ and $L'\notin RE$.


How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming? I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by absolute differences.

Example:

Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups.
Let's say we want to minimize sum of absolute differences (SAD).
Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)
Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 <- That's what we want to minimize.

The question is how to solve it using dynamic programming?

The original question - https://stackoverflow.com/questions/9275280

Fortunately you can calculate the group average that you are aiming for (sum of numbers, divided by the number of groups). In your case, you want the groups close to 18 1/3.

So using dynamic programming, you solve "How do I split the first m numbers into n groups, minimizing abs (sum of numbers in group - 18 1/3)", for 0 ≤ m ≤ M, and for 1 ≤ n ≤ N. You solve this by putting 0 ≤ k ≤ m items in the last group, calculating the penalty for the last group and adding the solution for n-1 groups made from the first m-k items, picking the best choice.

It feels a bit weird, because the solutions you find on the way are awfully bad. Splitting the first 0 numbers for example into 3 groups creates 3 empty groups, with a total sum of 3 * (18 1/3) = 55, but it works. What you find for N groups from M numbers is optimal.

This works easily on O (M^2 N). You can do this faster by first finding a reasonably good solution, and then excluding everything that isn't as good as the best solution.

Example: First, make each group as large as possible without the first n groups exceeding n * 18 1/3, that is (1 2 3 4 5) (6 7 8) (9 10) with penalties 3 1/3, 2 2/3, 2/3, total 6 2/3. Now we only care for 1 group with a penalty ≤ 6 2/3, then for 2 groups with a penalty ≤ 6 2/3 etc.

But also, if the remaining M-m items that need to go into N-n groups have a sum of S, they must have a penalty of at least abs (S - 18 2/3 * (N - n)), so the penalty for the first n groups plus this extra penalty must be ≤ 6 2/3. This will help if you have thousands of items.


Are machine codes always numerical? (WIkipedia is Ambiguous) Wikipedia article on machine code and more in general Wikipedia's take on machine code seems pretty amiguous sometimes.
Often it makes me wonder if there's more, or it is just bad generalization.

Look at this:

  Machine code or machine language is ......Numerical
  machine code (i.e., not assembly code) may be regarded as the
  lowest-level representation of a compiled or assembled computer
  program or as a primitive and hardware-dependent programming language.

It seems to treat numerical machine codes as a subset of machine codes.
Does this imply assembly has to be considered a machine code too?
Or...Is it just implying that exists some non-numerical machine code?
Maybe it's just bad-written, or maybe it's me.

Again, article on object code:

  In a general sense an object code is a sequence of statements or
  instructions in a computer language,[2] usually a machine code
  language (i.e., binary) or.....

"i.e, binary" Does this mean that there are non-binary machine codes?

I'm a little bit confused.

Yes and no and, really, it doesn't matter.

All data in computers, including programs, is stored in devices that have two possible states – e.g., memory cells that can be at a high voltage or low voltage or areas of a disc that are magnetized north–south or south–north. These two-state systems are naturally interpreted as the binary digits 0 and 1.  Any sequence of 0s and 1s can naturally be interpreted as a number written in binary.

Machine code is data that is stored on computers. Therefore, it is stored in a sequence of two-state cells, which can be viewed as a sequence of binary digits, which can be viewed as a binary number (or a sequence of binary numbers if you divide it into blocks). Does that mean it is a binary number? Really, that's a question of philosophy. The computer doesn't say "That pattern of 1s and 0s represents the number 3476247, which means I should do X": it just says "That pattern of 1s and 0s means I should do X." To the computer, it's just an instruction. But if you and I want to talk about that instruction, it's probably easiest to first see it as a number and then figure out what instruction it stands for.


What is the difference between undecidable language and Turing Recognizable language? I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask:

Prove that the language $ A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is undecidable.
Prove that the language $ A_{TM} = \{ \ <M,w> | \ M \mbox{ is a Turing Machine accepting } w\}$ is Turing Recognizable.

Are they the same thing? Can someone elaborate on this issue?

Another one, is the question at hand is known as the halting problem? Or is it different from halting problem?

A language $L$ is decidable if there exists a Turing machine $M$ such that:

If $x \in L$ and $M$ is run with input $x$, then $M$ halts at an accepting state.
If $x \notin L$ and $M$ is run with input $x$, then $M$ halts at a rejecting state.

(In particular, $M$ always halts.) If no such Turing machine exists, $L$ is undecidable.

A language $L$ is recognizable (or, recursively enumerable, abbreviated r.e.) if there exists a Turing machine $M$ such that:

If $x \in L$ and $M$ is run with input $x$, then $M$ halts.
If $x \notin L$ and $M$ is run with input $x$, then $M$ doesn't halt.

If no such Turing machine exists, $L$ is unrecognizable.

A basic fact about these definitions is:

  A language $L$ is decidable if and only both $L$ and $\overline{L}$ are recognizable.

Your language $A_{TM}$ is one way of stating the halting problem (there are many equivalent ways). It is recognizable but not decidable.


Why do we need assembly language? We mostly write programme in high level language. So while studying I came across assembly language. So an assembler converts assembly language to machine language and a compiler does the same with high level language. I found assembly language has instructions like move r1 r3 , move a 5 etc. And it is rather hard to study. So why was assembly language created?or was it the one that came first even before high level language? Why am I studying about assemblers in my computer engineering class?

"So why was assembly language created?"

Assembly language was created as an exact shorthand for machine level coding, so that you wouldn't have to count 0s and 1s all day.  It works the same as machine level code: with instructions and operands.

"Which one came first?"

Wikipedia has a good article about the History of Programming Languages

"Why am I studying about assemblers in my computer engineering class?"

  Though it's true, you probably won't find yourself writing your next
  customer's app in assembly, there is still much to gain from learning
  assembly.

  Today, assembly language is used primarily for direct
  hardware manipulation, access to specialized processor instructions,
  or to address critical performance issues. Typical uses are device
  drivers, low-level embedded systems, and real-time systems.

  Assembly language is as close to the processor as you can get as a programmer
  so a well designed algorithm is blazing -- assembly is great for speed
  optimization. It's all about performance and efficiency. Assembly
  language gives you complete control over the system's resources. Much
  like an assembly line, you write code to push single values into
  registers, deal with memory addresses directly to retrieve values or
  pointers. (source: codeproject.com)


Deletion of record from B+ tree I was going through the B+ tree deletion operation from the book Database System Concepts, 6th Edition by Henry F. Korth. One particular thing caught my attention.

A B+ tree is given. We have to delete the record "Gold" from this tree.

So we first locate the record by going down the tree and once we find the node, we delete the record. But this deletion leaves the node underfull, because a leaf node has to be at least half full or it has to have at least $\lceil{\frac{n - 1}{2}}\rceil$ values, where $n$ is the maximum number of pointers in each node.

So we merge the rightmost two nodes. But this leaves their parents left pointer pointing to nothing. We again have a violation. Because the internal nodes need to have at least two pointers. To get around this, we merge the parent with its sibling. Resulting tree is given below:

Now the problem I'm having is that, why the record "Gold" has been moved down? We could have just as easily moved the record "Katz" up without violating anything. And it makes more sense to me, because we've just deleted "Gold". So can anyone explain to me why this has been done like this in the book? And would I be right in saying that things would be the same if "Katz" had been moved up?

Yes and yes.

Any key that doesn't mess up the sort order can be used. Typically (in my experience), this is the minimum value from the right subtree. However, I'm not aware of any specific scenario where this would cause a problem either way.

When you delete a key (one practice I have seen is that) you delete the key along with the value. So, if you delete "Gold" you also delete all the keys with the value "Gold", so that no "Gold" remain. This wasn't done in this case and it's perfectly fine.

The thing about B tree and variants is that there are several ways you can implement them without violating any of the B tree properties. This leads to subtle differences like the one you've observed.


Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS? The following problem appears in "Introduction to Algorithms" by Thomas Cormen et. al., aka CLRS.
Problem 7-1.b
Hoare's partition algorithm from the book.

Part b: Assuming the subarray $A[p,\cdots,r]$ contains at least two elements, show that the indices $i$ and $j$ are such that we never access an element of outside the subarray $A[p,\cdots,r]$

I think this it is not possible to prove this because this statement is not correct, i.e., during the course of execution we happen to access elements outside the array.
Here I prove the converse of part b by using a counter-example.
Consider the array A = [1,2]. Let p = 1 and there r =2.

Initially, $i = 0$, $j = 3$ and $x = 1$.
After the loop $5-7$ executes once, $j$ becomes 2 and the condition in line 7 fails resulting the termination of the loop $5-7$.
Now we reach the loop $8-10$. Now let's look at the state after this loop executes twice. $i = 2$ and the condition in line 10 still holds. Therefore the loop executes a third time and $i$ becomes 3.
Now to test the condition in line 10 we access $A[3]$ which is outside the subarray $A[1,\cdots, 2]$

Is there a mistake in my reasoning or is the problem statement wrong?

The problem statement is correct.
I think you getting confused about: repeat $j \gets j-1$ until $A[j] \leq x$. It means that if $A[j]>x$ then do $j \gets j-1$.
Similarly, loop $8-10$ means that if $A[i]<x$ then do $i \gets i+1$.
Therefore, the algorithm executes in the following way on $A = [1,2]$:

After the loop $5-7$, $j$ becomes $1$ since $A[2] > x$.

After loop $8−10$, $i$ becomes $1$ since $A[1] = x$.

Since $i = j = 1$, the algorithm terminates and returns $1$.


Does amortized complexity always equal to worst case complexity divided by n? Is it true that given any operation that takes O(f(n)) amount of time, we do this n times in a process, then the amortized cost is O(f(n))/n?

I'm confused because this statement is so simple and applicable, I don't see the need for accounting method or potential method if we can just divide the worst case operation i.e. enlarging a dynamic array or multipop by the times we want the operation to be perfornmed

No, if all we know about an operation is that it takes $O(f(n))$ times, then its amortized time is also $O(f(n))$. Sometimes, however, it is the case that while the worst-case running time is $O(f(n))$, the worst case cannot happen all the time. A good example is dynamic arrays. Suppose we want to maintain an increasing array, but we don't know in advance how big the array is going to be. Therefore we use the following algorithm for inserting an element to the array; in the algorithm, $N$ is the current length the array, and $n$ is the current number of elements in the array, both initialized to $1$:

If $n = N$, create a new array of length $2N$, copy the old array into the new array, and free the old array.
Add the new element to the end of the array.

When $n < N$, this operation takes time $O(1)$. However, when $n = N$, we need to copy the entire array, and so it takes $O(n)$. The running time of insertion is therefore not even bounded! Nevertheless, the amortized running time of insertion is $O(1)$. Intuitively, the reason is that the expensive copying operation is very rare.

Indeed, suppose we perform $m$ insertion operations. The expensive operation occurs at the first, second, 4th, 8th, 16th, and so on, insertions, and involve copying $1,2,4,8,16,\ldots,M$ elements, where $M \leq m$. The total number of elements copied is $1+2+4+8+16+\cdots+M = 2M-1 < 2m$, and so the total running time is $O(2m) + O(m) = O(m)$, the first summand corresponding to the copying operations, the other corresponding to the cheap second step of the algorithm above. The amortized running time is therefore $O(m)/m = O(1)$.

There are several methods to prove upper bounds on the amortized running time, such as the accounting method and the potential method. These are just mathematical tricks that are supposed to help you analyze algorithms, though as the example analyzed above shows, you don't really need to use them formally in order to analyze the amortized running time; it's enough to use the definition of amortized running time. In more complicated cases these methods could be more helpful, though I feel that they are being taught mostly for historical reasons such as their inclusion in some influential textbook.


Problem with Church numerals evaluation I am trying to understand Church's Numerals for 4:

$$4 = \lambda f.\, \lambda x.\, f f f f x\,.$$

This will be evaluated in the following order:

$$\lambda f.\, \lambda x.\, (f (f (f (f x) ) ) )\,.$$

My question is why the function body will not evaluate left outer most, like

$$( ( ( ( (f f) f) f) f) x)\,?$$

Function application is not associative. It may seem at first that this is valid because function composition is associative, but according to Wikipedia,

  Bracketing may be used and may be needed to disambiguate terms. For example, ${\lambda x.((\lambda x.x)x)}$ and ${(\lambda x.(\lambda x.x))x}$ denote different terms (although they coincidentally reduce to the same value). Here the first example defines a function that defines a function and returns the result of applying $x$ to the child-function (apply function then return), while the second example defines a function that returns a function for any input and then returns it on application of $x$ (return function then apply).

$\lambda f.\lambda x.((ff)f)x$ is a distinct lambda term from $\lambda f.\lambda x.(f(ff))x$.


Rational subsets of a monoid In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the following properties:

the empty set is in $F$;
Each single element set is in $F$;
If $X, Y$ are in $F$, then $X \cup Y$ is in $F$;
If $X, Y$ are in $F$, then $XY$ is in $F$;
If $X$ is in $F$, then $X^*$ is in $F$.

In 4. $XY = \{xy \mid  x \in X \text{ and } y \in Y \}$, what is this product? concatenation product?

In the following link, there is a complete paper
http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1969-3RationalSetsCommutativeMonoids.pdf

The product is the monoid product. A monoid is a set equipped with an operation (which we can call product) satisfying certain axioms. The classical monoid we use in formal languages is $\Sigma^*$ (for some alphabet $\Sigma$), in which case the monoid product is indeed concatenation. But this is not the only possibility: for example, every group is a monoid, since the monoid axioms are a subset of the group axioms.


Equivalent unambiguous grammar Given the grammar:

$S \to AS\mid \varepsilon$
$A \to A1\mid 0A1 \mid \varepsilon$

Generate a new unambiguous grammar that generates the same language as the grammar above.

I have no idea how to make it unambiguous, I have proven already that the given language has two leftmost derivations for the string 01101.

Your grammar generates the language $L(A)^*$, where
$$
L(A) = \{0^i 1^j : j \geq i\}.
$$
You can generate $L(A)$ unambiguously in many ways. Two options are:

Use $0^i 1^j = 0^i 1^i 1^{j-i}$.
Use $0^i 1^j = 0^i 1^{j-i} 1^i$.

Given that, the current productions for $S$ will already generate $L(A)^*$ unambiguously.


Finding the point nearest to the x-axis over some segment I have problem with solving the following exercise

  Given the set $P$ on $n$ points in two dimensions, build in time $O(n\log n)$ a data structure of $P$ such that given a horizontal segment $s$ find the first point that $s$ touches when moving upwards from the x-axis in time $O(\log^2n)$.

The preprocessing time is equivalent to sorting, so we can perform sorting by one dimension.

The query time is a little bit confusing - $\log^2$n. I would say it's $\log n$ binary searchs but it doesn't make sense.

The $\log^2(n)$ implies that at each node in the search you probably have to do another search. This gave me an idea. Let's construct a tree from the input data:
$$\text{LeafNode} = \{ x, y \}$$
$$\text{NonLeafNode} = \{ \text{Min}_x, \text{Max}_x, \text{MinYPoint} \}$$

Each node will partition the input space into two non-overlapping ranges. The root node will thus be the complete range of $x$ in the input data with the minimum $y$ value.

Then we define a recursive search function that takes a node and the horizontal line segment and returns either the minimum $y$ or $\text{NotFound}$ condition (for simplicity say the value of $\infty$ represents $\text{NotFound}$).

GlobalMinY = Infinity

search( Node, segment ) -> MinY
    if Node does not overlap segment
        return Inf
    if Node.MinY >= GlobalMinY
        return Inf
    if Node is sub-segment
            GlobalMinY = Node.MinY
        return Node.MinYPoint

    return Min( search(Node.Left), search(Node.Right) )

It's easy enough to construct these tree using a modified merge-sort, so construction time is within the bounds. What I'm having a hard time showing is that the search time is within the required bounds.

Search time: Other than the root node, at each node one of the Left or Right nodes will either be included completely or excluded completely. Only one of them can have a partial overlap. If this is correct the time is $2 \log(n)$ -- from root we do two searchs and each follows only a single path through the tree. I'm not even sure the GlobalMinY optimization is needed.


Is the "subset product" problem NP-complete? The subset-sum problem is a classic NP-complete problem:

  Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ that sums to $k$?

A student asked me if this variant of the problem called the "subset product" problem is NP-complete:

  Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

I did some searching and couldn't find any resources that talked about this problem, though perhaps I missed them.

Is the subset product problem NP-complete?

A comment mentions a reduction from X3C to SUBSET PRODUCT attributed to Yao.  Given the target of the reduction it wasn't hard to guess what the reduction was likely to have been.
Definitions:

EXACT COVER BY 3-SETS (X3C)
Given a finite set $X$ with $|X|$ a multiple of 3, and a collection $C$ of 3-element subsets of $X$, does $C$ contain an exact cover $C'$ for $X$, where $C' \subseteq C$ and every element in $X$ occurs in exactly once in $C'$?
SUBSET PRODUCT
Given a list of numbers $L$ and a target $k$, is there a subset of numbers from $L$ whose product is $k$?

To reduce an X3C instance to a SUBSET PRODUCT instance:

Establish a bijective mapping between the members of $X$ and the first $|X|$ prime numbers.  Replace the members of $X$ and the $C$ subsets with the mapped primes.

For each subset in $C$, multiply its members together; the resulting list of products is $L$ for the SUBSET PRODUCT instance.  Because prime numbers are used for the mapping in step 1, the products are guaranteed to be equivalent iff the subsets are equivalent by the unique factorization theorem.

Multiply the members of $X$ together; the resulting product is the value $k$ for the SUBSET PRODUCT instance.

The prime factors of $k$ are exactly the members of $X$.  The prime factors of the numbers in $L$ correspond exactly to the members of the $C$ subsets.  Therefore any solution to the new SUBSET PRODUCT instance can be transformed into a X3C solution by mapping the solution members of $L$ back to the subsets in $C$.
Each of the 3 transformation steps involves operations that are polynomial to the size of the input $|X|$ or the size of a member of $X$.  The first $|X|$ primes can be generated in time O($|X|$) using the sieve of Eratosthenes and are guaranteed to fit into $O(|X|^2 \ln |X|)$ space by the prime number theorem.


Average number of full nodes in a binary search tree Let $f(N)$ be the average number of full nodes (nodes with two children) in an $N$-node binary search tree.

Determine the values of $f(0)$ and $f(1)$.

Given that for $N > 1$,
$\qquad \displaystyle f(N) = \frac{N-2}{N} + \frac{1}{N} \sum_{i=0}^{N-1} [f(i) + f(N - i - 1)]$,
show that $f(N) = \frac{N - 2}{3}$.

Using this information, show that the average number of nodes with one child in a binary search tree is $\frac{N + 1}{3}$.

I know that for (1) both values are $0$. I mainly need help proving (2).
I also found some hints for (2) and (3) but I can't figure it out:
(2) The root contributes $\frac{N − 2}{N}$ full nodes on average, because the root is full as long as it does not contain the largest or smallest item. The remainder of the equation is the expected contribution of the subtrees.
(3) The average number of leaves is $\frac{N + 1}{3}$.
Any help would be appreciated, even just pointing me in the right direction. Thanks!

As the both the formula itself is given $f(n) = \frac{n-2}{3}$ as well as the inductive structure $f(n) = \frac{n-2}{n} + \frac1n \sum_{i=0}^{n-1}{\dots}$, it seems you are requested to show the formula by (mathematical) induction. Hint (2) only explains the formula.

Inductively you apply the formula for $f(k), k<n$ in the recursive expression and conclude that it also holds for $f(n)$. I can do that, but run into trouble. The formulas do not match.

Summing $f(i) + f(n-i-1)$ is easy, as it is equal to $\frac{i-2}3 + \frac{n-i-1-2}3 = \frac{n-5}3$, so the $i$'s cancel. Plugging it into the recursion yields $\frac{n-2}{n} + \frac nn \frac{n-5}3$ which is not the expected $\frac{n-2}{3}$.

edit: The first values of $f$ however are special. $f(0) = f(1) = 0$, where the formule $\frac {n-2}3$ predicts $\frac {-2}3$ and $\frac {-1}3$ respectively.  Thus we have to correct this within the summation, twice as it occurs in both $i=0,1$ and $i=n-1,n$, and add $\frac 2n$. Amazingly, that works.

Part (3) just expects you to know what is the relation between the numbers of full nodes and leaves in a binary tree.


Why are these languages not regular? Show that the following languages are not regular:

$(1)\ L=\left\{a^nb^mc^k\mid n>k \land n,m,k>0\right\}$

$(2)\ L=\left\{a^nb^mc^k\mid m>k \land n,m,k>0\right\}$

I've difficulties showing that these two languages are not regular by using the Pumping Lemma. Any suggestions?

I think it is easier to prove if you first note note $$ L' = \{a^nb^mc^k|n\leq k \land n,m,k>0\} = \{a^nb^mc^k | n,m,k \geq 1 \} - \{a^nb^mc^k|n>k \land n,m,k>0\}$$ So if $\{a^nb^mc^k|n>k \land n,m,k>0 \}$ is regular then so is $\{a^nb^mc^k|n\leq k \land n,m,k>0\}$ since $\{a^nb^mc^k | n,m,k \geq 1 \}$ is regular and the difference of regular sets is a regular set.

But $L'$ is not regular, a contradiction. If you are NOT convinced that $L'$ is not regular then see the following proof using the Pumping lemma.

So, let's prove that $L' = \{a^nb^mc^k|n\leq k \land n,m,k>0\}$ is not regular using the Pumping lemma in order to obtain contradiction.

The Pumping Lemma:

Let $L$ be a regular set. Then there is a constant $n$ such that if $z$ is any word in $L$, and $|z| \geq n$ we may write $z = uvw$ in such a way that $|uv| \leq n$, $|v| \geq 1$, and for all $i \geq 0$, $uv^iw \in L$.

How to prove

1) Select the language you wish to to prove irregular.

2) The "adversary" picks $n$, the constant mentioned in the Pumping lemma. Once it has been picked, it may not be changed (fix it).

3) Select a string $z$  in $L$. Your choice may depend implicitly on the value of $n$.

We choose $z = a^nb^nc^{n+1}$ (since $n < n+1$, $z \in L$).

4) The "adversary" breaks $z$ into $u$, $v$, and $w$, subject to the constraints that $|uv| \leq n$ and $|v|$.

5) You achieve a contradiction to the pumping lemma by showing that there exists $i$ such that $uv^iw \notin L$.

Since $z = a^nb^nc^{n+1} = uvw$ and $|uv| \leq n$, $uv$ is a string consisting of only $a$s, and so is $v$. If we choose $i=n+2$ then we get
$uvvw$ such that $uv^{n+2}w$ has at least $n+2$ $a$s which is greater than $n+1$ $c$s which does not belong to $L'$. But this contradicts to the Pumping lemma.

You may try to prove the second language  yourself.


Karp hardness of a guarding set in digraph Our problem is to decide whether a digraph has a guarding set of size at most $k$. Definitions are following.

A digraph $G(V,A)$ has $V(G)$ as its vertex set and $A(G)$ as its arc set. A guarding set $S\subseteq V(G)$ is a set of vertices such that:

  For each vertex $v\in V(G)$, some of its incoming neighbor $u$ (i.e.
  $(u,v)\in A(G)$) is included in $S$ (i.e. $u\in S$) and some of its
  outgoing neighbor $w$ (i.e. $(v,w)\in A(G)$) is included in $S$ (i.e.
  $w\in S$)

  In case of empty incoming neighborhood or empty outgoing neighborhood,
  the vertex $v$ itself must be included in $S$. In other word, we may think that the incoming neighborhood and outgoing neighborhood of $v$ both include $v$.

Informally, imagine a facility in which one can enter at some entry points and exit at some exit points, a guarding set for this facility needs to be placed at least at some entry point (maybe where one can enter secret area of the facility) and at some exit point (maybe where one can bring out the secrets from the secret areas inside). Hope that this suffices to explain the terminology.

Our problem is now formally defined:

  Input: A digraph $G(V,A)$ and a natural number $k$

  Output: YES if $G$ has a guarding set of size $k$, otherwise NO

What is complexity of this problem?

It is NP-complete (it is obviously in NP) by reduction from the dominating set problem.

Given an instance $G=(V,E)$ of the dominating set problem, split each vertex $v$ into two vertices $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$, and for each edge $(u,v)\in E$, construct two edges $(u_{\mathrm{out}},v_{\mathrm{in}})$ and $(v_{\mathrm{out}},u_{\mathrm{in}})$. We claim that $G$ has a dominating set of size $k$ iff the newly-constructed graph (say $G'$) has a guarding set of size $2k$.

If $G$ has a dominating set $S$ of size $k$, easy to see $\{v_{\mathrm{in}}\mid v\in S\}\cup\{v_{\mathrm{out}}\mid v\in S\}$ is a guarding set of $G'$, which has size $2k$.

On the other hand, suppose $G'$ has a guarding set $S'$ of size $2k$. Let $S'_{\mathrm{in}}=S'\cap\{v_{\mathrm{in}}| v\in V\}$ and $S'_{\mathrm{out}}=S'\cap\{v_{\mathrm{out}}\mid v\in V\}$, then either $S'_{\mathrm{in}}$ or $S'_{\mathrm{out}}$ must has size at most $k$. Without loss of generality, say $\left|S'_{\mathrm{in}}\right|\le k$, then $S=\left\{v\mid v_{\mathrm{in}}\in S_{\mathrm{in}}'\right\}$ is a dominating set of $G$. This means $G$ has a dominating set of size $k$.


Algorithm to convert many instances of unidirectional lists to a graph? I feel like I'm missing something basic.
I have instances of a list compromising of unique graph nodes / elements visited. Lists happen in order, but follow graph based rules (can be cyclical, only some connections are allowed, there are optional nodes in a graph, some nodes always happen in unison, etc). How can I derive the graph represented by billions of instances of these lists? And maybe even sub-graphs nested within?
e.g. list instance #1: A -> B -> D -> E
e.g. list instance #2: A -> F -> K
e.g. list instance #3: A-> B-> K > B -> D -> E

e.g. graph vertices derived from these lists:
A -> B
B -> D
B -> K
D -> E
F -> K

This feels like a solved compsci problem that I'm trying rearticulate. Like, I get that I can always calculate the vertices (either by weight / likelihood to occur, or as booleans if they occurred). But that feels like I'm missing a lot of nested complexity and trying to reinvent the wheel. Is there an esteblished approach to this problem?

You can find the smallest graph that is consistent with those walks from the graph as follows: start with an empty graph; for each pair of vertices that are adjacent in a list, e.g., $A \to B$, add the corresponding edge $A \to B$ to the graph.  The resulting graph is one that could have led to those walks, and is the smallest such.
You can't guarantee to uniquely and correctly reconstruct the original graph.  If you are unlucky, there could be some vertex in the graph that was just never visited by any walk, and then it won't appear in the reconstruction.  If walks are chosen randomly and you have enough of them, the probability of this happening might be low enough that you are willing to accept this risk.


Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$ I'm asked to find all equivalence classes of the language

$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$

We have the following definition:

$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \Leftrightarrow yw\in L)$$

As I understand, words $x$ and $y$ belongs to different equivalence classes if $\exists z \in \Sigma^*: xz \in L$ and $yz \notin L$ (or viceversa).

The language L above is not regular so it has infinitely many equivalence classes under $R_L$. In order to differentiate between two classes, I was thinking about defining the equivalence relation in the following way:

$$xR_Ly = \text{"}x[n] = y[n] = 0\text{ and }x[n+1] = y[n+1] = 1\text{"}$$

with $x[k]$ I mean the $k$-th letter in $x$. Under this "approach", all equivalence classes are generated by taking $n$ to be any number $\in \mathrm{N}_0$.

Under my attempt I have the following questions:

In the definition, nothing is said about $x$ and $y$ in $(xR_Ly)$. Do I have to assume that those are two arbitrary words that are already in $L$? (If not, then my approach doesn't work).

For a fixed $n \in \mathrm{N}_0$ I think $\exists$ just one word in the class $C_n$. Then does it mean that the unique word in $C_n$ is only equivalent to itself?

I think I'm not even close to the answer, so would appreciate any help with this.

Let $\Sigma=\{0,1\}$. Here are all (Myhill–Nerode) equivalence classes, $O_0,O_1, O_2,\cdots, L_0, L_1, L_2, \cdots$ as well as $R$.

$$ \begin{aligned}
O_{k} &= \{0^k\},  \ \text{ where } k \in \mathrm{N_0}. \\
L_{k} &= \{0^{m+k}1^m: m \in \mathrm{N} \},  \ \text{ where } k \in \mathrm{N_0}. \\
R &=\{x10^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n\ge m\}\cup\{x0^n1^m: x\in\Sigma^*,\, n,m \in \mathrm{N_0},\, n<m\}
\end{aligned} $$

If $a\in O_{k}$ and $b\in O_{t}$, $k\neq t$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in O_{k}$ and $b\in L_{t}$, $a01^{k+1}\in L$ while $b01^{k+1}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in O_{k}$ and $b\in R$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.

If $a\in L_{k}$ and $b\in L_{t}$, $k\neq t$, $a1^{k}\in L$ while $b1^{k}\not\in L$. So $a$ and $b$ are in different classes.
If $a\in L_k$ and $b\in R$, $a1^k\in L$ while $b1^k\not\in L$. So $a$ and $b$ are in different classes.

What remain to be proved are the following.

For any $k\ge0$, all elements in $O_k$ belong to the same class, which is true trivially since there is only one element.
For any $k\ge0$, all elements in $L_k$ belong to the same class.
all elements in $R$ belong to the same class.
$\cup_{k=0}^\infty L_k\cup R =\Sigma^*.$

I will let interested readers to fill in the details.

Now that the correct equivalence classes are shown, let me get to your questions.

  In the definition, nothing is said about $x$ and $y$ in $(xR_Ly)$. Do I have to assume that those are two arbitrary words that are already in $L$? (If not, then my approach doesn't work)

No, $x$ and $y$ may or may not be in $L$. Your approach doesn't work.

  For a fixed $n \in \mathrm{N}_0$ I think $\exists$ just one word in the class $C_n$. Then does it mean that the unique word in $C_n$ is only equivalent to itself?

I cannot find where $C_n$ is defined. If it is what I guess it is, there are more than one word in $C_n$. If it means $O_n$ I defined above, then it does have only one word, $0^n$.


Are there algorithms with proven upper bounds but no proven lower bound (above constant time)? One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a lower bound greater than this, which do have a proven upper bound?

I'm interested in both problems and algorithms, but in either case practical examples (if they exist) as opposed to artificial ones.

To try and answer your question:

Yes. generally lower bound is much harder to prove than upper bound.
That is, to prove an upper bound, you must only show one algorithm that solves problem $A$ in $t_1(n)$ time.

To prove a lower bound $t_2(n)$ for the same problem $A$, you must show that ANY algorithm that solves $A$ MUST work in at least $t_2(n)$ time.

Take the median for example (under the comparison model). There is a recursive algorithm that solves the median problem in $O(n)$ time. That means any greater upper bound is moot, and any greater lower bound is wrong.

However a precise lower bound for the median is an open question. The algorithm mentioned above performs $c*n$ comparisons, where $c$ ~ $17$. It has been proven that for selection of median, a total of $\Omega(\frac{3n}{2})$ comparisons is required (which means a better algorithm does not exist).

However, we don't know if a greater lower bound exist. Proving a $\frac{5n}{2}$ comparisons lower bound is an open question!


Find the first integer with exactly $n$ divisors For given positive integer $n$ find the first number $x$ with exactly $n$ divisors. For simplicity of the problem we can assume that $x$ will always fit in integer size and $n \leq 1000$.

Example

If $n=4, x = 6, \text{ divisors of 6 are } \{1, 2, 3, 6\}\\n=6, x=12, \text{divisors of 12 are } \{1,2,3,4,6,12\}$

I was thinking because the number should have at most 1000 divisors we should brute force them in some way, but I cannot think how it could be done.

Some observations: If p is a prime, then $p^{n-1}$ has exactly n divisors. And if for example p, q, r are different primes, then $p^{n-1} q^{m-1} r^{j-1}$ has exactly n * m * j divisors.

And that's the only way we can find numbers with exactly n divisors: We write n as a product n = n1 * n2 * n3 ..., then find primes p1, p2, p3 and so on, and the product $p1^{n1-1} p2^{n2-1} p3^{n3-1} ...$ has exactly n divisors.

If we sort so that n1 ≥ n2 ≥ n3, then a product that is not in the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ can be made smaller while having the same number of divisors by using the primes 2, 3, 5 in that order. For example, if we start with $2^3 5^2$ then $2^3 3^2$ has the same number of divisors, but is smaller. Likewise, $3^3 2^2$ can be replaced with $2^3 3^2$ with the same number of divisors, bit smaller.

So the smallest number with n divisors has the form $2^{n1-1} 3^{n2-1} 5^{n3-1} ... $ with n1 ≥ n2 ≥ n3 ... and n = n1 * n2 * n3 ...

Now a number like n = 1000, or n = $10^{1000}$, can be written as a product in many ways, so you need to reduce the number of possibilities. You can use an algorithm where you try all possible exponents for 2 that could lead to the smallest number with n divisors, then all possible exponents for 3, and so on.

Let n = p1 * p2 * p3 ... * pk, with primes p1 ≥ p2 ≥ p3 ≥ ... ≥ pk. Whenever we choose an exponent, that exponent is either p - 1 where p is the largest prime not used so far, or it is of the form ab - 1 where b is the smallest prime factor of ab, and ab is greater than that largest prime. (That's quite obvious, right? It's a prime or composite minus 1, and since the exponents are in descending order, its the largest prime minus 1, or greater than that).

n was the product of k primes. Let P be the k-th prime. If an exponent is of the form ab-1, then P is not a factor of the number. And if we have a factor $p^{ab-1}$, then replacing this with $p^{a-1} P^{b-1}$ gives a number with the same number of factors, but smaller unless $p^a < P$.

This hugely reduces the number of choices. Take n = $2^{1000}$ which is the product of 2,000 primes. The k-th prime is very roughly P ≈ 20,000.

We saw that the smallest number with n divisors can only have a factor $p^{ab-1}$ if $p^a < P$. We have $2^{15}≥P ≈ 20,000$, $3^{10} ≥ P$, $5^7≥P$, $7^6≥P$, $11^5≥$, and $13^4≥P$, so a ≤ 14 when p = 2, a ≤ 9 when p = 3, a ≤ 6 when P = 5, a ≤ 5 when P = 7, a ≤ 4 when P = 11, and a ≤ 3 when p ≥ 13. And we must have ab ≥ 5, b is the smallest prime factor of ab, and ab must only have prime factors 2 and 5.

As a result, the only composite exponents minus 1 that are possible in the smallest number with $10^{1000}$ divisors are: $2^{4*2-1}$, $2^{5*2 - 1}$, $2^{5*5 - 1}$, $2^{8*2-1}$, $2^{10*2 - 1}$, $3^{4*2-1}$, $3^{5*2 - 1}$, $3^{5*5 - 1}$, $3^{8*2-1}$, $5^{4*2-1}$, $5^{5*2-1}$, $5^{5*5-1}$, $7^{4*2-1}$, $7^{5*2-1}$, $7^{5*5-1}$, and $11^{4*2-1}$. This is followed by a huge number of factors $p^{5-1}$, finishing with a huge number of factors $p^{2-1}$.

Since the exponents have to be in non-decreasing order, there is only a small number of cases to try, even for a huge number like $n = 10^{1000}$.

PS. In your trivial examples, n = 4 = 2 * 2, the solution was $2^{2-1} 3^{2-1} = 6$, and with n = 6 = 3 * 2, the solution was $2^{3-1} 3^{2-1} = 12$.

PS. Assume you have a more moderately sized n, let's say an n that is the product of 10 primes, making P = 10th prime = 29. We have $2^5<29$, $3^3<29$, $5^2<29$, but $7^2 > 29$. Therefore the only possible factors with an exponent that is not a prime -1 are: $2^{4-1}$, $2^{9-1}$, $2^{6-1}$, $2^{8-1}$, $2^{10-1}$, $2^{25-1}$, $3^{4-1}$, $3^{9-1}$, $3^{6-1}$, and $5^{4-1}$.


See that P$^{NP}_{||} = P^{NP}_{O(\log n)}$ I'm trying to prove that P$^{NP}_{||} =$ P$^{NP}_{O(\log n)}$ where $n$ is the length of the input.

So, to see that polynomially many non-adaptive queries to a problem in NP can do as much as logarithmically many adaptive ones.

I know I need to see both inclusions, and have worked out the "easy" one: P$^{NP}_{||} \supseteq$ P$^{NP}_{O(\log n)}$ by arranging all the logarithmically many possibilities in a long deterministic one, and then use the fact that it's still polynomial (from known time complexity properties).

Now, I bang my head on a wall when I try to do the other one. I'm not even sure of where to start. I would very much appreciate your input on this problem, and besides the problem advice on where I could read examples on similar problems to get a better hang on them.

Please refer the theorem 7, in On Truth-Table Reducibility to SAT
and the Difference Hierarchy over NP  and On Truth-Table Reducibility to SAT by
Samuel R. Buss. The problem you mentioned is the original result by Buss. Hemachandra proved one of the inclusions in his PhD thesis.


VAR autoincrement with constant space consumption for super large tables Assume there was a database system that had a data type called VARINT or some variant that allowed instead of fixed-length INTs regardless of value, a 1 would only take 1 BIT (1), 2 would take 2 BITs (10), etc.

In this perfect world, a VARINT could be used to autoincrement a PRIMARY column.  However, there's still the issue of the field growing in size, so the "older" parts of this TABLE would be very fast, but the "younger" parts would get slower and slower.

What counting system could be used to hold the space consumed constant and small or at least grow at a much slower rate?

If you want an ID (i.e. unique label, whether number or not) which is stored as a binary (or $k$-ary) string you will have at least logarithmic growth, because with $o(\log n)$ bits you can't identify more than $k^{o(\log n)}=o(n)$ objects. So you can't do much better.

You could however map the old IDs to new IDs every time the size of the table doubles. If the entry #$2^m$ is inserted, the old IDs become $\mathrm{id}'=2^{m+1}+\mathrm{id}$ and the younger elements get shorter IDs. This only works if you don't use the IDs elsewhere (major drawback for a PRIMARY) and you have a reason to believe that newer entries get requested more often than older ones.

Finally one may ask whether you really need big integers for some kind of ID. According to this there are $\approx 10^{80}\leq 2^{267}$ atoms in the observable universe, so a kilobit sized ID will do for most purposes.


Why is average waiting time is the same for FIFO and LIFO I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:

  Support retrieval in first in, first out (FIFO) order. This is surely
  the fairest way to control waiting times for services. You want the
  container holding jobs to be processed in FIFO order to minimize the
  maximum time spent waiting. Note that the average waiting time will be
  the same regardless of whether FIFO or LIFO is used. Many computing
  applications involve data items with infinite patience, which renders
  the question of maximum waiting time moot.

Can someone please explain what is meant by minimizing maximum time spent waiting and why the waiting time is same for FIFO and LIFO?

Thanks

Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be:

t(0): 'a' and 'b' added: [a, b] - 'a' processed after waiting $0$ - [b]
t(1): 'c' and 'd' added: [b, c, d] - 'b' processed after waiting $1$ - [c, d]
t(2): 'e' and 'f' added: [c, d, e, f] - 'c' processed after waiting $1$ - [d, e, f]
t(3): [d, e, f] - 'd' processed after waiting $2$ - [e, f]
t(4): [e, f] - 'e' processed after waiting $2$ - [f]
t(5): [f] - 'f' processed after waiting $3$ - []

Average wait time: $(0 + 1 + 1 + 2 + 2 + 3) / 6 = 1.5$, longest wait time: $3$

Then consider a LIFO stack:

t(0): 'a' and 'b' added: [a, b] - 'b' processed after waiting $0$ - [a]
t(1): 'c' and 'd' added: [a, c, d] - 'd' processed after waiting $0$ - [a, c]
t(2): 'e' and 'f' added: [a, c, e, f] - 'f' processed after waiting $0$ - [a, c, e]
t(3): [a, c, e] - 'e' processed after waiting $1$ - [a, c]
t(4): [a, c] - 'c' processed after waiting $3$ - [a]
t(5): [a] - 'a' processed after waiting $5$ - []

Average wait time: $(0 + 0 + 0 + 1 + 3 + 5) / 6 = 1.5$, longest wait time: $5$


pictorial representation of pre and post ordering for edge types I am reading chapter 3 Decomposition of Graphs of Algorithms by Dasgupta, Papadimitriou & Vazirani and they show a pictorial representation of pre and post numbers with brackets for tree, forward, back and cross edges. I have pasted the image of the area I am unclear on.
I am assuming that u is the node/vertex we see first and then we see v later. Comparing to the 2nd image showing the definitions on a graph, I am taking u as node A.
What I don't get is the order for the other 2 back and cross edges. What I have is

u v u v for back edge.
u u v v for cross edge.

Essentially the order is flipped with u and v in what the textbook has. Could someone clarify why this is the case with the image below.

I read this answer but I came out more confused with the explanation.
Surprisingly I was able to correctly identify the pre and post numbers in this figure in the textbook. It is the letters u and v that have me confused.

"I am assuming that $u$ is the node/vertex we see first and then we see $v$ later." That is a wrong assumption, which makes that summarizing table unintelligible.
The right assumption consists of two parts.

We are given a directed graph that contains $(u,v)$, the edge from $u$ to $v$.
We have just completed one depth first search (DFS) on that graph, which has discovered both $u$ and $v$.

Given the assumption above, that table lists the correspondence between the "pre/post ordering for $u$ and $v$", and the "edge type" of $(u,v)$. Please note that I rephrase "pre/post ordering for $(u,v)$" as in the table to "pre/post ordering for $u$ and $v$", since the meaning of "$(u,v)$", the edge from $u$ to $v$ does not fit the former phrase exactly.

The first row, "$\stackrel{[}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{]}{u}\ $ Tree/forward" says that $u$'s discovery time and departure time enclose $v$'s discovery time and departure iff $(u,v)$ is a tree edge or a forward edge. $u$ is visited first in this case.
The second row, "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{]}{v}\ $ Back" says that $v$'s discovery time and departure time enclose $u$'s discovery time and departure time iff $(u,v)$ is a back edge. $v$ is visited first in this case.
The third row, "$\stackrel{[}{v}\,\stackrel{]}{v}\,\stackrel{[}{u}\,\stackrel{]}{u}\ $ Cross" says that $v$'s discovery time and departure time are before $u$'s discovery time and departure time iff $(u,v)$ is a cross edge. $v$ is visited first in this case.

Neither do we assume $u$ is visited first nor do we assume $v$ is visited first. The node that is visited first on each row of that table is, of course, the node that appears first from the left on that row.

Exercise (as given in the book). With the same assumption, "do you see why no other orderings are possible?" For example, why is "$\stackrel{[}{v}\,\stackrel{[}{u}\,\stackrel{]}{v}\,\stackrel{]}{u}$" not possible? why is "$\stackrel{[}{u}\,\stackrel{]}{u}\,\stackrel{[}{v}\,\stackrel{]}{v}$" not possible?


Select a subset of the columns in $3\times n$ matrix, is it NP-hard? I want to know if this problem is NP-hard?

The problem: Given a non-negative integer-valued matrix of size $3\times n$ of the form

$$
\begin{bmatrix}
a_1 & \ldots & a_n\\
b_1 & \ldots & b_n\\
a_1b_1 & \ldots & a_nb_n\\
\end{bmatrix},
$$

where $a_i,b_i$ are non-negative integers. Given four non-negative integer numbers $b<n$, $c_1$, $c_2$ and $c_3$.

The goal: Find a subset of the columns of cardinality at most $b$ such that (i) the sum of the first row over the subset of the columns is greater than $c_1$, (ii) the sum of the second row over the subset of the columns is greater than $c_2$ and (iii) the sum of the third row over the subset of the columns is less than $c_3$. Return no if no such subset exists. That is to say, is there exists a set $S$ of cardinality at most $b<n$ such that:

$$
\sum_{i\in S}a_i\geq c_1,\\
\sum_{i\in S}b_i\geq c_2,\\
\sum_{i\in S}a_ib_i\leq c_3,
$$

How to show that this problem is NP-hard?

Attempt:

Here is a "similar" NP-hard problem that I asked. This problem has as instance $(n,b,c,\mathbf{A})$ where $\mathbf{A}$ is given by
$$
\begin{bmatrix}
x_1 & \ldots & x_n\\
y_1 & \ldots & y_n\\
\end{bmatrix},
$$
I tried to reduce the previous problem to the new one as follows: choose $c_1=c_2=c$ and choose $c_3$ very big and create the matrix as follows:

$$
\begin{bmatrix}
x_1 & \ldots & x_n\\
y_1 & \ldots & y_n\\
x_1y_1 & \ldots & x_ny_n\\
\end{bmatrix},
$$

Your problem is NP-complete, indeed. You can, e.g., reduce PARTITION to your problem. If you want to know if there is a subset of the set $\{d_1,\ldots,d_k\}$ that sums up to exactly $D := \frac{1}{2} \sum_{i=1}^k d_i$, you can use your problem by setting $b_i := 1$ and $a_i := d_i$ for all $i$ and by setting $c_1 := D$, $c_2 = 0$, and $c_3 := D$ as well as $b := n-1$.


Problem on finite state machines in the feynman textbook I'm currently reading Feynman Lectures on Computation and got stuck in problem 3.1 which says

  Suppose we feed a sequence of 1's and 0's - a binary number -
  into a machine. Design a machine which performs a pairwise sum
  of the digits, that is, one which takes the incoming digits two at a time  and adds them, spitting the result out in two steps. So, if two digits come in as 00, it spits out 00; a 10 or 01 results in a 01 (1+0 = 10+11!); but a 11 results in binary 10: 1+1 = 2, in decimal, 10 in binary. I will  give you a hint: the machine will require four states.

I don't ask you the answer. Just I don't understand what this is asking.
For example, when the input sequences are (00)(01)(10)(11)(10)(00), output sequences should be what?

Thanks in advance.

The numbers are encoded LSB first. In your example, $(00)(01)(10)(11)(10)(00)$ corresponds to the addition $011100 + 001010$, and the answer should be $011001(0)$, corresponding to the binary answer $(0)100110$. The bit in parentheses is the carry bit, which I don't think Feynman intended you to output.

More generally, Feynman wasn't very accurate, so you should think of a reasonable concrete interpretation of the problem which will result in an automaton which has a small number of states; I can think of several, some of which requiring less than four states. (It depends whether $(00)$ is a single digit or a pair of consecutive digits.) I don't think it's very important to guess what Feynman intended exactly.


Complexity class of Matrix Inversion Is inverting a matrix in the Complexity class $\text{P}$ ?

From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded by the input?

Yes, it can be done in polynomial time, but the proof is quite subtle.  It's not simply $O(n^3)$ time, because Gaussian elimination involves multiplying and adding numbers, and the time to perform each of those arithmetic operations is dependent on how large they.  For some matrices, the intermediate values can become extremely large, so Gaussian elimination doesn't necessarily run in polynomial time.

Fortunately, there are algorithms that do run in polynomial time.  They require quite a bit more care in the design of the algorithm and the analysis of the algorithm to prove that the running time is polynomial, but it can be done.  For instance, the running time of Bareiss's algorithm is something like $O(n^5 (\log n)^2)$ [actually it is more complex than that, but take that as a simplification for now].

For lots more details, see Dick Lipton's blog entry Forgetting Results and What is the actual time complexity of Gaussian elimination? and Wikipedia's summary.

Finally, a word of caution.  The precise running time depends upon exactly what field you are working over.  The above discussion applies if you are working with rational numbers.  On the other hand, if, for instance, you are working over the finite field $GF(2)$ (the integers modulo 2), then naive Gaussian elimination does run in $O(n^3)$ time.  If you don't understand what this means, you can likely ignore this last paragraph.


Find a straight line to divide two convex polygons by equal area Suppose, we have two non-overlapping convex polygons $A$ and $B$. How can we draw one straight line which divides $A$ into two parts of equal area and also divides $B$ into two equal area parts?
Also, can we do this in complexity $O(n^2)$ or better? ($n = |A| + |B|$)

This is known as the Ham-Sandwich theorem:

  Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line.

Note: Convexity is not needed. And $\mathbb{R}^2$ can be replaced by $\mathbb{R}^d$ with "line" replaced by a $(d{-}1)$-dimensional hyperplane.

(Image from curiosity.com.)

See the Wikipedia link
for computational versions.

Added in response to @WillardZhan's request:

  Ivan Stojmenovíc. Bisections and ham-sandwich cuts
  of convex polygons and polyhedra. Inf. Process. Lett.
  38(1): 15-21. 1991.
  (CiteSeer PDF download.)

  Abstract. We present a linear time sequential algorithm for finding a straight line that bisects two given disjoint convex polygons (i.e. cuts both of them into parts of equal area).

  Abbott, Timothy G., Erik D. Demaine, Martin L. Demaine, Daniel M. Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung. "Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane." In CCCG, pp. 61-64. 2005.
  (PDF download.)


How does variance in task completion time affect makespan? Let's say that we have a large collection of tasks $\tau_1, \tau_2, ..., \tau_n$ and a collection of identical (in terms of performance) processors $\rho_1, \rho_2, ..., \rho_m$ which operate completely in parallel. For scenarios of interest, we may assume $m \leq n$. Each $\tau_i$ takes some amount of time/cycles to complete once it is assigned to a processor $\rho_j$, and once it is assigned, it cannot be reassigned until completed (processors always eventually complete assigned tasks). Let's assume that each $\tau_i$ takes an amount of time/cycles $X_i$, not known in advance, taken from some discrete random distribution. For this question, we can even assume a simple distribution: $P(X_i = 1) = P(X_i = 5) = 1/2$, and all $X_i$ are pairwise independent. Therefore $\mu_i = 3$ and $\sigma^2 = 4$.

Suppose that, statically, at time/cycle 0, all tasks are assigned as evenly as possible to all processors, uniformly at random; so each processor $\rho_j$ is assigned $n/m$ tasks (we can just as well assume $m | n$ for the purposes of the question). We call the makespan the time/cycle at which the last processor $\rho^*$ to finish its assigned work, finishes the work it was assigned. First question:

  As a function of $m$, $n$, and the $X_i$'s, what is the makespan $M$? Specifically, what is $E[M]$? $Var[M]$?

Second question:

  Suppose $P(X_i = 2) = P(X_i = 4) = 1/2$, and all $X_i$ are pairwise independent, so $\mu_i = 3$ and $\sigma^2 = 1$. As a function of $m$, $n$, and these new $X_i$'s, what is the makespan? More interestingly, how does it compare to the answer from the first part?

Some simple thought experiments demonstrate the answer to the latter is that the makespan is longer. But how can this be quantified? I will be happy to post an example if this is either (a) controversial or (b) unclear. Depending on the success with this one, I will post a follow-up question about a dynamic assignment scheme under these same assumptions. Thanks in advance!

Analysis of an easy case: $m = 1$

If $m = 1$, then all $n$ tasks are scheduled to the same processor. The makespan $M$ is just the time to complete $n$ tasks in a complete sequential fashion. Therefore,
$$\begin{align*}
 E[M]
 &= E[X_1 + X_2 + ... + X_n] \\
 &= E[X_1] + E[X_2] + ... + E[X_n] \\
 &= \mu + \mu + ... + \mu \\
 &= n\mu
\end{align*}$$
and
$$\begin{align*}
 Var[M]
 &= Var[X_1 + X_2 + ... + X_n] \\
 &= Var[X_1] + Var[X_2] + ... + Var[X_n] \\
 &= \sigma^2 + \sigma^2 + ... + \sigma^2 \\
 &= n\sigma^2 \\
\end{align*}$$

It seems like it might be possible to use this result to answer the question for $m > 1$; we simply need to find an expression (or close approximation) for $\max(Y_1, Y_2, ..., Y_m)$ where $Y_i = X_{i\frac{n}{m} + 1} + X_{i\frac{n}{m} + 2} + ... + X_{i\frac{n}{m} + \frac{n}{m}}$, a random variable with $\mu_Y = \frac{n}{m}\mu_X$ and $\sigma_Y^2 = \frac{n}{m}\sigma_X^2$. Is this heading in the right direction?

As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T_i$ is the time it takes the $i$-th processor to finish its work.

As $n$ grows, the probability that $T_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T_i)$, $E[M]$ approaches $5k$.

For the second scenario this is $4k$ so increasing the number of processors makes the 4–2 split better.

What about $k$ — increasing the number of tasks per processor? Increasing $k$ has the opposite effect, it makes it less likely to have a processor with an unlucky set of tasks. I'm going home now but I'll come back to this later. My "hunch" is that as $k$ grows, the difference in $E[M]$ between the 4–2 split and the 5–1 split disappears, $E[M]$ becomes the same for both. So I would assume that 4–2 is always better except maybe for some special cases (very small specific values of $k$ and $n$), if even that.

So to summarize:

Lower variance is better, all else being equal.
As the number of processors grows, lower variance becomes more important.
As the number of tasks per processor grows, lower variance becomes less important.


How does this algorithm for verifying if a string is $0^n1^n$ work? I have found an efficient algorithm for verifying if a string $\omega$ is of the form $0^n1^n$, where $n \in \mathbb{N}$.

Scan across $\omega$. If a 1 appears before a 0, then reject.
Repeat so long as some 0s and some 1s remain on the tape.

Scan across $\omega$. If the total number of 0s and 1s remaining is odd, reject.
Scan across $\omega$. Cross out every other 0 starting with the first 0.
Scan across $\omega$. Cross out every other 1 starting with the first 1.

If no 0s and 1s remain in $\omega$, accept. Otherwise, reject.

I generally see how this algorithm is efficient. It gets rid of half of all 1s and 0s every iteration. How does it work though? Why must we reject if the total number of 0s and 1s remaining in $\omega$ is odd?

This is a very informal answer (other users will give you a more formal and concise answer :-)

Suppose you have two numbers written in binary notation (the smaller one left-padded with zeros); for example:

14 =  1110
 6 =  0110

A simple algorithm to check if they are equal is comparing the two binary representations bit by bit; this can be done comparing the lower bit and then dividing the number by two (i.e. dropping the lower bit):

111[0] = 011[0]   OK (14 mod 2 = 6 mod 2 )
 11[1] =  01[1]   OK ( 6 mod 2 = 3 mod 2 )
  1[1] =   0[1]   OK ( 3 mod 2 = 1 mod 2 )
   [1] =    [0]   NO => 14 and 6 are different

You can easily notice that the lower bits of two numbers are the same if the numbers are both even or both odd (i.e. if their sum is even).

The algorithm above does exactly the same thing but the numbers are represented in unary:

00000000000000 111111   even 0s, even 1s, sum even OK
-0-0-0-0-0-0-0 -1-1-1   odd 0s, odd 1s, sum even OK
---0---0---0-- ---1--   odd 0s, odd 1s, sum even OK
-------0------ ------   odd 0s, even 1s, sum odd REJECT!


Are there a lambda-mu expression equivalent to the yin yang puzzle? The yin yang puzzle was written in Scheme. Since it uses call/cc, it is not possible to express it in a pure lambda expression, unless we do a CPS transform.

However, given the fact that $\lambda \mu$-calculus have the power to model call/cc, is it possible to write an equivalent $\lambda \mu$-expression? I am still learning $\lambda \mu$-deductions, so this would be a good example to show how the deduction works.

There is no need to model the "display" command in a pure expression. Ideally only showing how the calculus keep looping and evaluates diffident terms again and again.

UPDATE My translation in $\lambda$-expression with CPS:

(λcallcc.callcc (λyin.callcc (λyang.yin yang))(λcc.cc cc)

In CPS, (λcc.cc cc) is what "call with current continuation" means. So the expression takes it as a parameter. This will result in assign the sub-expression starts λyin assign its continuation into parameter yin. And then in the body, the second callcc assigns the yang of sub-expression starts λyang into itself. Finally, apply yin yang.

Note the above translate is not full CPS, only the concept of call/cc has been translated. But it provides the same behavior and it is not hard to do a full CPS translate.

You can get an important hint to solution by thinking how to make the yin-yang puzzle work in a typed language, see this question. OCaml computes the type of yin and yang to be ('a -> 'a) as 'a, which is a recursive type equal to its own function space. Such a type is precisely what it takes to implement the untyped $\lambda$-calculus in a typed language.

What does this have to do with your question? In the untyped $\lambda$-calculus (or typed calculus with general recursive types) we can define $\mu$ and other fixed-point combinators. So, since yin and yang cannot be given types, we must use the untyped $\lambda$-calculus, but then $\mu$ is not needed as a primitive. In fact, the CPS transform of the puzzle will be just pure $\lambda$-calculus.

You can compute the CPS transform in the privacy of your mind. Here is my version, written in Ocaml. To run it, you need to pass -rectypes to Ocaml:

let callcc f k = f k ;;
let yin c = callcc (fun x -> x x) (fun k -> print_char '@'; c k) ;;
let yang c = callcc (fun x -> x x) (fun k -> print_char '*'; c k) ;;
let _  = yin yang (fun x -> x) ;;

Clearly, the let statements are just a convenience. Without them, and with callcc expanded out, we get:

(fun c -> (fun x -> x x) (fun k -> print_char '@'; c k))
(fun c -> (fun x -> x x) (fun k -> print_char '*'; c k))
(fun x -> x)

We could remove the print_char statement and $\eta$-reduce:

Start with:

(fun c -> (fun x -> x x) (fun k -> c k))
(fun c -> (fun x -> x x) (fun k -> c k))
(fun x -> x)

Reduce fun k -> c k to c:

(fun c -> (fun x -> x x) c) (fun c -> (fun x -> x x) c) (fun x -> x)

Reduce fun c -> (fun x -> x x) c to fun x -> x x:

(fun x -> x x) (fun x -> x x) (fun x -> x)

So the essence of the yin-yang puzzle is just self-application of self-application. How appropriate! As a last step, we can put in the print_char statements again, to get a one-liner:

(fun x -> x (fun k -> print_char '@'; x k)) (fun x -> x (fun k -> print_char '*'; x k)) (fun x -> x)


What is the language of Sigma^n? Confused about meanining I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?
Thank you so much!

By definition $\Sigma^n$ is simply $\underbrace{\Sigma\times \Sigma \times \cdots \times\Sigma}_{n \ \text{times}} = \{(\sigma_1, \sigma_2, \ldots, \sigma_n): \forall \ i\in [n], \sigma_i \in \Sigma \}$ which is the set of ordered tuples of length $n$ over $\Sigma$. Usually, when we refer to a tuple $w = (\sigma_1, \sigma_2, \ldots, \sigma_n)$, we omit the commas "," and the parenthesis "(" and ")", so the tuple $w$ is written as $\sigma_1\cdot \sigma_2\cdots \sigma_n$ to which we refer as a word of length $n$ over $\Sigma$. In other words, $\Sigma^n$ is the set of all words of length $n$ over $\Sigma$.
Formally, the map that maps a tuple in $\Sigma^n$ to the word that we get by omitting the commas and the parenthesis from the tuples, is a bijection from $\Sigma^n$ to the words of length $n$ over $\Sigma$.


How does matrix chain multiplication problem has an optimal substructure? We solve Matrix chain multiplication problem considering the optimal solution to subproblems but what I cant get through my mind is how this problem has an optimal substructure?

For eg. consider if these are optimal solutions for matrices A1.A2.A3.A4.A5.An:

  (((((A1.A2)A3)A4)A5)A6)An)  (((((A1.A2)A3)A4)A5)(A6.An))

If any of above is optimal solution then we won't be able to consider any optimal substructre.No?

First of all, it is correct and important to know that optimal solutions need not necessarily be unique!
However, this doesn't mean we cannot have optimal substructure. Recall what optimal substructure means: the structure is such that if we know to make an 'optimal' decision on some 'local' criterion, we can get the actual 'global' optimum by making such decisions repeatedly (usually via divide and rule)

Note that again, the 'optimal' decision need not be unique! So, by making different locally optimal decisions, it is possible to end up with multiple globally optimal results. So, the seeming contradiction of multiple optima and optimal substructure doesn't exist.


Differences between SISD, SIMD and MIMD architecture (Flynn classification) I have a problem with classifying certain CPUs to the proper classes of Flynn's Taxonomy.

1. Zilog Z80

According to this article on Sega Retro, Z80 has limited abilities to be classified as SIMD:

  a limited ability for SIMD (Single Instruction, Multiple Data) with instructions to perform copy, compare, input, and output over contiguous blocks of memory;

For what I understand, Z80 is usually behaving as a SISD but when it comes to performing thing like copying or comparing Z80 is able to process multiple data using a single instruction.

How should we classify Z80 then? Is the ability to become SIMD processor a voice for or against saying that Z80 implements SIMD architecture?

2. Intel i5 (Dual core)

Form what I understand, we classify multicore CPUs as MIMD.

Is it as simple as that?

3. ARM Cortex-A15 (single core)

I'd classify the architecture of this processor as a SIMD model. Wikipedia says that it has superscalar pipeline, but as we know from Why is a superscalar processor SIMD? that multiple pipelines does not imply MIMD model.

Are "modern" single cores usually implementing SIMD model or not?

Michael J. Flynn is one of the all-time great computer architects.  He was the design manager of the IBM 360/91, and made numerous foundational contributions in the areas of pipelining, and in computer arithmetic.

But the Flynn Taxonomy has not stood the test of time, and is no longer useful.

The SI/MI part of the taxonomy is easy to differentiate on the surface: how many hardware instruction pointers (sometimes called program counters) does the machine have?  If there is one hardware instruction pointer the machine is "SI" (either SISD or SIMD).  If there is more than one hardware instruction pointer the machine is "MI" (either MISD or MIMD).

If you go a bit deeper, it becomes less clear though.  Does a vector machine with one instruction pointer but vector predicate registers count as SI or MI?  Why is a machine with only one fetch unit that can quickly (just a few cycles) switch back and forth between two different instruction pointers MI, but a machine with only one fetch unit that can context switch once ever few-hundred or thousand cycles considered SI?  Is a machine with two hardware instruction pointers, but that only context switches at long-latency cache misses SI or MI?

The SD vs. MD distinction is just a complete mess.  When Flynn made up the classification I believe he was referring to whether the machine had instructions that could operate on multiple independent pieces of data or not.  That does not mean that the operations happen simultaneously.  It could mean that the machine has instructions that operate on vectors of numbers, one at a time (or maybe pipelined), like the CDC STAR-100. The vector instructions in the CDC STAR-100 were pretty complex, giving two vectors start addresses to load, a start address for storing the result vector back to memory, and an arithmetic operation.  The vector lengths were controllable on the CDC STAR-100.  The CDC STAR-100 designers could have leveraged the implicit independence of the operations in the vector instructions to make some of those operations happen truly simultaneously, but they did not.

It may be more appropriate to talk about whether certain instructions in an instruction set architecture are "SIMD" or not.  The ARM NEON instructions are SIMD instructions, but most of the other ARM instructions are not SIMD.

I don't know whether the Z-80's copy instruction was SIMD or not.  I guess I'd call it SIMD because I can't think of any reason not to call it SIMD.


Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer Well in many texts and places I have seen a called statement, which claims it self to the famous "Church Turing Thesis".
I have seen many texts say that based on Church-Turing Thesis :

"Anything that can be done by a digital computer can also be done by Turing Machine".

Peter Linz text roughly says that the thesis is :

"any computation that can be done by "mechanical" means can also be done by TM".

Linz even adds that mechanical term is not well defined. So TM can serve as a definition for mechanical machine.
A look in the Wikipedia says:

It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.

The Wikipedia indeed defines or considers Turing Machine to be that "mechanical" standard.
Googling about mechanical computation, results in the picture of a device something like this:
 Mechanical Computer
Even Ullman text has a proof of equivalence of TM and modern computer using the simulation of instruction set... But there the authors make a twist by saying they assume their digital computer says "yes" or "no" for input given.
Sipser says:

The definition came in the 1936 papers of Alonzo Church and Alan Turing. Church used a notational system called the λ-calculus to define algorithms. Turing did it with his “machines.” These two definitions were shown to be equivalent. This connection between the informal notion of algorithm and the precise definition has come to be called the Church–Turing thesis.

Most of the problems that can be solved by a TM in fact can be solved by applying the algorithm mechanically by an actual human using pen and paper. Like given a graph, one can trace out the TSP tour using pen and paper by drawing it and marking out the path. Or given two integers one can find the sum using pen and paper.
So in that case are our modern computers more powerful than a TM ? What is this mechanical model?
Using modern digital computers we can play Super Mario. Though Mario is after all a program and runs on the processor. The graphics rendering algorithms are algorithms after all. And some texts says that the notion of algorithm comes from the concept of Turing Machine. But a TM cannot possibly produce audio/video.
Then why some people believe that TM is equivalent to modern digital computers ? Or could we somehow use a multi dimensional TM and use each cell as a pixel to produce a picture.... I doubt?

I have seen the question here but it does not answer my query.

Modern computers are not more powerful than a TM.
The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world.  For instance, it would include mechnical devices, electronic devices, a human following a procedure "mechnically", and so on.
Wikipedia does not define "can be calculated by an effective method" as "can be calculated by a TM".  It doesn't define "mechnical" as can be calculated by a TM.  Rather, it says that the Church-Turing hypothesis asserts that any computation that can be carried out mechnically, can be carried out by a TM.  That's not a definition of what it means to carry out a computation mechnically -- that's a consequence of the Church-Turing hypothesis.
I think you are getting confused about the difference between a definition of computation, vs what the Church-Turing thesis claims/asserts/conjectures to be true about computation. The Church-Turing thesis is not intended as a definition of computation; it's intended as a statement/claim/assertion about computation.  The Church-Turing hypothesis doesn't provide a formal definition of "effective computation" or "mechnical means"; it leaves that up to the intuition.


First-order mutual-recursive functions Turing-complete or incomplete? Assume we have a C-like programming language with no pointer/heap semantics (i.e. there is no concept of memory; everything is on the stack). The only datatype supported is Integer, but suppose the Integer is infinitely large (i.e. without 32-bit, 64-bit, or any size limit).
Is it true that this language is Turing-incomplete, but becomes complete if we add pointer/heap semantics (i.e. access to RAM-like memory)?

Roughly speaking, as a heuristic, if your language includes primitives of unbounded size as well as standard control structures (e.g., loops and conditional statements), the language is likely to be Turing complete.  (Credits: I'm just expanding on Dmitry's observation.)  I'll show a few examples below.
If your language doesn't have loops, you can simulate them with recursion.
Linked lists
If your language includes linked lists, it will be Turing-complete.
In particular, you can encode a Turing machine with two linked lists.  You split the tape into two pieces, the part to the left of the head and the part to the right of the head.  Let $L$ be a linked list of the symbols on the tape to the left of the head, and $R$ the symbols to the right.  The linked list should start with the symbols closest to the head and go outward.
Now you can simulate each of the individual operations of the Turing machine using a few lines in your programming language.  For instance, shifting the tape head to the right can be done by popping an item $x$ from the front of $L$, then pushing $x$ onto the front of $R$.  The finite-state control works on finite data and so can be expressed as a finite number of simple operations.  Now put an infinite loop around this, with each iteration of the loop simulating one step of the Turing machine, and you have built an interpreter for a Turing machine in your language.
Bigints
If your language includes bigints (i.e., integers that can be of unbounded size) and basic operations on them (e.g., add, multiply, compare, divide), then it will be Turing-complete.
In particular, you can simulate linked lists of items over a fixed alphabet using bigints.  Suppose you want to encode a linked list of bits.  Then you can encode this as a bigint by treating the sequence of bits in the linked list as the binary representation of an integer (the least significant bit is the first bit in the linked list, and so on).  Basic operations on the linked list can then be translated into operations on the integer.  For instance, popping a bit from the head of a linked list can be expressed as $b := L \bmod 2, L := (L-b)/2$; pushing a bit can be expressed as $L := 2L+b$; and so on.  More generally, if you have a linked list where each item is in the range $\{0,1,\dots,k-1\}$ (e.g., a tape alphabet of size $k$), then this can be viewed as an integer in base $k$.  There are some details -- for finite lists, you probably want to have one reserved symbol to indicate the end of the list -- but they don't change the general picture.
Now you can use this to simulate linked lists, and then use the construction above to simulate a Turing machine.


If a connected graph has a bridge then it has a cut vertex Is it true that if a connected graph has a bridge then it has a cut vertex?

In my point of view, I don't think it is true to consider that a graph having a cut edge will definitely have cut vertex.

Consider a graph with a single edge $uv$; if we remove this edge, the graph will get disconnected but if we remove $u$, the graph will be connected as a graph with the single vertex is still consider connected.

An edge $e=uv$ is a bridge in $G$ if there is no path between $u$ and $v$ in $G-e$.

In general, $u$ and $v$ are cut vertices, but there are some special cases you must treat with care.

(1) If $G \simeq K_2$, then depending on the definition of connectivity, the $G-u \simeq K_1$ might and might not be considered connected*.

(2) There is another case in which you would not consider $u$ to be a cut vertex; An edge  $uv$ is called a pendant edge if $\deg(u) = 1$.  In this case, if $uv$ is a pendant edge and $\deg(v)>1$, you would not typically call $u$ a cut vertex.

Postlude

All that being said, definitions in graphs are hard (case in point: Diestel).  When we try to make definitions very general, special cases sometimes become absurd.

Note

1

* To address David Richerby's objection, $K_1$ is considered disconnected when deriving connectivity from k-connectivity, in which you require the graph to have more than $k$ vertices. By that definition ("a 1-connected graph is called connected"), $K_1$ is disconnected by having too few vertices.

2

To answer Thinker's follow-up question; since you wanted to know what to answer to a hypothetical exam question, I would do it this way:

Let $e = uv$ be a bridge.  We have three cases:

$\deg(u), \deg(v) > 1$.  The statement is true.
$\deg(u) = 1, \deg(v) > 1$.  The statement is true, $e$ is a pendant.
$\deg(u) = \deg(v) = 1$.  The statement is true if and only if $K_1$ is considered connected.


Execution time of an uneven pipeline I was trying to solve a question dealing with n instructions in an uneven pipeline with k stages. I came across a generic formula for even pipelines i.e. (k + n - 1) * clock cycle. But I feel this should not work for uneven pipelines as the above formula is based on fact that the 1st instruction takes time = sum(time of k stages) and the 2nd instruction onwards takes time = maximum of stage delays.

A example: A pipeline is designed with 5 stages having execution times respectively as 3ns, 4ns, 2ns and 4ns. How much time will it take to execute 1000 instructions?

The first instruction (I1) will pass through all the stages one by one without any stall and will take $3+4+2+4=13$ cycles.

The second instruction (I2) goes next and it begins at the end of cycle 3. As soon as it finishes the execution of S1, it is ready to go to next stage. But it is occupied by the previous instruction. Hence, I2 needs to stall for 1 cycle (as in yellow). After this stall, it need not to pause for any cycle and finishes at cycle 17.

The same pattern is followed by the coming instructions.

So, the first instruction finishes in 13 cycles.
Each of the remaining $n-1$ instructions finishes after 4 cycles taking $(n-1)*4$ cycles.

You put $n=1000$ and the total number of cycles comes to be $13+999*4 =4009.$

Hope it helps.


Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages I'm trying to create a formal algorithm in order to determine whether
  two given regular expressions $a$, $a'$ define identical/equal or
  unequal languages and if those languages are subsets of each other?

(I'm not sure if following thoughts are correct and formal enough and I'm glad if you spot mistakes and improve my algorithm.)

Let $a$,$a'$ be regular expressions. Now, we want to determine: $$\bigg(L(a)=L(a') \text{ or } L(a)\neq L(a') \text{ and } \Big((L(a)\subset L(a') \text{ or } (L(a')\subset L(a)\Big)\bigg)$$

In order to do that, we will "convert" the regular expressions $a$ and $a'$ into DFA's $M$ and $M'$. Those automatons have minimal and non-redundant states $K=\{q_1, \cdots ,q_n\}$ and $K'=\{q_1, \cdots ,q_m\}$ with $n,m \in \mathbb{N}$.

Now, we can simply determine, whether $K=K'$ with showing $K\subseteq K'$ and $K' \subseteq K \implies K=K' \implies L(a) = L(a')$.
If the above equation is not true, then we can imply that $K\neq K' \implies L(a) \neq L(a')$.  Furthermore, with $K\neq K'$ and $K \nsubseteq K'$ and $K'\subseteq K \implies K' \subset K \implies L(a')\subset L(a)$.
Analogue: $K\neq K'$ and $K' \nsubseteq K$ and $K\subseteq K' \implies K \subset K' \implies L(a) \subset L(a')$ .

Is this enough or do I need to compare final states, transfer function and the alphabet in order to be sure $L(a)=L(a')$ etc.?

If behaviour of the automaton didn't depend on the final states, transition function and alphabet, why would we define automata to have those useless things?


Big Theta Proof on polynomial function This is not homework. I have the solution but it's not what I'm getting. I know there are multiple solutions to the problem but I want to make sure that I'm not missing anything.

The question is as follows:

  Prove that 2$n^2$
   - 4n + 7 = Θ ($n^2$). give the values of the constants and show your work.

Here is how I approached the problem:

From the definition of Θ(g(n)):

0 ≤ C1$n^2$ ≤ 2$n^2$ - 4n + 7 ≤ C2$n^2$

Divide the inequality by the largest order n-term. (This is the only way I know how to solve these equations.)

  0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

Split the problem into two parts: LHS and RHS.

We start with the RHS:

Find constant C2 that will satisfy

  0 ≤ 2 - (4/n - 7/$n^2$) ≤ C2

n=1, (2 - (4/1 - 7/$1^2$)) = 5

n=2, (2 - (4/2 - 7/$2^2$)) = 7/4

n=3, (2 - (4/3 - 7/9)) =  13/9

We choose C2 to be 2, n≥2 to satisfy the RHS.

LHS: we try to find a constant that will satisfy

  0 ≤ C1 ≤ 2 - (4/n - 7/$n^2$)

From above, we know that after n=2, the equation approaches 2 as n grows larger, so if we pick a constant that is less than 2 then it should satisfy the LHS.

We choose C1 to be 1.
For n, choosing 1 would satisfy the left hand side, but since the RHS needs n≥2, we stick with it.

So the constants that prove 2$n^2$ - 4n + 7 = Θ ($n^2$) are

  C1 = 1 , C2 = 2 , n≥2

The given solution to this problem chooses n≥4, but I'm not sure why. It seems that n≥2 would work fine. Am I wrong somewhere?

If I'm not wrong, if I would have picked C1 to also be 2, wouldn't that also satisfy the left hand side since the inequality allows it to be ≤?

Your solution is fine.  There are multiple ways to prove this fact, all of them valid/correct.  So your approach is valid, and it's possible that the solution from your class is also valid: that's not a contradiction.

Let me give you one piece of advice for structuring your proof in the future, though.  In the argument you sketched in the question, you are "working backwards": you start from the statement you wish were true (that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$), and then you try to derive what needs to be true about $c_1,c_2$ for your wish to hold true.  Experience has proven that that kind of reasoning is error-prone, though: it's easy for you to make a mistake along the way.  It is also hard for others to check.

When you write up your proof, I suggest you do the reasoning in the opposite direction.  Start from what you know is true, and then derive the implications of that, ending with the conclusion that $c_1 n^2 \le 2 n^2 -4n + 7 \le c_2 n^2$.  This better matches how people think and makes it easier for the reader to understand what's going on.  And the purpose of a proof is to communicate an idea to the reader, so the proof should be structured to make the reader's life easier: to make it as easy as possible for the reader to verify that the proof's reasoning is correct and valid.  It's just like a good book; good writing is chosen to make life good for the reader.  Proofs are the same way.  And, ultimately, this will benefit you too: in my experience, if you follow this approach, then you're less likely to make a subtle mistake in your proof.

So, a better proof outline would be to show that $n^2 \le 2n^2 - 4n + 7$ holds for all $n\ge 2$ (because such-and-such), and show that $2n^2 - 4n + 7 \le 2n^2$ holds for all $n\ge 2$ (because blah-de-blah), and then conclude that $2n^2 - 4n + 7 \in \Theta(n^2)$.  I realize this kind of proof is harder to write, because you need to know the value of $c_1,c_2$ to use before you can start writing down this style of proof.  But you know what?  That's OK.  You can do a side calculation, on scratch paper, to figure out what value of $c_1,c_2$ to use.  Don't show us that side calculation; just figure out what value of $c_1,c_2$ would be good ones to do, and then start the proof with you pulling $c_1=1,c_2=2$ magically out of thin air, and demonstrate that your choice is valid.  This style of proof will be better for you, and better for the reader.


Are there any LTL to _non_ deterministic Rabin automaton translators? I know of two translators LTL -> deterministic Rabin automaton:

Rabinizer3
ltl2dstar

They produce deterministic automata, which can be much larger than their possible non-deterministic variants. Is there a translator LTL -> non deterministic Rabin?

(my synthesis tool could handle small non-det Rabin automata but not large though det ones)

You can easily translate LTL to non-deterministic Buchi automata, which can be thought of as a simple fragment of Rabin automata (although they are equally expressive).
I don't think any tool would actually output the acceptance condition described as a Rabin condition, but this is very easy to deduce from the Buchi states.

An example of an online tool to do this conversion is:
http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/

But I'm sure there are many others, as the construction is relatively simple.