Research regarding algorithm generation/discovery/heuristics

The phrase to look for is "program synthesis".  There's lots of literature in the programming literature on this topic; I suggest using Google Scholar to search through the literature and find relevant publications.

These days one hot approach is using "program sketching".  In program sketching, the programmer specifies a template for the code: partial code, with some holes left blank.  The tool then automatically tries to fill in those holes in a way that is consistent with the preconditions/postconditions, or is consistent with some provided test cases.  There's lot of literature on this topic.  For an introduction to this line of work, I'll suggest the following tutorial:

The Sketching Approach to Program Synthesis.  Armando Solar-Lezama.  Tutorial at PLDI 2012.


How should I design a hash table where all the keys are permutations?

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of

Once you have that index, you can make a table with exactly 9! slots - you have a perfect hash over your input domain.

For example, for n=3, the hash function produces

123 -> 0
132 -> 1
213 -> 2
231 -> 3
312 -> 4
321 -> 5


What is the relationship between minimum vertex cover and minimum clique cover

The minimum clique cover of the conflict graph is at most the minimum vertex cover of the original graph. In other words, if the original graph has a vertex cover of size $k$, then the conflict graph has a clique cover of size $k$. This is essentially because all edges adjacent to a vertex in the original graph constitute a clique in the conflict graph (though as the example of the triangle shows, there are also other cliques in the conflict graph). Details left to you.


When is the big-O relation preserved under exponentiation?

It is at least sufficient to have $\log f(n) \in o(\log g(n))$. This gives us that for sufficiently large $N$, we have $\log f(n) \leq \log g(n)$ for all $n > N$.

Hence immediately we have that for $c=1, n > N$, $f(n) \leq c\cdot g(n)$ and ergo $f(n) \in O(g(n))$.

This also suggests the condition that if we have that $\log f(n) \leq c\cdot \log (g(n))$ where $c \leq 1$ for sufficiently large $n$, then we also get $f(n) \in O(g(n))$.


Positioning items to maximize separation

Given a specific item $s$, how do I compute the maximum gap possible to the right of $s$? By maximum gap to the right of $s$ I mean the distance between $s$ and the next item to its right.

This is much more useful than the mathematical description.

First note that items that are to the left of $s$ don't hurt us in any way, so if it is possible to put an item to the left of $s$, do so. Then we note that if an item can't go to the left of $s$ we want it as far to the right as possible.

The conclusion? Each item is always at either its left or right boundary, with the exception of $s$. And once you know the position of $s$ you'll also know all the other positions.

So just loop over each interesting position of $s$, discard all items that can go on the left, and then choose the closest item on the right. Out of these closest items, which ever is the furthest is your answer (or well, it's associated position of $s$).

Now what are the interesting positions of $s$? Well it's each time you can put another item to the left of $s$. So it's all the left boundaries (plus one epsilon) of items that fall within $[l_s, r_s]$, and $l_s$ itself.


Sequence of total languages whose limit is turing complete

I'm not sure I full get your encoding and based on the comments there seem to be some problems with it, but I'll nevertheless provide my answer (or "answer", if you prefer).

A sequence of languages (your terminology) that satisfies your constraints is a sequence where the $i$th element in the sequence runs the Universal Turing machine for $i$ steps or until the machine halts, whichever comes first.

Clearly, each element in this sequence is total, but the limit is a Universal Turing Machine.


AVL trees should be binary search trees. In the example you gave, 2 is the right child of 3. That isn't right since 2 < 3. Assume the 2 and 3 are switched, which results in a correct binary tree.

Remember the rule for AVL trees: for any node, the height difference between the left child and right child is at most 1. Following the tree down, the 10 is inserted as the right child of 9. This breaks the rule. Look at the subtree rooted at 6. The height of the left child is 0 while the height of the right child is 2. The tree must be rotated, which is the tricky part. 8 becomes the right child of 4. 6 becomes the left child of 8. 7 becomes the right child of 6. After all of that, the final AVL tree would look like this:

(courtesy of Uottawa).
I always visualized rotations like this:

With your left hand, "hold" the 6 and "detach" it from the 4.
With your right hand, "hold" the 8.
"Drop" the 6 so that it swings counterclockwise, due to gravity of course. (6 is now the left child of 8)
The 6 "hits" the 7. (7 is now the right child of 6)
"Attach" this whole subtree (now rooted at 8, since the 6 "fell")
back onto the 4.


If all frames are naturally broadcast in a LAN, what is the need for a broadcast address?

So that receiving devices can blindly throw away packets that aren't addressed to them or the broadcast address. Doing this test is much simpler than having to verify the CRC and tossing it up to the next layer that may toss it out itself.

A switch will also make use of the target address to only propagate packets to where it knows the destination address resides, reducing congestion.

The broadcast destination is used for stuff like DCHP where the sender doesn't know the target's MAC but still needs to send out the message.


Find four sets where each element from those four appears in at least two of those four sets

Assume set A has an element x. Then you need to add another set B which also has the same element x. Then if there is an item y element of A or B but not both, you need to add a set C contains y. And finally add a set D containing all elements that are elements of exactly one of A, B or C, plus possibly elements common to two of them.

I’d first count for each of the elements how many sets contain it; if x is contained only by one set A, then remove A from the problem. Sort the elements of each set by how many sets contain them. Sort the sets in lexicographic order according to the number of sets containing each element, except sets with fewer elements come later. (So if A contains x and y, both elements of two sets only, and B contains u and v both elements of two sets, and w element of 200 sets, then B comes before A, and both close to the start of the list).

You said that your sets tend to have 10 to 15 elements, then each element will tend to belong to not more than 10 or 15 sets. If you have much more than n different items in total, that number is actually smaller.

Now take the first set A in the list. Take its element x belonging to the smallest number of different sets, and pick each of these sets as the second set B in turn. Take the element y belonging to exactly one of A and B belonging to the smallest number of sets, and pick each of those sets as the third set C. Take the element z belonging  to exactly one of A, B and C belonging to the smallest number of sets, and check all those sets in turn.

In cases where no element is required to be added (all elements belong to two of A, B and C for example), try all possible sets as the next set.

When all possibilities for B, C and D have been examined, remove A, adjusting all the counts. Assuming items don’t belong to more than k sets on average, this should take no more than n k^3 steps.

PS I assumed the number of different items is about the same as n. As long as the number of different items is at least n^(2/3) this will run in O(n^2). Well, roughly.


Reading / writing from disk.

Reading / waiting for keyboard / mouse input.

Reading / waiting for network data.

Printing a page.

Basically, as the text says, an I/O task is anything which the CPU can't perform on its own, and has to rely on other components. Usually this involves waiting a long time, compared to the CPU speed, so it's better to switch to another task while waiting.

In this way, even if the browser is waiting for the server to respond, the other running tasks can move on (unless they also need to wait for I/O, of course).


Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

You can establish a reduction $\overline{H}\le_M T$ by mapping $\langle M\rangle\rightarrow \langle N\rangle$ where

N(x) =
   if x = 0, accept
   if M halts on the empty string
      if x = 1, accept

Now

If $\langle M \rangle\in H$ then $L(N) = \{0, 1\}$ which implies $\langle N\rangle\notin T$
If $\langle M \rangle\notin H$ then $L(N) = \{0\}$ which implies $\langle N\rangle\in T$

and since you already know $\overline{H}$ is not recognizable, $T$ must not be recognizable.


What is considered arithmetic when dealing with bits?

A program that uses only bitwise operations is just that – a program which only uses bitwise operations. Bitwise operations are universal, that is, you can define any function using them. What makes things interesting is that we care about the complexity of implementing a given function using only bitwise operations.

In particular, suppose that we only care about the complexity up to multiplicative constants (i.e. we only care about the big O). Any operation which can be implemented using a constant number of bitwise operations is admissible – the resulting notion of complexity is the same (up to multiplicative constants). So if you can implement addition using a constant-size formula, then you are welcome to use addition.

The constraint doesn't mean that at no point of your program are you allowed to compute by chance some arithmetic function – it just means that the basic operations you are allowed are only the bitwise ones.


Count elements of a sorted matrix that fall into a given interval

First, notice that you only need to know how to count the number of elements bigger than $k_{min}$, because then, by a very simple transformation, you can count the number of element smaller than $k_{max}$, and compute the desired result : since the set $A$ of element bigger than $k_{min}$ is of the form $[a;max]$, and the set $B$ of element smaller than $k_{max}$ is $[min;b]$, you have $|A \cap B| = |A| + |B| - n^2$

Now, find the last element smaller than $k_{min}$ on the last row, at column $c_0$.
On this last row, exactly $n - c_0$ elements are bigger than $k_{min}$.
On the row above, the last element smaller than $k_{min}$ has to be right to $c_0$, because otherwise, since $M$ is sorted on row and column, you would have a contradiction. Hence, in order to find the last element smaller than $k_{min}$ on this row, you can start at column $c_0$ and go right to find $c_1$.
Then again, the number of elements bigger than $k_{min}$ on this row is $n - c_1$.

Repeating this process, you then sum the number of elements on each row to compute the result, and you'll scan only at most $2n$ elements since the path followed by the algorithm is a path from the point $(0,n-1)$ to the point $(n-1,0)$, going only up and left, and these kind of path have length $2n$.
This is hence indeed an $\mathcal{O}(n)$ algorithm.

EDIT: details added


Someone who owns (an abstract of) the book might be able to give you a better contextualized answer, but in general models and simulations are subject to certain 'laws' that the systems they represent usually are not. In the case of multi-agent systems, one of these is the fact that some agent gets to act first on a given time step, even though the designer often assumes and intends for them to act in parallel (this is the result of computers being incapable of truly parallel computation). If the same agent were to consistently act first, that could introduce significant bias into the system. This is probably what the author means with the pitfall of predictability and why randomization is important; so that we can prevent (to some extent) these sorts of issues.


Is there an NP-hard problem for which no Fixed-Parameter Tractable algorithm exists?

You have to be a bit careful with your question here. Note that an NP-hard problem is a decision problem, while FPT algorithms solve parametrized decision or search problems. So the question is a bit poorly formed. However, I think the question you probably intended to ask is:

Is there an NP-hard problem for which we can add a parameter1 to create a "natural"2 parametrised problem for which no FPT algorithm exists?

To which the answer is (unconditionally!) yes.
First of all, note that FPT, the class of problems that are solvable via a fixed parameter tractable algorithm, is a proper subset of XP, the class of "slice-wise polynomial" parameterized problems that can be solved by a polynomial-time algorithm if the parameter is fixed. In other words: $\mathrm{FPT} \subsetneq \mathrm{XP}$. (I must confess I'm not able to provide the proof by "standard diagonalization" which my source offers as the only justification. Perhaps a complexity theorist can help me out here)
Next, note that since at least one problem in XP cannot be solved by an FPT-algorithm, any XP-hard (in the sense of FPT-reductions) problem cannot be solved by an FPT-algorithm.
In the chapter "Provable Intractability: The Class XP" in Downey and Fellows' Fundamentals of Parameterized Complexity, they complete the argument by showing that what they call the PEBBLE GAME PROBLEM is XP-hard by "reinterpreting" a problem that is known to be at least PSPACE-hard (after "removing the parameter"), so certainly NP-hard. See there book chapter for more details.

Let me add that this result was very surprising to me as well, because for most practical problems, we require al sorts of conjectures ($P\neq NP$, ETH, SETH, 3-SUM, etc.), but this result is an actual fact that is independent of any conjecture.

1: To clarify, by "adding a parameter", I mean given an NP-hard problem $L\subseteq \Sigma^*$, define a parametrized problem $L'\subseteq \Sigma^* \times \mathbb{N}$ as $L':= \{\langle x, k\rangle \mid f(x)=k\}$ for some function $f : \Sigma^* \rightarrow \mathbb{N}$. This captures the intuitive idea that the additional parameter measures a property of the input.
2: The definition in 1 still allows all sorts of strange parameterizations with functions such as $f(x)\equiv 1$. Ideally, we'd require $f$ to measure something meaningful about the instance, but that seems hard to formalize. I couldn't think of any other formalisation that removes all "unnatural" parameterizations, either. So, I will instead copy the informal notion of "natural parameterized problems" from Downey and Fellows' book.


b. is completely trivial - just set each variable to FALSE.

d. trivially reduces to c.    c. reduces to d. as follows:

For each double-negative clause, remove the negatives.  Replace each

single-negative clause with 2 clauses, each of which has one of the original clause's variables

and a new variable that's shared with the other of the 2 new clauses but otherwise unused.

That works because:

for 2-variable clauses, NAE is just ≠

for boolean variables,    x  NAE  not y    simplifies to  x = y

for boolean variables, [there exists a y such that    x ≠ y  and  y ≠ z ]  if and only if  x = z

By    variables <-> vertices  and  clauses <-> edges  ,    c. is equivalent to bipartiteness.

Bipartiteness is logspace-complete.  (Thus, c. and d. are logspace-complete.)

By throwing in k extra variables to handle "at most" vs. "exactly", a. is in W[P].

By    vertices -> variables  and  edges -> clauses  ,    vertex cover reduces to  a. .

(Thus, for unrestricted k, a. is NP-complete.)  However, a. is fixed-parameter tractable.

Proof:
By replacing each clause with k+1 copies of itself and then [for each variable, putting in a

clause whose literals are both the negation of that variable], a. reduces to Almost 2-SAT.

By part 2.1 of that paper, that paper handles the case of clauses whose 2 literals are the same.

Theorem 7 of that paper explicitly covers "possible repeated occurrences of clauses".

I have no clue regarding possible kernalizability of a. or

$\big[$the space requirements of algorithms for a. whose runtimes aren't  max$\hspace{-0.03 in}\big(\hspace{-0.04 in}$nΩ(k),$\hspace{.02 in}$2Ω(n)$\hspace{-0.03 in}\big)\big]$.


Counter example to graph coloring heuristic using BFS

Here's one:

The labels indicate the intend BFS ordering (alphabetical). A different ordering can produce a different result, so more work would have to be done to get a graph where your BFS approach fails for every starting point (it would probably be very messy too).

Assuming we follow this ordering however, we get the following colouring:

The key being that $e$ and $f$ get coloured last, so $c$ removes blue from the possibilities, and $d$ removes red, so $e$ and $f$ must have two new colours.

However this graph is 3-colourable:

By choosing to use more colours earlier, it relaxes the constraints later.

I'll also throw in a conjecture that this is smallest counterexample, for no other reason than to challenge others to find smaller ones ;).


Longest subsequence such that A[i].x < A[i+1].y

It's easier to change notation.  Suppose the array is $A$, with the $i$-th element denoted $A[i]$ for $i=1,2,\dots,n$, and that element $i$ has attributes $A[i].x$ and $A[i].y$.  Associate a directed graph $G$ with the array as follows.  The vertices of $G$ are the indices $1\dots n$ of the array.  Vertex $i$ is connected to vertex $j\ $ if both conditions $i<j$ and $A[i].x < A[j].y\ $ hold.

You are then asking for a longest directed path in $G$.

Note that $G$ is actually acyclic, since the arcs form a subset of the usual order on the set $\{1,\dots,n\}$.
Any standard linear algorithm can then be used to compute the longest path, such as a topological sort.


Since you asked specifically about cubic, consider $f(x)=x+x^3$.
The Newton iteration would be $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n+x_n^3}{1+3x_n^2}=\frac{2x_n^3}{1+3x_n^2}$$
It converges to the root $x=0$. So, for $1-3|x_n|^2>1/2$,
$$\epsilon_{n+1}=|x_{n+1}-0|=\frac{2|x_n|^3}{|1+3x_n^2|}\leq \frac{2|x_n|^3}{1-3|x_n|^2}\leq 4|x_n-0|^3=4\epsilon_n^3$$


Context-free grammars cannot express the rules of INDENT/DEDENT and so Python (which we use today in practice with INDENTs/DEDENTs)is not pure CF. Parsers (or lexical analyzers or lexers) for these languages use additional techniques to handle those structures. For example keep track of indentation levels, or tokenizer (scanners) may count number whitespaces and store that info in a table for later use. This is similar to something like trying to write a parser for the language $a^nb^{2n}c^n$, where you must keep track of value of $n$.

A simple example of adding additional power to a lexer is removing redundant whitespace symbols (space/tabs/newlines) or removing comments which has no meaning for the parser (parsing a CFL).

As another example, roughly it can be described as following. Assume a grammar $a^nb^mc^k$ which is clearly CFG.  You use BISON/YACC like tools to generate a parser for this grammar. Then you can introduce an additional rule like number of $a$s must be equal to the number of $c$ which makes the language non CF. So you just add extra logic (manually coding) to your parser to handle that rule by means of, say, annotated trees. Your original language is still context free but extra piece of code you added manually allows it to accept non CF subset of the original language.

I don't think that such parsers are generated automatically by compiler tools (at least I don't know) and so that ("non context free") part must be coded manually.


Hint:

 Consider the special case where $y=0$.


Push relabel algorithms in flow networks

You just have to reorder the elements of $U\times U$, because the double sum contains each edge $(u,v) \in U\times U$ exactly once:

$$\sum_{u \in U}\sum\limits_{v \in U}f(v, u) =
\sum_{(u,v) \in U\times U}f(v, u) =
\sum_{(u,v) \in U\times U}f(u, v) =
\sum_{u \in U}\sum\limits_{v \in U}f(u, v)$$

The fist sum sorts the edges by their first vertex, the third sum (of the question's equation) sorts the edges by their second vertex. This is the simplest imaginable form of a double counting argument.


Find the sum of the first K subsets of integer array

Say the multiset is $S=M\cup P$ where $M$ is the set of negative numbers and $P$ is the set of non-negative numbers. Define $S^+=(-M)\cup P$ where $-M$ means the set of opposite numbers of elements of $M$. For a subset $T=(-M_T)\cup P_T$ of $S^+$ where $M_T\subseteq M$ and $P_T\subseteq P$, define $f(T)=(M\backslash M_T)\cup P_T$, which is a subset of $S$. Now easy to see $f$ is a bijection, and the sum of $f(T)$ is the sum of $T$ plus a constant (the sum of $M$). So we only need solve the problem on $S^+$, and transform the result, say $T_1,T_2,\ldots, T_K$ to $f(T_1),f(T_2),\ldots, f(T_K)$. That is to say, we only need to solve the problem where all elements are non-negative.

This is solved in this post. For completeness of this answer, I quote it here.

  (Going to assume nonempty subsets for simplicity. Handling the empty subset is a line or two.)

  Given a nonempty subset of indices S, define the children of S to be S \ {max(S)} U {max(S) + 1} and S U {max(S) + 1}. Starting with {1}, the child relation forms a tree that includes every nonempty subset of positive integers.

{1}
|  \
{2} {1,2}______
|  \     \     \
{3} {2,3} {1,3} {1,2,3}

  Keyed by the sum of corresponding array elements, this tree is a min-heap. If you compute the keys carefully (by adding and subtracting rather than summing from scratch) and implement the min-heap deletion lazily, then you get an O(k log k)-time algorithm.


Proving Regularity of Languages that are 1/k of an already known regular language

Let $L$ be a regular language and let $(p, q) \in \mathbb{N}^2$. Then the following language is regular:
$$
  L_{p,q} = \{ u \in A^* \mid  \text{there exist $x$ and $y$ in $A^*$ such that $|x| = p|u|$, $|y| = q|u|$ and $xuy \in L$} \}
$$
Furthermore, for any subset $S$ of $\mathbb{N}^2$, the language
$$
  L_S = \bigcup_{(p,q,r) \in S} L_{p,q}
$$
is also regular. I would like to insist that it works for any any subset $S$, including non recursively enumerable subsets of $\mathbb{N}^2$, which might look a little bit suspicious at first glance...

You can try to prove these results by using automata, but it is much easier to use the fact that a language is regular iff it is recognized by a finite monoid.

Let $L$ be a regular language of $A^*$. It is recognized by a finite monoid $M$, that is, there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Now $\mathcal{P}(M)$, the powerset of $M$, is also a finite monoid under the multiplication defined, for $X, Y \in \mathcal{P}(M)$, by $XY = \{ xy \mid x \in X, y \in Y\}$.

Let now $h: A^* \to \mathcal{P}(M) \times M$ be the monoid morphism defined, for each letter $a \in A$, by $h(a) = (f(A), f(a))$. Then for each word $u$, $h(u) = (f(A^{|u|}), f(u))$. I claim that $L_{p,q} = h^{-1}(Q)$ where
$$
   Q = \bigl\{(R,m) \in \mathcal{P}(M) \times M \mid R^pmR^q \cap P \not= \emptyset \bigr\}.
$$
and similarly $L_S = h^{-1}(T)$ where
$$
   T = \Bigl\{(R,m) \in \mathcal{P}(M) \times M \mid \Bigl(\bigcup_{(p,q) \in S}R^pmR^q\Bigr) \cap P \not= \emptyset \Bigr\}.
$$
Thus $L_{p,q}$ and $L_S$ are recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence are regular.

Proof of the claim.
\begin{align*}
  h^{-1}(Q) &= \{u \in A^* \mid (f(A^{|u|}), f(u)) \in Q \} \\
  &= \{u \in A^* \mid f(A^{p|u|}f(u)f(A^{q|u|}) \cap P \not= \emptyset \} \\
  &= \{u \in A^* \mid f(A^{p|u|}uA^{q|u|}) \cap P \not= \emptyset \} \\
  &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap f^{-1}(P) \not= \emptyset \} \\
  &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap L \not= \emptyset \} \\
  &= L_{p,q}
\end{align*}


Encoding set of At-Most-One constraints as a MAX-SAT problem

The standard way to create soft constraints in MaxSAT is to use label variables:

For each $AMO_j$ constraint, create a new variable $l_j$. Then create an unit clause $(\lnot l_j)$ with weight $1$ and add the literal $l_j$ to every clause of the standard $AMO_j$ encoding that contains only hard (infinite weight) clauses.

Now the label variable $l_j$ acts as a switch: setting $l_j = true$ will "turn off" the $AMO_j$ hard constraint, but does not satisfy the unit clause $(\lnot l_j)$.


When you bitwise AND a number in this format with 7F800000 you get:

    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 01111111100000000000000000000000

  = 0EEEEEEEE00000000000000000000000

Everything gets set to 0 except the exponent. Yes, it is necessary for the correct answer to have 8 ones, but it is also necessary that they are in the correct positions. 00007F80 would not be correct because it would result in:

    SEEEEEEEEMMMMMMMMMMMMMMMMMMMMMMM
AND 00000000000000000111111110000000

  = 00000000000000000MMMMMMMM0000000


How to prove a language isn't necessarily regular?

If we take $L = \{a^n \mid n \in \mathbb{N}\}$, then $L' = \{a^{2n} \mid n \in \mathbb{N}\}$, which is a perfectly fine regular language. Or even more trival, we could observe that $\emptyset' = \emptyset$.
As such, it does not hold that $L'$ is never regular for a regular language $L$. This means that answering the question will involve constructing a particular language $L$ for which you can prove that $L'$ is not regular (and such a proof could use the pumping lemma).
As a heuristic for how to attempt this, I would first look at some typical examples of non-regular languages, and try to find a way to express them as $L'$ for some regular language.  If I don't succeed with that, I'd attempt to built $L$ by simultaneously ensuring that $L$ itself is regular, and by running the pumping lemma on $L'$ to prove that it is not.


Suppose that vertices are retrieved in alphabetical order, then we'd have:

Iteration

Before stack is modified
stack: [a], visited: []
After stack is modified
stack: [c, b], visited: [a]

Iteration

Before stack is modified
stack: [c, b], visited: [a]
After stack is modified
stack: [f, a, b], visited: [a, c]

Iteration

Before stack is modified
stack: [f, a, b], visited: [a, c]
After stack is modified
stack: [c, a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [c, a, b], visited: [a, c, f]
After stack is modified
stack: [a, b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [a, b], visited: [a, c, f]
After stack is modified
stack: [b], visited: [a, c, f]

Iteration

Before stack is modified
stack: [b], visited: [a, c, f]
After stack is modified
stack: [d, e], visited: [a, c, f, b]

Iteration

Before stack is modified
stack: [d, e], visited: [a, c, f, b]
After stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]

Iteration

Before stack is modified
stack: [b, e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e, e], visited: [a, c, f, b, d]

Iteration

Before stack is modified
stack: [e, e], visited: [a, c, f, b, d]
After stack is modified
stack: [e], visited: [a, c, f, b, d, e]

Iteration

Before stack is modified
stack: [e], visited: [a, c, f, b, d, e]
After stack is modified
stack: [], visited: [a, c, f, b, d, e]

Iteration

Finished

For me, the culprit was to notice that when the algorithm encounters the first element on stack which was already visited, it will not add more vertices to the stack.  This happens in iterations 4, 5, 8, and 10.


Recursive definition of sum of two numbers in terms of the successor function

Here is a hint:

  a + 3 = succ(succ(succ(a)))

Also, by definition, every natural number is either 0 or the successor of some (smaller) natural number.


Can the W hierarchy by defined by circuits having a satisfying assignment of weight at most k?

No, but something similar holds true.

There is sort of a duality between even and odd levels of the W hierarchy. In particular, maximization problems like p-IndependentSet tend to inhabit the odd levels while minimization problems like p-DominatingSet inhabit the even levels. Asking for something of weight $\leq k$ is a minimization problem.

In terms of p-WSAT, the result you cite extends as follows: For odd levels, antitone levels suffice (antitone means that all atoms are negated). Then, there is a satisfying assignment of weight $k$ iff there is one of weight $\geq k$ (provided there are $\geq k$ variables at all, but if there aren't, the problem can be solved in FPT time by brute force).

And if you choose the wrong monotonicity, you even drop by one level: If $t$ is odd, then p-WSAT for monotone weft $t$, depth $d$ circuits is complete for $W[t-1]$ (respectively is in FPT for $t=1$). If $t$ is even, the same holds for p-WSAT for antitone such circuits. I'll sktech a partial proof.

Let us stick with odd $t$. Using standard normalizations, we can also assume that the circuit is in fact a tree of depth $t+1$ with alternating layers of AND and OR gates, the tree root being an AND gate, and small gates only in the very last layer. As $t$ is odd, the lowest sub-trees all are in $f$-CNF, where the bound $f$ on clause size is the fan-in bound for small gates from the definition of weft.

For some intuition, let us first assume $f=2$. Then, we have monotone 2-CNFs. Consider the graph whose vertices are variables and whose edges are clauses of the 2-CNF at hand. A satisfying assignment of the 2-CNF is a vertex cover of the graph and vice versa. We know how to handle vertex cover in FPT time.

More precisely, using the bounded branching algorithm for p-VertexCover, we can also do the following in FPT time: List all minimal vertex covers of size $\leq k$ of a given graph. With the same technique we can also solve the respective problem for arbitrary $f$: Given a monotone $f$-CNF circuit, list its minimal satisfying assignments of weight $\leq k$. Then, generate a new circuit with an OR gate at top. It has one input for each minimal satisfying assignment from the list. This input is an AND gate, whose inputs in turn are the variables that are set to true in that assignment. It can be seen that the new $k$-DNF circuit is equivalent to the old $f$-CNF one for assignments of weight $\leq k$. Thus we can replace each $f$-CNF subtree by its respective $k$-DNF subtree. After merging the latter's top OR gate with the OR gate that was the former's parent, we have reduced depth to $t$.

As sketched here, the fan-in of small gates is not bounded by a constant any more but by the parameter. Further techniques can remedy this. For the present purpose however, it may be sufficient that we have seen the depth to collapse by $1$.


Turing Machine equivalence in MinTM proof

How do we know that $MIN_{\mathrm{TM}}$ is inifinite?

There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description.

  Why $C$ is equivalent to $D$?

Because of point 3., which essentially forces $C$ and $D$ to have the same behavior. In this case, yes, equivalence is used in the sense that $L(C) = L(D)$.

  Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$
  cannot be minimal"?. Why do we expect $D$ to be minimal?

$D$ is minimal because $\langle D \rangle \in MIN_{\textrm{TM}}$. Recall that, by assumption, the enumerator $E$ only outputs descriptions in $MIN_{\textrm{TM}}$. The point is that $\langle C \rangle$ is fixed (because we have just provided a description for it), but $E$ gives us descriptions of TMs of arbitrary length indefinitely; hence, $E$ will eventually output some description which is longer than $\langle C \rangle$.


Why is the address-of operator in C/C++ represented with the "&" symbol?

Because B did!
A user on software engineering.sx contacted Ken Thompson:

From: Ken Thompson
c copied from b so & and * are same there.
b got * from earlier languages - some assembly,
bcpl and i think pl/1.
i think that i used & because the name (ampersand)
sounds like "address." b was designed to be run with
a teletype model 33 teletype. (5 bit baud-o code)
so the use of symbols was restricted.


What kind of math problems can be solved by automated theorem provers?

Most of your statements are elementary algebra, so these can be proved automatically by a computer algebra system (CAS), such as Maple or Mathematica.

(In case you're interested in the mathematics behind CAS, I can recommend the book Modern Computer Algebra by Joachim von zur Gathen and Jürgen Gerhard,  a beautiful book, considered the 'bible' of the field)

Automated theorem proving tends to be mostly a case of doing heuristic search on a structure that represents proofs, if the proof is not one of the few cases for which there is an algorithm that can conclusively solve it. Given that this statements aren't very complicated, it is likely that an automated prover is able to 'find' a proof.

However, I think it is interesting to say a bit more about the statements for which there are nice algorithms:

Statement 3 is (a very simple case of) about roots of a (system of) polynomial equations and can be solved by finding a Gröbner basis with Buchberger's algorithm. The Gröbner basis and Buchberger's algorithm to find one are very nice tools for automated theorem proving. For example, we can even automatically prove elementary theorems in geometry by automatically transforming the problem to finding a root of a polynomial equation in a clever way!

Another interesting class of theorems are statements expressible in quantifier-free Presburger arithmetic (in particular, this arithmetic is without multiplication, so this doesn't apply to your statements), as there is an algorithm to solve all such statements, even though the algorithm is a bit slow.


What's the connection between the two "Fast Walsh Transform"?

Suppose that $A$ and $B$ are vectors of length $n$, where $n$ is a power of 2. We index $A$ and $B$ using binary vectors of length $\log_2 n$, and define their convolution $C$ as
$$
C_i = \sum_{j \oplus k = i} A_j B_k.
$$

You can calculate the convolution of $A$ and $B$ using the following algorithm:

Compute the Walsh transform of $A$: $\alpha = H_n A$.
Compute the Walsh transform of $B$: $\beta = H_n B$.
Multiply $\alpha$ and $\beta$ pointwise: $\gamma(S) = \alpha(S)\beta(S)$ for all $S$.
Compute the inverse Walsh transform of $\gamma$: $C = H_n^{-1} \gamma$.

(Note that up to normalization, $H_n^{-1}$ and $H_n$ are the same matrix.)

The way we compute the convolution of $A$ and $B$ is using the Walsh transform and its inverse. The Walsh transform itself simply consists of multiplying a vector by the Walsh matrix, which can be done in $O(n\log n)$ time. Since the third step takes only $O(n)$ time, the entire algorithm runs in $O(n\log n)$.


Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?

The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this:

  Is there a function $f\colon \mathbb{N} \to \{0,1\}^*$ satisfying $|f(n)| = o(\log n)$ and a program $P$ such that $P(f(n))$ uses space $O(f(n))$ and outputs $1^n$?

It is a basic result of Kolmogorov complexity that this is impossible, even without the restriction on space. However, if you are willing to allow randomness and to incur some (multiplicative) inaccuracy, you can use the approximate counting technique of Morris and Flajolet, for which $|f(n)| = \Theta(\log \log n)$.


The set $A$ cointains all the strings on the alphabet $\{a,b,c\}$ starting with $a$, ending with $c$ and with the same number of $b$s and $c$s. Similarly, $B$ is made by strings on the same alphabet, starting with $a$, ending with $c$ and with the same number of $a$s and $b$s.
So the intersection $A\cap B$ simply cointains all the strings on the alphabet $\{a,b,c\}$ starting with $a$, ending with $c$, with the same number of $b$s and $c$s and the same number of $a$s and $b$s. By the transitivity of equality (I mean, if $x=y$ and $y=z$ then $x=z$, where $x$, $y$ and $z$ are the numbers of $b$s, $c$s and $a$s in a string), you can express these last two condition by saying that the number of $a$s, $b$s and $c$s is the same, i.e., that the strings in $A\cap B$ are of the form $a^n b^n c^n$ for some natural number $n$ (of course here you can use the letter $m$, or any other letter you prefer, instead of $n$).


Constructing an unrestricted grammar for a^n b^m c^n d^m

How about the following:
$$
\begin{align*}
&S \to XY \\
&X \to aXC | aC \\
&Y \to BYd | Bd \\
&CB \to BC \\
&aB \to ab \\
&bB \to bb \\
&Cd \to cd \\
&Cc \to cc \\
\end{align*}
$$
In this grammar you need to apply $O(nm)$ rules to get $a^nb^mc^nd^m$.


Yes, it is always optimal.

No, there is no threshold where it would use less space to use fixed length non-encoded data.

I found a number of proofs on the Web, but there is sufficient discussion in the Wikipedia article Huffman coding.

This also covers other techniques which achieve higher compression (working outside the space for which the Huffman code is optimal).


Difference between free and global variables

They don't play in the same category.

The notion of free variable is relative to a scope. If a variable is present in a term (i.e. a subprogram) and its scope is larger than this term, then the variable is said to be free in that term.

A global variable is one whose scope is the whole program, or the whole file, or the whole module, or whatever scope is called “global” in the programming language you're considering.


How to give the nearest text that the user has written

This is not an easy task.  There is no simple answer; you could do something crude that might give mediocre results, or you could put a lot of effort into it; and it's not obvious to me what will work best.
One possible simple approach is to map each word (except for a few stopwords) to an encoding, using a standard word embedding (e.g., word2vec), average the vectors of the words to get an embedding of the phrase, and then compare two phrases using the L2 distance of their embeddings.  I don't know how well this will work; you could try it and see.
There will probably be more sophisticated approaches, e.g., training a language-based model to compare two phrases for similarity, perhaps building on an existing model (such as BERT) and fine-tuning it.  I anticipate this will require many labelled samples and a non-trivial amount of research and experimentation, so it's not a minor project to take on.


An epsilon transition (also epsilon move or lambda transition) allows an automaton to change its state spontaneously, i.e. without consuming an input symbol.
You need them for two cases
$1.$ The string or part of the string includes a Kleene star $^*$. E.g. $(10)^*$
$2.$ We have the option to choose between different strings. E.g. $0|1$
Now to make the string $$1^*(00|011^*)^*00$$ much easier, we will split the string in different steps.
Step $1$: Find NFA for $1^*$. We can do this by the following

Step $2$: Find $(00|011)^*$. We will skip $1^*$ to make it ourself easier.

Step $3$: Now we add $1^*$ to the previous NFA. We actually can 'substitute' the DFA in step $1$.

Step $4$: Make sure the string ends with $00$.

If we combine the previous steps, we get the following

You also can always check your answers by a RE to DFA/NFA converter.
Note: The above NFA is made inductivly and can be reduced by removing $\epsilon$ transitions as it is not necessary.


With Memoization Are Time Complexity & Space Complexity Always the Same?

There are plenty examples for which you

need $\omega(1)$ time to compute each table entry or
do not need to keep all table entries.

An example for the former would be CYK; for the latter memoized Fibonacci and Bellman-Ford.


Can you do an in-place reversal of a string on a vanilla turing machine in time $o(n^2)$?

The standard way to prove things like this is to show that $\Theta(n)$ bits of information must cross at least $\Theta(n)$ points.

That is, if you're reversing it "in place", the first third of the bits must cross all $n/3$ middle cells and end up in the last $n/3$ cells. Since the head moves $O(1)$ bits a distance at most $1$ cell each step, this requires $n^2/9$ steps. If the reversed copy ends up in a different set of cells, a very similar argument gives an $\Omega(n^2)$ lower bound.

It takes some work to make this intuitive idea rigorous, but it has been done, although I don't have enough time to locate the papers these results appeared in. If anybody can point to a relevant paper, please edit this answer to do so.


Clique decision problem restricted to a subgraph

Formally, time complexity is defined as

  Let T : N → N. A Turing Machine M has time complexity T(n) if $∀ x ∈ \{0, 1\}^*$
  , M(x) halts in at most T(|x|) steps.

That is to say, time complexity captures the (relative) amount of time taken for all inputs.

Thus the answer is no, that doesn't change the time complexity at all, because then you would just have an instance of the question: Given a graph $G(V',E)$, where $|V'| = m$, and an integer, $k$, determine if a clique with size $k$ exists.

As $m$ increases, the running time would increase in the way similar to how it would if |V| increases in the original problem.

However, if $m$ is defined to be a constant, then the time-complexity would be $O(1)$ (the TM would halt in at most x steps no matter what the graph is) but the problem itself would not make any sense

  Given a graph G(V,E), and k-integer, determine if a clique with size k exists after checking m vertices, where m is a constant.

because a decision problem is formally defined in terms of set-membership, and a different algorithm (a different way to finding if a clique exists) would yield a different result, for $|V| > m$.


Are the languages recognized by deterministic one-counter machines equivalent to deterministic context free language?

The conclusion is: the languages recognized by DOCA(deterministic one counter automata) is a proper subset of the languages recognized by DPDA(deterministic pushdown automata).

The reason why Hopcroft said the proof is complex is that in his definition, the input string of DOCA is appended with an endmarker  \$ [1:P356]. So, the actual difficulty is to prove that: for any language $L$, there exists DPDA $P$ s.t. $L = L(P)$ $\Leftrightarrow$ there exists DPDA $P$ s.t. $L\$ = L(P)$.

This is shown in Exercise 8.5.2 [1:P362] .But I failed to prove the exercise by Hopcroft's hint. I find a detailed proof here by Hendrik Jan Hoogeboom and Joost Engelfriet [2, see remark end of Section 1.6].

Since, we can prove that the languages of DOCA is a subset of the languages of DPDA.

In contrast, $\{ a^n b^m a^m b^m | n, m \ge 1 \}$ is a language that can be recognized by some DPDA but can't be recognized by any DOCA. (Thanks to @Vor in his answer)

References

[1] John E. Hopcroft and Rajeev Motwani and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. Boston/MA: Addison Wesley.

[2] H.J. Hoogeboom, J. Engelfriet (2004). Pushdown Automata.
Chapter in: Formal Languages and Applications, C. Martín-Vide, V. Mitrana, G. Paun, eds. Springer.


How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?

Although your question does not say it, I'm assuming that you do not want windows to overlap.

One approach to this problem is to use a constraint solver such as Choco. One simply writes down the constraints encoding your problem, tunes the solver to act in a smart way, and then let it run. This means that all the thinking you need to do will be spent on finding a good way of encoding the problem, not on devising an algorithm and doing the programming and tuning. Here is a partial answer to get you started.

Assume that the screen size is by $x_{max}\times y_{max}$.

For each window, $W_i$, you'll have a set of variables $x_i, y_i, h_i, w_i$ and constraints

$x_i,y_i,h_i,w_i\ge 0$
$x_i + w_i \le x_{max}$
$y_i + h_i \le y_{max}$
Perhaps also some constraints on the minimal size of windows, e.g., $h_i\ge 100$ and so forth.
Aspect constraints: If aspect ratio is 3:4, the constraint could be something like $4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$, where $\epsilon$ is some small non-zero error term to allow for non-perfect window sizes, as otherwise you'd over constraint the problem.

Now you need to take care of window overlap. For each pair of windows, $W_i, W_j$, where $i\neq j$, you'll generate constraints like the following, which capture that no corner of $W_j$ appears within $W_i$. For $(x,y)\in\{(x_j,y_j), (x_j+w_j,y_j), (x_j,y_j+h_j), (x_j+w_j,y_j+h_j)\}$, generate constraint:

$\neg(x_i \le x\le x_i + w_j \wedge y_i\le y \le y_i+h_j)$.

The constraints specified thus far only describe non-overlapping windows that do not spill over the sides of the screen, that satisfy some minimal size constraints, and that preserve their aspect ratio.

In order to get a good fit, you need to specify a metric that captures what it means to be a good layout. One possibility is to assume that you want to keep windows roughly equal in size and/or that you want to minimize "white space". I do not think that this can be specified using Choco, but it may be possible with another constraint solve (someone else might be able to help here).

Choco does allow one to maximize wrt to an objective function specified as a single variable.
Based on this idea, you could maximize the following:

$\sum_i (h_i + w_i)$

by writing a constraint $\mathit{cost}=\sum_i (h_i + w_i)$ and telling Choco to maximize $\mathit{cost}$.


$(V\cup\Sigma)$ represents the set of variables (like $P$) and terminals (like $0$).

$(V\cup\Sigma)^*$ represents all finite strings (including the empty string) that can be made from variables and terminals (like $0P0$ or, $01P10PP0P0$, for instance). The expression $(V\cup\Sigma)^+$ is almost the same, but excludes the empty string.

Functions are essentially matchings so can be represented by a Cartesian product $(x, f(x))$, so in your definition, a production in $(V\cup\Sigma)^+\times(V\cup\Sigma)^*$ is a pairing from nonempty strings to strings, like the ones you gave. Others would include

$V\rightarrow \epsilon$ (the empty string is often denoted by $\epsilon$ or $\lambda$).
$S\rightarrow 01001$, or even
$aT\rightarrow TbT$


How would you create a Turing machine that copies a string and prints it to the tape?

You are pretty close, here is a TM deciding the language (pseudocode):

Check the input contains a single $\Box$,

If false, reject.

Zig-zag across the tape, check identical letters, and replace them
by $X$.

If not identical, reject.

When all the letters left of $\Box$ are marked $X$, check for remaining
letters right of $\Box$

If there are remaining letters, reject.
Otherwise, accept


Simple Bayesian classification with Laplace smoothing question

The correct formula is

$$P(w|\text{ending}) = \frac{\text{count}(w,\text{ending}) + 1}{\text{count}(w) + N},$$

where $N$ is the number of possible values of $w$.  Here $w$ ranges over the set of all words that you'll ever want to estimate $P(w|\text{ending})$ for: this includes all the words in the training text, as well as any other words you might want to compute a probability for.  For instance, if you limit yourself to only computing probabilities for English words in a particular dictionary, $N$ might be the number of words in that dictionary.

The intuition/idea behind add-one smoothing is: in addition to every occurrence of a word in the training set, we imagine that we see one artificial "occurrence" of each possible word too -- i.e., we augment the training set by adding these artificial occurrences (exactly one per possible word), and then compute probabilities using the ordinary unsmoothed formula on this augmented training set.  That's why we get $+1$ in the numerator and $+N$ in the denominator; $N$ is the number of artificial occurrences we've added, i.e., the number of possible words.


Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$

The automaton for that language is, as you say, extremely simple: it consists of a triangle, in which 0s move clockwise and 1s move counterclockwise:

A classic way to turn this into a regular expression is to eliminate states one at a time, converting transitions through each state into regular expressions. Eliminating state 2 is easy since there are no epsilon transitions or self-loops, so we end up with:

$$\begin{align}s0 \to s0&: 10 \\
s0 \to s1&: 0 + 11 \\
s1 \to s0&: 1 + 00 \\
s1 \to s1&: 01 \\
\end{align}$$

When we then eliminate state 1, we produce a relatively simple regular expression:

$$(10 + (0+11)(01)^*(1+00))^*$$

Is that regex intuitive? I guess that depends on your intuitions. $10$ and $01$ both have no effect on $2|w|_1 + |w|_0 \pmod{3}$; $0+11$ adds 1, and $1+00$ subtracts 1. So the regex definitely shows the path around the three possible values of $2|w|_1 + |w|_0 \pmod{3}$


Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams [1] that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon > 0$, assuming SETH.

This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see [1]). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega < 2.376$ using matrix multiplication.

[1] Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. 2010.


Regular expression for a binary number that includes "10" and has an odd number of 0's

You can write a regular expression directly:

First ignore the odd number of zeroes. You can easily write an expression for this modified language, based on the fact that you can choose to particularize the first occurence of $10$ (namely $0^*1^*10(0+1)^*$ is a valid expression).
Now you want to modify the first part ($0^*1^*$) and the second part $(0+1)^*$ to take into account the odd number of zeroes. Since these two parts have to agree (have the same parity of zeroes) there are two disjoint cases: either you have even numbers of $0$'s before and after the $10$ pattern, or an odd numbers:

To have an even number of $0$'s before the pattern, simply write $(00)^*1^*$. For an even number after the pattern, this is simply an expression for a word with an even number of zeroes: $1^*(01^*0)^*1^*$ (each $0$ has a friend). Together, this gives you the expression: $(00)^*1^*\ 10\ 1^*(01^*0)^*1^*$.
To have odd numbers, you can re-use modified versions of the expressions in 1.: Before the pattern, you add a first $0$ in front: $0(00)^*1^*$; After the pattern, you need a first $0$ but also $1$'s in the middle: $1^*01^*(01^*0)^*1^*$. Together: $ 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$.

Globally, you have the disjunction of the two cases:

$$(00)^*1^*\ 10\ 1^*(01^*0)^*1^* + 0(00)^*1^*\ 10\ 1^*01^*(01^*0)^*1^*$$

This is not meant to be the smallest possible expression, but at least it shows how you can construct one. For instance, you can factorize the common parts to obtain
$$ (00)^*(1^*10+01^*101^*0)1^*(01^*0)^*1^*.$$


I can give two candidate solutions for your specific situation.

Approach #1: parity

This only works if $k$ is odd.  Notice that if $k$ is odd, the parity of $f(x)$ is the reverse of the parity of $x$.  In other words, the xor of the bits of $f(x)$ is the complement of the xor of the bits of $x$.

This suggests an encoding.  Define $g(x)$ to choose between $x$ and $f(x)$ by always  choosing the one with even parity.  In other words, $g(x)=x$ if the  the bits of $x$ xor to zero, otherwise $g(x)=f(x)$.  Now we have $y \in \{0,1\}^{2k}$ with even parity, and we want to map it to a $2k-1$ bit index/offset.  We can do that by simply truncating the last bit of $y$ (since we know $y$ has even parity, the  last bit of $y$ is uniquely determined by all the other bits).

This scheme is simple, easy to implement, efficient, and achieves perfect compression of your table.  Unfortunately this doesn't work if $k$ is even.  I don't know if there is a simple generalization of this idea to the case where $k$ is even.

Approach #2: multiple tables

This scheme works for arbitrary $k$.  Instead of having a single lookup table, we will have $k/2$ lookup tables $T_1,T_2,\dots,T_{k/2}$, each of which stores a different subset of the space of $k$-mers.  The mapping will have the property that $x$ and $f(x)$ map to the same table and same offset/index within the table.

Define $h(x)$ to be the smallest $i$ such that $f(x_i x_{k+1-i}) \ne x_i x_{k+1-i}$  (here by $x_i$ I mean the $i$th base in $x$, where $i \in \{1,2,\dots,k\}$; so $x_i$ is two bits).   Now we will store $x$ in the table $T_j$ where $j=h(x)$.  For instance, if $h(x)=1$, we'll store $x$ in $T_1$; if $h(x)=2$, we'll store $x$ in $T_2$; and so on.  Conveniently, we have $h(x)=h(f(x))$.  So, we'll define $g(x)$ to compute $j=h(x)$ and then choose between $x$ and $f(x)$ by choosing the value $y$ such that $y_j < f(y_j)$.  In other words, if $x_{h(x)}$ is lexicographically smaller than $f(x)_{h(x)}$, then $g(x)=x$, otherwise $g(x)=f(x)$.

How do we determine the index into the table?  Suppose $h(x)=1$.  Then there are 12 possibilities for $x_1,x_k$ such that $h(x)=1$ (the other 4 possibilities yield $h(x)>1$), and our definition of $g$ picks out 6 of them as canonical.  So, in total there are $6 \times 2^{2k-4}$ possible values of $x$.  Thus $x$ can be easily converted into an index into $T_1$ by mapping $x_1,x_k$ to $\{0,1,2,3,4,5\}$, say $i_1$, and mapping $x_2,\dots,x_{k-1}$ to an integer in the range $0..2^{2k-4}-1$, say $i_2$, and then using $2^{2k-4} i_1 + i_2$ as our index.  You can generalize to the cases $h(x)=2$, $h(x)=3$, etc.  For example, suppose $h(x)=2$.  Then there are 4 possibilities for $x_1,x_k$; 12 possibilities for $x_2,x_{k-1}$, but $g$ picks out 6 of them as canonical; and $2^{2k-8}$ possibilities for $x_3,\dots,x_{k-2}$.  So you can map $x_1,x_k$ to an integer in the range $0..3$, map $x_2,x_{k-1}$ to an integer in the range $0..5$, and map $x_3,\dots,x_{k-2}$ to an integer in the range $0..2^{2k-8}-1$; then map those to an index in the range $0..4 \times 6 \times 2^{2k-8}-1$.  And so on for larger values of $h(x)$.

This strategy works for any value of $k$.  It achieves perfect compression.  It's not too difficult to implement and should be pretty fast.


what is the name for the space between the leaves of a tree

The empty space is called "OTIOSE".   Pronounced "oh-she-ohs"

otiosity

Synonyms & Antonyms for otiose
Synonyms
abortive, barren, bootless, empty, fruitless, futile, ineffective, ineffectual, inefficacious, profitless, unavailing, unproductive, unprofitable, unsuccessful, useless, vain


To remove all comments in a JavaScript file, do we need just a scanner or also a parser?

Scanner (tokenizer) will be enough. Most programming languages do not allow comment nesting, so there is no need to use recursive parsers to strip all comments.


Homomorphisms and isomorphisms in an equational calculus

Can you come up with two different algebras, say, one where the domain is $\mathbb{N}$ and one where the domain is $\{0,1\}$ and in the former, suc and pred work as you would assume, and in the latter, they are modulo 2 operations?  Then, try to come up with a homomorphism from one to another.

Then, try to make an algebra, where the domain is $\{0, s0, ss0, sss0, \dots\}$ and define suc and pred as you would guess.  Make an isomorphism from this one to the one with $\mathbb{N}$ as domain.

Finally, you can make the "term algebra", which has as domain all strings that are valid "terms", i.e.: "0" is in the domain, and for every element $t$ in the domain, "suc($t$)" is in the domain, and "pred($t$)" is in the domain.  Their interpretation is simply that the constant 0 maps to the string "0".  The term pred(suc(suc(suc(0)))) maps to the string "pred(suc(suc(suc(0))))".  Now, you might have a hard time making an isomorphism from this to the standard algebra (the one with $\mathbb{N}$), since "0" and "pred(suc(0))" should both map to 0.

I'm not sure exactly what you ask for, but these two tasks should get you started, at least.


Lower bound on worst case pancake number?

I assume that you are talking about the Pancake sorting (wiki) problem. Your argument for $P_n \ge n$ is rather informal.

The paper "Bounds for Sorting by Prefix Reversal (1979)" gives the lower bound $P_n \ge n$ in the Introduction section. Better lower bounds are also mentioned in this paper.

This paper "Pancake Flipping Is Hard" (2011) proves that determining the minimal number of moves for a given stack is NP-hard.


What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?

The asymptotically optimal algorithm is to split in 2 groups at each step.  In other words, the ability to split into more than 2 groups does not allow us to find an asymptotically more efficient algorithm.

Suppose we split into $k$ at each step.  Then we get an algorithm whose running time is given by the following recurrence relation:

$$T(n) = T(n/k) + O(k).$$

We do $\lg(n)/\lg(k)$ recursive calls to reach the base case, so the solution to this recurrence relation is

$$T(n) = O(k \lg(n)/\lg(k)).$$

Now the function $f(k) = k / \lg(k)$ attains its minimum at $k=2$; for larger $k$, it is strictly increasing.  Therefore, the optimal choice of $k$, if we split by the same ratio at each level and disregard constant factors, is $k=2$.

Splitting by a different amount at each level doesn't help.  The above argument applies to all $n$, so it applies no matter the number of balls -- i.e., no matter what level we split at.

Here is another way to think about it.  Suppose we split into $k_1,k_2,k_3,\dots,k_m$ groups at each level ($k_1$ groups in the first call, $k_2$ in the second recursive call, and so on).  Let's count the number of bits of information we've gained.

How many bits of information do we get after applying the scale when we've split into $k$ groups?  $\lg k$ bits of information, since there were $k$ possibilities.  So, we get $b_i$ bits of information at the $i$th call, where $b_i= \lg k_i$.

Now we need a total of $\lg n$ bits of information to uniquely identify the ball.  Therefore, we need to select $b_1,\dots,b_m$ so that

$$b_1 + b_2 + \dots + b_m \ge \lg n.$$

What is the running time for any particular choice of $b_1,\dots,b_m$?  Well, in the $i$th call, we split into $k_i = 2^{b_i}$ groups, and the time to use the scale is $O(k_i)$, i.e., $O(2^{b_i})$.  Therefore, the total running time for a particular choice of $b_1,\dots,b_m$ is

$$O(2^{b_1} + 2^{b_2} + \dots + 2^{b_m}).$$

Now we want to find the optimal choice of $b_1,\dots,b_m$.  This requires us to minimize $2^{b_1} + + \dots + 2^{b_m}$ subject to the constraint that $b_1 + \dots + b_m \ge \lg n$.  One can compute that the minimum is attained for $b_1= \dots = b_m = 1$.

At the end of your post, you propose an algorithm that increments the number of splits at each step.  You didn't compute the asymptotic running time of your algorithm or compare it to binary search, but if carry through that analysis, it turns out that your algorithm is asymptotically slower than binary search.  Therefore, your proposed algorithm is worse than straightforward binary search.  It does not contradict any of the above analysis.

Details:   By Stirling's approximation, $\Gamma^{-1}(n) = O(\lg n)$ (roughly, ignoring log-log factors), so your proposed algorithm's running time is something like $O((\lg n)^2)$ (roughly, ignoring log-log factors), i.e., worse than binary search.


Is membership of x in an infinite set decidable?

No, this is not allowed, in general, if we know nothing about the set $B$.

As Andrej Bauer explains in the comments: if the set $B$ is arbitrary and there are no guarantees about the set $B$ (as you state in the comments), then no, you cannot write "IF $X \in B$" in a program, as the predicate $X \in B$ might not be computable (depending upon the set $B$).

Re-reading your question, I see that you are allowed to choose a set $B$ of your choice (subject to some conditions).  If you're able to choose $B$ in a way that makes $B$ recursively enumerable, then $B$ is no longer completely arbitrary and you now have an additional condition on $B$ which makes this a straightforward homework (as Andrej Bauer also explains in the comments).


A PCP is a probabilistically checkable proof, and the PCP verifier is the algorithm that checks it. In our case, we are given an instance of Unique Label Cover which is promised to be either at least $(1-\eta)$-satisfiable (Yes instance) or at most $\gamma$-satisfiable (No instance). The (polynomial size) proof, which is similar to a witness in an NP verifier, purports to show that the instance is a Yes instance. It is given by a sequence of bits. The verifier is a probabilistic algorithm which checks the proof. If the instance is a Yes instance then there is a proof which convinces the verifier with probability at least $c$ (the completeness), and if the instance is a No instance then every proof convinces the verifier with probability at most $s$ (the soundness).

This particular verifier chooses two bits $\pi_i, \pi_j$ of the proof $\pi$ according to some complicated distribution, and checks that $\pi_i \neq \pi_j$. Every Yes instance has a proof such that $\Pi[\pi_i \neq \pi_j] \geq c$, and for No instances, all proofs satisfy $\Pr[\pi_i \neq \pi_j] \leq s$.

You can encode this verifier as an instance of Max Cut. The vertices $v_1,\ldots,v_N$ correspond to the bits of the proof $\pi_1,\ldots,\pi_N$, and two vertices $v_i,v_j$ are connected with an edge whose weight is the probability that the verifier chooses to check the two bits $\pi_i,\pi_j$. A cut in the graph can be though of encoding a proof: vertices on one side of the cut are 0 bits, and vertices on the other size are 1 bits. Under this encoding, an edge $(v_i,v_j)$ is cut iff in the corresponding proof, $\pi_i \neq \pi_j$.

The upshot is that if the Unique Label Cover instance is a Yes instance, then the Max Cut instance has a cut whose value is at least $c$, whereas if the Unique Label Cover instance is a No instance, all cuts of the Max Cut instance have value at most $s$. Therefore any approximation algorithm for Max Cut whose approximation ratio is better than $c/s$ would be able to solve Unique Label Cover, which is UGC-hard.


Are instructions defined as expressions with side-effects?

The answer is no. But this is hardly enough.

I think you put your finger on a slightly sore but important point of
computer science and programming. We can pretty well define what is an
expression because that is well formalized in mathematics. But we
somehow wave our hands on what constitutes the essence of instructions, or
side-effects.  "Side-effect" is itself a strange word, with an almost
negative connotation, which says a lot about mixed feelings on the
issue. I do not mean that instructions have not been well formalized with
precise semantics (they have), but they often seem perceived more as a necessary
evil than as a desirable tool. And this is not easily explained. Maybe it is that, unlike expressions, they do not have an obvious counterpart in mathematics. There may be other issues.

But let's try to see the difference.

Mathematically, expression are precisely defined syntactic structures,
often called well formed formulae. From a computational point of view,
these expression are operateur operand structures, that are
interpreted in some domain of value (for operands) and of functions
(for operators). And an expression is just supposed to apply the
functions to the values in the order specified by the structure and
come back with the result (this is pretty close to the abstract
mathematical notion). As in mathematics, a function is supposed to be
just a mapping, giving a result in a given range.

I would define an instruction as a syntactic writing meant to specify
a modification in an environment. What then is an environment? An
environment is something that can be modified, and that can thus
memorize information (I should add transmit information, but let's
stay simple). A typical and very simple environment is the state of the finite
control of a Finite Automaton (FA). It can be changed, and the change
is memorized and can be used later on. A transition of a FA is an
instruction, since it changes the environment. In the case of a Turing
Machine the environment is constituted of the state of the finite control, the tape
content, and the position of the head on the tape. The content of the environment is precisely what is often called an instantaneous description of an automaton.

Since a side-effect is a modification of an environment, one
could say that an instruction is a syntactic structure meant to specify
a side-effect.

Note that the concept of environment (thus of side-effect) is itself
relative. It may be internalized so that we do not even have to know
it exists. For example, the evaluation of an expression may be done by
a device operating with a succession of instructions modifying a small
environment, until the end result is obtained. The modifications and the environment itself can
then be forgotten, and only the result is kept. There may have been
temporary "local" side-effects, but they are irrelevant outside the
evaluation of the expression. That is actually what happens in the
computer. But we still say that the evaluation of the expression has
no side-effect (none remains).

An environment can include places to store values (what is usually
called a variable). An instruction may be an assignment of a value in
some variable, and the value itself may be specified with an
expression. Conversely, the expression can include variables, and is
evaluated by replacing the variables by their current value in the
environment. So the two concepts interact, and are really two faces of
a computational coin.

Note in passing that we have considered that some environments are
more transient than others (for evaluating an expression). That means
that we may actually consider many environments. Managing environments
is actually a major issue in programming language design, and in
programming, particularly to make side-effects as transient as
possible to make program analysis and maintenance easier.

Coming back to our computational coin, the two faces appear in
various guises:

denotational semantics vs operational semantics;
lambda-calculus,
combinatory logic or recursive funtion theory vs Turing Machines, automata and rewriting systems;
evaluation of expressions vs execution of instructions;
functional programming vs imperative programming;
regular expressions vs finite automata.

Sometimes, the same text can allows both readings. A context-free
grammar can be seen as a set equations between expression valued in
sets of strings (denotational view) or as a string rewriting system
(operational view).

Of course, in programming languages, things are made more complicated
by the mixing of expressions and instructions. Instructions use values
that are obtained by evaluation expressions. That is not too bad.
What is worse is that the evaluation of some expressions may cause
side-effects. This is because programming languages often allow
implementing functions with instructions as described above, but
without restricting the side-effects to a local environment that
disappear when the function terminate.

It may also happen that a function will not always return the same
result when called with the same arguments, because it uses internally
values provided by an outer environment that may be subjected to
side-effects. Though it is sometimes put to good use by programmers,
this may be a reason for the distrust of side-effects, as it seems to depart from our mathematical understanding of functions.


Rice's Theorem: implication of having an undecidable property

An undecidable property $\pi$ of Turing machines is the same as an undecidable language consisting of all encodings of Turing machines satisfying $\pi$. We identify the property with the language of encodings of Turing machines satisfying the property.

The fact that a language is undecidable just means that no Turing machine decides the language — this is the definition of undecidability. In particular, no machines recognize the language, assuming recognize means decide; a machine $T$ decides a language $L$ if $T$ terminates on all inputs, on inputs $x \in L$ returns $1$, and on inputs $x \notin L$ returns $0$. A machine cannot be undecidable, only a language can be undecidable.


Finding a '1' cell with a '0' to its right in a binary array

After viewing the original question, it seems that you have an additional piece of information: you know that the first element is 1 and that the last element is 0.
This is crucial!

So indeed you can solve it with binary search: first observe that if the first element is 1 and the last is 0, there must be subsequence of the form $1,0$ in the array.

Denote the array by $A[1,...,n]$. If $A[n/2]=1$, then there is a $1,0$-subsequence in the subarray $A[n/2,...,n]$. If $A[n/2]=0$, then there is a $1,0$-subsequence in the subarray $A[1,...,n/2]$.

So you can use Binary search, which takes $O(\log n)$ time.


Is there a way of objectively measuring the efficiency or quality of software or code design?

The abstract conclusion is not really that "some languages are better than others" but that "some languages are better than others for some purposes". Different languages are somewhat like species in evolutionary biology. They have evolved to fill certain niches. There are many evolutionary niches. They have strengths and weaknesses in different areas. Sometimes these types of analysis can degenerate into what is known in stackexchange as "gorilla vs shark" debates.

The question seems to mix up certain distinct areas in CS study. Code quality is measured by defects and is more programmer and implementation related than language related. Defects can be high or low in any language. efficiency in CS is generally considered interchangeable with ("execution") complexity and measured with Big-O notation. There is also another notion of code/ programming complexity where some functionally equivalent implementations may have different levels of complexity in their programs. This is studied especially in OOP theory.

However recently there is some research along the lines you mentioned. There is a large database of programs with identical functions written in the Rosetta code database and some comparative/ objective/ scientific/ quantitative analysis has been done by researchers. See eg:

A Comparative Study of Programming Languages in Rosetta Code / Nanz, Furia
Code length measured in 14 languages / McLoon, Mathematica


My Solutions

I will try to elaborate on what solutions I found, their implementations and those implementation's running time.
As I don't have any real computer science background, please point out any mistakes/unclarities you find.

First: The problem, in general terms, is to partition a set of points from
$A \subset \mathbb{R}^d$ into groups such that every point in them is $\epsilon$-reachable
from every other point in the group.
Reachable,for $x_1, x_n \in A$, means there is a sequence of points $x_1,\dots,x_n \in A$ s.t. $d(x_i,x_{i+1})<\epsilon$.
In other terms: If two points are closer than $\epsilon$ to each other, the algorithm must assign them to the same group/cluster.

DBSCAN:
DBSCAN is a super general algorithm. I will use $B_{\epsilon}(x)$ for the $d$-dimensional sphere around $x$ with
respect to some arbitrary metric $d(\cdot,\cdot)$. DBSCAN finds clusters by defining:

$x \in A$ is a core point, if at least $N$ other points of $A$ lie in $B_{\epsilon}(x)$
$x \in A$ is directly reachable from $y \in A$ if both are core points and $d(x,y)<\epsilon$
$x \in A$ is reachable from $y \in A$ if there exists a sequence $x_1 =x, \dots, x_n =y \in A$ s.t. $x_{i+1}$ is reachable from $x_i$
non reachable points are outliers

Now, as you might see, for $N=2$ (if you include every point itself when counting) and $d(\cdot, \cdot)$ the usual
euclidean metric
this defines exactly the problem I stated above. DBSCAN clusters together core-points deterministically,
but also adds non-core points to clusters. So if $x \in A$ is reachable from core point $y$, it might
end up in the same cluster without being a core point itself. I say might, because non-core points
may be reachable from different clusters. The assignation is then determined by the order in which
the algorithm runs through the clusters. This ambiguity however resolves with $N=2$, as then every point
that is reachable from another is automatically a core point, that is reachability as stated
above is then a symmetric relation. Clusters are then unambiguous.
In case of an indexing structure that does neighborhood querys in $O(logn)$, the runtime complexity is
apparently $O(n \; logn)$, but don't take my word for it.

I used scikit-learn's implementation of DBSCAN (http://scikit-learn.org/stable/modules/generated/sklearn.cluster.DBSCAN.html).
I failed to find out what runtime complexity this implementation has, but the docs state memory complexity
of $O(n.d)$.

Intersection graph:
As it has been proposed in a different answer: One can also think of the problem as a graph-theoretical one.
The graphs vertices are represented by the points in $A$, with two vertices being adjacent iff their
points are in $\epsilon$-distance of each other. On this graph the problem translates to finding the
connected components.
The paper of
Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212
provides an algorithm for constructing this graph that runs in linear time and is essentially identical to the one proposed
by @D.W.. Finding the connected components can also be done in linear time, e.g. by breadth- or depth-first algortihms.

Python Code:
For the Code, I mainly used the DBSCAN implementation of scikit-learn, networkx for graphs and finding
connected components (it is open source but I couldnt find any reference on the runtime complexity)
and scipy.spatial's cKDTree implementation (which I do not understand in detail).

from sklearn.cluster import DBSCAN
from sklearn.datasets.samples_generator import make_blobs
import networkx as nx
import scipy.spatial as sp

def cluster(data, epsilon,N): #DBSCAN, euclidean distance
    db     = DBSCAN(eps=epsilon, min_samples=N).fit(data)
    labels = db.labels_ #labels of the found clusters
    n_clusters = len(set(labels)) - (1 if -1 in labels else 0) #number of clusters
    clusters   = [data[labels == i] for i in range(n_clusters)] #list of clusters
    return clusters, n_clusters

Is my minimal implementation of the previously described goal. The method returns clusters and their size.
For the graph method, I wrote a little class. The class describes a graph whose vertices are the indices
of the corresponding points in $A$ as list. Using the cKDTree's data structure, finding pairs of
reachable points is lightning fast. You can then slice out the elements via the indices.

class IGraph:
    def __init__(self, nodelst=[], radius = 1):
        self.igraph = nx.Graph()
        self.radii  = radius
        self.nodelst = nodelst #nodelst is array of coordinate tuples, graph contains indices as nodes
        self.__make_edges__()

    def __make_edges__(self):
        self.igraph.add_edges_from( sp.cKDTree(self.nodelst).query_pairs(r=self.radii) )

    def get_conn_comp(self):
        ind = [list(x) for x in nx.connected_components(self.igraph) if len(x)>1]
        return [self.nodelst[indlist] for indlist in ind]

def graph_cluster(data, epsilon):
    graph = IGraph(nodelst = data, radius = epsilon)
    clusters = graph.get_conn_comp()
    return clusters, len(clusters)

I also did a little benchmark, but it is in no way representative. I create a cluster with:

centers = [[1, 1,1], [-1, -1,1], [1, -1,1]]
X,_ = make_blobs(n_samples=N, centers=centers, cluster_std=0.4,
                            random_state=0)

For different N, the methods compare differently, on my machine for example:

$N = 20000$: "cluster": 293.711 ms, "graph_cluster": 422.089 ms
$N = 7000$: "cluster": 87.455 ms, "graph_cluster": 95.322 ms
$N = 700$: "cluster": 3.764 ms, "graph_cluster": 1.689 ms

For small datasets, and this specific clustering, the graph solution wins. But apparently
the DBSCAN shows better scaling behavior. I haven't looked at different dimensions of the data,
but that may also be interesting. Also: the results are exactly the same for both algortihms.
Additional Note: The graph solution scales heavily with $\epsilon$, which is 0.1 in my code. Larger values make it far worse! In other words: If you have small clusters, the graph solution outperforms DBSCAN by ages, for large clusters it is the other way around (apparently).


Not getting the clear picture of Goto actions , reduce and shift actions in SLR Parsing

Remember that a stack entry is a state and a symbol. (In fact, the symbols are not really important for the parser, but they will prove useful later on when you encounter semantic values.)

A reduction action consists of popping the right hand side of a production from the top of the stack and pushing the left hand side. (The number in the reduction action is the number of the production, so you know what the left- and right-hand sides are.)

When the right hand side is popped off the stack, a new state is revealed (at the top of the stack). The Goto action which corresponds to that state and the left-hand side non-terminal tells you which state to push along with the non-terminal.

The parser's actions are illustrated in the chart at the end of section 4.8 of your text, which I reproduce below. However, the reduction and subsequent goto action are combined in the chart:

Stack         Symbols       Input             Action
0                           id ( id + id) $   shift 4
0 4           id            ( id + id ) $     shift 5
0 4 5         id (          id + id ) $       shift 4
0 4 5 4       id ( id       + id ) $          reduce T → id
0 4 5 8       id ( T        + id ) $          reduce E → T
0 4 5 6       id ( E        + id ) $          shift 2
0 4 5 6 2     id ( E +      id ) $            shift 4
0 4 5 6 2 4   id ( E + id   ) $               reduce T → id
0 4 5 6 2 3   id ( E + T    ) $               reduce E → E + T
0 4 5 6       id ( E        ) $               shift 7
0 4 5 6 7     id ( E )      $                 reduce T → id ( E )
0 8           T             $                 reduce E → T
0 1           E             $                 accept

Let's look at what the parser does at the highlighted line in the above chart. We can see that the parser is in state 3 (which is the state at the top of the stack) and is about to perform a reduction.
 The right-hand side of the production to be reduced has three symbols – E + T – which we can also see at the top of the stack (in the Symbols column). So the first thing the parser does is pop the right-hand side of the production:

0 4 5 6 2 3   id ( E + T    ) $               pop E + T

Now, the parser is in state 5 and needs to do something with the E which was just reduced (that is, the left-hand non-terminal in the reduced production).

0 4 5         id (          ) $               push E

We consult the parser action chart, looking for the action for an E corresponding to state 5. That action is G6, meaning that the parser pushes state 6 onto the stack with the symbol E, giving us the next line:

0 4 5 6       id ( E        ) $               shift 7

Aside from the fact that it's a non-terminal rather than a terminal being pushed onto the stack, there is no difference between a shift and a goto action. Of course, the goto action does not consume the lookahead symbol, so that symbol is then used in the new state (resulting, in this case, in a shift action).


How do I choose an optimal cell size when searching for close pairs of points, and using cells to implement this?

There's an enormous amount of work on data structures and algorithms for this sort of problem.  I suggest you start by reading the general literature on this problem.

Start by reading about algorithms for nearest neighbor search, including all nearest neighbors and the fixed-radius nearest neighbors problem.  Those techniques are applicable to your problem.

Then, read about quadtrees, octrees, k-d trees, VP trees, and the general category of BSP trees.


How are lamport timestamps useful in practice?

As Wikipedia explains:

The algorithm of Lamport timestamps is a simple algorithm used to determine the order of events in a distributed computer system. As different nodes or processes will typically not be perfectly synchronized, this algorithm is used to provide a partial ordering of events with minimal overhead, and conceptually provide a starting point for the more advanced vector clock method.
Conceptually, this logical clock can be thought of as a clock that only has meaning in relation to messages moving between processes. When a process receives a message, it resynchronizes its logical clock with that sender. The above mentioned vector clock is a generalization of the idea into the context of an arbitrary number of parallel, independent processes.

In distributed systems, it is often necessary for (almost) all the nodes to reach agreement on things such as the order of events. That agreed upon order need not be the God's Eye knowledge of the order of events. There are various other distributed agreements needed.


If my computer is a 32 bit system,it has a 32 bit address right?But when i print any memory address in C why do i get a short value?

If my computer is a 32 bit system, it has a 32 bit address right?

You should not take it for granted.

Many older processors had external (or internal) buses narrower than 32 bits (thus limiting memory size or demanding more cycles for instruction fetch) but were labeled 32-bit based on the fact that they had 32-bit registers and instructions able to manipulate 32-bit quantities.

Some examples are Motorola 68000 and IBM System/370.

Also a 32 bit system, for backward compatibility, may use a non linear address space (e.g. Intel 80386 fully support the 16-bit segmented address space of its predecessors).

Conversely processors with 32-bit registers and instructions that manipulate 32-bit quantities may have bigger external address bus (e.g. Pentium Pro with 36 bits and a larger address space than 4 GB).

Anyway the correct explanation (educated guess) is in the comments (further details in https://stackoverflow.com/q/5208641/3235496).


What are efficient ways to compute the derivatives of iterated functions?

An unordered hierarchical partition of $n \geq 2$ is composed out of two ingredients:

A non-trivial partition $n_1,\ldots,n_k \vdash n$, where $n_1 \leq \cdots \leq n_k$ and $k > 1$.
For each $n_i$, an unordered hierarchical partition of $n_i$. Furthermore, if $n_i = n_{i+1}$ then in some fixed order of hierarchical partitions of $n_i$, the one chosen for $n_i$ must precede or equal the one chosen for $n_{i+1}$.

In the base case $n = 1$ there is a single unordered hierarchical partition.

This gives the following algorithm for generating all unordered hierarchical partitions. We generate a list $P^{(n)}_1,\ldots,P^{(n)}_{q(i)}$ of all $q(n)$ unordered hierarchical partitions of $n$. For $n = 1$, the list consists of the single trivial partition. In order to generate the list for $n$:

Go over all non-trivial partitions $n_1,\ldots,n_k \vdash n$. We can write this partition more succinctly as $1^{m_1},\ldots,(n-1)^{m_{n-1}}$, where $m_i$ is the multiplicity of $i$.
For each $i \in \{1,\ldots,n-1\}$, make a list of all non-decreasing sequences of length $m_i$ consisting of numbers in $\{1,\ldots,q(i)\}$; there are $\binom{q(i)+m_i-1}{q(i)}$ of these.
Each choice of one sequence for each $i$ from the corresponding list corresponds to one unordered hierarchical partition of $n$.


Which Turing machine problems are Decidable?

You can simulate a given Turing machine to a given number of steps. This allows you to decide Problem 1 and Problem 3, by running $M_N$ on the empty type for $N$ steps (or fewer, if it halts earlier).

Regarding Problem 2, assuming that $N$ is in the language if

$M_N$ halts on the empty tape, and
$M_N$ doesn't halt within the first $N$ steps,

then you can use this language to solve the halting problem (using the same effective enumeration). Given $N$, in order to determine whether $M_N$ halts on the empty tape:

Run $M_N$ for $N$ steps. If it halts, answer Yes.
Otherwise, use Problem 2 to determine whether $M_N$ halts on the empty tape, but not within the first $N$ steps.

Hence Problem 2 is undecidable.


Construct Pushdown Automaton that accepts language $x\in\{a,b\}^*, a=2b$

GPDA$\to$PDA Approach

See you have got a solution from chat. But the first thing popped my mind is a Generalized_pushdown_automaton(GPDA), which can be constructed pretty straight forward.

GPDA construction

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

$(q_0,a,Z)\to(q_0,aZ)$
$(q_0,b,Z)\to(q_0,AAZ)$
$(q_0,a,a)\to(q_0,aa)$
$(q_0,b,A)\to(q_0,AAA)$
$(q_0,a,A)\to(q_0,\epsilon)$
$(q_0,b,aa)\to(q_0,\epsilon)$
$(q_0,b,aZ)\to(q_0,AZ)$
$(q_0,\epsilon,Z)\to(q_f,\epsilon)$

GPDA$\to$PDA convertion

Using the algorithm provided on Wikipedia, we can convert it to PDA easily. Only 6. and 7. need to convert:

6.1 $(q_0,b,a)\to(p_0,\epsilon)$

6.2 $(p_0,\epsilon,a)\to(q_0,\epsilon)$

7.2 $(p_0,\epsilon,Z)\to(q_0,AZ)$

Resulting PDA is $M=(Q',\Sigma,\Gamma,\delta',q_0,Z,\{q_f\})$ where $Q'=\{q_0,p_0,q_f\}$ and $\delta'=(\delta\setminus\{6,7\})\cup\{6.1,6.2,7.2\}$. The constructed PDA is non-deterministic.

Convert to DPDA

To convert to DPDA, the only affected transitions are 1. 2. and 8 in above rules:

$M=(Q,\Sigma,\Gamma,\delta,q_0,Z,\{q_f\})$, where $Q=\{q_0,p_0,q_f\},\Sigma=\{a,b\},\Gamma=\{a,A,Z\}$,$\delta$ includes following rules:

$\mathbf{(q_0,\epsilon,Z)\to(q_f,Z)}$
$(q_0,a,a)\to(q_0,aa)$
$(q_0,b,A)\to(q_0,AAA)$
$(q_0,a,A)\to(q_0,\epsilon)$
$(q_0,b,a)\to(p_0,\epsilon)$
$(p_0,\epsilon,a)\to(q_0,\epsilon)$
$(p_0,\epsilon,Z)\to(q_0,AZ)$
$\mathbf{(q_f,a,Z)\to(q_0,aZ)}$
$\mathbf{(q_f,b,Z)\to(q_0,AAZ)}$


Why would a function be tabulated in advance and then retrieved?

This sort of computation can be used for optimization purposes.

A classic simple example is computing the Fibonacci sequence. Apart from the base cases, $f(n) = f(n - 1) + f(n - 2)$, but then $f(n+1) = f(n) + f(n-1)$ and $f(n+2) = f(n+1) + f(n)$, and so on. So the value of $f(n)$ for each $n$ is used repeatedly. The effect is more dramatic if you use the naïve recursive algorithm.

This computation can be significantly optimized if we keep the values of $f$ that we have already computed and simply access the result as we need it.

If all we want to do is compute $f(n)$ for some $n$ once, this is already an observable improvement in the asymptotic running time of the algorithm (and it shows up very quickly in practice too). If we need to repeatedly use values of $f$ in a larger program, the improvement is even more effective.

Doing things like this form part of a technique called memoization, which is closely related with dynamic programming.


Connecting strings in a graph is a PSPACE problem

You say that you need to solve this "without Savitch", but what you're doing is (almost) implementing Savitch's proof within your algorithm.

That's perfectly fine, of course, as long as you're aware of that.

As for the space analysis of your algorithm - indeed, you present an exponential-space algorithm, in particular because you keep track of an exponential number of strings.

Consider the following change: in your subroutines (in the recursion), instead of limiting the set of vertices you're allowed to visit, how about limiting the number of steps you're allowed to take?

That is, define the subroutine that takes $<M>,x,z,t$ and checks whether $z$ is reachable from $x$ within $t$ steps, with $t$ encoded in binary.

Then, in the recursion, you can divide $t$ by $2$ at each step, thus obtaining a polynomial recursion depth.

This is, in fact, exactly how we prove Savitch's theorem, so it's no surprise that it works...


How does DFS produce MST and All pairs shortest paths in unweighted graphs?

There are two claims here.

  For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.

This is true; in unweighted graphs, every spanning tree is minimal since they all have the same number of edges, $n-1$.

A nitpick I'd have is "the"; they should write "a minimum spanning tree".

  For an unweighted graph, DFS traversal of the graph produces the all pair shortest path tree.

This is false, it doesn't even produce a single-source shortest path tree. See here.

In general, an APSP tree may not even exist. There are $n(n-1)$ shortest paths to encode, and it would be quite the coincidence if they shared only $n-1$ edges. Which can happen, e.g. in acyclic graphs, but it is certainly not always true. I'll leave it to you to come up with a small counter example.


Huffman coding is optimal for letters and can certainly be adapted to sequences. For instance, if the sequence "ab" results in fewer bits than the bits for "a" and "b", then simply add it to the tree ...and so on.

...you can also probably use some simple library which does that all for you with near optimal performances, so that you won't gain much using your custom made super fancy compression algorithm.


Is the langauge of (descriptions of) DFAs that accept $\Sigma^*$ decidable?

It's decidable. Think about what an DFA's accepting states must look like if it accepts every possible string. That property is very easy to check.


Merge sort and quicksort recursion tree depth

There is a pattern, and it has to do with the fact that you are splitting the lists in half in each time. Keep in mind the runtime of mergesort is $O(n \cdot log(n))$, that should provide some hints as to where to go with this problem.
There isn't really a even constant unless you define the constant in terms of $n$. I wouldn't think about this problem in that way, instead I would consider the best and worst cases for quicksort, i.e what choice of pivot is the best / worst, and how does it affect the depth of the recursion tree?
This is very similar to the first problem, in fact, I believe if you figure out the first problem, then this one shouldn't be too hard to come up with. Once again, think about the fact that you are halving the size of the list each time. I'm not sure if you are familiar with recurrence relations, and if not that is something you will definitely want to take a look at.

Here is a good resources to look at:

The whole chapter will be a good read, but for your purposes, just the bits about mergesort and quicksort will suffice

http://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf

I have only given hints and general guidance because I think this is a good problem to think about and to test your understanding of general algorithm analysis, but if you need a stronger hint, feel free to comment.


If a language L is regular then the given operation sort(L) is context free

The way to solve this sort of question is using your problem-solving skills. Here are three ways to approach this question:

Take some DFA (or NFA) for $L$. Now construct a PDA for $\mathsf{sort}(L)$ along the following lines. The PDA starts by reading $0$s, pushing them into the stack. At some point it switches to a second phase in which it only accepts $1$s. At each step it first pops an arbitrary number of $0$s from the stack and feeds them to the DFA, and then reads the next $1$ if any, feeding it to the DFA. It accepts if after processing all the $0$s in the stack and all the $1$s in the input, the DFA is in an accepting state.
Take a left regular grammar for $L$ (so the rules are of the form $A\to\epsilon$, $A\to a$, and $A\to a B$), and replace $A\to 1B$ with $A\to B1$. The result is a context-free grammar for $\mathsf{sort}(L)$.
Parikh's theorem states that $\mathsf{sort}(L)$ is of the form
$$
\bigcup_{i=0}^m \{ 0^{x_i+n_1 y_{i,1}+\cdots+n_{\ell_i} y_{i,\ell_i}} 1^{z_i + n_1 w_{i,1} + \cdots + n_{\ell_i} w_{i,\ell_i}} : n_1,\ldots,n_{\ell_i} \geq 0 \},
$$
where $x_i,y_{i,j},z_i,w_{i,j} \geq 0$. It's not hard to check that all languages of this form are context-free, for example by constructing a context-free grammar.

Note how all of these approaches rely on the alphabet being binary. The language $(012)^*$ shows that this assumption is necessary. (Similarly, the language $(01)^*$ shows that $\mathsf{sort}(L)$ need not be regular.)

Parikh's theorem implies that for languages over the binary alphabet, $\mathsf{sort}(L)$ is context-free whenever $L$ is context-free (that is, we don't need to assume that $L$ is regular, it suffices to assume that it is context-free). You can try proving this fact directly.


Can we test whether two vertices are connected in time linear in the number of nodes?

It is not possible to decide $s$-$t$ connectivity in $O(n)$, in the adjacency matrix model. In fact, here is an $\Omega(n^2)$ lower bound. Let $|S| = |T| = n/2$ be a partition of the vertex set, and choose some $s \in S$ and $t \in T$. Consider the graph in which $S$ and $T$ are both cliques. In this graph $t$ is not reachable from $s$. If we add any edge from $S$ to $T$, then $t$ is reachable from $s$. A simple adversary argument shows that any algorithm that decides where $t$ is reachable from $s$ has to potentially check all $|S| \cdot |T| = n^2/4$ potential edges: if it didn't query some edge $(x,y)$, then it wouldn't be able to distinguish the case in which there is no edge from $S$ to $T$ (and so $t$ is not reachable from $s$) from the case in which $(x,y)$ is the unique edge from $S$ to $T$ (and so $t$ is reachable from $s$).


The idea is to think of your output as representing a number in a mixed base. The $i$th digit has base $b_i$, where $b_i$ is the number of options for the $i$th element. You can then print all possible vectors essentially by implementing a counter. I'll let you work out the details.


How to prove that n&(n-1) and n&(-n) respectively returns and removes the least significant bit?

For $n=0b101000$ we have $n-1=0b100111$, so $n \& (n-1)=0b100000$.
As to the second, then knowing $-n=\sim n+1$ we have $-n= 0b10111 +1 = 0b11000$ so $n \& (-n)= 0b101000 \& 0b11000= 0b1000$.
Addition for general proof.

Let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$.Then
$$n \& (-n) = 2^k$$
proof: as we know $-n=\sim n+1$. So, first step, $\sim n$, gives inversion for each bit. Hence in bits lower then $k$ we will have ones and in bit $k$ we will have zero. Now adding $1$ gives all zeros in bits lower then $k$ and in bit $k$ we again have one, but all upper bits are reversed. So $-n$ have in all  bits more then $k$ reversed values with respect to $n$, which gives result.

Again let's take $n \in \mathbb{N}$. Suppose $k$ is first one in its binary expansion i.e. $n=2^m a_m+ \cdots + 2^k a_k$, where $m \geqslant k$. If we consider $n-1$, then we get zero in $k$-th bit. So $n$ and $n-1$ have different coefficient only for bit $k$. This gives, that in
$n \& (n-1)$ we have all coefficients same as in $n$ besides $k$-th bit is zero.


The upper bound comes also from the proof of the pumping lemma. If you have a DFA with $n$ states, you know that if it accepts a word in length $\ge n$ then the word passes through a circle in the states, thus you can repeat the circle as many times as you like and get an infinite language.

Now, for the upper bound, assume the DFA is infinite, and accepts a word of length $\ge2n$. Now, when you run the word on the DFA, and since the DFA has only $n$ states, there must be a cycle. That cycle must be of length $\le n$. You can now remove a number iterations from that circle such that you will get a word $w$ of length $n\le |w| < 2n$.

The proof is even easier when you use the pumping length $n$ derived from the pumping lemma. Just show that for a word $w=xyz$ where $|w|\ge 2n$, since $|xy|\le n$ and $|y|>0$ there exists an $i\in \mathbb{N}$ such that $n\le |xy^iz| < 2n$.


Counting different words in text using hashing

If you really just want to count the number of distinct words in the document, you don't need to save each instance of the word to the hash table.

So, if you find a words that's already in the table, just don't add it there. This means you don't have to deal with chaining as often, which will speed things up.

But you still have to deal with collisions, because two different words can have the same hash code.

This way, the expected time complexity is $\mathcal{O}(n)$, where $n$ is the total count of characters in the text, assuming a good hash function.


How to prove quantum circuit identity in Qiskit?

You can check whether the unitary matrices are equivalent.

def circuits_equivalent(a, b):
    au = Operator(a)
    bu = Operator(b)
    return au.dim == bu.dim and np.allclose(au.data, bu.data)


Implications of $NP = \Sigma_2 P$ for PH collapse

The answer is yes.
notice that $NP=\Sigma_1$ and for all $i$ you have $\Sigma_i=\Sigma_{i+1} \Rightarrow \Sigma_i=\Pi_i$. This is true since $\Pi_i\subseteq \Sigma_{i+1}=\Sigma_i$. The inclusion holds since if $\bar{L}\in\Sigma_i$ then you have $x\notin L \iff \exists v_1\in \left\{0,1\right\}^{p(|v_1|)}...Q_iv_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=1 $ or equivalently $x\in L \iff \forall v_1\in \left\{0,1\right\}^{p(|v_1|)}...\bar{Q_i}v_i\in\left\{0,1\right\}^{p(|v_i|)}M(x,v_1,...,v_i)=0$. So now your $\Sigma_{i+1}$ verifier for $L$ will ignore $v_1$, run $M(v_2,...,v_{i+1})$ and flip the answer. It remains to show $\Sigma_i\subseteq\Pi_i$. Let $L\in\Sigma_i, \bar{L}\in \Sigma_{i+1}$ and since $\Sigma_i=\Sigma_{i+1}$ you get $\bar{L}\in\Sigma_i$.

Back to your question. If $NP=\Sigma_2$ (or $\Sigma_1=\Sigma_2)$ then $\Sigma_1=\Pi_1$. Let $L\in\Pi_2$ then $\bar{L}\in\Sigma_2\Rightarrow \bar{L}\in\Sigma_1\Rightarrow \bar{L}\in\Pi_1\Rightarrow L\in\Sigma_1$, So $L\in NP$ as required. The opposite direction is clear(for all $i$ $\Sigma_i\subseteq\Pi_{i+1}$).