Graph theory: BFS (Breadth First Search) - why is current processed first?

1) In answer to the semantic question "Wouldn't 'breadth first' mean 'Process children first, then process parent'?"

This question is a duplicate of the following: What is the meaning of 'breadth' in breadth first search?

2) In answer to the technical question "Why is the current node printed (and processed) first before its children are processed?":

BFS processes nodes in the following order: the starting vertex, then all the vertices at distance 1, then all the vertices at distance 2, etc. As pointed out by @user111398, you need to mark a node as visited before processing it or you will go on an infinite loop if the graph is cyclic. If you mark the parent but don't process it before (marking and) processing its children then you are processing the nodes in the following order: all the nodes at max distance, then all the nodes at max depth minus one, etc. This is reverse-BFS, not BFS.


How to create a regular expression for this language?

Your language $L$ is not regular.
Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular.

Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping lemma there is some $1 \le \ell \le n$ such that all words of the form $a^{n+i\ell} b^{n}$ belong to $M$, for all choices of an integer $i \ge -1$.

We pick $i=3$, so that the resulting word is $a^{n+3\ell} b^{n}$. Clearly $n+3\ell \equiv n \pmod{3}$ while $n+3\ell \neq n$. This shows that  $a^{n+3\ell} b^{n} \not\in M$, a contradiction.


Reducing Zero-One Integer Linear Programming problem to SAT

The existence of such a reduction follows immediately from the Cook-Levin theorem, which guarantees that you can reduce any problem in NP to SAT and describes explicitly one way to do it.  Just work through the steps of the proof of the theorem (which can be found in any textbook) and you'll obtain a valid reduction from 0-1 ILP to SAT.


Let me first discuss some possible solutions for the case of $n$ particles and 2 points per particle, then extend it to an arbitrary number of points.

Suppose we're given $n$ particles and 2 points per particle.    Assume we're also given an additional constraint: the initial direction of each particle is also specified.  For each particle, it's easy enough to draw a path from the starting point to the ending point.  Now consider the collection of those paths, and find all collisions.  If we don't have any limit on the velocities or accelerations of each particle, it should be straightforward to pick a particle, choose the speed at which it traverses its path (if a constant speed causes collisions, slow down until you reach the collision point, then speed up afterwards, and adjust until there are no more collisions), and repeat, one particle at a time.

Let's suppose you have an algorithm you're happy with, for $m=2$ points per particle.  Then you can use that to solve the problem for $n$ particles and $m$ points per particle, for any $m \ge 2$: you simply solve it for each pair of adjacent time steps (i.e., the $i$th and $i+1$th points), then combine those solutions.

Probably this could be improved, by finding a better way to handle the $m=2$ case.  For instance, if there is an algorithm for laying out a graph as a planar graph, given pre-specified locations for all vertices, that might help find better solutions.  However, maybe this illustrates one approach that can find at least a possible solution, even if it's not optimal.


Why multiplying float number by multiple of 10 seems to preserve better precision?

The only numbers that can be stored exactly are rational numbers whose denominator is a power of 2 (read any source on floating point numbers to understand why). For example, floating point numbers do satisfy
$$ 1/4 + 2/4 = 3/4 $$
but do not satisfy (or rather, don't necessarily satisfy)
$$ 1/3 + 2/3 = 3/3. $$
There's nothing magical about the number 10. It's just an artifact of the common decimal representation. So in general it won't help to multiply by a power of 10.


Construct regular expression for language

Assuming that the input alphabet is $\Sigma = \{a,b\}$, the term $(a|b)^*a(a|b)^*b(a|b)^*$ describes all words where there is an $a$ followed by a $b$, and the term $(a|b)^*b(a|b)^*a(a|b)^*$ describes all words where there is a $b$ followed by an $a$. If we combine both, we get
$$
((a|b)^*a(a|b)^*b(a|b)^*)|((a|b)^*b(a|b)^*a(a|b)^*)
$$
which describes the set of all words in which at least one $a$ and one $b$ occurs.

Edit: An even shorter solution would be
$$
(a|b)^*(ab|ba)(a|b)^*.
$$
However, this solution requires the alphabet to contain exactly $a$ and $b$ whereas the first solution can easily be extended to arbitrary alphabets.


Type Theory and Principia Mathematica Part IV "Relation Arithmetic"

relational databases are among the highest value, most researched applications of computer science

James, what do relational databases have to do with the question? And why have you tagged this q with 'relational-algebra'? It seems to me entirely gratuitous.

Just because databases are 'relational' does not mean they have much to do with whatever Russell meant by 'relation-arithmetic'.

Relational database theory sticks to simple set theory and FOPL. Precisely because it wants to avoid getting into higher-order complications (and type theory).

Similarly just because historically Russell's theory of types kicked off an area of research, does not mean that everything these days to do with type theory must therefore derive from Russell, or that his later musings would necessarily help.

  Is Russell's theory of relation-arithmetic still largely unnoticed even in modern computer science based on type theory, despite the critical role computers play in bringing mathematical understanding of the empirical world into practical use? If so, why?

I'd say yes, entirely unnoticed.

Again what relevance does the "critical role computers play" have wrt Russell?

On looking at a few of the standard early works in programming language type theory, I see no citations of Russell: Landin 1965 on the semantics for ALGOL; Strachey 1967; Reynolds 1983.

The Reynolds paper has the word "relations" in the abstract. And cites a paper Morris 1973 'Types are not Sets'. And mentions [Dana] "Scott's discovery of how to construct sufficiently rich universes without encountering Russell's paradox".

Modern type theory derives mostly from typing models for Lambda Calculus; of which Russell had no inkling. That could be why.

BTW your opening link to the answer on type theory, which mentions "Russell's paradox occasionally shows up" then points to some results in Haskell I think is again drawing a very long bow. Also those results back in 2010 are for some early developments of then-new type-level features. I'd classify them as bugs. They rely essentially on Impredicativity about which the compiler's user guide says "GHC has extremely flaky support for impredicative polymorphism, ..."; indeed I think the feature is to be blocked as a 'very hard problem to get right'.


Algorithms for Solving Rubik's Cubes by Demaine et al. shows that an $n\times n\times n$ Rubik's Cube can be solved in $O(\frac{n}{\log n})$ moves and this is (asymptotically) optimal.

I am not certain on the complexity of actually computing such a solution but I suspect that (by closely following the steps in the proof) it can be done in polynomial time (probably $O(n^2)$ or $O(n^2\log n)$).

There likely isn't anything out there on higher-dimensional cubes. If there was, they would certainly have cited the Demaine paper. There is a trivial way to solve a $n\times n\times n$, since there exist move sequences that solve an individual cubie in $O(1)$ time. Therefore, if such sequences also exist for higher-dimensional cubes, they could be solved in $O(n^{d-1})$ steps since that is how many cubies are on the surface. And perhaps by extending Demaine's technique you could get that down to $O(\frac{n^{d-1}}{\log n})$ by solving multiple ($O(\log n)$) cubies in one go.

You might be able to find more information here: http://www.superliminal.com/cube/solution/solution.htm


You should define carefully what it means to "find a correct solution". In trivial problems, this may be different than verifying. For example, consider the problem of deciding whether a graph is colorable in some number of colors. This problem is trivial, since every graph is colorable in $|V|$ colors. Moreover, it is easy to define such a coloring - give a distinct color for each vertex.

However, verifying that a coloring is correct takes quadratic time.

As for an upper bound - if verifying a solution takes time $T(n)$, than going over all solutions will take time $2^{O(T(n))}$, so not exactly $2^{T(n)}$, but close.


Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO.

In other words, $\emptyset$ is decidable.

You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.


Terminology - Ensemble or Bag of classifiers?

No, this isn't bagging.  It could perhaps be called an ensemble of classifiers (see https://en.wikipedia.org/wiki/Ensemble_learning) but the most effective description will probably be to just describe what you are doing along the lines you listed in the question.  A "name" is primarily useful as a short way to describe what you are doing.  Some techniques are used so commonly that they have an accepted "name".  What you are doing isn't standard and might not have any well-known "name", but that's OK -- you can describe what you are doing in a sentence or two, so just do that.


What algorithm to use to generate random path of given length

Algo for solving problem when path self-intersections are allowed

Auxiliary problem

First let's solve another problem:

  How many paths of length $K$ exists starting at coordinate $(StartRow, StartColumn)$.

Such problem can be solved by dynamic programming: let $dp[K][R][C]$ be answer for question:

  How many paths of length $K$ exists that start in $(StartRow, StartColumn)$ and ends in $(R, C)$".

Base case:
$$
dp[0][StartRow][StartColumn] = 1
$$

Step of dynamic:
$$
dp[K][R][C] = dp[K-1][R-1][C] + dp[K-1][R+1][C] + dp[K-1][R][C-1] + dp[K-1][R][C+1]
$$

Here we suppose $dp[K][X][Y]=0$, for any $X$ and $Y$ that outside of grid (e.g. $X < 1$ or $X > N$ or $Y < 1$ or $Y > N$)
Also we can even add more constraints for problem and add obstacles: for doing so - we need to suppose $dp[K][R][C]=0, \forall K$, where cell $(R, C)$ is impassable (e.g. is obstacle).

This will take $O(N*M*K)$ time, where $N$ - number of rows, $M$ - number of columns, and $O(N*M*K)$ memory if we will keep all steps of dynamic or $O(N*M)$ if we will keep only last step of dynamic.

Original problem

  Generate random path of length $K$ between cells $S(R_s, C_s)$ and $E(R_e, C_e)$.

First of all we need count how many paths of length $K$ exists between this cells, for that we can use previously described dynamic:
futhermore run it from end cell (e.g. count how many paths of length $K$ exist that start at $(R_e, C_e)$) and save all step of dynamic (we will use it in next steps).
Now add order relation between all paths of length $K$ starting at cell $(R, C)$ and ending at cell $E(R_e, C_e)$:

if $K=0$ we have $0$ or $1$ such paths (such collection is always ordered);
if $K>0$ let's suppose: Paths that go UP $<$ Paths that go RIGHT $<$ Paths that go DOWN $<$ Paths that go LEFT (and for ordering paths in each of 4 groups we can recursevly apply this definition again).

Then we know how many paths of length $K$ exist between cells $S$ and $E$, lets name it $A=dp[k][R_s][C_s]$, now we can uniformly at random peek number $L\in[0, A)$ that will identify choosen path among all $A$ available.
We had ordered all $A$ paths and choose some path to output $L$ ($0-indexed$) and just need to find it. Let $choose(R_c, C_c, L, K)$ - function that return $Lth$ path of length $K$ staring at cell $(R_c, C_c)$ and ending at $E(R_e, C_e)$:

$$
 choose(R_c, C_c, L, K) =\small\left\{
                \begin{array}{ll}
                  \langle empty \rangle, K = 0\\
                  \langle UP, choose(R_c - 1, C_c, L - 0, K - 1)\rangle,
                  \\ \hspace{45pt} L \in [0, Count_u)\\
                  \langle RIGHT, choose(R_c, C_c + 1, L - Count_u, K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u, Count_u + Count_l)\\
                  \langle DOWN, choose(R_c + 1, C_c, L - (Count_u + Count_l), K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u + Count_l, Count_u + Count_l + Count_d)\\
                  \langle LEFT, choose(R_c, C_c - 1, L - (Count_u + Count_l + Count_d), K - 1)\rangle,
                  \\ \hspace{45pt} L \in [Count_u + Count_l + Count_d, A)\\
                \end{array}
              \right.\\
$$
$$
Where \forall K, R_c, C_c\\
Count_u=dp[K - 1][R_c - 1][C_c]\\
Count_l=dp[K - 1][R_c][C_c + 1]\\
Count_d=dp[K - 1][R_c + 1][C_c]\\
Count_r=dp[K - 1][R_c][C_c - 1]\\
$$

And $Count_u$ means how many paths of length $K$ starts at $(R_c, C_c)$ and ends at $(R_e, C_e)$ and first move is $UP$, $Count_l$, $Count_d$, $Count_r$ defines respectively for another directions.

More intuitively, imagine we at $X$ cell choosing for $7th$ path:

...
_   4   _
5   X   0
_   9   _
...

If we go $UP$ we will follow paths $\in [0, 4)$, there is no paths to $RIGHT$, if we go $DOWN$ we will follow paths $\in [4, 4+9)$, so we need to go $DOWN$ and choose $(7 - 4)th$ path among all that starts in that cell.

Note: due to we define ordering on paths $I'th$ path everytime will be the same (so it's possible to store path just as index number among all such paths and restore path when it is needed). Also need to notice that order $UP < RIGHT < DOWN < LEFT$ is not only right choise, you can use any order - just keep it thorugh all algorithm flow the same.


An oracle is basically a magic black box that does something (e.g. query the entries of an array), usually in constant time. How the oracle does this is abstracted away from (and sometimes an oracle might even do something impossible like solve the halting problem). It's just a way of saying "presume we had these computational abilities, then ...".


Is the Kleene star of an intersection contained in the intersection of Kleene stars?

Yes, it is true. But  the argument to support the conjecture is incorrect.

The correct proof is as follows: $L_1 \cap L_2 \subseteq L_1 $ and therefore $(L_1 \cap L_2)^* \subseteq L_1^*$. (argument: if $A \subseteq B$ then $A^* \subseteq B^*$).
Similarly $(L_1 \cap L_2)^* \subseteq L_2^*$.

Therefore $(L_1 \cap L_2)^* \subseteq (L_1^* \cap L_2^*)$ (argument: if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$).

Anyway you can not write $(A \cap B)^i \cup (C \cap D)^j = (A^i \cup C^j) \cap (B^i \cup D^j)$.

Correct relation is: $(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup D) \cap (A \cup D) \cap (B \cup C) $

However $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq (\bigcup^\infty_{i=0}L_1^i \cap \bigcup^\infty_{i=0}L_2^i)$ is correct because
$\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_1^i $  and $\bigcup^\infty_{i=0}(L_1 \cap L_2)^i \subseteq \bigcup^\infty_{i=0}L_2^i $.


It helps to think of $L$ as having two parts.

First part: $L_1$ is all strings not in the form $a^i b^j c^k$. We can write this with the regular expression $\neg [a^* b^* c^*]$, so it's regular.

(I've been informed this notation isn't universal, so to spell it out: it's the complement of the regular language $a^* b^* c^*$, and the complement of a regular language is regular.)

Second part: $L_2$ is all strings in the form $a^i b^j c^k$ such that the given conditions on $i, j, k$ are not fulfilled.

The given conditions are that $i, j, k$ are all different. So how can those conditions be violated? Either $i=j$, or $j=k$, or $i=k$. We can call these three options $L_{2a}$, $L_{2b}$, and $L_{2c}$ if you want.

Let's take just one of them as an example; the others work the same way. $L_{2a}$ is all strings of the form $a^i b^i c^k$. Can you write a regular expression for this? How about a CFG? (The answers are no, and yes: in fact, this is one of the classic examples for what a CFG can do that a regular expression can't.)

Now, since $L_{2a}$, $L_{2b}$, and $L_{2c}$ are all context-free, their union ($L_2$) is also context-free. And since $L_1$ is regular, it's also context-free. So $L$, as the union of two context-free languages, is context-free.


Solving the recurrence $T(n)=T(n-1)*T(n-2)$

Your reasoning is perfect. To wit, here is what you get if you don't make any mistakes in your algebra. As you mention, $S(n)$ satisfies the Fibonacci recurrence, and furthermore $S(1) = 2 = F_3$, $S(0) = 1 = F_2$. We conclude that $S(n) = F_{n+2}$. Therefore $T(n) = 2^{F_{n+2}}$. The first few values are
$$
2, 4, 8, 32, 256, \ldots
$$
To get a closed formula, note that
$$
F_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n.
$$
Therefore
$$
\begin{align*}
S(n) &= \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \\ &=
\frac{3+\sqrt{5}}{2\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{3-\sqrt{5}}{2\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &=
\frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n,
\end{align*}
$$
using the fact that $(1\pm\sqrt{5})/2$ are roots of $x^2=x+1$.


Why would total comparison of functions solve the Halting problem?

The specific representation of functions doesn't really matter here, so we'll talk about the usual encoding of Turing machines. We denote the encoding of a machine $M$ by $\langle M \rangle$ (if this bothers you, think of it as the scheme code of the function).

Nothing prevents you from comparing two machines syntactically (by comparing the encoding/scheme code as strings). The problem arises when you claim that you have an operator "$=$" which checks whether the functions are equivalent semantically, i.e. give the same result for each input.
In the language of Turing machines, this means you can decide the following language:

$L = \left\{\left(\langle M_1\rangle ,\langle M_2 \rangle \right) | L(M_1) = L(M_2)\right\}$

The halting problem can be reduced to the above. Given $\langle M\rangle$ and $w\in \Sigma^*$, ask whether the machine $M_w$ which disregards the input, simulates $M$ on $w$, and accepts, computes the constant $1$ function. Thus, $L$ is not decidable. In fact, it is $\Pi_2^0$ complete, so $L$ is not even semi decidable.


What use are the minimum values on minimax trees?

This figure (which is in fact correct) is used in the explanation of the alpha-beta pruning algorithm on a minimax tree. Alpha-beta pruning is a method used to prune parts of the minimax tree in an adversarial search problem. In the context of a tic-tac-toe game, minimax trees are meant to allow the computer to search through the space of all possible game boards (configurations of x's and o's) assuming the player moves are optimal. This allows the computer to come up with a move that provides the best outcome (this is why the connect-four game on your computer is so incredibly difficult to beat!). For a more complete description, I highly suggest "AI a Modern Approach" by Stuart and Norvig (pg. 162-170 ish in the 2nd ed.).

Now that we've cleared up some confusion on to the algorithm. Alpha-beta pruning tries to avoid expanding subtrees based on how the minimax algorithm works. We know that the max node at the top level will take the largest value of all its children. So, node $B$ finds the value $3$, and so far, this is the maximum value its willing to pass up to its parent so it puts this value in the MAX slot. Then it finds $12$. Remember that $B$ is a MIN node, so it wants to minimize the value it passes up to its parent, thus it keeps the value $3$ in the MAX slot. Again for $8$. When $B$ has searched all of its children, it knows the maximum lower bound ($\alpha$) solution and the minimum upper bound ($\beta$) solution of its subtree and maintains those values in MIN ($\alpha$) and MAX ($\beta$) (as [3, 3]).

Note: min and max labeled in the figure are NOT the minimum and maximum values of the subtree! They are (quite confusingly labeled) the alpha-beta bounds of the solutions of the subtree (remember this is an adversarial search problem).

Next we move to node $C$. Here we come across a $2$ in the first position. Node $C$, wanting to select the lowest value from its subtree now KNOWS that its parent will not pick its value since node $B$ found a larger value already. Therefore, we can prune the rest of the subtree and continue on to $D$.

Finally, to answer the specific question: Why is $B$.min = 3?
A value for $\alpha$ (the maximum lower bound of solutions at this node) and $\beta$ (the minimum upper bound of solutions at this node) is maintained at each node in order to perform the pruning. These values bound the possible cases in which the value from a node (or its subtree) may be part of the solution.

In this example, it does not appear to play a role, however, try to look at more complicated examples (i.e. trees with a height > 3) like this one and see if you can make sense of it.

I cannot do justice to minimax or alpha-beta pruning here (mostly because I haven't used them in years), so if you would really like to understand this please check out a book on AI like the one by Stuart and Norvig (the wikipedia page surprisingly has no visualization either).


What data structure might this game use?

A hashtable is asymptotically optimal.  Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces).  Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space.  You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal.  Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors.  But speaking pragmatically: I expect a hashtable will be fine.  The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.


How to construct a max heap that preserves insertion order for duplicate elements?

That's a perfectly reasonable approach.  Use (priority, insertion timestamp) as the priority value for your heap, with comparisons using lexicographic order (compare by priority, breaking ties by insertion timestamp).  That's all simple and easy to implement, and has no downsides that I can see.

Alternative, you can have one node in the priority queue per priority, with a pointer to a queue of items with that priority.  That also works and is easy to implement.


Hardness of approximation of the 3 colorability problem


If you have a binary tree, you should be able to solve this using dynamic programming.
Let $A[v,j,k]$ denote the maximum possible value of the objective function
$$f'(N) = \sum_{x_1,x_2 \in N} \text{dist}(x_1,x_2) + k \sum_{x \in N} \text{dist}(v,x)$$
where $N$ ranges over all subsets of exactly $j$ leaves from among those that are descendants of $v$ (i.e., leaves of the subtree rooted at $v$).
If $v$ is a leaf, it is easy to compute $A[v,j,k]$ for all $j,k$.
If $v$ has one child $v'$, it is easy to compute $A[v,j,k]$ for all $j,k$ from $A[v',\cdot,\cdot]$.
So now suppose $v$ has two children $v',v''$.  Then we can work out a recursive equation for $A[v,j,k]$ in terms of values $A[w,\cdot,\cdot]$ where the $w$'s are descendants of $v$:
$$A[v,j,k] = \max A[v',j',k+j''] + A[v'',j'',k+j'] + 2 j' j'' + jk$$
where $j',j''$ range over all values such that $j'+j'' = j$, $0 \le j',j'' \le j$.  The intended meaning is that $j'$ counts the number of leaves in $N$ that are descendants of $v'$ and $j''$ counts the number of leaves in $N$ that are descendants of $v''$.  In other words, we split $N=N' \cup N''$ where $N'$ contains $j'$ leaves from the descendants of $v'$, and $N''$ contains $j''$ leaves from the descendants of $v''$; then (loosely speaking) we compute the maximum value of $f'(N)$ in terms of the maximum values of $f'(N')$ and $f'(N'')$.  The $2jj'$ term counts distances of the form $\text{dist}(x_1,x_2)$ where $x_1 \in N'$ and $x_2 \in N''$.  The $jk$ term accounts for the fact that the $j$ root-to-leaf paths all need to be extended by one edge (thank you @j_random_hacker).

If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $v$ with $m$ children, create a little binary tree with $m$ leaves, then put $v$ at the root of that binary tree and paste the children of $v'$ in at its $m$ leaves.  Put a distance of 0 on all the edges of that new little binary tree except the top level.  Repeat recursively.
In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $v,w$ is the sum of the distances on the edges in the path between $v$ and $w$.  Now you should be able to generalize the above algorithm to that case.  I'll let you handle the details.


What does it mean to take a union of a transition function with a starting state?

The function $\delta_1$ is the transition function of an NFA. It outputs a set of states. So $\delta_1(q,a) \cup \{q_1\}$ is just the union of two sets of states.


Are there pseudorandom number generators (PRNG) with no finite period?

If the state of the PRNG is finite, then it has a finite period.  (By finite, I mean the same as we mean when we say that a finite-state automaton is finite: the set of all possible states is finite.  For instance, if the state always fits into $b$ bits, for some fixed value of $b$, then its state is finite.)

In practice, worrying about the period of the PRNG may be akin to arguing over angels on a pinhead.  A 256-bit state is large enough that a well-designed PRNG will never repeat within the lifetime of the universe.  Therefore, concerns about repetition are pretty much irrelevant for any reasonable, well-designed PRNG.

In practice, the real challenge is to make the PRNG unpredictable (or close enough for the application's purposes); ensuring it won't repeat is much easier, relatively speaking.


Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L

And, I suspect that that's the purpose of the stuff with the angle brackets.

This is just a way to write elements of a cross product. For example: $$\lbrace 1,2\rbrace\times\lbrace 3,4\rbrace = \lbrace \langle 1,3\rangle,\langle 1,4\rangle,\langle 2,3\rangle,\langle 2,4\rangle \rbrace$$

  I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed.

Basically yes. The construction creates four copies of $A$. The first three copies behave just as $A$ behaved originally with a minor twist: If state $q$ is reached, instead afterwards the state $q$ in the next copy of $A$ is reached. (I will ignore the $\epsilon$ edge inscriptions for now. I come back to this later.)

Thus, initially we are in state $s_0$ of the first copy of $A$ (written as $\langle s_0,1\rangle$). Then, some letter $a$ is read. Let's say that in $A$ this would lead from $s_0$ to state $p$. Now, in the new automaton, this leads to state $p$ in the second copy of $A$, i.e. $\langle p,2\rangle$. Next, some letter $b$ is read. Let's say that this would lead from $p$ to $q$ in $A$. In the new product automaton, this leads from $\langle p,2\rangle$ to $\langle q,3\rangle$, i.e. it also moves on to the next copy of $A$.

The effect of this construction so far is that we not only "behave as $A$ would behave", but also that we know if the current letter position is exactly a multiple of three, or a multiple of three plus one, or a multiple of three plus two: All multiplies of three end up in the first copy of $A$, all multiplies of three plus one in the second copy, etc.

Now, let's go back to the $\epsilon$ edge inscriptions: So far, the automaton that was constructed just behaves as the original automaton $A$. But we want it to read just every third letter and skip the other two. We do this by replacing all edge inscriptions in the first two copies of $A$ with $\epsilon$. This will lead to a lot of non-determinism, because now all outgoing edges have the same label. The idea here is that when we have an input $a_3a_6a_9\dots$ the automaton "guesses" what the missing symbols $a_1, a_2, a_4, \dots$ could be. Each such guess is represented by taking an $\epsilon$-labelled edge. Only the third copy of $A$ is not modified, so this copy still actually reads $a_3a_6a_9\dots$

  What does the fourth copy do?

(No one actually wrote this question, but I need it for structure ;-) )

The fourth copy in the construction from the question actually does not do anything. When the automaton is in state $\langle q,4\rangle$, the only option to continue is to go to state $\langle q,1\rangle$ (via an $\epsilon$-transition). Thus, the fourth copy can just be removed and instead we go directly to $\langle q,1\rangle$.

  Can't one just add those additional transitions to a single copy of A?

First, there are no additional transitions (well, okay, the transitions from $\langle q,4\rangle$ to $\langle q,1\rangle$ can count as additional transitions). Instead, the construction keeps the original transitions but replaces some of the inscriptions with $\epsilon$.

Next, a single copy is not enough.
The automaton still has to keep track on the position in the input.
As an exercise, construct a DFA accepting $(abcd)^*$ and try out the construction on it.


Linear programming vs integer linear programming

The program $x_1 + 2x_2 = 2$ has the integer solution $(0,1)$ and the fractional solution $(1,1/2)$ but not an integer solution of the form $(1,\cdot)$.


How to make a Post Machine for $a^nb^n$?

This language $a^nb^n$ can be recognized by a one counter automaton,
i.e. a pushdown automaton with only one kind of stack symbol (other than the stack bottom).

That can be easily mimicked by a Post machine (with capital P, like
Turing), according to the Wikipedia definition.

So first try to design the PDA with a single stack symbol (that is
easy), and then translate it to a Post machine.

But I am not sure you are using the same type of Post machine as described in Wikipedia, and you did not describe your model.


Your problem is a variant of Mastermind. In particular, it is "Super Mastermind". Wikipedia contains some relevant pointers, and you can find many more by searching for Super Mastermind. For example, Temporel and Kovacs describes a heuristic algorithm that solves Super Mastermind using roughly 5–7 guesses. The same work also contains pointers to other algorithms.


Construct the line graph of $G$, then solve the Travelling Salesman Problem on the resulting line graph.  This yields the optimal solution to your problem, assuming you want to visit every edge in your graph exactly once.

See also the route inspection problem (also known as the Chinese postman problem).


Reducing context-free languages with polynomial-time reductions

Since context-free languages are in P and $M$ is non-trivial, there is an easy polynomial time reduction from every context-free language $L$ to $M$. The reduction decides whether the input is in $L$ or not, and according to that outputs either $\epsilon$ or $0$, say.


You are right. Notice that the term $O(n+m)$ slightly abuses the classical big-O Notation, which is defined for functions in one variable. However there is a natural extension for multiple variables.

Simply speaking, since
$$ \frac{1}{2}(m+n) \le \max\{m,n\} \le m+n \le 2 \max\{m,n\},$$
you can deduce that $O(n+m)$ and $O(\max\{m,n\})$ are equivalent asymptotic upper bounds.

On the other hand  $O(n+m)$ is different from $O(\min\{n,m\})$, since if you set $n=2^m$, you get $$O(2^m+m)=O(2^m) \supsetneq O(m)=O(\min\{2^m,m\}).$$


The difference between dense graph and sparse one

You have to be careful with your definitions. For any graph, the number of nodes and the number of edges is a constant, so $O(V) = O(E) = (1)$. This is clearly not helpful.

Sparse and dense only make sense for a family of graphs $\{G_n\}_{n=1}^\infty$.

The edge density of a graph $G$ is the proportion of possible edges that a graph actually has:

$$ D = \frac{|E(G)|}{{|V(G)|}\choose{2}}. $$

The edge density of a family of graphs is

$$ D = \lim_{n \to \infty} \frac{|E(G_n)|}{{|V(G_n)|}\choose{2}}. $$

The family is sparse if $D = 0$ and dense if $D > 0$. You must analyze the performance of your algorithm under either type of family as inputs.

This definition is from Diestel's Graph Theory.


What is different between "Arithmetic Calculation" and "Calculation" in computer science?

"Arithmetic calculations" are those involving addition, subtraction, multiplication and division of numbers. eg (2+13)/5

There are also "algebraic calculations"  eg Find y such that y + 2x = 13 and more.


Your problem is known as bipartite perfect matching. Unfortunately, the query complexity of your problem is $n^2$ (where $n = |P| = |E|$), that is, in the worst case you might need to make a lot of queries of the form $p(e)$. The complexity remains $n^2$ even if you are allowed XOR queries, and remains $\Omega(n^2)$ even if you are allowed AND queries, or if you are allowed OR queries. See Gal Beniamini and Noam Nisan, Bipartite Perfect Matching as a Real Polynomial.


Your understanding of $AF AX p$ is correct (in my opinion). But whether it seems particularly strange or hard to understand is rather subjective. The argument you quote compares the expressiveness or usability of LTL and CTL, and tries to convince readers that LTL is easier to understand (especially for engineers in practice).

In my experience, it indeed takes more time for me to figure out and confirm the meaning of $AF\,AX\,p$ than that of $AX\,AF\,p$, which is in turn more than that of $X\,F\,p$ or $F\,X\,p$. By the way, if $AF\,AX\,p$ were easier to understand than the other three formulas, you  would probably not bother asking for confirmations here.


How to split a context-free language into three sub-languages?

The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$:
$$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$
We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last:
$$ \begin{align*} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align*} $$
Alternatively, let us notice that the condition $2j < i < 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar
$$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$


Solving the recurrence $T(n) = 2^{n/2}T(n/2) + 2^n$ using a recursion tree

I don't know what a recursion tree is, but I know how to expand a formula:
$$
\begin{align*}
T(n) &= 2^{n/2} T(n/2) + 2^n \\ &=
2^{n/2} (2^{n/4}T(n/4) + 2^{n/2}) + 2^n \\ &=
2^{(3/4)n} T(n/4) + 2^n + 2^n \\ &=
2^{(3/4)n} (2^{n/8} T(n/8) + 2^{n/4}) + 2^n + 2^n \\ &=
2^{(7/8)n} T(n/8) + 2^n + 2^n + 2^n \\ &= \cdots
\end{align*}
$$
You take it from here, along the following lines:

Assume that $n$ is a power of $2$. How many times do we need to apply the recurrence identity until we get to $T(1)$? (Above I applied it three times and got down to $T(n/8)$.)
When we do get to $T(1)$, what are we left with? (When we get down to $T(n/8)$, we are left with $2^{(7/8)n} T(n/8) + 3\cdot 2^n$.)
Suppose that $T(1) = C$. Can you come up with a formula for $T(n)$? Can you deduce a tight asymptotic bound?


Is the set-partition problem polynomial time reducible to the subset-sum problem?

First, both problems are NP-complete, and are therefore reducible to each other. A concrete reduction can go through the Cook-Levin theorem (i.e. SET-PARTITION$\le_p$SAT$\le_p$SUBSET-SUM).

However, in this case there is a fairly trivial direct reduction: given an instance $\{x_1,...,x_n\}$ for SET-PARTITION, compute $t=\sum_{i=1}^n x_i$ and output $\{x_1,...,x_n\},t/2$ as input for SUBSET-SUM. The correctness of this is very easy to show.


Can a DFA have an empty string as input?

Yes, an empty string is a valid input to a DFA. If this were not the case, DFAs would not be closed under all of the Kleene algebra operations.

In this case, the argument is correct. Think of the problem statement as an implication. If $i$ is an odd position, then $S_i$ is 1.


sort n numbers in the range [0,1] without multiplying or dividing

The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$.

(Proof: Take any array of numbers.  You can find the maximum and minimum in $O(n)$ time.  Then, rescale the array.  In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$.  After the replacement, every element will be in the range $[0,1]$.  If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)


In a nutshell: What your teacher probably meant is that the semantics of while is pretty much the same in most languages, while the semantics of for may change considerably (see discussion below). Hence, abstract language independent proof are more reliable with a while, but one should be careful that a proof with a for loop may not match the semantics of the for loop in many languages.

Your question is not precise enough (though that may not be your
fault).

The point is that, afaik, there is no official, ISO supported
standard, or otherwise officially accepted reference definition of
for and while loops. The definition depends on the programming
language.

Hence you cannot make any general statement regarding their
equivalence before you have defined precisely what each can do. I
adress that more precisely, since it is one of the main argument used
in other answers (and the discussion will be useful in what follows).

On intertranslatability of for and while loops

Summary: it depends on the programming language, but is always
possible a long as you can have one infinite loop and a way to get out
of it.

But you can make such a statement for a specific programming language,
and the answer will depend on the features fo the language.

That also means that there is no general proof, but only one for each
programming language.

One thing that is generally true is that a while loop can generally
mimic a for loop, because the while loop can do the exit condition
testing of the for loop, doing the initialisation of the control
variable with an assignment before entering the loop, and doing the
incrementation at the end of the loop body, so that

for i from 1 by 2 to 10 do { xxx }

becomes

i=1
while i≤11 do { xxx; i←i+2 }

This more or less works for most languages, but it is not as obvious as
it seem, and there may be many "details" to worry about.

For example, in many languages, the for loop evaluates it 3
arguments (initial value, increment, and final value) as strict
arguments, evaluated once before entering the loop, while others will
take then as thunk arguments to be reevaluated at each turn, or
possibly as lazy argument to be evaluated only when first needed.

Another point may be that the increment variable may be local to the
for loop, or have to be a local variable of the function where the
loop appears.

Depending on such issues, the translation of a for to a while may
vary widely, though it is usually possible to achieve it.

The same holds for the converse, thranslating a while into a for loop.

Th first problem is that a while loop will always reevaluate the
exit condition at each turn. But some for loops do not provide for a
condition that is reevaluated at each turn, other than comparison of
the control variable with some fixed value computed on loop entry.
Then the translation is not possible unless there is some other mean
to jump out of the loop on some arbitrary conditions.

That is achievable with various devices, usually starting with a
conditional statement testing the condition, followed by an a jump out
implemented, as available, by a loop exit statement, a return
statement (after encapsulating the loop in a function), a goto
statement or an exception raising.

In other words, it is again very dependent on languages, and possibly
on subtle features of languages.

This say, as answered by @milleniumbug, the intertranslation is easy
in the language C, because a for lopp is essentially a while loop
plus some extra for an incremented control variable.

But this does not necessarily apply to other languages, and most
likely not in the same way.

This being said, programming languages are usually supposed to have
Turing power with only one of these loops, since all you need for it
is one infinite loop. So, as long as you have some way of looping for
ever, and possibly deciding to stop, you are pretty sure you can mimic
any other construct ... but not necessarily easily.

Regarding proofs

Summary: There is no reason known to me to assert that proofs should be significantly harder with one or the other (unless some weird feature of the language).

There is probably a misunderstanding, or your teacher had his mind on
something else.

Formals semantics can be defined for the various kinds of loops
defined in programming languages, and then used for proving
properties.

It may be, again depending on the language, that conducting formal
proofs regarding programs may be more complex in some cases. But that
depends on the language.

I cannot imagine a reason why proofs should be significantly harder with one construct more than with the other. The for loop may be more complex since it can offer, as in C, all that is done with a while plus other things. But if you did it with a while, you would have to add the extras in some other form.

I could use the formal general argument of intertranslatability, as long as there is the possibility for a single infinite loop. I will however refrain from doing that, as the constructions involved are nothing you want to deal with in a proof, and it would clearly be an unfair statement, at least in practice.

Following the above discussion, however, we have seen that the difficulties for intertranslatability come from the great variability of the for loop from language to language. Hence the following conclusion which is probably the right answer:

One possibility to understand your teacher's statement is that the semantics of the while loop is pretty much the same in all programming languages, while the syntax and semantics of the for loop can vary significantly from language to language. Hence, it is possible to make general "abstract" proofs with while loops that have language independent semantics to a good extent, while this is not possible for the for loop that has syntax and semantics changing too much from language to language. But this does not apply within a given language, when the semantics of both are precisely defined.

My best suggestion is that you should ask your teacher what he precisely meant, and whether he can give you an example. Misphrasing or misunderstanding is a common event.


It's possible to do slightly faster, by using sophisticated algorithms for transitive closure based on fast matrix multiplication, but apparently it is not known how to do this much faster than the naive solution.  See https://cstheory.stackexchange.com/q/553/5038 and https://cstheory.stackexchange.com/q/736/5038 and https://cstheory.stackexchange.com/q/4258/5038.


Is it possible to evaluate $n!$ in $O(1)$?

There are two scenarios:

Your integers are of fixed size. Then, you absolutely can compute $n!$ in $O(1)$. In fact, every algorithm that computes $n!$ satisfies this. Why? There are finitely many inputs to your algorithm. If it takes $f(n)$ steps to compute $n!$, and there are finitely many $n$ values, then there must be some maximum for $f$. That's the upper bound on your runtime.
Is this answer useful? No, since it doesn't give you any hints as for how to speed up an algorithm. But, it hints that maybe Big-O notation isn't an accurate measure of time for your particular application.

Your integers are of unbounded. Then there can't be an $O(1)$ way to compute it.
How do we know? Well, suppose you have an algorithm that takes at most $k$ steps for any input. Give it an input with $k+1$ bits. It can't possibly examine each bit, since looking up a bit requires a step. So your algorithm only looks at $k$ bits of the $k+1$-length function. But then, if you give the same input with the ignored bit flipped, it will give the same answer! This is impossible, since factorial is an injective function. Flipping a bit should always give us a different answer, so we must examine each bit, so we can't compute it in $O(n)$.


Reduction from a m-coloring to a m-partition

By definition, a $m$-coloring is a function $f : V \to \{1,\dots, m\}$ such that $\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$. This means that at least $|E|$ edges have their endpoints in different sets of the partition $\{V_1, \dots, V_m\}$ of $V$ with $V_i = \{ v \in V : f(v)=i \}$.

On the contrary, if there is a partition $\{V_1, \dots, V_m\}$ of $V$ such that at least $|E|$ edges have their endpoints in different sets, then the function $f : V \to \{1, \dots, k\}$, where $f(u)$ is the unique index $i_u \in \{1, \dots, m\}$ such that $u \in A_{i_u}$, satisfies $\forall u,v \in V \; f(u) = f(v) \implies (u,v) \not\in E$.

The above shows that the instance $G=(V,E)$ of $m$-coloring can be reduced (w.r.t. Karp reductions) to the instance $\langle G, |E| \rangle$ of $m$-partition.


Showing that a problem in X is not X-Complete

Actually proving $X$ is not $PSPACE$-complete (under, say, polynomial-time reductions) would be extremely hard to do.

If $P=PSPACE$, then all non-trivial (i.e., not $\varnothing$ and not $\Sigma^{\star}$) and infinite problems in $PSPACE$ are $PSPACE$-complete under polynomial-time reductions. Since the existential theory of the reals has this non-trivial and infinite property, proving that it isn't $PSPACE$-complete would imply $P \neq PSPACE$. (See the answer to this question on CSTheory.SE for a sketch of the proof.)


The state of the machine can be used as a finite memory. You can use the state to remember (or, if you prefer, "encode") what the last character you saw was, since there are only finitely many possibilities. If necessary, you can remember the last two characters, or ten or a million, as long as you fix the number at the time when the machine is designed.

What you can't do is remember an unbounded amount of information in the state. So you can't remember, for example, all the characters you've passed over since you last saw an '$a$', or even the number of characters since then.


Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?

There is a preprocessing method called vivification$^1$ that can be used to detect subsumed clauses.  It relies on unit propagation to work.

To vivify a clause, make a partial variable assignment such that all the proposed clause's literals are false.  E.g. if your proposed clause is $x_1 \lor \lnot{x_2} \lor x_3 \lor \lnot{x_4}$, assign $x_1$ = FALSE, $x_2$ = TRUE, $x_3$ = FALSE, and $x_4$ = TRUE.  If while you're doing these assignments unit propagation produces a conflict, or if one of the variables is set by unit propagation and vivification later wants to set it to a different value, then the new clause is implied by the existing formula and can be discarded as redundant.

$^1$"Vivifying Propositional Clausal Formulae" by Cédric PIETTE,
Youssef HAMADI and Lakhdar SAÏS


Let's start by assuming that we have two bit vectors $A,B$ of size $m$ instead of two matrices – the matrix structure is unhelpful.

Let $w \in \{\pm1\}^m$ be chosen randomly, and let $\varphi = x \mapsto \langle x,w \rangle \pmod{3}$. If $A,B$ differ on the coordinates in $S$ then
$$ \varphi(A) - \varphi(B) = \sum_{i \in S} (A_i - B_i) w_i \pmod{3}. $$
The distribution of this is the same as the distribution of
$$ \Delta = \sum_{i \in S} w_i \pmod{3}. $$
Suppose $s = |S|$. In order to compute the distribution of $\Delta$, let $\omega$ be a primitive third root of unity, and consider
$$ \left(\frac{\omega + \omega^{-1}}{2}\right)^s = \frac{(-1)^s}{2^s} = \left(\frac{1}{3} + \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \omega^0 + \left(\frac{2}{3} - \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \frac{\omega + \omega^{-1}}{2}. $$
For concreteness, here is the probability that $\Delta = 0$ for $s = 0,1,2,\ldots$:
$$ 1,0,\frac{1}{2},\frac{1}{4},\ldots $$
These probabilities tend to $1/3$ exponentially fast, alternately being above and below it. In particular, if $s = 1$ then $\Pr[\Delta = 0] = 0$, and otherwise $\Pr[\Delta = 0] \geq 1/4$.

This suggests the following algorithm, in the case in which the two computers are allowed shared randomness:

Both computers extract $k$ random functionals $\varphi_1,\ldots,\varphi_k$ from the common randomness.
Computer 1 sends $\varphi_1(A),\ldots,\varphi_k(A)$ to Computer 2.
Computer 2 computes $\varphi_1(B),\ldots,\varphi_k(B)$, and outputs Yes if $\varphi_i(A) \neq \varphi_i(B)$ for all $1 \leq i \leq k$.

If the two vectors differ in exactly one location, then Computer 2 always outputs Yes. Otherwise, it outputs No with probability at least $1 - (3/4)^k$. Choosing $k = 3$, we get $1 - (3/4)^3 > 1/2$.

What if the computers are not allowed shared randomness? A standard trick allows us to simulate shared randomness using an overhead of $O(\log m)$. In total, the communication complexity is $O(\log m)$.


As all productions in  $A\rightarrow \mathrm{ab}A\text{ }|\text{ }A\mathrm{b}\text{ }|\text{ }ε$ are linear, and (crucially) there is only one non-terminal symbol, all derivation sequences can be reordered into equivalent ones where left-side derivations always precede (or always succeed) right-side ones.

For instance:

$wAv \Rightarrow  w\mathrm{ab}Av \Rightarrow  w\mathrm{ab}A\mathrm{b}v \Rightarrow  w\mathrm{abab}A\mathrm{b}v \Rightarrow  w\mathrm{abab}A\mathrm{bb}v\equiv \\wAv \Rightarrow  wA\mathrm{b}v \Rightarrow  wA\mathrm{bb}v \Rightarrow  w\mathrm{ab}A\mathrm{bb}v \Rightarrow  w\mathrm{abab}A\mathrm{bb}v$

(This is a hint of what an inductive proof using fixed-points would look like in this particular case. Check this if you are determined to go down that road).

This means that this grammar can be converted into a regular grammar in two steps, by grouping left-linear and right-linear productions:

1.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow A''\mathrm{b}\text{ }|\text{ }ε$

2.

$A \rightarrow A'A''\\A' \rightarrow \mathrm{ab}A'\text{ }|\text{ }ε$
$A'' \rightarrow \mathrm{b}A''\text{ }|\text{ }ε\\$

So $\mathcal{L}(A) = (\mathrm{ab})^*\mathrm{b}^*$


Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

If the vertex $u$ is not added to to $G'$, then a Hamiltonian cycle in $G'$ does not necessarily correspond to a Hamiltonian path from $s$ to $t$. This is because the cycle may not have $s, t$ adjacent to each other.
For example, one could have

Since there is no Hamiltonian path from $s$ to $t$ in the first graph, there is no Hamiltonian cycle in the second graph. However, if you didn't include $u$,

then there is a Hamiltonian cycle so the reduction fails.


Difference between Lamport timestamps and Vector clocks

Although similar they have different purposes: version vectors can distinguish whether two operations are concurrent or one is causally dependent on the other; Lamport timestamps enforces total ordering. Total ordering although more compact cannot tell whether two operations are concurrent or causally dependent.


Which of the following problems can be reduced to the Hamiltonian path problem?

Problem 1 can be solved in polynomial time. Here is a simple algorithm to compute it in $O(n^2 + nm)$ (it can probably be done faster).

This can be solved in a dynamic programming style. If we find the shortest length $k$ path to all nodes from source $s$, then we can easily find the shortest length $k+1$ path to all nodes from source $s$. Let $d_k(v)$ be the length of the shortest $k$-length path to node $v$ from source $s$. We have:

$$d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$$

Where $d_0(s) = 0$ and $d_0(v) = \infty$ if $v \neq s$. Then we must simply iterate over all $k$ and compute the necessary values.

set d(s) = 0
set d(v) = infty for all v != s
for k in 1, 2, ..., n-1 do:
  for all nodes v do:
    set dp(v) = infty
    for all nodes u adjacent to v do:
      set dp(v) = min(dp(v), d(u) + w(u,v))
  set d = dp
return d(t)

Note that dp is just an intermittent variable so that $d_k$ is correctly computed on $d_{k-1}$ rather than accidentally overwriting $d_{k-1}$.

The two inner for loops take $O(n + m)$ and the outer takes $O(n)$. Overall this algorithm takes $O(n^2 + nm)$.

The reason for this speed-up is precisely what Peter said. We do not need to keep track of intermediate nodes in order to prevent cycles, we simply keep going without worry of cycles at all. If we needed to keep track of intermediate nodes then it is not necessarily the case that $d_{k+1}(v) = \min_{u\ \in\ adj(v)} \ d_k(u) + w(u,v)$. It may end up being that case that we would actually not use $d_k(u)$ to compute $d_{k+1}(v)$ because there may be a slightly longer path to $u$ that actually allows us to use edge $(u,v)$. This creates a combinatorial explosion in terms of what we must check and remember.


What the heck is a memory channel "CS bus"?

I think it is the "Chip Select" part which is mentioned at slide 26.

It probably selects whether to use the chip on the front or in the back.


if traveling salesman problem is decidable in polynomial time, can an actual solution be proposed in polynomial time?

If you have available a TSP decision oracle -- that is, a function that answers questions of the form "Does directed graph $G$ have a TSP tour of length at most $k$?" in constant time -- then the following algorithm will allow you to construct an actual TSP tour using $O(|E|)$ calls to the oracle, and $O(|E|^2)$ time overall:

Run a binary search on $k$, calling the decision oracle at each step, to determine $OPT$, the minimal tour length of the original graph $G$.  (If necessary, the absence of any Hamiltonian cycle at all can be first tested for by calling the oracle with a very large threshold -- e.g., equal to the sum of all edge weights.)
If $G$ contains 3 or fewer edges, then stop.  (These must form a triangle.)
Choose an arbitrary vertex $u$ in $G$.
For each out-edge $uv$ in $G$:

Create a new graph $G'$, which is the same as $G$ except that the edge $uv$ has been collapsed (specifically: delete vertices $u$ and $v$ and all edges they are incident on, and create a new vertex $x$ that has all of $u$'s incoming edges and all of $v$'s outgoing edges).
Run the decision oracle on $G'$ with the length threshold $OPT-w(uv)$.
If the answer is YES, then some optimal solution to $G$ contains the edge $uv$: Replace $G$ with $G'$ and $OPT$ with $OPT-w(uv)$ and go to 2.
If the answer is NO, then no optimal solution to $G$ contains the edge $uv$: Delete $uv$ from $G$, and continue iterating through other out-edges of $u$ in $G$.

The iterations in the loop beginning at step 4 execute at most $|E|-3$ times.  How quickly the graph modification steps (edge collapsing, edge deletion) in each iteration can be performed probably depends on the graph representation used, but they can certainly be done in $O(|E|)$ time each, for $O(|E|^2)$ time overall, which is enough to show the algorithm is polynomial.  (Can anyone think of faster $O(|V|)$ or even $O(|1|)$ ways to perform these modifications?)

The above runs on a directed graph $G$.  If you have an undirected graph, you can first turn each undirected edge into a pair of opposite-facing directed edges having the same weight, and then run the algorithm as before.


Explanation of Tag, Index, and Offset in Direct Mapping Cache

If the cache blocks are not sectored, then if the tag field matches any offset within the block will be a hit. With sectoring a cache block can have multiple valid bits, in which case the tag might match but the valid bit for the section corresponding to the offset might be cleared (indicating that the section is invalid).

In theory a valid bit could be provided for every smallest unit of access (commonly an 8-bit byte), but sectoring is more commonly used to allow an outer level of cache to use a larger block size than L1 caches without forcing all the data associated with a tag to be invalidated when the smaller unit needs to be. For an inclusive cache, this avoids unnecessary back-invalidation of L1 cache. (It would also be possible to include fully independent coherence state, e.g., MESI, rather than just validity. This could be used to avoid unnecessary writebacks, e.g.)

Sectoring can also be used to directly fill the cache and allow early restart; alternatives include using a side (fill) buffer with extra valid bits (similar to a write buffer) and waiting for the entire cache block is loaded before restarting execution.

To confuse matters, Intel uses cache line to indicate the smaller unit that shares a tag with other lines in a sector while some others use cache block/line for the larger unit with the term sector used for the portion that can be individually invalidated.

For the level of complexity for this type of exercise, one can reasonably assume that sectoring is not used, so a tag match would indicate a hit regardless of the offset.


Why is the dynamic programming algorithm of the knapsack problem not polynomial?

When we say polynomial or exponential, we mean polynomial or exponential in some variable.

$nW$ is polynomial in $n$ and $W$. However, we usually consider the running time of an algorithm as a function of the size of the input.

This is where the argument about $\log W$ comes in. Ignoring the values of the items for the moment (and considering only their weights), the input of the knapsack problem is $n$ numbers $\leq W$. Each number is represented with $\log W$ bits, and there are $n$ numbers, so the size of the instance is $n\log W$.

This makes $nW$ not polynomial in the size of the instance, since $W$ is exponential in $\log W$.

However, (coming back to your example about sorting) an instance for sorting consists of $n$ elements to be sorted, and representing these takes at least $n$ bits (and probably a bit more, since the elements themselves are probably bigger than $1$ bit each). We can represent the number $n$ using $\log n$ bits, but we can't represent $n$ things using $\log n$ bits.

The main difference is that $W$ represents a number in the input, while $n$ represents "the number of things".

Note that if we were to "cheat", we could represent $W$ using $W$ bits if we used a unary encoding. This version of the problem is technically polynomial, but really only because we were deliberately being less efficient.

It turns out that there is a whole class of Strongly NP-Hard Problems, which are still NP-hard even when the input is represented in unary format. But Knapsack
is not one of these problems.


Why is the halting problem decidable for LBA?

The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is $S$, the alphabet size is $A$, and the number of states is $Q$, then the number of possible configurations is $QSA^S$. If the machine halts then it must halt within $QSA^S$ steps, since otherwise, by the pigeonhole principle, it has a repeated configuration and so is stuck in an infinite loop. Therefore to determine whether the machine halts, we just run it for $QSA^S$ steps and see whether it halts within that time frame.


Are programming languages becoming more like natural languages?

Not really, no. Programming languages have become more like natural languages only in the sense of “words we have in english” (sic).

A key feature of programming languages is that they are not ambiguous. When you write a program and execute it, it has a well-defined meaning, which is its behavior. If you want to write a program that works as intended (a difficult objective), it is important that the behavior¹ of the program be as predictable as possible. Programming languages haven't made much difference in the wide gap towards natural languages.

Conversely, there has been work in bridging the gap from the other side: analyzing natural languages with the same tools as programming languages. This field is called natural language processing. These approaches have been pretty much discarded in favor of machine learning. I'll cite a passage in the Wikipedia article which is directly relevant here:

  Up to the 1980s, most NLP systems were based on complex sets of hand-written rules. Starting in the late 1980s, however, there was a revolution in NLP with the introduction of machine learning algorithms for language processing. This was due both to the steady increase in computational power resulting from Moore's Law and the gradual lessening of the dominance of Chomskyan theories of linguistics (e.g. transformational grammar), whose theoretical underpinnings discouraged the sort of corpus linguistics that underlies the machine-learning approach to language processing.

One way in which programming is evolving is that as we design larger and larger systems, source code is not always a good way of understanding them. For example, an Intel CPU is one of the most complex objects ever designed by Man, and its “source code” is not just a collection of text files, far from it. But the full design isn't evolving towards anything resembling a human language either. I don't know what the appropriate cognitive tools or metaphors here, and I don't think anybody knows just yet; ask again in a couple of centuries.

¹  Or rather the set of possible behaviors annotated with the circumstances under which they arise, but that's only adding one step of indirection in the modeling, so this isn't really relevant here.


Question about 'Software Transactional Memory' by Shavit and Touitou

So nowhere in this scenario is T1 executed again?

"Retry" is not among the main topics of the classic STM paper.

You can let the initiator of $T_1$ call StartTransaction() (treat $T_1$ as a new transaction) upon each Failure until it receives a Success. The authors have just ignored it probably because they want to focus on the ingenious STM concept.

Retry is of course a big topic itself, for instance, in Composable Memory Transactions.


Let me put together the two comments.
The function $A$ is Euler's totient function, which is often called $\phi$.
The function $B(x)=\sum_{d|n}\phi(d)$ is known to be equal to $B(x)=x$.
Now, observe that $D(x)=\sum_{i=1}^{x}C(B(i))=\sum_{i=1}^{x}C(i)=C(x!)$, where the last equation is because $C$ satisfies $C(a)+C(b)=C(ab)$.
Now, if $p_1<p_2<\ldots<p_k$ are the primes less than or equal to $x$ and $x!=p_1^{a_1}p_2^{a_2}\dotsm p_k^{a_k}$, then $$C(x!)=a_1+a_2+...+a_k$$
We can use Legendre's formula to compute each $a_i$. Note that the formula doesn't need to compute $x!$, but it computes $$a_i=\left\lfloor\frac{x}{p_i}\right\rfloor+\left\lfloor\frac{x}{p_i^2}\right\rfloor+\left\lfloor\frac{x}{p_i^3}\right\rfloor+\ldots$$
where there are actually finitely many summands.
So, an algorithm to compute $D(x)$ can be:

Compute the primes $p_1,p_2,\ldots,p_k$ up to $x$. This can be done using some sieve, like Erathostenes' or Atkin's
Then for each prime evaluate Legendre's formula above, which takes about $\log_{p_i}(x)$ divisions.


Is the language of words with equal number of 010s and 101s as substrings regular?

No, the language of words containing same number of 010s and 101s is not regular.

Consider $x_n=(0100)^n$ and $y_n=(1011)^n$. Then $x_iy_j$ contains $i$ number of 010s and $j$ number of $101s$. That is, $x_iy_j$ is in the language if and only if $i=j$.

So $x_i$ represents a distinct Nerode-Myhill equivalence classes for all $i$. Since there are infinitely many such $x_i$, there are infinitely many Myhill-Nerode equivalence classes. By Myhill–Nerode theorem, the language is not regular.

Here are several related exercises. Exercise 2 answers the more general situation in the question. Exercise 3 is a further generalization.

Let $\Sigma=\{0,1\}$.

Exercise 1. The language of words over alphabet $\Sigma$ containing the same number of 01s and 10s is regular. The language of words over alphabet $\{0,1, 2\}$ containing the same number of 01s and 10s is not regular.

Exercise 2. Let nonempty $w\in \Sigma^*$. Let $\overline w$ be the one's complement of $w$. For example, $\overline{010010111}=101101000$. Let $E_w$ be the language of words over $\Sigma$ containing the same number of $w$s and $\overline w$s. Show that
$$ E_w\text{ is regular} \iff w=01\text{ or }w=10$$
(It may take a while to do this exercise.)

Exercise 3. Let $u$ and $v$ be two different non-empty words in $\Sigma^*$. Let $E_{u,v}$ be the language of words over $\Sigma$ containing the same number of $u$s and $v$s. Let $N_{u,v}$ be the language of words over $\Sigma$ containing no $u$ nor $v$ as a subword. Show that
$$ L_{u,v}\text{ is regular } \iff
\{u,v\}=\{01,10\}\text{ or } E_{u,v} = N_{u,v}.$$
(It may take a while to do this exercise.)


Binary 2s Compliment Applied Twice Gives Original - How?

First, if we wouldn't get the same number after negating it twice, it wouldn't make much sense, right?

So we just need to prove that the "complement and add 1" has indeed the effect of negation, i.e., taking $x$ into $-x$  (and thus, $-x$ to $x$). (well, maybe except for an edge case I will mention below.)

A signed number of $n$ bits, $b_{n-1}, \ldots, b_1,b_0$ where each $b_i\in\{0,1\}$,  is to be interpreted in the following way: the $i$-th bit amount $2^i$ except for the last bit (MSB). The MSB $b_{n-1}$ is what makes the number negative, and can be seen as having the value $-2^{n-1}$.

  Sanity check.
  4 bits. The number 5 is 0101 = 2^2+ 2^0 = 4+1.
  The number -5 is 1011 = -2^{3}+ 2^1+2^0 = -8+2+1 = -5.

With this in mind, given $x = -2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i$ if we complement each bit ($b_i \to (1-b_i)$) we will get
$$\begin{align}NOT(x) &= -2^{n-1}(1-b_{n-1}) + \sum_{i=0}^{n-2}2^i(1-b_i) \\
& = -2^{n-1} + \sum_{i=0}^{n-2}2^i - [-2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i] \\
&= -1 -x
\end{align}$$
therefore, $NOT(x)+1$ equals $-x$.

Note the edge case(s).If $x=0$ then negating it should give 0. Yet complementing each bit gives $111111 \ne 0$ and after +1 we will get back 0  (ignoring the carry).
The other edge case is the maximal negative number $1000$ for 4-bit numbers.
If we negate it we get $0111$ after complementing and $1000$ after adding 1 to the complemented number. In this case (and this case only) the 2-complement system "doesn't work" and gives that the negation of $x$ is $x$.


You can do different analysis with forward and backward flow algorithms:

Forward-analysis can provide information about some code to "future" code -- along the normal path of execution. A good example is constant propagation where you provide the value of variables to code further down the line.

Backward-analysis can provide information about some future properties "back in time". A good example is dead code elimination where you can remove assignments to variables if they will never be read in the future.

Real compilers like gcc or llvm perform both kind of analysis and there are even optimizations that require both kind of analysis simultaneously:

Partial redundancy elimination is one of those forward- and backward-analysis requiring algorithms: It tries to move code to the latest-necesary, earliest-possible place.


lower bound for Renyi–Ulam Game with lies

For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \{1,\ldots,n\}$, let $x_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.

For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\{1,\ldots,m\}$, even when A is allowed to lie at most once. Partition $\{1,\ldots,n\}$ into $m$ intervals $[x_1,x_2),[x_2,x_3),\ldots,[x_m,x_{m+1})$, where $[a,b) = \{a,\ldots,b-1\}$, $x_1 = 1$, and $x_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x_{i+1}-1}{x_i}$. I leave the rest to you.

The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell < n/3$).


Use a proof by induction on the length of the paths.  In other words, prove first that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 1; then that you've found a correct shortest path for all vertices that can be reached by a shortest path of length 2; and so on.


Why do all recent SAT solvers work on CNF instead of circuit SAT?

there are a lot of different angles on your question. generally agreed with your premise that looking at "structural information" in a SAT formulation ought to be an excellent research area.

SAT encoded in CNF has been a standard for decades. it was solidified in the early-to-mid 1990s with the DIMACS format/ competitions.
what technically is "structural information"? it may be hard to formally nail that concept down and avoid near-tautological circles. there is not really any difference between a SAT CNF encoding and and other encodings that preserve a network structure. this is embodied in the "clause/ variable graph" concepts which very many SAT solvers tend to utilize. in other words, in some rough sense, every significant SAT solver uses "structural information".
yes, newer directions in research have focused on ASP and SMT solving which nearly actually embody the "structural information" you inquire about.
Tseytin transformation easily converts a circuit into SAT in P time/ space for input into a standard SAT solver. it is presumably widely used in many contexts esp EE circuit contexts.
there is some rather isolated research generally along the lines you mention but unfortunately (again along with your premise) it never seemed to develop much into a research trend. dont think that is due to lack of potential but more human factors. two favorite papers[1][2], another is to look at particular instances from areas such as "industrial instances" or "electrical engineering" instances of which there is some specialized research.
CS purists sometimes tend to want to avoid psychology/ sociology considerations in all the mathematical abstractions, but reasonably its still a factor in computer science. you ask about research trends, which are based on human psychological factors. its possible there is some streetlight effect going on here aka "low hanging fruit". one might say/ consider that even now a few decades old, SAT algorithmic research is somewhat in its infancy, such that big questions like P vs NP seem nowhere in sight, and maybe existing research while still substantial is still just "scratching the surface".

[1] Decomposing satisfiability problems
 or Using graphs to get a better insight into satisfiability problems, Herwig 2006 (83pp)

[2] The constrainedness knife edge Walsh 1998


Yes, absolutely. SMT solvers are actually quite well suited for such problems. Unfortunately, the input language to them (SMTLib) is rather machine-oriented, but there are many "high-level" interfaces to many solvers, Z3 itself providing a Python interface, for instance.

For this problem, I'll use the Haskell SBV library, which translates your constraints more or less directly to Z3. Note that I've put the equations into SSA form (single-static assignment), as is usual in such analyses. The whole problem is:

{-# LANGUAGE ScopedTypeVariables #-}

import Data.SBV

q = do k1 <- sInt32 "k1"
       k2 <- sInt32 "k2"

       a0 :: SInt32 <- forall "a"
       b0 :: SInt32 <- forall "b"
       c0 :: SInt32 <- forall "c"
       d0 :: SInt32 <- forall "d"

       let a1 = b0 + 1
           c1 = d0
           c2 = c1 `xor` d0
           a2 = a1 + c2
           a3 = a2 + 4

       constrain $ a3 .== b0 + k1
       constrain $ a3 .== d0 + k2

Also note that I (arbitrarily) picked 32-bit integers, though you can go with other types as well as needed. As stated, we get:

*Main> sat q
Unsatisfiable

Meaning that there's no such k1/k2 that satisfy your equations, as you yourself observed. If we let go of the second constraint (by commenting out the very last line in the definition of q), we get:

*Main> sat q
Satisfiable. Model:
  k1 = 5 :: Int32
  k2 = 0 :: Int32

Here's the solver picked the arbitrary value of 0 for k2 since there are no constraints on it; but k1 became 5 as you predicted.

Long story short, yes; this sort of reasoning is absolutely possible with SMT-solvers; and there are high-level language bindings that let you express them rather concisely.


Why classes implicitly derive from only the Object Class?

This is only an answer to answer the question in the title.

Languages such as Java have every class deriving from Object for two reasons.

Firstly, to increase the amount of polymorphism available. This was particularly required before generics were added to the language. Without Object,  collection classes would be impossible to write in a useful fashion.

Secondly, there are many methods that classes are expected to have or are useful, and these are collected in Object. By ensuring that all classes inherit from Object, all classes will implement  the same minimal interface.

As mentioned in a comment, C++ does not have a class like Object. C++ is in many ways untyped, so the issues I mention above are not applicable. Also, C++ templates provide a lot of polymorphism and are used to implement collections.


Amortizing or batching circuit evaluation for many different inputs?

Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory.

For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general construction with known size, or by observing that 2^2^n different functions require 2^2^n different circuits, so the size of the largest circuit encountered cannot be so small that there are less than 2^2^n different circuits of up to that size. Knuth Vol 4A section 7.1.2 Theorem L shows that these bounds are in fact very close together, and require a circuit of size O(2^n/n) for a general function on n bits. So combinatorial logic circuits without memory do not waste much complexity by having many different circuits computing the same function.

If we stick to the design of a gray code generator feeding a circuit with internal memory, the only source of variation is the choice of the circuit, which now includes memory elements. The description of such a circuit needs a few more bits per item to offer the possibility of memory elements, but this is just a constant factor. By the requirement that to be able to compute any of 2^2^n different functions we must provide 2^2^n different circuits, and by the observation that ordinary combinatorial logic circuits do not have staggering inefficiencies, I think we find that introducing internal memory into an otherwise pedestrian design will not allow all possible functions to be calculated using only circuits of size significantly smaller than their best combinatorial logic implementation.

(but if P=NP our simulator has other options, such as Valiant Approximate Counting, which allow them to estimate the fraction of input states leading to a particular outcome in a simulation, without actually simulating all possibilities).

I remain interested in any comments, pointers, or whatever, about anything that bears on this.


Pushdown Automata - can you have multiple transition functions options between 2 states?

Simple answer: yes, that is allowed. In the example you give, it's simple--depending on the input symbol and the stack contents, there's one and only one choice for the action of the machine in state $q_0$. It's even possible to have several actions as consequence to a single (input, stack top) pair, like this,

-- input 0 and stack top 1, push 0 and go to state $q_2$

-- input 0 and stack top 1, push 1 and go to state $q_3$

Seems wierd, I know but such machines are called nondeterministic pushdown automata and are quite useful; look them up.


Prove that if $\mathsf{P^k}=\mathsf{NP}$ then $\mathsf{NP}=\mathsf{co\text{-}NP}$

Hint: The proof that $\mathsf{P}=\mathsf{co\text{-}P}$ relativizes. That means that if the machines in question are allowed access to some oracle, then the proof goes through. The reason is that the proof just works even when you add the oracle - go over the proof carefully and convince yourself.

"Can I also say that ... or do I have to prove it?" You should be able to answer this yourself. If you can't, go over the definitions a few more times until you really understand what they mean, and then, at the very least, you can say whether "..." follows directly from something that you saw in class, or whether it does not. In the latter case, you should prove it.

In this specific case, given that you already saw a proof of a similarly looking result $\mathsf{P}=\mathsf{co\text{-}P}$, it should seem reasonable to try and see if that same proof generalizes to give $\mathsf{P}^K = \mathsf{co\text{-}P}^K$. In this case it does; in other cases it might not, and then you have to work harder.


Potential General Model of Computation with Physics?

It would be meaningful, if you properly defined "formal physical system", "set in motion", and so on, in a mathematical way. Pretty much anything can be made meaningful in mathematics (which is what this sort of theoretical computer science really is).

The question is, is it useful?

It would seem that the functions computable by Turing machines are a subset of this new class, since you can make a Turing-complete physical computer with enough rolling marbles. (Or, if you allow transistors in your "formal physical systems", I could just use "my laptop at the moment when I run this Python code" as the system.)

Then, are there things your physical systems can do that Turing machines can't? Given that a Turing machine can simulate classical mechanics to arbitrary precision, given enough time and memory, I'm inclined to say no.

Finally, are your physical systems easier to work with mathematically? The answer seems like a pretty solid "no", given how much calculus is involved in classical mechanics, compared to the simple state-machine-plus-memory of a Turing machine.

So while you could in theory use physical systems to define computability, there doesn't seem to be an advantage to doing it this way.


NPC PROBLEM minimum sum of vertex coloring

We will reduce from 3COL, which is the following problem: Given a graph, is it 3-colorable?

Given a graph $G=(V,E)$, we construct a new graph $G'$ on $V \times \{1,2,3\}$, whose edges are
$$
\{((i,a),(j,a)) \mid (i,j) \in E, a \in [3]\} \cup \{((i,a),(i,b)) \mid i \in V, 1 \leq a < b \leq 3 \}.
$$
In words, we take three copies of $G$, and connect all copies of the same vertex.

If $G$ is 3-colorable then $G'$ can be 3-colored: given a 3-coloring $\chi$ of $V$, color $(i,a)$ with the color $\chi(i) + a \bmod 3$. The sum of the colors is $6|V|$.

Conversely, suppose that $G'$ has a coloring $\chi'$ whose sum is at most $6|V|$. Note that the three copies of each vertex $(i,1),(i,2),(i,3)$ must be assigned different colors, which sum to at least $6$. Therefore $\sigma \chi' \geq 6|V|$ for any coloring $\chi'$, and $\sigma \chi' = 6|V|$ iff $\chi'$ is a 3-coloring. Considering one of the copies of $G$, we see that $G$ is 3-colorable.


Minimum number of states in DFA accepting strings where the numbers of a and b are divisible by X and Y respectively?

I think the minimum number of states is $X\cdot Y$.  In particular, for $X=6$ and $Y=8$, I think 48 states are required.

One can prove this using Myhill-Nerode.  The equivalence class (in Myhill-Nerode) of string $s$ is uniquely determined by the pair $\langle n_a(s) \bmod X, n_b(s) \bmod Y \rangle$, where $n_a(s)$ counts the number of $a$'s in $s$, and $n_b(s)$ the number of $b$'s.  Two different equivalence classes $\langle i,j \rangle$, $\langle i',j' \rangle$ can be separated by the suffix $a^{X-i} b^{Y-j}$, since that'll take the former to an accepting state and the latter to a non-accepting state (if $i \ne i'$ or $j \ne j'$).  This gives us $X \cdot Y$ different equivalence classes, so any DFA accepting this language must have at least $X \cdot Y$ states.

Are you sure you can do it in 15 states, for $X=6$ and $Y=8$?  Is it possible you might have made a mistake somewhere in your DFA?


You're confusing "or" with concatenation.  Also, In computer science, a string matching a regular expression means that the whole string matches whereas regular expressions used in computer software usually just require some part of the string to match the expression.

A string matches $a^+$ if the whole string is composed of $a$s and nothing else, and there's at least one $a$.  A string matches $bcd^*$ if it consists of a $b$ followed by a $c$ followed by zero or more $d$s and nothing else.

A string matches $a^++bcd^*$ if it matches $a^+$ or it matches $bcd^*$ or if it matches both. However, it's not possible to match both: a string can't be composed entirely of $a$s and also begin with a $b$ and a $c$.

In particular, $aabcdd$ doesn't match $a^++bcd^*$ because it doesn't match $a^+$ (it contains characters that aren't $a$) or match $bcd^*$ (it doesn't even begin with $b$).  However, $aabcdd$ does match $a^+bcd^*$, which is the concatenation of $a^+$ and $bcd^*$.  $bcddaa$ matches neither $a^++bcd^*$ nor $a^+bcd^*$.


CSMA/CD with binary exponential backoff: Do both back off or just the loser?

You are right.  This does seem like an undesirable consequence of the CSMA-CD protocol.

I suspect this behavior was selected because it is implementable, and because it is not so easy to come up with an alternative that is simple and avoids this problem.

Recall, the only thing that is observable to B when it tries to send is whether that send was successful or a collision occurred.  B can't see anything about whether it "wins" or "loses"; it has no visibility of the other parties.  It doesn't know that A is also trying to send at the same time.  If B tries to send and succeeds, then B doesn't know whether that's because no one else wanted to send; or A wanted to send and previously "won" (already finished sending); or A wants to send but has "lost" (hasn't sent yet and has a backoff time that is still in the future) -- B has no way to distinguish between those cases.

It sounds like one of your alternative proposals is that B should give up permanently as soon as it is involved in a two consecutive collisions.  That doesn't seem to make sense to me.  When B gives up permanently, that means that it just powers down and never sends on the network again?  You can't have permanent disconnection -- that wouldn't be useful.  There has to be some point at B is going to try to send something again, so it's just a question of what that condition is.

It sounds like another of your proposals is that if B collides with A, and A gets to send first, then B should wait until A is finished.  That's harder to implement, and I'm not sure it has much benefit for B (B is still stuck waiting).  Why is it hard to implement?  It's hard to implement, because it's not clear how B would know when A is "done" transmitting.  It's not even clear what "done" means.  Even A won't know when it is done; A doesn't necessarily know what other packets it might want to send in the near future.  So now we get into some design space where we try to figure out what we mean by "done", and how B would know when A is done (maybe it's that A hasn't sent anything in the last 20ms?).  It's not enough to have A declare how much more it currently has to send as soon as it succeeds on a retransmission attempt and then require B to wait until that much has been sent, because what if after A finishes sending that much, A discovers it has more that it wants to send?  (Presumably, there's some application running on A that periodically wants to send stuff.  A's ethernet card can't predict what future sends the application will want to do.  Maybe the application will end up continuously trying to send packets, one after another, rapid-fire.)  If A tries to send some new message as soon as it finishes the previous one, you'll be back to the same scenario where A is more likely to win, so this doesn't eliminate the problem.

Or, if you were proposing that each PC remembers who won the last time and you alternate, that is also problematic, for a different reason.  It doesn't scale well to more than two PCs on the same network.

The standard protocol is memoryless; it doesn't require keeping track of past history.  This makes it simple, scalable, and reasonably efficient in many scenarios.


How to determine if this problem is decidable?

As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.


Type inference in compiler is context sensitive?

The context that is needed tells us the types of known variables. Suppose We want to infer the type of

if b or 2 = x then a else b

To make sense of this we need to

Check that the type of b is bool
That the type of x is numeric
That a and b have the same type.

To answer these three questions, we look up information about variables in a typing context, which is a mapping from variables to their types. Furthermore, the result is context-sensitive, as the type of the whole expression is the type of a (and b), which is given by the information in the context.

Now you are also mentioning grammars. These are not really relevant here, because we are talking about a stage of compilation which comes after parsing. I think you just got confused by the word "context" being used outside of the subject of grammars. Or you are reading a very strange book. By the way, there is a reason scientists want other scientists to give precise references to their sources. So instead of saying "I read a compiler book", you should have given the author and the title. Now I am just guessing.


How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

This is an $O(n\log n)$ solution. An $O(n)$ solution pointed out by Willard Zhan is appended at the last of this answer.

$O(n\log n)$ solution

For convience, denote $f(i,j)=(h[j]-h[i])(j-i)$.

Define $l_1=1$, and $l_i$ be the smallest index such that $l_i>l_{i-1}$ and $h[l_i]<h[l_{i-1}]$. Similarly, define $r_1=n$, and $r_i$ be the largest index such that $r_i<r_{i-1}$ and $h[r_i]>h[r_{i-1}]$. The sequences $l_1,l_2,...$ and $r_1,r_2,\ldots$ are easy to compute in $O(n)$ time.

The case where there are no $i<j$ such that $h[i]< h[j]$ (i.e. $f(i,j)>0$) is trivial. We now focus on non-trivial cases. In such cases, to find the solution, we only need to consider such pairs.

For each $i<j$ such that $h[i]<h[j]$, let $u$ be the largest index such that $l_u\le i$, and $v$ be the smallest index such that $r_v\ge j$, then $h[l_u]\le h[i]$ (otherwise $l_{u+1}\le i$ by definition of $l_{u+1}$, thus contradicts to the definition of $u$), and similarly $h[r_v]\ge h[j]$. Hence
$$(h[r_v]-h[l_u])(r_v-l_u)\ge(h[j]-h[i])(r_v-l_u)\ge(h[j]-h[i])(j-i).$$
This means we only need to consider pairs $(l_u,r_v)$ where $l_u<r_v$.

Denote $v(u)=\arg\max_{v:\ l_u<r_v}f(l_u,r_v)$, we have the following lemma.

  A pair $(l_u,r_v)$ where $l_u<r_v$, and where there exists $u_0$ such that $u<u_0$ and $v<v(u_0)$ or such that $u>u_0$ and $v>v(u_0)$, cannot be a final optimum solution.

  Proof. According to the definition of $v(u_0)$, we have
  $$
(h[r_{v(u_0)}]-h[l_{u_0}])(r_{v(u_0)}-l_{u_0}) \ge (h[r_v]-h[l_{u_0}])(r_v-l_{u_0}),
$$
  or
  $$
(h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)}
\ge 0.
$$

  In the case where $u<u_0$ and $v<v(u_0)$, note $h[r_v]-h[r_{v(u_0)}]<0$ and $r_v-r_{v(u_0)}>0$, and also $l_u<l_{u_0}$ and $h[l_u]>h[l_{u_0}]$, we have
  $$
\begin{align*}
&(h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})\\
>\ &(h[r_v]-h[r_{v(u_0)}])l_{u_0}+h[l_{u_0}](r_v-r_{v(u_0)}).
\end{align*}
$$

  This means
  $$
(h[r_v]-h[r_{v(u_0)}])l_u+h[l_u](r_v-r_{v(u_0)})+h[r_{v(u_0)}]r_{v(u_0)}-h[r_v]r_{v(u_0)}
> 0,
$$
  or
  $$
(h[r_{v(u_0)}]-h[l_u])(r_{v(u_0)}-l_u) > (h[r_v]-h[l_u])(r_v-l_u).
$$

  So $(l_u,r_{v(u_0)})$ is a strictly better solution than $(l_u,r_v)$. Proof for the other case is similar. $\blacksquare$

We can compute $v(\ell/2)$ firstly where $\ell$ is the length of the sequence $l_1,l_2,\ldots$, then recursively compute the optimal solution $o_1$ among $(l_u,r_v)$'s for $u=1,\ldots,\ell/2-1$ and $v=v(\ell/2),v(\ell/2)+1,\ldots$, and the optimal solution $o_2$ among $(l_u,r_v)$'s for $u=\ell/2+1,\ell/2+2,\ldots$ and $v=1,\dots,v(\ell/2)$. Due to the lemma, the global optimum solution must come from $\{(l_{\ell/2},r_{v(\ell/2)}),o_1,o_2\}$.

$O(n)$ Solution

Let $f(l_u,r_v)=-\infty$ if $l_u\ge r_v$. The proof of the lemma also shows an important property: for $u>u_0$ and $v>v_0$, if $f(l_{u_0},r_{v_0})\ge f(l_{u_0},r_v)$, then $f(l_u,r_{v_0})>f(l_u,r_v)$. This means the matrix $M[x,y]:=-f(l_x,r_{c-y+1})$ is a totally monotone matrix where $c$ is the length of the sequence $r_1,r_2,\ldots$ (so $r_{c-y+1}$ means the $y$-th element from the end), then SMAWK algorithm can apply to find the minimum value of $M$, thus the maximum value of $f$.


Let $T(n)$ denote the number of noughts that are necessary to write down all numbers from $0$ to $n$ (included) in base $10$. On input $(n,m)$ ($m>0$), the number you are looking for is then $T(n)-T(m-1)$ (i.e. count the numbers of noughts that you write to go up to $n$, then subtract the ones that you used to go up to $m-1$. The remaining number is the number of noughts that you wrote from $m$ to $n$.), and on input $(n,0)$ the output is simply $T(n)$. It remains to compute the table $T(n)$ quickly enough.

We write $T(0)=1$, and then use the relation $T(n) = T(n-1) + \mathrm{Noughts}(n)$ for $n>0$, where $\mathrm{Noughts}(n)$ denotes the number of noughts needed to write $n$ in base $10$. Given $n$, one can compute all the values of $T$ up to $n$ in time $O(n\log n)$ (the function $\mathrm{Noughts}(n)$, that could be built by examining all the digits of $n$, takes time proportional to $\log n$). Then, for any $0\leq m\leq n$, one can give the output to the problem on $(n,m)$ in constant time!


The padding is there since the distribution of letters at the beginning and end of words is very different from their distribution inside words. To capture that, separate words with spaces and add trailing spaces on both sides: ' hello i am johnny '.


Approximate Subset Sum with negative numbers

I believe the issue is with the definition of approximation.

Let's assume that we want to find a subset that sums to $C=0$.  Then the approximate subset sum problem determines whether or not there is a subset within $(1-c)C$, which is just $0$.
Thus "approximate" subset sum is exactly subset sum if there are negative numbers (and thus can't be solved in polynomial time).

You can demand that the target value $C$ is nonzero, but this is insufficient---if $A$ is integral, then if $C = 1$ we can set $c = 1/2$ and again our algorithm is forced to obtain an exact answer.
In fact, $C$ must be more than polynomial to avoid a contradiction.
Thus, previous work has simply assumed a positive $A$, and we get a nice definition for what we want.

Note that if $A$ is positive, the interesting $C$ are very large, whereas with possibly-negative $A$ they may not be.  This is part of the reason that positive $A$ is a sufficient condition for interesting approximation algorithms.

On the other hand, positive $A$ is probably not quite necessary.  It is possible that one can limit $C$ and $A$ in such a way as to ensure that the problem is interesting even for possibly-negative $A$.  Looking at the reduction, it seems that $C >> NM$ may do the trick (if $M$ is the absolute value of the smallest negative number in $A$); particularly if $C$ is exponential in $N$, and $M$ is polynomial (in other words, the negative numbers of $A$ are all very small).  But at first glance, this seems to add complexity to the analysis without gaining much in return.  Also, more work would have to be done to make sure this matches the approximate subset sum definition correctly.

As for the reduction: that reduction as-is does not work well if the goal is $C = 0$.  Let's say, for example, that you start with a possibly-negative set $A = \{a_1,\ldots,a_N\}$, where the largest negative number is $\geq -M$, for a large positive $M$.  We want to find a subset that sums to 0.  Then, as per the reduction you cited, we construct $A' = \{a_1 + M,\ldots, a_N + M, M, \ldots, M\}$ with $N$ copies of $M$.  We want to find a subset that sums to $NM$.  This can trivially be accomplished by taking the $N$ copies of $M$.

Even if $C\neq 0$ this reduction doesn't work quite the way we would (probably) want.  We obtain a solution within $[(1-c)(NM + C),NM+C]$.  This may be significantly different than a solution within $[(1-c)C,C]$ for the original problem.  However, as noted above, if $C >> NM$ this is somewhat close to a $(1-c)$ approximation ratio.  We would need to be careful about solutions within $[C,NM+C]$, however.


Functional problem and verifying solutions

It appears that you are asking whether FP = FNP.  That is an open problem.  It is known that FP = FNP if and only if P = NP.  I suspect that most theoreticians expect that it's likely that P != NP, which would imply FP != FNP.  If FP != FNP, there exists a function problem whose solutions can be verified in polynomial time, but where you can't find a solution in polynomial time.  In particularly, any FNP-complete problem -- such as FSAT, say -- will have that property, if FP != FNP.  So, the FNP-complete problems are particularly good candidates for having the property you articulate.  See https://en.wikipedia.org/wiki/Function_problem for an overview.


how to calculate time complexity of non terminating loops

If the program runs forever, its running time is infinite.  So, if it always enters an infinite loop, its running time is infinite.

This is a degenerate case.  Normally we focus only on algorithms that are certain to terminate (but see footnote).

See also How to come up with the runtime of algorithms? and Is there a system behind the magic of algorithm analysis?.

Footnote: When studying randomized algorithms, this gets relaxed a bit, and we frequently look at algorithms that in principle could run forever if they keep getting an unlucky choice of random bits, but whose expected running time is finite.  However, if you're just starting with algorithms, it's likely that you are dealing with deterministic algorithms, not randomized algorithms, so this is unlikely to come up.


Perfect Hash Function: How does it cope with lookups outside the set of keys?

Given a set of keys, a “perfect” hash function is one that gives a different hash for each key. As soon as you try to apply it to a key outside that set, it is quite likely not “perfect” anymore.

Let’s say you are writing a compiler, and you found a”perfect” hash function that maps each reserved identifier of your programming language to a different hash code. And I give you a word that is not one of the reserved words of the language. If you apply your “perfect” hash function then the hash code is either not the hash code of a reserved word (you need to check for that case), or it may be the hash code of a reserved word ( you need to check for that as well). The advantage is that at most one check is needed.