What makes a common programming language non-context-sensitive but RE?

I think you are conflating syntax and semantics.

A formal language is RE if it is possible to recursively enumerate all valid "sentences" (read "complete programs"). Validity here effectively means only that a compiler could convert the program into an executable, without saying anything about what that executable does.

That has basically nothing to do with the semantics of the program. We could design a programming language which is arbitrarily difficult to parse, but whose semantics are simple enough that the generated executable is guaranteed to be a complete function. (Removing all looping constructs is a good start.)

On the other hand, we could design a language which is trivial to parse, as are most stack languages, but whose semantics are effectively Turing complete (aside from the finiteness of memory in a physical realization of a processor.)


Pumping Lemma: Is language with equal number of "aa" and "bb" regular?

Your intuition is correct: regular languages can't count.  Indeed, a quick way to prove that $L$ isn't regular is to observe that $L\cap \{a^mb^n\mid m,n\geq 0\} = L'\cup\{a,b\}$. Since the intersection of any two regular langauges is regular, and $\{a^mb^n\mid m,n\geq 0\}$ is certainly regular, it must be that $L$ is not – because if it was regular, then its intersection with $\{a^mb^n\mid m,n\geq 0\}$ would have to be regular, and it isn't.

To prove with the pumping lemma, you need to show that, for every $p>0$, there is a string $s$ of length at least $p$ such that every way of writing $s=xyz$ with $|y|\geq 1$ and $|xy|\leq p$ has $xy^nz\notin L$ for some $n\geq 0$. (I originally wrote "just need to show" but deleted "just" because the statement that follows is such a mouthful!)

Your string $s$ works just fine.  If we rewrite it in the required form $s=xyz$, the fact that $|xy|\leq p$ means that $x=a^k$, $y=a^\ell$, with $1\leq\ell\leq p$ and $0\leq k\leq p-\ell$.  And $z$ is the rest of the string.  But, now, for any $n\neq 1$, we have
\begin{align*}
  xy^nz &= a^ka^{n\ell}a^{p-k-\ell}(aa)^pb^p(bb)^p\\
        &= a^{3p+(n-1)\ell}b^{3p}\,,
\end{align*}
and this string is not in $L$, since the number of $a$s at the front is different from the number of $b$s at the back, so the number of $aa$ substrings is different from the number of $bb$s.

Insofar as that proof works, there's no problem with your choice of $s$.  But, if you read through the proof, you'll see that there would have been a bit less writing if you'd just chosen $a^pb^p$. The point is that, when something in the $a^p$ part gets "pumped", it breaks the required property of having the same number of $aa$s as $bb$s.

It's hard to give general advice, because proof is a creative act and you can't just follow recipes. The general scheme is to pick a string where repeating any sequence of characters from the first $p$ will break the property that defines the language.


Is there an algorithm that given a PDA $M$ decides if there exists a string in $L(M)$ with a suitable decomposition?

In a context-free language $L$, by the Pumping Lemma, there exists a $p > 0$ such that every $w \in L$ such that $|w| \ge p$ admits a decomposition $w = uvxyz$ such that $uv^ixy^iz \in L$ for all $i \geq 0$.

If $L$ is infinite, it has words of length $\ge p$, and you can pick any of them. If $L$ is finite then no word satisfies the condition (this is not a contradiction with the pumping lemma, because the pumping lemma gives a length $p$ which is more than the length of any of the words in $L$).

It is decidable if a context-free grammar generates an infinite language (see e.g. Is it decidable whether a given context free grammar generates an infinite number of strings?).

Therefore the algorithm is

  On input $\langle M \rangle$, where $M$ is a PDA

  Convert $\langle M \rangle$ to the description of an equivalent CFG $\langle G \rangle $
  Check if $L(G)$ is infinite
  If yes, then answer yes else answer no


Prove that the equal-length concatenation of regular languages is context free

To expand a bit on @babou's comment, let $M_A$ and $M_B$ be the FAs for $A, B$ respectively. Make a PDA that acts like this:

(1) repeat
      read the input, using MAs transition rules.
      For each character read, push a marker on the stack.
    until MA enters a final state or no input remains
(2) if no input remains and MA is in a final state, go to (3)
    else if no input remains and MA is in a non-final state, halt and reject
    else nondeterministically go to (1) and (3) [guessing that we're done with the first half]
(3) repeat
      run the PDA on any remaining input, using MBs transition rules
      For each character read, pop the stack
    until the stack is empty or no input remains
(4) if MB is in an accept state, no input remains, and the stack is empty, halt and accept
    else halt and reject

(I apologize in advance for any missing details/programming errors, but the intent, I hope, is clear: process the first part of the input, guess that we're in the middle and process the second part.)


Proving whether an input sequence is in a given RE language

A language is recursively enumerable if there exists a Turing machine that:

halts and says "yes" whenever its input is in the language;
either halts and says "no" or just doesn't halt whenever its input is not in the language.

The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given the code of a Turing machine which accepts some language) and a string, can determine whether the string is in the language or not. In general, all you can do is run the Turing machine and see if it accepts its input. However, if it seems to be taking a long time to run then, in general, there's no way of figuring out if it's in an infinite loop, so even this doesn't actually work.

However, that doesn't mean that you can never tell whether a particular machine will have certain behaviour.  For example, it's easy to tell that the machine

IF the first character of the input is 0 THEN accept
ELSE [do something complicated]

will accept any string that begins with $0$.  More sophisticated analytic techniques will allow you to prove that more complicated machines do or do not accept certain inputs.  However, what the lack of a general algorithm means is that, whatever analytic techniques you develop, there will be some machines and some inputs (in fact, infinitely many of them) where your techniques fail. In those cases, your only options are to develop even more advanced techniques (which still won't work in all cases) or to give up and just run the machine.


If you go to the empty leaf from the root in the pattern [Right, Left], you get to an empty leaf encountering 1 black node. If you go [Right, Right, Left] or [Right, Right, Right], you get to an empty leaf hitting 2 black nodes. This is not allowed in a Red Black Tree because by definition a path from root to an empty leaf should contain the same amount of black nodes as every other path from root to an empty leaf.

The other important thing to know is that NULL nodes (leaves) aren't drawn; only the internal nodes are drawn.  By convention, all leaves (NULL nodes) automatically are considered to be colored black.


Asymptotic analysis for quicksort on special case

A more correct recurrence is
$$T(n,m) = \begin{cases} T(n-m,m) + \Theta(m^2+n) & m \leq n/2, \\ \Theta(m^2+n) & m > n/2. \end{cases}$$
In order to solve the recurrence, let us assume that the hidden constants are all $1$, and that $n = km$. Then
$$
\begin{align*}
T(km,m) &= T((k-1)m,m) + m^2 + km \\
&= T((k-2)m,m) + 2m^2 + km + (k-1)m \\
&= \cdots \\
&= T(m,m) + (k-1)m^2 + km + \cdots + 2m \\
&= km^2 + km + \cdots + m \\
&= km^2 + \frac{1}{2}k(k-1)m \\
&= \Theta(km^2 + k^2m).
\end{align*}
$$
Substituting $k = n/m$ and hoping for the best, we get
$$ T(n,m) = \Theta(nm + n^2/m). $$
This quantity ranges from $\Theta(n^{3/2})$ to $\Theta(n^2)$.


Using Myhill-Nerode to prove that language is not regular

Consider two words $u_i = b^i aa, u_j = b^j aa \in \{a, b\}^\ast$ with $i < j$. We have that $u_i \not\sim_L u_j$ because if you concatenate the word $v = b^{i+2}$ to both words we obtain
$$u_i \cdot v = b^i aa \cdot b^{i+2} \in L \text{, but } u_j \cdot v = b^j aa \cdot b^{i+2} \notin L.$$
Thus, $v$ separates $u_i$ and $u_j$ for $L$. Since we can find infinitely many $i, j \in \mathbb{N}$ with $i < j$ we have also infinitely many Myhill-Nerode-equivalence classes.


Schedule two trains whose tracks overlap so they don't crash

A related and well studied area is threading/multiprocessing. Your initial solution is a simple lock; the critical section of tracks can only be used by one train at a time. To extend this while avoiding deadlocks (two trains waiting in each other) or starvation (a train waits forever), you would want to use some more sophisticated locking mechanism and scheduler.


Global indexing of shared nodes in parallel

Assume you have an array (random access sequence) of tuples <q, j, x, y, first, k_tmp, k> where q is the (integer) identifier of a quadrilateral, j is the local index (within the quadrilateral) of a node, x, y are the coordinates of a node contained in quadrilateral q, and first, and k_tmp, and k are fields to be filled in later.

sort the array lexicographically on x, then y, then q (i.e. all the array elements corresponding to the node at x,y will be adjacent in increasing order by q).  The sort can be done in parallel.  See for example Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha, "A comparison of sorting algorithms for the connection machine CM-2", Proc ACM Symp Parallel Alg and Arch, SPAA-3:3-16, 1991, or Arpaci-Duesseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson, "High-Performance Sorting on Networks of Workstations", SIGMOD Conference, 1997:243-254.
foreach element e of the array, in parallel:

array[e].first = if (array[e].x = array[e-1].x and array[e].y = array[e-1].y) then 0 else 1

resort the array lexicographically on q, and j.
calculate array[].k_tmp as the parallel prefix sum (sometimes called a "scan" operation) of the array[].first fields.  A good paper on parallel prefix sum is Chatterjee, Blelloch, and Zagha, "Scan Primitives for Vector Computers," Proceeedings of Supercomputing, 1990:666-675.
resort the array lexicographically on x and y and q.
calculate array[].k as the segmented copy scan of array[].k_tmp using array[].first as the bit vector to determine the segment boundaries (see Section 3.2 of the paper by Chatterjee, Blelloch, and Zagha).  Briefly: The segmented copy scan will use array[].k_tmp if array[].first is 1, else it will use the array[].k_tmp from the first element to the left where array[].first is 1.
you can now resort the array lexicographically on q and j and the k field should be correct for each array element.

The fact that we sorted the array back and forth and back and forth seems to indicate that we should probably, in practice, use two data structures (one sorted on q and j and one sorted on x and y) with pointers back and forth between them.


Does Turing Machine divergence depend on the input?

No. It is very easy to reduce $A_{TM}=\{(M,w): M$ accepts $w\}$ to the complement of the problem you describe: given input $(M,w)$, output a machine $M'$ that simulates $M(w)$. If $M$ accepts $w$ then $M'$ halts and accepts. Otherwise, $M'$ goes into an infinite loop (either if $M$ loops on $w$, or manually if $M$ rejects $w$).

Now, if $M$ accepts $w$, then $M'$ does not diverge on every input, and otherwise it does.


NP Complete Proof - Polynomial Reduction

Probably you can get your answer from here: Reducing independent set to triangle-free subgraph
Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.


How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?

You have to be careful here, since the answer depends on the particular log function you use. As Lieuwe noted if $\log$ in this context means $\log_{10}$ then $10^{\log n}=n$ and certainly $n$ "ranks before" $3n^2$, under any reasonable interpretation of "ranks before". However, if we have a different base for the logarithm, that might not be the case.

It's not hard to show that $10^{\log_b n}=n^{log_b{10}}$ (take the log of both sides) and so $10^{\log_b{n}}$ will be asymptotically larger than $n^2$ as long as $\log_b10>2$, i.e., when $b^2<10$, so when you use logs to base $b$ with, say, $b=3$ you'll have $10^{\log_b n}$ "ranks after" $3n^2$.


Where is pivoting done in the Crout decomposition algorithm?

That algorithm doesn't do any pivoting. It requires non-zero elements on the diagonal of A to work, otherwise you divide by zero. Note the check:

if (L[j][j] == 0) {
    printf("det(L) close to 0!\n Can't divide by 0...\n");
    exit(EXIT_FAILURE);
}


Disruption refers to the phenomenon in which a schema represented by a particular parent is not passed down into its offspring.

That bit about schemata is important -- disruption isn't really defined except for in terms of schemata. Briefly, a schema is a ternary string containing 0s, 1s, and *s (don't-cares), whereas individuals are only binary (no *s). Each individual is a representative of $2^n$ schemata. For example,

10010011

is an instance of all of the following schemata:

1*******
*00**01*
1******1
...

The idea Holland had was that, for example, if good solutions tended to have a 1 in the leading bit, then the proportion of the population that is an instance of the schema

1*******

would increase over time according to a certain inequality. That's the schema theorem. Now, what if instead of that simple schema being more fit than average, we had a more complicated one, like

1*****0*

That is, suppose that individuals matching that pattern are above average in fitness. According to Holland, the GA should work by increasing the proportion of the population that conforms to that pattern over time.

But look at what happens with one-point crossover. It's going to pick a crossover point somewhere along the string and split it around that point. If both parents are instances of the schema, then both children will be as well. But if either parent is not an instance of the schema, then we have a probability that the children won't inherit that pattern. That failure to inherit the pattern is called disruption. Holland would have said that this was very bad. The presence of that schema in the population is evidence that it's good, and crossover is wrecking it. The modern understanding is much more nuanced than that, but that's the rationale behind considering disruption as a concept at least.

So you question asks whether schemata that have bits that are close together are more or less likely to be disrupted. We should really be more precise -- it's not whether any old bits are close together that matters. It's the distance between the first and last non-* bit that matters (called the defining length). The greater that distance, the more likely we'll put a crossover point in between them, and therefore the more likely we are to disrupt the schema.


Your problem is essentially a $NP^{coNP}$ problem. If $P=NP$ then the polynomial hierarchy collapses and your problem is in $P$.

If $P=NP=coNP$ then we can check in polynomial time whether a solution $S_0$ is valid (using a polynomial-time algorithm to check each property, which exists because $coNP=P$). Thus, the problem is in $NP$, and thus, in $P$.


Does data entropy depend on the arrangement of the characters in a file?

Entropy is a property of the source of the data, i.e., of the distribution that the data is drawn from -- not a property of the particular file.  You can't calculate the entropy given a single file.  Instead, you need to know the distribution that file came from.  Or, to put it another way, the entropy is a measure of the process used to generate the particular file, not a measure of one particular file you happened to get from that process; and observing one  output from that process isn't enough to let you calculate the entropy of the process.  So, the question isn't well-formed.

You might be thinking of forming the empirical distribution of characters, then assuming the file came from a memoryless iid source (where each character was drawn independently according to that distribution), and then calculating the entropy under that assumption.  But that assumption doesn't hold for your bigger file, so this isn't a valid way of calculating the actual entropy of the process that was used to generate the bigger file.

To learn more: How to practically measure entropy of a file?, https://en.wikipedia.org/wiki/Entropy_(information_theory).


Find a vertex that is equidistant to a set of vertices?

Starting with $i=0$ and going up, for every $f \in F$ consider a subset of $V$ containing points at the exact distance of $i$ from $f$. Look at intersection of all of those subsets. If you're lucky, as $i$ grows, you'll find this intersection non empty - those will be the solutions.

For the actual implementation, I'd suggest removing vertices closer than $i$ to any of $f$ at every iteration. To find intersection you could simply increment a counter on a vertex, whenever it is included in one of the subsets. When for some vertex v.count = |F|, you are done.

One way to implement it could be as follows

For each v in V, v.count = 0.

For each f in F,
    f.subset = {f},
    f.count = f.count + 1
    if f.count = |F|, return f.

While V is not empty,
    For each f in F,
        old_subset = f.subset,
        f.subset = the set of neighbors of vertices in old_subset,
                   (consider only vertices in V and not in old_subset)

        For each v in old_subset,
            if v.count == 1, remove v from V,
            else v.count = v.count - 1

        For each s in f.subset,
            s.count = s.count + 1
            if s.count = |F|, return s.

return "no such vertex"

While the running time of the above algorithm depends a lot on chosen graph representation, it can be as good as $O(|V| + |E|)$ assuming that you can find the neighbors of a vertex $v$ and remove it from the graph in $O(\deg(v))$ time. In that case, because $\sum_{v \in V} \deg(v) = 2 |E|$, most of the cost of the algorithm is covered by the $|E|$ term.


For simpler language $\{1^n0^n\ | \ n > 0\}$, we can write grammar as
$S \rightarrow 1S0\ |\ 10$.

Now we can replace the non-terminal $S$ by $A$. And write context free grammar for the language in the question. $A$ is in the center of $0^m$ and $1^m$. Also remember $m,n > 0$.

$A \rightarrow 1A0 \ | \ 10$
$S \rightarrow 0S1 \ | \ 0A1$


Filling a string with wildcards with minimum cost

I think I've found a solution (thanks, Yuval Filmus and D.W.!). It consists of 2 major steps:

1) Generate a valid string at minimal steps. You start traversing a string from left to right, moving by 1 character each time. I do this recursively. At each recursion level, you iterate a substring in a range [current_pos, block_size] and continue recursion from each character. By doing this you are exploring possibilities to print, let's say, 3 characters and to continue from any of them without any costs. During recursion, you explore all input characters: X, Y, Z, so each time you generate 3 branches. When you hit an end of a string, corresponding recursion depth equals to a number of used blocks.

2) Searching for an optimal block_size. Using binary search over a block's length to find the optimal block size could be tempting, but it does not work in general. The reason is that depending on costs of block's preparation/usage, cost function could be non-monotonic. Thus, it looks like you have to use linear search.


Optimization version of decision problems

As already stated in the comments, it depends on the definitions, as usual. My attempt to answer this needs quite a few definitions, so this will be another example of my inability to give concise answers.

Definition: An optimization problem is a tuple $(X,F,Z,\odot)$ with

$X$ the set of suitably encoded (strings) instances or inputs.
$F$ is a function that maps each instance $x\in X$ to a set $F(x)$ of feasible solutions of $x$.
$Z$ is the objective function that maps each pair $(x, y)$, where $x \in X$ and $y\in F(x)$, to a real number $Z(x, y)$ called the value of $y$.
$\odot$ is the optimization direction, either $\min$ or $\max$.

Definition: An optimal solution of an instance $x\in X$ of an optimization problem $P_O$ is a feasible solution $y\in F(x)$ for which $Z(x, y)=\odot\{Z(x, y')\mid y'\in F(x)\}$. The value of an optimal solution is denoted with $Opt(x)$ and called the optimum.
Definition: The evaluation problem, denoted $P_E$, corresponding to the optimization problem $P_O$ is the following: Given an instance $x\in X$, compute $Opt(x)$ if $x$ has an optimal solution and output “no optimal solution” otherwise.
Note that this just asks for the value of the optimal solution not the whole solution itself with all its details.
Definition: The decision problem, denoted $P_D$ corresponding to the optimization problem $P_O$ is the following: Given a pair $(x, k)$, where $x\in X$ and $k\in\mathbb{Q}$, decide whether $x$ has a feasible solution $y$ such that $Z(x, y)\le k$ if $\odot=\min$ and such that $Z(x, y)\ge k$ if $\odot=\max$.
A first observation is now that $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$. The proof is not difficult and omitted here.
Now intuitively $P_E$ and $P_D$ corresponding to $P_O$ are not more difficult than $P_O$ itself. To express this feeling formally (thereby defining what equivalent is supposed to mean) we will use reductions.
Recall that a language $L_1$ is polynomial-time reducible to another language $L_2$ if there is a function $f$, computable in polynomial time, such that for all words $x$, $x\in L_1\Leftrightarrow f(x)\in L_2$. This kind of reducibility is known as Karp or many-to-one reducibility, and if $L_1$  is reducible to $L_2$ in this manner, we express this by writing $L_1\le_m L_2$. This is a central concept in the definition of NP-completness.
Unfortunately, many-to-one reductions go between languages and it is not clear how to employ them in the context of optimization problems. Therefore we need to consider a different kind of reducibility, Turing reducibility. First we need this:
Definition: An oracle for a problem $P$ is a (hypothetical) subroutine that can solve instances of $P$ in constant time.
Definition: A problem $P_1$ is polynomial-time Turing-reducible to a problem $P_2$, written $P_1\le_T P_2$, if instances of $P_1$ can be solved in polynomial time by an algorithm with access to an oracle for $P_2$.
Informally, just as with $\le_m$, the relation $P_1\le_T P_2$ expresses, that $P_1$ is no more difficult than $P_2$. It is also easy to see that if $P_2$ can be solved in polynomial time, so can $P_1$. Again $\le_T$ is a transitive relation. The following fact is obvious:
Let $P_O\in \mathrm{NPO}$, then $P_D\le_T P_E\le_T P_O$.
Because given the full solution, computing its value and deciding whether it meets the bound $k$ is simple.
Definition: If for two problems $P_1$ and $P_2$ both relations $P_1\le_T P_2$, $P_2\le P_1$ hold, we write $P_1\equiv_T P_2$; our notion of equivalence.
We are now ready to proof that $P_D\equiv_T P_E$ given the corresponding optimization problem is $P_O\in \mathrm{NPO}$ and $Z$ is integer valued. We have to show that $P_E \le_T P_D$ holds. We can determine $\odot\{Z(x,y)\mid y\in F(x)\}$ with a binary search usign the orcale for $P_D$. The definition of $\mathrm{NPO}$ ensures that $|Z(x, y)|\le 2^{q(|x|)}$ for some polynomial $q$, so the number of steps in the binary search is polynomial in $|x|$. $\Box$
For an optimization problem $P_O$ the relation to $P_E$ is less clear. In many concrete cases, one can show directly that $P_D\equiv_T P_E \equiv_T P_O$. To prove that this holds generally within the framework given here we need an additional assumption.
First we need to extend $\le_m$ from pairs of languages to pairs of the corresponding  decision problems. Then it is easy to see that $\le_T$ is more general than $\le_m$.
Let $P$ and $P'$ be decision problems; then $P\le_m P' \Rightarrow P\le_T P'$. This holds because a many-to-one reduction can be interpreted as making use of an oracle in a very restricted way: The oracle is called once, at the very end, and its result is also returned as the overall result. $\Box$
Now we are ready for the finale:
Let $P_O\in \mathrm{NPO}$ and suppose $Z$ is integer-valued and that $P_D$ is NP-complete, then $$P_D\equiv_T P_E \equiv_T P_O.$$ With the previous observations it remains to show $P_O\le_T P_E$. To do this we will exhibit a problem $P_O'\in \mathrm{NPO}$ such that $P_O\le_T P_E'$. Then we have $$P_O\le_T P_E' \le_T P_D'\le_T P_D\le_T P_E.$$ The second and third $\le_T$ hold because of the equivalence of the decision and evaluation version proofed earlier. The third $\le_T$ follows from the NP-completness of $P_D$ and the two facts mentioned before, namely $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$ and $P\le_m P_O' \Rightarrow P\le_T P_O'$.
Now the details: Assume that the feasible solutions of $P_O$ are encoded using an alphabet $\Sigma$ equipped with a total order. Let $w_0, w_1, \ldots$ be the words from $\Sigma^*$ listed in order of nondecreasing length and lexicographic order within the blocks of words with common length. (Thus $w_0$ is the empty word.)  For all $y\in\Sigma^*$ let $\sigma(y)$ denote the unique integer $i$ such that $y=w_i$. Both $\sigma$ and $\sigma^{-1}$ can be computed in polynomial time. Let $q$ be a polynomial such that for all $x\in X$ and all $y\in F(x)$ we have $\sigma(y)<2^{q(|x|)}$.
Now the problem $P_O'$ is identical to $P_O$ except for a modified objective function $Z'$. For $x\in X$ and $y\in F(x)$ we take $Z'(x, y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$.  $Z'$ is computable in polynomial time thus $P_O'\in \mathrm{NPO}$.
To show that $P_O\le_T P_E'$ we observe that $x$ is feasible for $P_O$ if and only if it is feasible for $P_E'$. We can assume that this is the case, since the opposite case is trivial to handle.
The substituion of $Z'$ for $Z$ is monotonic in the sense that for all $y_1, y_2\in F(x)$, if $Z(x, y_1)<Z(x, y_2)$ then $Z'(x, y_1)<Z'(x, y_2)$. This implies that every optimal solution for $x$ in $P_O'$ is an optimal solution of $x$ in $P_O$. Thus our task reduces to the computation of an optimal solution $y$ of $x$ in $P_O'$.
Querying the oracle for $P_E'$ we can get the value of $Z'(x,y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$. Forming the remainder of this number modulo $2^{q(|x|)}$ yields $\sigma(y)$ from which $y$ can be computed in polynomial time.


Simple example: 2-approximation for vertex cover

Hint:

Prove the stronger claim that if $M$ is any matching, then any vertex cover must contain at least $|M|$ vertices.
Conversely, if $M$ is any maximal matching (a matching which cannot be extended), then the $2|M|$ vertices in $M$ form a vertex cover.
Show that the greedy algorithm that you describe constructs a maximal matching.
Conclude that your algorithm (modified so that it outputs a set of vertices rather than a set of edges) is a 2-approximation for minimum vertex cover.
Consider the complete bipartite graph $K_{n,n}$. What is its minimum vertex cover? What vertex cover does your algorithm produce?


When you compute the topological ordering, you usually select one node with no predecessor and remove it from the graph. Instead you can scan the whole list of vertices and select all source vertices and remove them at once, only then you update the degree of the remaining vertices. The groups of vertices you remove together represent tasks that can be executed in parallel.

Note: As it stands now, all your tasks take the same amount of time. In reality however tasks started at the same time aren't finished at the same time. You maybe want to have a look into the Program evaluation and review technique


What is the sqrt(n)-approximation algorithm for set packing problem

See Viggo Kann's page on set packing. Viggo mentions two $\sqrt{|U|}$ algorithms:

Unweighted case: Halldórsson, M. M., Kratochvíl, J., and Telle, J. A. (1998),
"Independent sets with domination constraints",
Proc. 25th Int. Colloquium on Automata, Languages and Programming, Lecture Notes in Comput. Sci. 1443, Springer-Verlag, 176-185.
Weighted case: Halldórsson, M. M. (1999a),
"Approximations of weighted independent set and hereditary subset problems",
Proc. 5th Ann. Int. Conf. on Computing and Combinatorics, Lecture Notes in Comput. Sci., Springer-Verlag, 261-270.

I found this link on the first page of the Google search set packing approximation algorithm. I suggest that next time you spend some quality time with your favorite search engine, looking at all links in the first few pages.


Is it possible to implement a Neural Network using a graph data structure?

Many implementations you can find out in the web are done on matrices (MATLAB for instance) since it provides a compact notation. Haykin's textbook on neural networks takes this approach. Matrices also provide a simple translation to hardware design (FPGA, ASIC, etc.). They are also more often implemented on the FPU.

If you implement a neural network in an object oriented manner, you are effectively doing what your question asks: implementing a neural network on a graph. Your neurons are then objects that have relations with each others. There are a few books that take that approach. One I can think of is an undergrad level book by Renard called Réseaux de neurones (sorry, only in French).


Time complexity version of the Church-Turing Thesis

Short answer

The thesis that all reasonable models of computation are polynomially-equivalent — that is, in the amount of work that they perform; whether sequentially or in parallel, albeit different by some polynomial scaling factor — is generally known as the Strong Church-Turing thesis or the Extended Church-Turing Thesis.

Details

The idea that all reasonable models of computation are equivalent up to polynomial factors is most important to two groups of researchers:

Those working in quantum computation (who most often believe that it is false, or at least that if it were true that it would have very important implications for physics), and
Those who are specifically skeptical towards the feasibility of quantum computers (who believe that the thesis is true, typically because quantum computers are the only thing which has come close to a 'reasonable' model of computation, and because the feel that quantum computers would somehow requires access to an unreasonable amount of information to carry out computations).

I started doing a bit of a literature search starting from Sid's link to the Computational Complexity blog entry above. That blog entry specifically concerned the Strong Church Turing Thesis, and asked whether anyone actually cared about such an "extended" version of the Church-Turing thesis before quantum computing came along.

It turns out that people have been trying to formulate this notion for a while however. It would seem that at the very least, the Strong Church-Turing Thesis arose naturally from concerns about what "reasonable computational models" could or could not achieve, in the context of sequential versus parallelized computing. There is both a "sequential" and "parallelized" computational thesis, which concern how different either sequential or parallelized models of computing can be with respect to computational power. Here are some quotations showing some of the history of the sequential thesis, which would be the one which quantum computing would be most naturally construed to violate.

  The belief that all reasonable sequential computers which will ever be dreamed of have polynomially related execution times is called the sequential computation thesis.

— Goldschlager, Lister. Computer science: a modern introduction. Prentice/Hall International, 1982 (p. 96).

  [The] sequential computation thesis [10] states that time on all "reasonable" sequential machine models is related by a polynomial.

— Parberry, Parallel speedup of sequential machines: a defense of parallel computation thesis. ACM SIGACT News 18 (pp. 54-67), 1986.

  "Reasonable" machines can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

— van Emde Boas, Machine Models and Simulations. Handbook of Theoretical Computer Science A, Elsevier, 1990.


Clarifiaction on the NP-hardness of k-SUM-variants

Yes in case of 3-sum problem they are equivalent. Let $P$ be the version where the three numbers have to be distinct and $P'$ the version where you can use the same number multiple times. The reduction $P'$ to $P$ is by solving the cases with overlapping in preprocessing (since both overlapping cases can be done in almost linear time).

The other direction is a bit more complicated. We will reduce $P$ to another variant $P''$ and from $P''$ to $P$. We start by defining $P''$: given three sets of integers $A,B,C$. Can we pick a number from each to sum to zero.

$P''$ to $P'$ is quite easy. Let $M$ be the largest number in all sets. Let $U := 3M + 1$ build the set $$S := \{a+U:a\in A\} \cup \{b + 2U: b\in B\} \cup \{c-3U:c\in C\}$$ as input to $P''$. Try to prove why the reduction is correct as an exercise.

Now the last reduction from $P$ to $P''$ is a bit more complicated. It is actually randomized. Fix a correct tripple in $S$. A random partition of $S := A\dot\cup B \dot \cup C$, we will have the numbers in the triple assigned to distinct sets with probability at least $2/3 \cdot 1/3 = 2/9$. By repeating a constant factor of $\log n$ you get a running time of $O(n\log n)$ reduction with high probability.


Minimizing a regular expression is PSPACE-hard, so there is no general method that is generally applicable and can be completed in a reasonable amount of time.  You'll need to inspect each individual situation on a case-by-case basis.

If you want to read about general methods, see https://cstheory.stackexchange.com/q/31630/5038 and https://cstheory.stackexchange.com/q/12361/5038.  CSTheory has a nice blog post with an overview of the field.  The alternative is to stare at that regular expression, understand very well what language it recognizes, and write down a shorter regexp.  You might be able to find some simplifications that work for that particular case, even though they are not general.


Backpropagation for 'Classification' Neural Network

As D.W. points out, please consult a textbook on neural networks, or Wikipedia. The answer to your question lies in the insight that neural networks do not inspect the cost function or algorithm used to compute it, but it is an empirical method. That is, you will have to play many games of Tic Tac Toe (or generate configurations at random, whichever), compute the cost function yourself, and then feed the configuration with its cost function to your neural network, which then does backpropagation, and repeat. Alternatively, you may collect a large batch of data and feed the batch to the neural network. Either way, the gradient of the network at a particular configuration is a value computed only from available data.

That said, and while most numerical algorithms have no well-defined derivatives, there are edge cases, for example the identity function $f(x) = x$, but most have no practical use. Then there are algorithms that estimate the derivative of a function such as the one you supplied form a large batch of data that a neural net can use to aid its search by improving its gradient estimate, but that will get you into some very deep waters. Deep waters, but fun waters, so consult a textbook if you want to know about that.


How to prove that the subset sum problem is polynomially reducible to the knapsack problem

The subset-sum problem is a pair $(S,k)$ and a question whether there exists $S' \subset S$ such that $\sum_{s \in S'} s = k$.
The knapsack problem is a tuple $(w,v,W, V)$ that is weights, values, the knapsack capacity and the target value, and a question can you pick such a set of items $\mathcal{I}$ such that:

$\sum_{i \in \mathcal{I}} w_i \leq W$
$\sum_{i \in \mathcal{I}} v_i \geq V$

Hint: Given an instance $(S,k)$ of subset-sum, is there a way to set the weights and values of our items in the knapsack, so that these inequalities turn into a single equality related somehow to $k$?


Do computers actually use carry-lookahead adders?

This is a straightforward question with a very complex answer.

First off, some background.

Real-world VLSI design is an extremely technical field which features a constantly-changing balance of tradeoffs. The time that a circuit takes to calculate an answer is rarely the only important factor. There's also power draw and physical area, plus a bunch of factors which reveal that the circuits you're designing are actually analogue (e.g. wire resistance, parasitic capacitance). All of these are important in a real circuit and may impact which design is chosen.

Secondly, you have to consider the entire life-cycle of a project. An adder which is appropriate for a VLSI realisation may not be appropriate for an FPGA realisation. If the design is going to go through a phase being tested on an FPGA... you get the picture.

Thirdly, not every adder is made equal. On a typical CPU, there are lots of adders hanging around which do different tasks; there are probably several integer ALUs, a floating point mantissa adder, an adder which does address calculation, an adder which calculates branch targets, and so on. That's not counting the carry-save adders that you find in modern multiplication units. Each has its own peculiarities and constraints.

Branch target calculation, for example, typically involves adding a small constant to a full word, which suggests a different adder design from one which adds two full words together. Similarly, floating point addition requires a post-addition rounding step which might take less than a cycle, so there's no reason why you couldn't steal the rest of the cycle to finish off the addition.

Lastly, and perhaps most importantly, the big players (e.g. Intel, AMD, NVIDIA) are fairly tight-lipped about low-level implementation details for obvious reasons, unless they think they can get a paper and/or patent out of it. Even then, you often can't be sure what they actually did without reverse-engineering.

Having said that, there are a few things we know.

The key thing you need to realise is that carry-lookahead methods are building blocks, and not necessarily methods in themselves. An analogy might be in order here.

If you think about algorithms classes, you probably learned a bunch of sorting algorithms such as quick sort, merge sort, insertion sort, and so on. In the real world, if sorting is a performance bottleneck, any decent engineer would think of these as primitive building blocks from which a "real" sort can be constructed.

The sort algorithm from the GNU C++ standard library, for example, uses quick sort, using insertion sort when the intervals get small enough. However, if after a few passes it looks like the quick sort partitioning has hit pathological behaviour, it falls back to heap sort. That's three different sort algorithms to make one industrial-strength sort.

The same is true of adder circuits. It is known, for example, that the Pentium 4 integer unit used a Han-Carlson adder, which is a mix of Kogge-Stone and Brent-Kung. (Han-Carlson is especially interesting, because it's a "sweet spot" in the tradeoff between propagation delay and die area which also being quite power-efficient.) It often pays to use a mix of several methods.

"Pure" carry-lookahead adders are still very much the norm in synthesised circuits (e.g. if you feed a Verilog "+" operator to Cadence or Synopsys), when it comes to hand design, modern high-end CPUs with their superscalar out-of-order execution engines seem to be moving towards a slightly different design for their integer units.

Speculative adders are circuits which have extremely low propagation delay, but only work correctly some of the time (95% of the time is typical), and it's possible to tell with very little logic whether the speculative adder returns the correct result or not. So the idea is to do a speculative addition and half of a carry-lookahead addition in parallel, in one cycle. If the speculative adder returned the correct answer, the instruction is done. Otherwise, stall the pipeline and do the other half of the accurate addition.

Because you know that the slow path will take two cycles, the designers could use a more space and power-efficient method even if it would be too slow for general use.


You are using Adjacency matrix representation, instead just maintain a list of pairs of friend (i.e. edge list) and iterate it once.


Hint for idea: Consider the subgraph $G'$ induced by the vertices in $V \setminus U$. Compute its MST $T'$. Then how should you attach the vertices in $U$ to $T'$?

Hint for implementation: To achieve $O(|E| \log |V|)$, you still run ordinary MST on the original graph $G$, but pay special attention to the vertices in $U$.


These complexity classes are not just defined by a machine model but also by the criteria about when a machine accepts a strings. So although $\mathsf{NP}$ and $\mathsf{coNP}$ can be defined using essentially the same underlining machine structure their accepting criteria are different. That is the main point you are missing.

In my experience, generally it is intuitively more clear for people to think about $\mathsf{NP}$ using its verifier-certificate definition and forget about the non-deterministic TM (which can be confusing).

We say a language $L$ is in $\mathsf{NP}$ if there is a polytime DTM with two inputs $V$ (think of $V$ as a certificate verifier) s.t. for all $x$,
$ x \in L$ iff there exists a polynomial size certificate $y$ s.t. $V$ accepts $(x,y)$.

In more intuitive terms, $\mathsf{NP}$ is the set of problems that given an instance and a polysize solution/certificate/proof for that instance, we can efficiently verify the correctness of the given solution.
E.g. given a graph and a list of vertices in it, it is possible in polynomial time to check if the list is a Hamiltonian path in the graph. Therefore Hamiltonian path problem is in $\mathsf{NP}$.

So in intuitive terms, $\mathsf{NP}$ is the set of problems that a given solution can be confirmed efficiently and $\mathsf{coNP}$ is the set of problems that a given solution can be refuted efficiently. For example, a refutation for a $TAUT$ instance is an assignment that makes the formula false.


An epsilon transition is simply a transition that doesn't consume any characters in the input string.

Taking it is optional, and it is what makes the non-deterministic finite automata non-deterministic: by allowing it to 'branch' it can 'explore' two plausible paths through the language it accepts. It is essentially just a space saving measure: DFAs (which do not permit epsilon transitions) are computationally equivalent to NFAs. There are steps to convert an NFA to an equivalent DFA, removing epsilon transitions is part of this conversion.

To explicitly draw out answers to your questions: In your example it is akin to a 'NO_INPUT' symbol, but more like 'NO_COST'. Think of it like this: Each edge has a 'cost' in the symbol along it that you must pay to transition along that edge. An epsilon has no cost. You don't 'spend' any characters from your input string to traverse that edge. Because of that, you now have multiple paths: Take the epsilon transition (or transitions) and spend no symbols from the input string, or 'spend' an input string along an edge. So it essentially the computation 'branches', and your NFA accepts a string if any path through it concludes in a success state.


Are context free grammars the only ones that have parsing trees?

If you look at the Chomsky Hierarchy and the corresponding definitions
of grammars for each of the four types you can make the following
remarks:

there does not seem to be any natural concept of derivation
(generation) tree for type 0 grammars, the unrestricted kind, that
would apply to all.
for context-sensitive (type 1) grammars, at least in the form given
in the wikipedia article, one could associate a tree structure to
the derivation of the string, but this tree, even annotated with
the grammar rule applied at each node, would not be sufficient to
recover simply the order of application of the rules. You would
have to actually associate some partial order with the tree nodes.
I do not know whether this was ever used.
The context-free case (type 2) is well known.
The regular case (type 3) is well known too. It may be seen as a
special case of CF. But regular grammars, and associated tree
structures are not interesting since they are trivial. They do not
really provide useful generative information, nor do they impart
structure on the generated string. Note however that CF grammars
with interesting tree structures could well generate regular
languages.

However, this is not the end of the story. There are many kinds of
grammars, between the regular family and the full context sensitive
(CS) family, i.e. around the CF realm. Many can associate a derivation
tree with the generation process, and they can also associate a
derived tree with the generated string, thus giving it a structure.

These two trees are the same in the case of CF grammars, but, as I
indicated in my answer to another of your questions, they may also
differ, notably in grammars involving multi-parts constituents. such
as Tree Adjoining Grammars (sometimes called mildly context
sensitives) or more generally Linear Context-Free Rewriting Systems
(LCFRS). These grammars depart somewhat from the basic model of
Chomsky hierarchy, as do many others, such as indexed grammars.

For all these formalisms, the languages defined are usually in the context
sensitive realm, and cannot be generated by a CF grammar. The derived
trees associated with the strings are thus also beyond what can be
done with CF grammars. However, many of the formalisms considered in
the literature have sets of derivation trees that are the same as those
of Context-Free languages.

The set of parse trees (meaning here both derivation and derived
trees) for context-free language is a tree language. The family of
parse-tree languages associated with CF grammar is precisely what is
called regular sets of trees. They can be defined by Regular Tree
Grammars (that may look suspiciously like string CF grammars). They can be
recognized by finite state tree automata.

What distinguishes CF Grammars is that their derived trees are regular
sets of trees, which is not the case for the other formalisms. However,
many of these formalisms have regular sets of derivation trees, the
same as CF languages.


I presume you are looking for a way to prove the identity using a calculus. So far you have used distributivity an idempotency.

Recall that A = A1 so you get A1+AB and you can use distributivity again, this time in the other direction. Then two obvious steps.


experimental analysis of running times in extendable table

An extendable array isn't a two-dimensional array (I don't know what's an extendible table). The idea is that you start with an array of a fixed size, and each time you are trying to insert an element into the array but it's full, you increase the size from $N$ (its current size) to $f(N)$ (its subsequent size, until it needs to be enlarged again). That means that you allocate new memory ($f(N)$ items), copy the old array into the new place, and then free the old memory. When you have added $f(N)-N-1$ more elements, a subsequent insertion would require enlarging the array to size $f(f(N))$, and so on. The question is what is the best choice for the function $f$.

Experimentally, you can try different functions $f$. For each such suggestion $f$ (and the same initial size of the array, say something like 20 or 100, you decide), plot $n$ against the time it takes to add $n$ elements (what elements you add isn't important; you could just add zeroes), averaged over several trials. I'll let you decide how exactly to do that, but you probably want several different values of $n$, and $n$ as large as roughly a million or so (you decide exactly how large). You can then find which function is better than others. I suggest you use C rather than python in your experiments.


Is there a "sorting" algorithm which returns a random permutation when using a coin-flip comparator?

No, this is impossible unless $n \leq 2$. The probability that a permutation is generated by your algorithm using a random comparator is dyadic, i.e. of the form $A/2^B$, whereas the probability should be $1/n!$. When $n > 2$, there is no way to write $1/n!$ in the form $A/2^B$.


Synchronizing sequence and Synchronizable DFA, how come states repeat if synchronizing word length is $>|Q|^{2}$?

synchronously moving through the DFA beginning with two different states while an input of a word w can be described as choosing two states out of k on every step. So there exist $\binom{k}{2}$ possibilities to do that.
As $k^2>\binom{k}{2}$, there will be one step where we choose a pair of states which we already had before. So the word $w$ can be shortened: this is the contradiction to the claim that the word is longer then $k^2$.


Soundness and completeness w.r.t. programming languages

I'll focus on your question:

  An example that I thought of is: If an analyzer is designed to accept all programs, does this mean the analyzer's system is sound but incomplete? I'm not quite sure if my reasoning is correct.

No, your reasoning is not correct. Let's take the definition your instructor gave you:

  Soundness: [...] If a program is accepted by an analyzer, then the program is guaranteed to be safe.

If a sound analyzer accepts every program, by definition every program must be safe. This is not the case -- so a sound analyzer must not accept everything.

  Completeness: [...] If a program is rejected, then that program has errors.

By definition, the always-accepting analyzer is complete: since it accepts everything, it rejects nothing, so all programs it rejects (i.e., none) have errors. This follows because from a false hypothesis ("a program is rejected") we can logically infer anything at all (including "the program has errors").

So, the always-accepting analyzer is complete, but not sound.

By contrast, an always-rejecting analyzer would be sound but not complete.

My preferred way to describe soundness and completeness is pretending we have an analyzer which, given an input program, returns "SAFE" (technically, accepts) or "NOT SAFE" (technically, rejects). A sound analyzer is one that can be trusted when it says "SAFE". A complete analyzer is one that can be trusted when it says "NOT SAFE".

A sound & complete analyzer can always be trusted, so (if it always halts) it is a decider for program safety. (Actually, by Rice's theorem, such a perfect analyzer can not exist.)

A sound but not complete analyzer, can be trusted only on "SAFE" answers. So, we can pretend it reliably answers "SAFE" or "DO NOT KNOW". (Indeed, "NOT SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")

A complete but not sound analyzer, can be trusted only on "NOT SAFE" answers. So, we can pretend it reliably answers "NOT SAFE" or "DO NOT KNOW". (Indeed, "SAFE" answers can not be trusted, so they actually mean "DO NOT KNOW")


"Minimum" maximum flow with extra capacities

The smarter Naive approach of extending a solution to the Maximum Flow problem to a similar graph with at least as much capacity is to only add flow to augmenting paths that you'd find from the Residual of the initial graph. And if no augmenting paths exist, then terminate. This is known as the Ford-Fulkerson Algorithm, and if you were to have run it on the a graph of $E$ edges initially, this would incur a runtime of $O(E\cdot f^*)$, where $f^*$ is the maximum flow in the graph.

In case you haven't heard of some of these terms, or the Algorithm, visit: http://en.wikipedia.org/wiki/Ford-Fulkerson_algorithm


Linear-time algorithm to check monotonicity of polygonal chain

This answer is related to the remarkable answer for a similar problem. The only difference is that the OP asked about monotonicity of a polygonal chain, but not about monotonicity of a polygon.

The algorithm idea is the same - we need to determine ranges of "authorized" angles for normals to $L$ looking at the adjacent chain segments. An angle is considered authorized if a normal with this angle defines such a straight line $L$, that all the straight lines, orthogonal to $L$, intersect the chain not more than once. In case of a polygon it was enough to look at concave vertices only, but in our case we must look at all the internal vertices.

The picture below shows a polygonal chain with four segments. Authorized angles at each internal vertex are marked by green color.

If an intersection of all the $(n-1)$ ranges of authorized angles isn't empty, then the polygonal chain is monotone, and the line $L$ exists. This algorithm apparently will take $O(n)$ steps.


RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1

You can show that $ap\mod q =(ap)^e\mod q$ by using the fact, that $ap-bq=1\Longleftrightarrow ap=bq+1$.
You know that $q|bq$ and therefor $ap\mod q = bq+1\mod q \equiv 1\mod q$.
This implicates that $(ap)^e\mod q = (bq+1)^e\mod q \equiv 1\mod q$. Therefor $ap\mod q \equiv (ap)^e\mod q.$
Now with the chinsese remainder theorem we know that $ap\equiv_N(ap)^e$.


Mathematical conjectures equivalent to the halting of a Turing machine

Your question is answered by the arithmetical hierarchy. The existence of an odd perfect number is a $\Sigma_1$ statement, and so you can test it using a $\Sigma_1$ machine, which halts iff the statement is true. The twin prime conjecture is a $\Pi_2$ statement, and so you can construct a TM with access to the halting oracle which halts iff the statement is false.
In a strict logical sense, you can always make a Turing machine that halts iff statement $\phi$ holds:

If $\phi$ holds, then take a machine which halts.
If $\phi$ doesn't hold, then take a machine which doesn't halt.

To see that this construction is valid, consider the logical form of your statement:
$$ \forall \phi \exists T . \phi \Leftrightarrow T\text{ halts}. $$
You can clear this confusion up by asking a slightly different questions:

What is a set of statements $\Phi$ such that there exists a Turing machine which halts on $\phi \in \Phi$ iff $\phi$ is valid?

Above I have indicated that $\Sigma_1$ statements form such a set.


Your problem is in NP.
Generalized Sudoku is NP-Complete, but your mapper is in P. Check whether given grid is generated by mapper runs in $\mathcal O(n^2)$ time.
Your mapper is not NP-Complete and your decision problem is not NP-hard.

On the other hand decision version of Sudoku is NP-hard.

The main problem is that you have not provided anything about checking uniqeness of solution, but since your mapper resolves only one solution from family of solutions it can't decide it.

If you insist on proving NP-hardness please provide valid reduction (hint, it will not run in polytime, so answer is no).


Prove that $L$ is closed under Kleene star iff $L=NL$

Let $A$ be the language consisting of the following words:
$$
(u,v)|\Sigma^*|(v,w),
$$
where $u,v,w$ are numbers encoded in binary. This language is in $\mathsf{L}$.

Given a directed graph $G$, we can encode it as a list of edges in the following way:
$$
(x_1,y_1)(x_1,y_1)|(x_2,y_2)(x_2,y_2)|\cdots|(x_m,y_m)(x_m,y_m)
$$
where $x_i,y_i$ are vertex numbers encoded in binary. Furthermore, this string, which we denote by $\langle G \rangle$, can be output by a logspace machine.

Suppose now that we are given two vertices $s,t$, and that there is an $s$-$t$ path of length $\ell$ of the form $(s,x),\ldots,(y,t)$ in $G$. Then I claim that for all $L \geq \ell$,
$$
(s,x)|\langle G \rangle^L|(y,t) \in A^*.
$$
Conversely, if such a string belongs to $A^*$ then there is an $s$-$t$ path in $G$. In other words,
$$
\exists \text{$s$-$t$ path in $G$} \longleftrightarrow (s,t) \in G \lor \exists x,y \text{ s.t. } (s,x)|\langle G \rangle^n|(y,t) \in A^*.
$$

If we assume that $\mathsf{L}$ is closed under Kleene star then $A^* \in \mathsf{L}$, and so we can evaluate the right-hand side formula in logspace. Since $s$-$t$ reachability is $\mathsf{NL}$-complete, we deduce that $\mathsf{L}=\mathsf{NL}$.


Computer vision: object detection with labels that are single coordinates

The state of the art in such problems is done these days via deep neural networks. Among others, two popular and recent approaches for solving the problem of detection and localization of objects are the YOLO paper, and the faster-RCNN, which run a classifier over many variously sized regions in an image.

As humans, boats and cars are popular object classes, I'd first attempt to see what existing pre-trained networks can do for your problem, and then, if needed, try and re-train them using your data.


Why is one traversal sufficient for the Kuhn's maximal matching problem algorithm?

Kuhn's algorithm maintains the following invariant: after scanning through vertices $v_1,\ldots,v_k$ on the left, the current matching is a maximal matching of the graph consisting of $v_1,\ldots,v_k$ on the left, and the entire right-hand side. Hence at the end, we get a maximal matching of the entire graph.

How do we know that Kuhn's algorithm maintains the invariant? We prove it when we prove that Kuhn's algorithm is correct. I encourage you to find a correctness proof of the algorithm (such proofs are surely not too hard to find online) and read it.


Is there any study or theory behind combining binary search and interpolation search?

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates.

Though theoretically faster, interpolation search has two disadvantages compared to binary search:

It has terrible (linear) worst case performance
The overhead of computing the midpoint is rather large; a binary search iteration is hundreds of times faster than an interpolation search one

I would expect that an approach where you do interpolation search while the range is large and switch to binary search when the range becomes small is the most efficient. It would be nice if you could try this experiment.

As your dataset becomes small, the difference between $\log n$ and $\log \log n$ becomes insignificant; $\log n$ is already really small, and $\log \log n$ couldn't possibly be much smaller. At this point, the overhead of doing interpolation search is not worth it compared to the iterations you might save.

I think that your results can be explained by two phenomena:

Combining with binary search allows you to avoid the worst-case behavior
The positive effect of switching to binary search on a small dataset


Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$

It seems that you're trying to construct the graph $K_{37}$ from string and nails without cutting the string.  For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once).

In the case of a complete graph, finding an Euler trail is trivial: start at any vertex and move from vertex to vertex without repeating an edge. As long as the last thing you do is returning to the initial vertex, you've created an Euler trail.  (This is essentially Fleury's algorithm except that checking you've not disconnected the graph is trivial for a complete graph.


Mathmatical way to represent an image kernel?

Applying the filter corresponds to two-dimensional convolution:
$$
(f \ast g)(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty f(i,j) g(x-i,y-j).
$$
In our case, $f$ is the filter, $g$ is the image, and $f \ast g$ is the filtered image. Since the support of $f$ (the number of non-zero entries) is finite, the sums in question are finite, and the convolution is well-defined. More explicitly, we have $f(0,0) = 5$, $f(-1,0) = f(1,0) = f(0,-1) = f(0,1) = -1$, and $f(i,j) = 0$ otherwise.

Edit 1: Here is another way of viewing it. This time, $f$ is the image and $g$ is the filter, defined by $g(0,0) = 5$, $g(-1,0) = g(1,0) = g(0,-1) = g(0,1) = -1$, and $g(i,j) = 0$. The same formula for filtering, $f \ast g$, works before, since $f \ast g = g \ast f$. In other words, the filtered image $h$ is given by the formula
$$ h(x,y) = \sum_{i=-\infty}^\infty \sum_{j=-\infty}^\infty g(i,j) f(x-i,y-j). $$

Edit 2: We can rewrite the convolution as a product of generating functions. Suppose the original image is given by
$$ F = \sum_x \sum_y f(x,y) X^x Y^y. $$
The filter $G$ in your case is given by
$$ G = 5 - X - X^{-1} - Y - Y^{-1}. $$
Filtering the image corresponds to the multiplication $H = FG$, and the filtered image $h$ can be extracted as
$$ H = \sum_x \sum_y h(x,y) X^x Y^y. $$

Edit 3: Going back to the notation of Edit 1, in terms of the two-dimensional Fourier transform, we have
$$ \hat{h} = \hat{f} \hat{g}, $$
where the multiplication on the right is pointwise. So filtering corresponds to multiplying each Fourier coefficient by some fixed amount, which depends on the filter.

Edit 4: In this particular case, the relation between the original image $f$ and the filtered image $h$ is
$$ h(x,y) = 5f(x,y) - f(x-1,y) - f(x+1,y) - f(x,y-1) - f(x,y+1). $$

Edit 5: The image you posted handles the boundary issue by extending the first and last rows and columns past the boundary. For example, $f(x,-1) = f(x,0)$, $f(-1,y) = f(0,y)$ and $f(-1,-1) = f(0,0)$.


What is the advantage of probability algorithm?

What is advantage of probability algorithm (we usually use randomized algorithm instead of probability algorithm)? Well this is a big question, e.g. we don't know if $P = BPP$, if so then we would say that deterministic algorithm is the same as randomized algorithm. If not, i.e. $P \ne BPP$ then randomized algorithm gives us more power than deterministic algorithm. I think randomized algorithm can give us some polynomial speed up but I'm not sure if it can give us an exponential speed up over deterministic.
Note that P is the class of all problems that can be done by efficient algorithm (i.e. polynomial algorithm in the size of the input) while BPP stands for Bounded-error Probabilistic Polynomial time, i.e. it contains all problems that have a non-deterministic TM with at least 1/2 of the branches accepts and less than 1/3 of the branches rejects.
A quick example of a randomized algorithm is verifying polynomial identities, e.g. given (x+2)(x-4)(x+22)(x-43)(x+11) = x^5-2x+4. The question is: Can you verify that the right-hand side is equal to the left hand side? One way to do is to multiply all terms together which takes O(n^2) where n is the number of terms. But we can do it in O(n) time by selecting some random number and text whether they are equal or not. Yes, there is a probability of wrong answer, but with many run of the algorithm (say 100) if there is at least one counterexample, then this is enough.
There are two major textbooks in randomized algorithm which are:

Probability and Computing - Randomized Algorithms and Probabilistic Analysis by Michael Mitzenmacher and Eli Upfal

Randomized Algorithm By Rajeev Motwani and Prabhakar Raghavan

I recommend the first since it is easier and have one or more examples in each chapters while the second is good if you are interested in randomized complexity.


Regular language not accepted by DFA having at most three states

The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma:

  Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$.

You can use this characterization to prove that the language $\{0^p\}$ requires $p+1$ states.

Another method is to use the Myhill--Nerode theorem. Two words $x,y$ are inequivalent (with respect to some language $L$) if for some word $z$, either $xz \in L$ and $yz \notin L$ or the other way around. The Myhill--Nerode theorem states that if there are $p$ pairwise inequivalent words, then every DFA for $L$ has at least $p$ states. For the example $L = \{0^p\}$, you can find $p+1$ pairwise inequivalent words, namely $\epsilon,0,\ldots,0^p$.


For each v from V, we relax only those edges e, which werent computed
  yet. If vertex v is already computed (red on gif above), we don't need
  to work with it anymore.

Your are assuming that each edge is visited only once, but this assumption is not quite right. Let's say we have two sets $S$ and $S'$, such that $V=S \cup S'$ and $S$ is the set of vertices, for which we have found the shortest path from source $s$. Each time, we need to find an edge $e=(u,v)$ ($u \in S$ and $v \in S'$) that sits on a shortest path, but how do you find this edge? You need to either

(1) use a brute-force algorithm and spend $O(|V|)$ to look at all edges $e=(u,v)$ ($u \in S$ and $v \in S'$) for finding the minimum one, which takes $O(|V|^2)$ (because each time you are looking at the same edge that are not in the shortest path).

or

(2) use a min-heap and spend $O( \log |V| ) $ for finding that edge, and achieve $O( (|V| + |E|)\cdot \log |V| )$ overall running time.

However, if the graph is unweighted, your assumption is right and you can achieve the running time $O(|V|+|E|)$.


Is there any official terminology about something like double quotes "" grammar?

FOLLLOW sets are not used in the parsing of either string or nat. In both cases, the parser merely needs to determine if the input is in a set of valid symbols. In the case of nat, the valid symbols are digits; in the case of string, they are characters other than ". (In real languages, the parser would also be checking for \). But in both cases, a check is necessary, and there's no good criterion for saying one test is "simpler" than another. (In practice, both checks are likely to be a simple table lookup. So they're O(1).)
FOLLOW sets are only needed when the grammar contains ε productions. Even then, the parser's actions are not complicated. What is more complicated is building the parser, something which only happens once. It's not really that big of a deal, but it's sufficiently notable that "ε-free grammars" are a thing. I don't think there's any common vocabulary to describe the difference between explicitly and implicitly-terminated repetition, and any way the distinction will be very hard to define strictly. Your string would be parsed by a parser which used a different rule to collect the trailing ", and it's quite possible that the two parsers end up with the same implementation.


Algorithm to determine whether two regexes are equivalent

Hendrik Jan gives a good answer for complexity class, but not an algorithm itself.

The simplest algorithm to do this that I know of is to convert the regular expression to a DFA. There are known techniques for converting a regular expression to an NFA, and an NFA to a DFA.

Once you have two DFAs, testing for equivalence is efficient and decidable, since the minimal form of a DFA is unique up to isomorphism.

However, constructing these DFAs from NFAs could take lots of time, and produce extremely large DFAS, exponentially large in the worst case.


I'm going to need to question your premise here.

I have no doubt that you can poly-time reduce 2SAT to your custom problem. But you can poly-time reduce 2SAT to pretty much anything. The idea of "P-hardness" under poly-time reduction isn't really a useful one.

For example, let's take the following problem:

  IS-IT-ONE: given a single bit, is that bit a 1?

This problem is "P-hard" under poly-time reduction. For example, I can reduce 2SAT to it:

  Reduction from 2SAT to IS-IT-ONE

  Solve 2SAT the usual way
  If the problem is satisfiable, let $B$ be 1
  If the problem is unsatisfiable, let $B$ be 0
  Run IS-IT-ONE on $B$ and return the result

This reduction runs in poly-time, because solving 2SAT can be done in poly-time.

In other words:

Every problem in P can be poly-time reduced to any other non-trivial problem.

(Only two languages are considered "trivial" for this purpose: "return true" and "return false", aka $\Sigma^*$ and $\varnothing$.)

If you're interested in classes smaller than P, great! There are several of them, such as L: the set of problems that can be solved using a logarithmic amount of memory. It may or may not be the same as P—that's an open problem.

But if you want to talk about P versus L or NL or anything else within P, you can't use poly-time reductions any more. When talking about L, for example, you'll usually want a log-space reduction, using a Turing machine with writable tape bounded by the log of the input size. These aren't as famous as poly-time reductions, but they're still quite important in complexity theory.


PDA with N-Stacks comparison with Turing Machines

2 stacks is enough for a PDA to be as powerful as a Turing Machine. Basically, you can pop from one stack and push into the other to simulate moving across the tape head, writing, etc.

In fact, a 2-counter machine is as powerful as a Turing Machine, though the proof is much more involved. There's a sketch of it on Wikipedia


I understand "to bail out" as to give up permanently; "to back out" is to give up some track, possibly to try something else.


Polynomial time approximation of NPC problem

Is it feasible to show it with the experimental results?

No, you can not. There is no shortcut around formal proofs here.


As said Yuval Filmus in the comment, some unary languages are undecidable, so they don't even have an equivalent binary language in P.


Problems unsolvable by an oracle machine?

Every problem $P$ can be solved with an oracle machine with oracle access to $P$. In order to get a more meaningful answer, we consider the concept of Turing semi-degree, which is the set of all problems computable with an oracle to $P$, for some problem $P$. The same diagonalization argument used to prove that the halting problem isn't decidable shows that no Turing semi-degree encompasses all languages. (Alternatively, there are uncountably many languages but only countable many problems computable with any given oracle.)

A Turing degree consists of the "hardest" problems in a Turing semi-degree. More formally, it is the set of problems equivalent to some problem $P$: problems which are computable given an oracle to $P$, and conversely $P$ can be computed given an oracle to them. The study of Turing degrees consists a significant part of classical recursion theory.


Is Simon's problem a good NP-intermediate candidate?

Simon's problem is not a pure NP problem, for two reasons:

It is an oracle problem.  We are given an oracle for some function $f$.  That's not something that you can do within the definition of a NP problem.
It is a promise problem.  We are given the promise that $f$ will satisfy a particular property (it is two-to-one, and has a particular structure).  That too is not something you can do within the definition of a NP problem.

So Simon's problem is not a problem in the formal complexity class NP; it's just something different.  For the same reasons, it's not NP-intermediate, either.


Graph Algorithm (Modification on Dijkstra?) : Tech Interview

The Hamitonian path problem is reducible to your problem. Given a directed graph $G(V,E)$, set $C=|V|$ (number of nodes), $A = V$, and weight of each edge is equal to $1$. Thus, this instance of the problem requires to find a shortest path containing all vertices. Since it asks to find the shortest path, cycles are not allowed, and since it asks to include all vertices, the path visits all vertices once. This is a Hamiltonian path. So, your problem is NP-complete meaning it is unlikely to find a polynomial time algorithm. In this case you should try approximation algorithms or Linear/Integer programming algorithms.

Note (on  @user53923's comment): There is a chance to get a path with a cycle, from the problem from the question, which is shortest including all vertices. But in this case we could check in polynomial time if the path has a cycle and if it has then simply reject. This would mean the graph does not have a Hamiltonian path, otherwise it would return it since its length would be shorter from that containing a cycle.


Bellman-Ford algorithm - Why can edges be updated out of order?

Consider the shortest path from $s$ to $t$, $s, v_1, v_2, \dots, v_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles.

In round one, we know that the edge $(s, v_1)$ will be relaxed, so the distance estimate for $v_1$ will be correct after this round. Note that we have no idea what $v_1$ is at this point, but as we've relaxed all edges, we must have relaxed this one as well. In round two, we relax $(v_1, v_2)$ at some point. We still have no idea what $v_1$ or $v_2$ are, but we know their distance estimates are correct.

Repeating this, after some round $k+1$, we have relaxed $(v_k, t)$, after which the distance estimate for $t$ is correct. We have no idea what $k$ is until the entire algorithm is over, but we know that it will happen at some point (assuming no negative weight cycles).

So, the crucial observation is that after round $i$, the $i$-th node of the shortest path must have its distance estimate set to the correct value. As the path is at most $|V|-1$ edges long, $|V|-1$ rounds suffices to find this shortest path. If a $|V|$th round still changes something, then something weird is going on: all paths should already be 'settled' to their final values, so we must have the situation that some negative weight cycle exists.


Graph isomorphism problem for labeled graphs

You might be interested in this paper:

Aidan Hogan:
Skolemising Blank Nodes while Preserving Isomorphism.
WWW 2015: 430-440

It has an algorithm (based on Nauty) for testing the isomorphism of RDF graphs, which are essentially directed labelled graphs that may contain fixed labels. The algorithm takes labels into account to narrow the search space.

If you can represent your input labelled graph as an RDF graph, you could try use the associated software package "blabel" to test isomorphism.


Actually, what you've described confuses ballooning and 'same-page-merging'. I'll try to elaborate on the two to make the distinction apparent.

Memory ballooning

This is a trick to make sure that some of the memory allocated to the guest virtual machine remains usable by another guest or the host itself (caches, etc). It's done in the following way:

The guest kernel is injected with a driver, that monitors guest memory usage, and 'steals' some of the unused memory (allocating it for itself in the guest memory space, thus making sure nothing on this guest can touch that range).

Then it informs the host kernel, that it can in fact remove these memory pages from the core, that they are not going to be used in the guest (until the guest experiences some memory pressure, at which point the balloon will deflate, and use these ranges again).

Ultimately, the kernel can allocate the exact same memory to another guest, and make the entire memory usage a lot more efficient if the guests are running with a lot of free memory.

Same Page Merging

This technique identifies identical memory pages, that for some reason are not already marked 'quasi-read-only' with copy-on-write, and marks them as such.

Now, on the OS level, there is limited need for these kinds of tricks. Simply enough, most time when you have identical memory pages, they are already read-only (sometimes even without CoW), since these are mostly applications code, libraries etc. They are natively opened through a Memory Map, and thus the kernel can keep only one copy of them in core (if any at all, it can also completely page it out, and allow it to be paged in from primary store as needed).

On the virtualized OS level, the same principle is properly applied within each guest subsystem. However, the host kernel, has no idea if two of the guests are running mostly the same code, and thus are sharing the same memory - the guests don't communicate to coordinate that.

Which is why it can occasionally scan the entire system for identical memory pages - most of the time, they will be identical across the guest OS's, not within each one - the guest kernel makes a decent job keeping the memory neat within it's range. Thus, in the typical VM environment, where one host kernel handles 50+ guests, the memory savings can be pretty substantial.

Both at once

Ballooning and Same-Page-Merging can co-exist very well, achieving pretty substantial memory overcommit for identical systems.

To answer your question - the Same-Page-Merging can and sometimes is enabled at an OS level. It has to do with page sharing that are interpreted, and thus could end up being identical without having the same backing file.

In your Chromium example - the process binaries themselves are already deduplicated through read-only startup map - they share the exact same memory space. The page caches (contents of the tabs) are usually also shared between processes (read-only copy-on-write) due to the way disk cache is managed - the same on-disk file can be opened simulatenously between different processes in the VM-optimal sense.

The advantage would be most evident with the shared state of different Javascript engines - but I'm not sure if they are allocated in the exact same memory layout, ensuring that the entire memory page is identical.

This is different on mobile systems. Android, for instance, extensively employs KSM to deduplicate identical code between different applications.

In either case, you can enable it yourself on Linux (Kernel SamePage Merging). The driver exports various statistics that, after reading this answer, you should be able to interpret, and make your own decision whether it's a good match for your purpose.

https://www.kernel.org/doc/Documentation/vm/ksm.txt


How can I solve this problem using dynamic programming?

Increasing all elements but one is equivalent to decrease only that element. Find minimum value m, now for each element x you need to find minumum number of subtractions to go from x to m (change-making problem), since you can use greedy algorithm for coins (1, 2, 5), you can solve this problem in O(n).


Let $\Sigma$ be the alphabet on which $A_{TM}$ is defined over, and assume w.l.o.g that:

$A_{TM}\cup \overline{A_{TM}} = \Sigma^*$, and
$0, 1 \notin\Sigma.$

The set $J$ can be written as:
$$
J = \{0\}\cdot A_{TM} \ \cup \{1\}\cdot \overline{A_{TM}}
$$
where $J$ is defined over the alphabet $\Sigma \cup \{ 0, 1\}$.
Now, using De morgan's law, it holds that:
$$
\overline{J} = \overline{\{0\}\cdot A_{TM}} \ \ \cap \overline{\{1\}\cdot \overline{A_{TM}} } \\
$$
$$
=\left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^*\right) \ \cap \\
\left(\{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right) \\
$$
$$ = \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \left[\{0\}\cdot \overline{A_{TM}} \ \cup \{1\}\cdot \Sigma^* \right] \cap \left[ \{1\}\cdot A_{TM} \ \cup \{0\}\cdot \Sigma^*\right] \right)
$$
$$
= \{w: \text{ $w \neq \sigma\cdot u$, $\sigma\in\{0, 1\}$ and $u\in \Sigma^*$} \} \cup \left( \{ 0\}\cdot \overline{A_{TM}} \cup \{ 1\}\cdot A_{TM} \right)
$$
So, we have that $w \in \overline{J}$ iff $w$ does not encode a bit followed by a word of the form $\langle M, w \rangle$, or $w = 1x$ for some $x \in A_{TM}$ or $w = 0y$ for some $y \in \overline{A_{TM}}$.
Finally, note that they're implicitly assuming w.l.o.g that every nonempty word in $\{0, 1\}\cup \Sigma^*$ is of the form "$\text{bit} \cdot \langle M, w\rangle$". This assumption is okay, as checking whether a word respects some encoding can be easily done by a TM.


What is the difference between 'features' and 'descriptors' in computer vision / machine learning?

The SIFT descriptor vector is a feature vector.  "Descriptor vector" and "feature vector" are synonyms in this context.  Most of the descriptions of SIFT I've seen use the phrase "descriptor vector", but occasionally they'll refer to it as a "feature vector" or refer it to as "SIFT features", perhaps to draw upon intuition from machine learning.

SIFT works by analyzing the image, identifying a set of keypoints (a set of points in the image that will be helpful for alignment), and then for each keypoint, it computes a descriptor vector (a feature vector).  Then it uses the descriptor vectors for the keypoints in image $I_1$ and the descriptor vectors for the keypoints in image $I_2$ to try to align the two images to each other.  The intuition is that if the descriptor vector for a keypoint in image $I_1$ is "similar" to a descriptor vector for a keypoint in image $I_2$, then maybe those two points should be aligned to each other.  Here "similarity" is measured by the Euclidean distance between the two descriptor vectors.

Thus, a descriptor vector for a keypoint is a vector, e.g., in $\mathbb{R}^{128}$, chosen so that if the image is translated, scaled, rotated, etc., then the descriptor vector for that point won't be changed much by the transformation.

You can find a reasonable description of SIFT in Wikipedia: https://en.wikipedia.org/wiki/Scale-invariant_feature_transform


Is there a measure of space usage over time?

Sure.  Of course, you are absolutely right, that time complexity and space complexity don't capture the whole story.  No one metric is likely to.

There are many ways one could plausibly distinguish between those two programs.  For instance, one could ask about average space usage (averaged over the lifetime of the program).  These metrics might be harder to use, but might be more relevant in some situations.  Only you can know what you want to optimize, so you only you can determine which metric is most suitable for your particular situation.  You might find that asymptotic analysis is not the best tool for the job and instead you want to measure space usage on a real-world benchmark/workload. That is also reasonable.


In the beginning, computable functions were always total, but when where the partial functions included

The Stanford Encyclopaedia of Philosophy has a summary of the history of recursive functions. In particular, in Section 1.8 we can read that Stephen Kleene explicitly defined the partial recursive functions, and showed them to be equivalent to several other notions of computable functions, in a series of papers between 1936 and 1954. For example, already his 1936 paper General recursive functions and natural numbers introduces the unbounded search operator which leads to partial functions (when the search does not find anything).


If a language consists of an NP and coNP question, do we have to place it in P^NP^NP?

No, because $A$ isn't necessarily $NP$-complete and $B$ isn't necessarily $coNP$-complete.  You'd need both to be true to force the implication $NP = coNP$ by $X$ being a member of both problem classes.  In fact $A$ and $B$ could both be in $NP$ and $coNP$.  E.g. $A$ and $B$ could both be in $P$.  $NP \cap coNP$ is not the empty set.


How efficient of this prime sieving algorithm?

The loop "int c ... " is much too complicated and difficult to get right, just start with c = a, b = a*a, and iterate upwards.
Most people create a sieve for odd numbers only. Some create a sieve only for the eight out of 30 numbers that are not multiples of 2, 3 or 5. That's a factor of 3.75 in space. And removing multiples of 2, 3 and 5 takes substantial time.
Only checking multiples of 2, 3 or 5 also allows you to check fewer multiples of the prime. Another factor 3.75.
If you want to be fast, you use a bit array, and use SIMD instructions to remove multiples of small primes, say up to 100, which saves a huge amount of time. Checking whether c is still considered a prime is time consuming and likely takes more time than it saves, especially since you will end up with lots of mispredicted branches.
Now for primes up to a million that's all irrelevant, but for larger ranges it makes a huge difference.


Find unambiguous grammar for an ambiguous grammar

I'm not sure whether my approach or answer is correct or not.

It is not correct. Your modified grammar can produce at most three consecutive 'a's or 'b's, while the original grammar can produce an unbounded number of consecutive 'a's or 'b's.

Your approach starts fine by looking for counterexamples, but then runs into a trap by staying too close to the given grammar. This is a trap, because the problem asks for extensional equality of languages. After you isolated the critical part of the grammar which generates the problem, you should first try to understand the generated language (that interacts with that part), before starting to modify the grammar.

  I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

Your first step to look for a counterexample and isolate the part of the grammar which generates the problem makes sense.
My next step would be trying to understand the generated language. Let me try your example:

From S, I can generate any number of 'a's, followed by the same number of 'b's, and end up in S again. Can I ever generate more 'a's than 'b's? No, the number of 'a' or 'A' on the left side is identical to the number of 'a' or 'A' minus 'b' or 'B' on the right side for all rules. Can I generate any string with the same number of 'a's and 'b's? Yes, because ...

Ah, so the generated language is simply the language where the number of 'a's equals the number of 'b's.

After you understood the generated language, you can try to determine whether it can be generated by an unambiguous grammar, and write down such a grammar if desired. Let me try for your example:

The generated language is so simple, I would have heard if this language were ambiguous. It should even be deterministic, I can just push 'a's on the stack when there are more 'a's than 'b's, and push 'b's on the stack when there are more 'b's than 'a's. Of course, when the symbol on top of the stack differs from the current symbol, then I will just pop it. I know it is possible to convert this sort of deterministic PDA into a deterministic grammar, so I'm done without even trying to write down any specific deterministic grammar.


A special case for the subset sum problem

Obviously, even numbers cannot add up to an odd $M$. Other than that, we could just set $v_i = w_i /2$ and $N = M/2$. Then finding a subset of $w_1, \dots w_n$ which adds up to $M$ would be the same as finding a subset of $v_1, \dots, v_n$ which adds up to $N$, where the latter is the unconstrained knapsack problem.


What is Turing's main argument in "Computing Machinery and Intelligence"?

As I see it, the paper is not trying to do any of that.  The introduction is explicit: instead of trying to definitely answer the question "Can machines think?", it suggests an alternative question we can ask that can be specified much more precisely.  "Can machines think?" is vague and open to many possible interpretations; in contrast, the paper proposes a question that is less ambiguous.
(Implicitly, the implication is presumably that this shift of perspective might be interesting and help us think more clearly about the topic.  But it's up to each reader to form their own opinion about whether they find this interesting or useful in clarifying their thinking.)
This purpose is explained in clear and direct terms in the essay, particularly in the first paragraph of the essay as well as the second section of the paper.
To answer your specific questions, here is how I read the paper:

No, the paper is not trying to definitively answer the question of whether it is possible for a machine to pass the Turing test. Rather, the paper is suggesting that the question "Can a machine pass the Turing test?" is an interesting question, worthy of our attention.
Think of this like a scientific paper that proposes an experiment -- it's not necessarily trying to persuade anyone about what the result of the experiment will be, but rather suggesting that the experiment would be an interesting one to carry out or to consider.  That can be a useful, even ground-breaking, contribution.

No, the paper is not arguing that passing the Turing test necessarily signifies intelligence or thinking.  As far as I can tell, it doesn't take an explicit position on that.
We could imagine that one position that is compatible with the essay would be to say "I'm not confident I could define exactly what counts as intelligence or thinking -- that seems hard to define -- but whatever the answer is, passing the Turing test seems like it would be a significant milestone."  We could also imagine that another position that seems compatible with the essay would be "Yes, according to the way I personally define intelligence and thinking, passing the Turing test would signify intelligence and thinking."

No, I think it's pretty clear that Turing is not claiming that the metric is purely arbitrary.  On the contrary, the essay tries to argue that investigating this metric is worthy of our time.  See, e.g., section 2, which begins with "The new problem has the advantage of...."  You might find this argument persuasive, or you might not -- you might find the paper's proposal worthy of our time, or you might not -- you might find the paper's proposal arbitrary -- but I don't think it's fair to say that Turing thought the question was arbitrary.

These are my personal opinions and interpretations of the paper.  Others might vary.
Note that I've answered the question "What is the essay arguing?"  I haven't tried to tackle the question "What did Turing think?" since it can be hard to know what someone is thinking, and it's easier to grapple with the intellectual ideas as expressed in a particular paper.
Separately, one might ask "What do many computer scientists think?" or "What views have many computer scientists taken away, after reading the paper and thinking about the subject?" or "How has this paper influenced the perspective of many computer scientists?"  That's a separate question, with different answers, and potentially a bit more subjective.  For instance, you might find that many computer scientists have formed the opinion that the Turing test is possibly the best way we have to formalize the informal question "Can machines think?" into something answerable in a scientific way, and that many computer scientists think that at least in principle it should be possible for machines to think, if we can surmount the engineering challenges (see the Church-Turing hypothesis).
You might also be interested in reading  Human computing power: Can humans decide the halting problem on Turing Machines? and Would creating a complete computer simulation of the human brain prove the Church-Turing thesis? and https://philosophy.stackexchange.com/q/15460.


"Symbol Codes" means codes that work over a (finite) alphabet with an arbitrary size. Many times people focus only on binary codes, and Shannon Thm says that the minimal code length of some random variable $X$ is between $H(X)$ and $H(X)+1$ bits.

But what if, instead of bits, you use trits, or symbols from a larger alphabet of size, say, $a$?  Then, the length of $X$'s coding needs to be adjusted since every symbol of the codeword now "contains"  $\log_2 a$ bits.
Then, the wikipedia page says, the minimal code length will be
between $H(x)/\log_2(a)$ and $H(x)/\log_2(a)+1$ symbols.

Multiply the equation by $\log_2 a$ to convert into information bits:
the codeword will have $S$ symbols, hence $S\log_2 a$ bits, and this amount, by Shannon's coding theorem, can be minimized so that it is almost $H(X)$ (maybe up to one additional symbol, i.e., additional $\log_2 a$ bits).


What are some "easy" unreasonable implications of O(1) time memory access?

Memory access is assumed to be constant time, because normally you access memory that is close to each other, eg. from one hard drive or one given computer. Under that assumption there is a constant maximum amount of time to retrieve that data.

You are right. If I access data randomly accross very large amounts of data, then it's nowhere near constant, but normally you can arrange the data beforehand in a way that makes it O(1), because of it fitting onto one machine or very close machines. Another reason is that, harddrives all come with their hardware. That means normally you won't be switching hard drives in and out of one machine, and each drive comes with it's own reader. Also most machines are limited to a certain amount of drives. Those technical limitation give O(1) comlexity to most pratical applications and the software perspective of things.

One easy and unreasonable implication of O(1) time memory access is violating the assumptions above by scattering data randomly, across multiple machines in an unordered fashion or switching drives in and out of machines and expecting O(1) access times. Anything relying on wrong assumption is doomed to be wrong and thus unreasonable.