Random observations of a total ordering, how much they tell us?

Answer to Question 1

We can assume without loss of generality that the original ordering is the usual one: $a_1 < a_2 < \cdots < a_n$. Some ordering $\pi$ is compatible with our observations if whenever $\pi(i) < \pi(j)$ for some $i > j$, this observation is missing. In other words, $\pi$ is compatible with probability $(1-p)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions of $\pi$. Using the generating function of the number of inversions, we get that the expected number of compatible orderings is exactly
$$
\mathbb{E}[K] = \prod_{m=2}^n \frac{1-(1-p)^m}{p}.
$$
In the same way you might be able to compute larger moments of $K$, and so obtain some concentration bounds. Whether one should expect good concentration, and for which values of $p$, remains to be seen, though perhaps it's best to perform some numerical experiments to get a feel for how this behaves.

Answer to Question 2

Let $q_\delta$ be the probability that $O^*$ contains $(i,i+\delta)$. We can compute by brute force
\begin{align*}
q_1 &= p, \\
q_2 &= p + p^2 - p^3, \\
q_3 &= p + 2p^2 - p^3 - 4p^4 + 4p^5 - p^6, \\
q_4 &= p + 3p^2 - 11p^4 + p^5 + 30p^6 - 42p^7 + 26p^8 - 8p^9 + p^{10},
\end{align*}
and so on. Consulting the OEIS, we find the sequence of coefficients (for $-q_\delta(-p)$) as A214670.

Given the $q_\delta$, it is easy to compute the expectation of $I$, though since there isn't a particularly nice formula for $q_\delta$, this won't result in a reasonable formula for $\mathbb{E}[I]$.

You could ask for the threshold behavior of $\mathbb{E}[I]$, that is, at what value of $p$ does the expectation jump from 0 to 1, and how quickly. This is a different and interesting question.


Consensus anomaly about read-write registers and test&set

Consensus number and consensus hierarchy are defined in the classic paper "Wait-Free Synchronization" by Maurice Herlihy, 1991.

Note the keyword: wait-free.

Since you did not give the algorithms for test&set using read/write registers only, I guess that they are not wait-free. (They may be lock-free instead.)

Added:

After the discussions with the OP in the comments, I realize that the OP has not fully understood the difference between atomic test&set registers and atomic read/write registers. He/she thought that the protocol given in the post uses read/write registers only. In fact, it uses test&set registers/operations/instructions in the second step.

A test&set register supports the test&set operation, which is a combination of test and set that cannot be interrupted. See this wiki for more details.


Balancing subproblems in resilience testing

Drop the first jar at the $\sqrt{n}$th rung, $2\sqrt{n}$th rung, and so on until it breaks at the $m\sqrt{n}$th rung. (This takes at most $\sqrt{n}$ steps). Then drop the second jar at every rung between the $(m-1)\sqrt{n}$th rung and the $m\sqrt{n}$th rung until you find the precise breakpoint.


Give a recursive function $r$ on $A$ that reverses a string

A recursive function requires base cases and recursive rules. Depending on how your system works, your base cases might include:

$r(\lambda) = \lambda$
$r(\sigma) = \sigma$ for $\sigma \in \Sigma$
etc.

You then need a general rule for more complicated cases. You're on the right track; you need a rule that takes something of the form $\sigma w$, where $\sigma \in \Sigma$ is a single letter and $w \in \Sigma^*$ is some arbitrary string, and produces the correct output. You will likely find, and should try to prove, that a rule like the following works:

$r(\sigma w) = w \sigma$

Fits the bill. Putting it all together, in pseudocode, you should arrive at something roughly like the following:

Reverse(string[1...n])
1. if n = 0 then return the empty string
2. else if n = 1 then return string[1]
3. else return the concatenation of Reverse(string[2...n]) with string[1]


You can use either formula, since as you mention, the resulting algorithms are completely equivalent. The reasoning behind the standard formula $(W+E)/E$ is that it is the ratio between the expected completion time to the expected running time. Presumably when the algorithm was first suggested, the expected completion time was denoted by its own variable.


MIPS pipeline: choosing between slowing down a stage and adding a new stage

Your answer is probably correct for an exam.

In reality, adding a pipeline stage to MIPS is a major undertaking. The MIPS pipeline is very simple, that’s why it is taught in CS courses. Adding a pipeline stage adds a whole new level of complexity. Take an instruction sequence

X = A+B
X = C+D
Z = X+Y

In the current pipeline design, Z can just about be made to pick up the correct X - when C+D is stored, it goes directly into the first input of X+Y. With an additional pipeline stage, the second X is nowhere near ready when the third instruction starts. So you must make that instruction wait. But only because X isn’t ready in time. Since you don’t want to always wait, you need to detect this and add logic for that. And then the question is how often does this happen.

The alternative is that instructions using the second pipeline stage - and only those - stop all the other stages from progressing. So the timing would be the same as if this instruction was two instructions. In that case you could just make it two instructions.


Compute the sorted scores (and associated children) in the first window with a persistent sorted tree. This step takes $O(k \log k)$ time.
Create a DAG on children and add a directed edge from each child to each other child who is between $p$ and $2p$ places lower than it. This step takes $O(pk)$ time.
Shift the window forward one child at a time. Incrementally update the tree to obtain a new one for this window in $O(\log k)$ time per tree.
In each tree in step 3, place directed edges between pairs of children of distance $p$ where the child that entered the window in this tree is in between the children in the pair. This can be done in $O(p)$ time per tree (avoiding a $\log k$ factor) if one starts at the node obtained by insertion in step 3.
Assign candies to children topologically: each leaf child gets 1 candy; each internal child gets max(child's candies) + 1 candies. This runs in $O(n)$ time.
Sum the candies.

Note: the DAG with all of the edges from steps 2 and 4 sorts children by relative number of candies.

The resulting algorithm runs in $O(n(p+\log k))$ time.


How to find a good saw function for PRNG?

I think this is an effect of the rounding in your implementation or in the histogram.

Let's say your histogram contains 100 columns. Each represents a width of 0.01. The column at 10 shows how many items fall between 9.995 and 10.005. The column at 0 shows how many items fall between -0.005 and 0.005. However, there are no items below 0, so there is nothing between -0.005 and 0. This column will only show halve of the items in the other columns.


Big-Oh vs Theta in recurrence tree method

In this particular case $T(n) = 2T(n/2) + n^2 \geq n^2$, so the lower bound is trivial.


what is weak extensionality in $\lambda$-calculus?

There are different kinds of equality. Equality is said to be extensional when things are equal when their parts are equal, so to speak:

Equality the elements of $A \times B$ is extensional if, for all $u, v : A \times B$, $u = v$ if and only if $\pi_1(u) = \pi_1(v)$ and $\pi_2(u) = \pi_2(v)$. Here $\pi_1$ and $\pi_2$ are canonical projections. That is, $u$ and $v$ are equal if they have the same components (parts).
Equality of elements of $A \to B$ is extensional if, for all $f, g : A \to B$, $f = g$ if and only if $f(a) = g(a)$ for all $a : A$. That is, $f$ and $g$ are equal if they have the same values (parts).
Equality of sets is equal if, for all sets $S$ and $T$, $S = T$ if and only if $x \in S \Leftrightarrow x \in T$ for all $x$. That is, $S$ and $T$ are equal if they have the same elements (parts).

Equality which is not extensional is called intensional. For instance, if by $A \to B$ we mean programs (pieces of code) which take inputs $A$ and produce outputs $B$ then equality of functions could simply mean equality of the code.

The rules of the $\lambda$-calculus do not specify whether equality is extensional or intensional. They allow for both possibilities. With this in mind we see that it is not entirely clear whether the $\xi$-rule (that's what it's called)
$$\frac{M = N}{\lambda x . M = \lambda x . N} \tag{$\xi$}$$
should be part of $\lambda$-calculus. Normally it is, but we could envision a situation in which $\lambda x . M$ gets compiled differently from $\lambda x . N$ for some reason. So much about it being "obviously true".

Personally, I would not call the $\xi$-rule "weak extensionality" because that conveys the wrong idea. It is a congruence rule expressing the fact that $\lambda$-abstraction preserves equality. Another congruence rule is
$$\frac{M_1 = M_2 \qquad N_1 = N_2}{M_1 N_1 = M_2 N_2}.$$

If we insist, we can think of the $\xi$-rule as weak form of extensionality in the sense that two $\lambda$-abstractions are equal if their bodies (parts) are equal.


Consider the following set of $n$ orders, which I give for $n = 6$:
$$
123456 \\
213456 \\
132456 \\
124356 \\
123546 \\
123465
$$
Hopefully the generalization to arbitrary $n$ is clear.

If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an argument, but it can be converted to one); this is tight (for this example).

Let me also mention two well-known papers in the area:

Fredman showed that if there are $\Gamma$ many possible orderings, then you can find the correct one using $\log_2 \Gamma + 2n$ queries.
Kahn and Kim showed that if the potential orderings constitute all possible orderings extending some partial order, then $O(\log \Gamma)$ queries suffice.


Implications of Halting Problem being unsolvable?

I have a valid reduction below, but it is all very formal, and it's not the intuition I have for this kind of problem. When I consider, is this problem decidable/NP-Complete/etc, I frame it as a challenge: somebody says I bet BP is decidable!, and I reply Oh yeah?! Well, if that were true, then I could solve HP!. And then I show how I would do that: I suppose that BP is decidable, (i.e. I accept the challenge) and then I use that to solve HP. Granted, acknowledging this takes away some of your street cred, but it does work for me.

Here's a cheat sheet:

Show a reduction $f$ so that $HP \leq_f BP$: Hey I bet HP is decidable! Reply: Oh yeah?! Then I can solve BP like $f$
Show that Indset is NP-Complete by reduction from 3Sat, i.e. $3Sat \leq_f IndSet$: Hey I bet IndSet is easy! Reply: Oh yeah?! Well if it were easy, then I could solve 3SAT like so! I would take my arbitrary 3SAT instance $\phi$ and transform with $f$ to an IndSet instance $f(\phi)$ and then we'll let you solve $f(\phi)$ with your supposedly fast IndSet algorithm!

I hope that if these comments do not make you laugh, at least they help you internalize the notion of what a reduction is supposed to do, and how you are supposed to make one.

Now for a valid reduction. You have reduced HP to BP via a reduction $f$ (like the one I gave for your prevous question), so if somebody asked, does $M$ halt on $w$?, then you can reduce the HP instance $\langle M, w\rangle$ to the BP instance $A=f(M,w)$ (e.g. $A$ is a TM that simulates $M$ on $w$ given the blank tape), and ask your BP machine whether $A$ halts on the blank tape. So if BP were decidable, we would have an algorithm for HP, namely the one that I just described. But we don't. So BP is not decidable.


Is this problem decidable? (computation of $M_1$ longer than $M_2$ on every input)

Hint: Let $M_2$ be a machine that on input $n$ runs for $n$ steps roughly, and only consider machines $M_1$ that don't depend on their input. If you could solve your task then you could determine whether a given input-less machine ever halts.


A canonical representative, for this equivalence relation on matrices

Here are some ideas to get started. First, we can arrange that the diagonal is of the form $0 \cdots 0 1 \cdots 1$. This breaks the original problem into two new problems which are equivalent to each other. Let's concentrate on the part with zeroes on the diagonal. We can sort the rows according to Hamming weight, and can arrange the first row to be of the form $0\cdots 0 1\cdots 1$, say the one with minimal weight. If it is the only row having the same weight, then again we have broken the problem into two parts, and can continue recursively. If there are several rows with the same minimal weight, we can try tie-breaking using column weights, but this is not always enough. That's where this approach gets stuck, though perhaps one could be more creative and extract a normal form from these ideas.


When would the worst case for Huffman coding occur?

According to NIST:

  The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For this and other relations see Alex Vinokur's note on Fibonacci numbers, Lucas numbers and Huffman codes.

According to Alex Vinokur a sample Huffman encoding of a sample Fibonacci distribution was 2.3846 times longer than the original. See example 3.1.1.
As I understand it the inefficiency gets worse as the alphabet increases which is why wikipedia talks about unbounded inefficiency.

Note that is not the fact that a single character is prevalent that's the issue it is the distribution of the frequencies that's the problem.

A more useful description comes from your wikipedia quote:

  The worst case for Huffman coding can happen when the probability of a symbol exceeds $2^{-1} = 0.5$, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding;

This happens when a few letters in the alphabet are much more prevalent then others; a skewed distribution as described in the NIST quote above.
This is common in uncompressed bitmap files.

The reason for this is that:

  The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.

This is why run length coding or other forms of compression are usually applied prior to Huffman coding.
It eliminates many of the worst case scenario's for Huffman coding.
If it turns out the run length encoding is suboptimal it can simple be skipped.

Zip's deflate algorithm uses de-duplication + run length encoding followed by huffman encoding.

Huffman codes and binary trees
A Huffman code is closely related to a binary tree, however unlike a binary tree a Huffman code only stores its information in the leaf nodes.
The optimal input for Huffman compression is one where the output tree is fully balanced. I.e. where all letters of the Huffman alphabet are equally likely, but where more bits are used in the encoding than needed.
E.g. a text file where 8 bits per character are used even though only 64 different letters are in use. The distribution of letters in a typical language is much flatter than a Fibonacci sequence and thus well suited to Huffman.

Note that it is not necessary the case that all input letters for Huffman should be same size, they can very well be different sizes.
Usually this is not considered in order to simplify the implementation.

Strategies for avoid worst case behavior
Do a frequency analysis on your input data prior to Huffman encoding.


Here's a short method of transforming a BST $T_1$ into any other BST $T_2$ on the same set of keys, taken from notes written by Doug Hogan at Penn State:

  Define the right spine of a BST as the root and all descendants of
  the root that are reachable by following only right pointers from the
  root. A right-linear chain is a BST that has all n nodes in the
  right spine.

  Let $T'$ be the (unique) right-linear chain of $n$ keys.  Let $r = (r_1, r_2, ..., r_k)$
  be a sequence of right rotations that transforms $T_1$
  into $T'$, and let $r' = (r'_1, r'_2, ...,r'_{k'})$ be a sequence of
  right rotations that transforms $T_2$ to $T'$.  We know there exist
  sequences $r$ and $r'$ with $k, k' \leq n-1$, since a right rotation
  adds exactly one node to the right spine.  For each right rotation
  $r'_i$ let $l'_i$ be the corresponding left rotation.  Then, the
  sequence $(r_1, r_2, ..., r_k,l'_{k'},l'_{k'-1}, ..., l'_2, l'_1)$
  transforms $T_1$ to $T_2$ in at most $2n-2$ rotations.

...and here's another explanation, which gives a nice recursive algorithm.

Google search terms: binary search tree transform rotation proof.


The best answer I can give is that you are confused about the meaning of words. I tried to explain this already in another answer to you, so let me be more explicit this time.

To say

  type $A$ indexed by type $B$

and

  type $A$ indexed by values of type $B$

is the same thing. People say both of these to mean one and the same thing.

The important thing is to think of $A$ as a function with domain $B$ and codomain $\mathsf{Type}$ (the "type of all types" or a "universe of types"). So, whatever people say and however you are getting confused about "value" vs. "type" here, a dependent type is a function from a type (the indexing type) to the universe of types. Thus:

  A dependent type $A$ indexed by $B$ has as its domain the type $B$, therefore it takes as inputs values of type $B$.

You cannot index a dependent type by just a single value, that makes no sense. That would be like saying "the dependent type of lists of length 7". That is not dependent on anything because "7" is fixed. If you say "the dependent type of lists of length $n : \mathsf{nat}$" that is the same thing as saying "the dependent type of lists whose length is indexed by type $\mathsf{nat}$". Here $n$ is not fixed, it is just a sloppy way of introducing an unecessary variable. To be less sloppy, you would have to say "the dependent type which, for any $n : \mathsf{nat}$, gives the lists of length $n$". This is more correct because it explains that the dependent type is a function taking any $n$ to a type.

I hope that helps.

Just to be sure, let me also say explicitly that in set theory and ordinary mathematics the domain of a function is a set (and not an element of a set). Is that clear?


minimum travel from point to point with incremental steps

Interesting question. It is surprising that the answer depends only on $|x|+|y|$. For example, the same number of the steps is needed to reach $(1,1)$ or $(0,2)$.

The minimum step is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is even and nonnegative.
Here is an $O(1)$-time algorithm that returns the value described above, where least_n, i.e., $\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, is the least nonnegative integer $n$ such that $n(n+1)/2-(|x|+|y|)\ge0$.
def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

Given the number of steps $s$, the distance travelled is $1+2+\cdots+s=s(s+1)/2$.

The correctness of the formula and algorithm above comes from the following characterization.
Proposition. The minimum count of steps from $(0,0)$ to $(x,y)$ is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is nonnegative and even.
Proof. If we can go to $(x,y)$ in $n$ steps, the sum of some numbers between 1 and $n$ or their negations must be $x$ and the sum of the remaining numbers or their negations must be $y$, i.e.,
$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$
for some choice of all $\pm$'s. That means,
$$1+2+\cdots+ n - (|x| + |y|)$$
is nonnegative and even.
Now it is enough to prove that $(x,y)$ is reachable in $n$ steps if $n(n+1)/2-(|x|+|y|)$ is nonnegative and even. Let us prove it by induction on $n$.

The base cases, $n=0$ or $1$ means $(x,y)=(0,0), (0,1), (1,0)$. These cases are immediate to verify.
Suppose, as induction hypothesis, it is correct for smaller $n$'s. Now consider the case of $n\ge2$ with $n(n+1)/2-(|x|+|y|)$ nonnegative and even. We can assume $x$ and $y$ are non-negative; otherwise, for example, if $x$ is negative, we can change $x$ to its absolute value and reverse the direction of all steps that are parallel to $X$-axis.
There are three cases.

$x \ge n$.  Let $x'= x-n$. Then $$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$ is nonnegative and even. By induction hypothesis, we can go to $(x',y)$ in $n-1$ steps. To reach $(x,y)$ in $n$ steps, we continue $n$ units in X-direction.
$y\ge n$. This is symmetric to the case above.
$0\le x\lt n$ and $0\le y\lt n$. There are two subcases.

$x\ge 2$ and $y\ge 2$. Let $x'=(n-1)-x$ and $y'=n-y$. Then $|x'|\le n-3$ and $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ The parity of $(n-1)(n-1)/2-(|x'|+|y'|)$ is the same as $n(n+1)/2-(|x|+|y|)$, i.e, even. By induction hypothesis, we can go to $(x',y')$ in $n-2$ steps . Reversing all the steps, we can go to $(-x', -y')$ in $n-2$ steps as well. To reach $(x,y)$ in $n$ steps, we can continue with two more steps, $n$ units in X-direction and $n+1$ units in Y-direction.
One of $x$ and $y$ is $0$ or $1$. Let $g(k)=k(k+1)/2-(|x|+|y|)$. The smallest nonnegative integer such that $g(k)\ge0$ is  $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Since both $x$ and $y$ are $\lt n$ and one of them is $0$ or $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$
When $g(m)$ is even, $n=m$ by definition. When $g$ is odd, since either $g(m+1)=g(m)+(m+1)$ or $g(m+2)=g(m)+(m+1)+(m+2)$ must be even,  either $m+1$ or $m+2$ must be $n$. So, whether $g(m)$ is even or odd, we have $$n\le m+2.$$
Combing the two inequalities above, we have
$$n\le \frac{5+\sqrt{8n+1}}2,$$
which implies $n\le 6$.  Since X-direction and Y-direction are symmetric, let us assume $y=0,1$. Since $x\lt n$, $x\lt 6$. So it is enough to verify the cases where $(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$ It is easy to verify each of them.

$\ \checkmark$


Why do we do topological sorting to find shortest or longest path in weighted DAG?

By using this algorithm the expected time complexity would not be O(V+E) as we have to visit an edge multiple times.

queue.add(s)
while(the queue is not empty)
 for every adjacent vertex v of u
   if( dist[v] > dist[u] + weight(u,v) )
       dist[v] = dist[u] + weight(u,v)
       add v to the queue

But by using the topological sorting, we get the order in which the vertices should be traversed so that an edge is visited exactly once. So we could have guaranteed T.C. of O(V+E).

So to solve this problem to work in O(V+E) we use topological sort.

But I think this is not enough, we should also know why to use Topological ordering here and so that it helps in other problems.

Why Topological ordering ?

Topological ordering gives us the order like 0 1 2 3 4 5 then, once we reach a node in this ordering (let's say 4) then we've already computed the shortest path to it (4) as all the edges(as well as paths) of type u -> v (v = 4) and have already been visited.


There is no such PDA because $A$ is not context-free. This can be proved by pumping.


The language of TMs accepting some word starting with 101

First, it should be intuitive that L is not decidable.
Decidable means that you can can tell in finite amount of time if a word (in this case, coding of turing machine) is in L.
In m opinion, this should be one of the first things that should come in mind while solving these kinds of questions.

Note that there are infinitely many string that have $101$ as prefix (for example $101, 1011, 10111$, or in general, $101^i$ for $ i \geq 1$).

There are several problems with your solution.
First, the input for a TM for $L$ is $\langle M\rangle$, and not $\langle M, w\rangle$.
Second, what happens if $M$ doesn't halt on $w$? Your TM for $L$ also doesn't halt, and hence can't decide $L$.

You can show that $ L \in RE\setminus R $.

Show that $L \in RE $ by describing a TM $M'$ that recognizes $L$ (meaning, on input $\langle M\rangle$, if $ \langle M\rangle \in L$ then $M'$ accepts $\langle M\rangle$, otherwise $M'$ rejects or doesn't halt.

An easy way to show that $L\notin R$ is a reduction $f$ from the halting problem $HP$ to $L$, such that if $\langle M,w\rangle \in HP$ , then $f(\langle M,w\rangle) \in L$ (Hint: $f(\langle M,w\rangle)$ we accept any input if and only if $M$ stops on $w$).


Converting connected graph to disconnected graph by removing minimum vertices

The minimum number of vertices that have to be removed in order to disconnect the graph is known at the connectivity of the graph. Wikipedia outlines an algorithm for finding the connectivity of a graph. More efficient algorithms might exist.

A related problem is the vertex separator problem, in which we want to disconnect two specific vertices by removing the minimal number of vertices.


One natural approach goes as follows. Compute recursively for each node both the longest leaf-to-leaf path in the subtree rooted at the node, and the depth of the deepest leaf. From this information for the two children of a node you can compute the same information for the node itself. Once you have reached the root, you have obtained your answer.

The above only computes the length of the longest path, but you can actually extract the longest path itself from the data for each node. Details left to you.


SAT solvers solve the Boolean Satisfiability Problem. This is "the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE."

An example is find an assignment of truth values to variables $a,b,c$ such that
$(a \lor b \lor c)\land (\lnot a \lor \lnot b \lor c)\land (a \lor \lnot b \lor \lnot c)\land (\lnot a \lor b \lor \lnot c)$ is true. A SAT solver could return a solution such as $a=true$, $b=true$, $c=true$.

SMT solvers solve a more general problem, namely Satisfiability Modulo Theories. This is "a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality".
These theories could include "the theory of real numbers, the theory of integers, and the theories of various data structures such as lists, arrays, bit vectors and so on."

An example, given typed variables $x:int$ and $y:int$ and $f:int\to int$, asks whether the following is
$f(x+2) \neq f(y-1) \land x=(y- 4)$ satisfiable.
An SMT solver would answer yes, with solution  $x=-2$, $y=2$, $f(0)=1$
and $f(1)=3$.

Unification is a specific technique that takes two terms and finds a substitution that would make the terms equal. For example, given terms $book(x,\text{"Fishing"},2010)$ and $book(\text{D.~Smith},y,2010)$, unification would produce substitution $\{x\mapsto\text{D. Smith},y\mapsto\text{"Fishing"}\}$.
Unification is likely used inside SMT solvers.


Sorting using comparison is superlinear or sublinear?

In complexity theory, the input size is by convention (or definition, really) the number of cells the input takes up on a Turing machine tape.

The famous $\Omega(n \log n)$ bound does not adhere to this convention, though; $n$ is not input size but number of elements here. The input is (in general) longer than that since every element will have to be encoded on the tape in some way.

Generally, in sorting we consider the input to be the array (or list) of elements to be sorted. We don't pass the comparison matrix.

But you touch on an important point: complexity statements depend on machine model and input encoding. We usually default to TMs or RAMs depending on context and "reasonable" (i.e. not wasteful) encodings, but if there is any chance for ambiguity you need to state all the parameters.

For instance, the input size of sorting is $n$ is you consider RAMs with unit cost measure!


Patriot Missile Software Bug (Range Gate Calculation)

there is some scientific/ engineering analysis of this defect & its background by professionals eg this turned up by the SEERI institute, Software Engr Ethics Research institute, An analysis of the patriot missile system (note, some glitch with figure(s) at time of this writing). essentially the missile tracking logic is highly time dependent and relies on the clock being accurate to predict the missile location and intercept position and steering corrections. there are many other "classic" bugs in software that are related to clock logic. analysis of the failure also includes/ points to inadequate testing.

another reference cited in that article, Roundoff error and the patriot missile / Robert Skeel, SIAM News.

this particular defect is getting some attention lately as it was recently ranked in the 5 most infamous software bugs of all time and of course its related to missile defense technology, a hot topic during wars.


Execution time of NP and NP-Complete algorithms

Asymptotic (/Big-Oh/Landau) notation is not special to polynomial time algorithms, or indeed any class of algorithm. It is the standard way of communicating (asymptotic) running times, amongst other resources.

So we say that binary search runs in time $O(\log n)$ because that is what its asymptotic running time is, and hence the Searching problem in $\mathrm{P}$, but not it is in $\mathrm{P}$ and hence we can get some $O(\cdot)$ expression for it. The Tower of Hanoi problem has an $O(2^{n})$ algorithm for example (in fact $\Theta(2^{n})$), this happens to put it in the class $\mathrm{EXP}$ , but the asymptotic expression is still an evaluation of the running time, regardless of which class it is in.

Note the distinction here between problems an algorithms as well. A problem is in a complexity class, and algorithm has a running time. By extension we say that the problem can be solved in time "blah" because it has an algorithm runnning in that time. So we can't have an $\mathrm{NP}$-complete algorithm, only an $\mathrm{NP}$-complete problem. We can abuse the language a small amount an say we have and $\mathrm{NP}$ algorithm, but what we mean is that we have  a nondeterministic polynomial time algorithm, i.e. an algorithm that demonstrates that whatever problem it's for is in $\mathrm{NP}$, just as binary search is a polynomial time algorithm that demonstrates that Searching (the formally defined problem) is in $\mathrm{P}$. Then David Richerby's answer applies - they're just polynomial but on a nondeterministic machine, i.e. $O(n^{c})$ for some fixed $c$.

On the flip side, we can have an algorithm for an $\mathrm{NP}$ problem that is not the one that shows that the problem is in $\mathrm{NP}$. For example, there's an algorithm for the Travelling Salesman Problem that just tries all the possibilities. This algorithm has running time $O(n!)$. It's not the best algorithm, but it is an algorithm for an $\mathrm{NP}$-complete problem, and that's its running time expressed asymptotically.

Finally, $\mathrm{P}$ is a subclass of $\mathrm{NP}$, so all those "P algorithms" are also "NP algorithms" - they just don't use the nondeterminism.


Reduce the running by using doubly logarithmic tree

I will assume you are using parallel processing to achieve the advertised runtimes. Say algorithm B scales the size of P by a factor $c<1$. If we apply algorithm B $k$ times, the size of our problem will be $c^kn$. This will require time
$$\sum_{i=0}^{k-1}O(\log(c^in)/\log(\log(c^in)))=\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$
and
$$\sum_{i=0}^{k-1}O(c^in)=O\left(\frac{1-c^k}{1-c}n\right)$$
operations. Then an application of algorithm A will require $O(\log(c^kn))=O(k\log c+\log n)$ time with $O(c^kn\log(c^kn)=O(c^kn(k\log c+\log n))$ operations. For the overall operations to be $O(n)$, we need
$$\frac{1-c^k}{1-c}+c^k(k\log c+\log n)=O(1)$$
The only way for this to be constant with the $c^k\log n$ term is if $k$ depends on $n$. Then the $c^kk\log c$ term will shrink with $n$, since $\log c<0$. Taking $c^k=\frac{N}{\log n}$ for some positive constant $N$ gives
$$\frac{1}{1-c}-\frac{N}{(1-c)\log n}-\frac{N(\log \log n-\log N)}{\log n}+N=O(1)$$
As $n$ grows, we can see that this approaches $(1-c)^{-1}+N=O(1)$ from below. Plugging this into the expression for the runtime (sum of both parts) gives
$$O(\log n+\log N-\log \log n)+\sum_{i=0}^{k-1}O\left(\frac{i\log c+\log n}{\log(i\log c+\log n)}\right)$$
Since $\log c<0$, we can make the sum larger by doing $i\log c=k\log c$ on the bottom to get
$$O(\log n)+O\left(\frac{\frac{k(k-1)}{2}\log c+k\log n}{\log(k\log c+\log n)}\right)$$
Substituting the earlier expression for $k$ gives
$$O(\log n)+O\left(\frac{\substack{-\log (c) \log (N)+\log (c) \log (\log (n))+2 \log (N) \log (n)\\-2 \log (N) \log
(\log (n))+\log ^2(N)+\log ^2(\log (n))-2 \log (n) \log (\log (n))}}{2 \log (c)
\log (\log (N)+\log (n)-\log (\log (n)))}\right)$$
which simplifies to
$$O(\log n)+O\left(\frac{\log n \log \log n}{-\log (c)
\log (\log (N)+\log (n)-\log (\log (n)))}\right)$$
giving $O(\log n)$. That was tedious. Don't ask about the intermediate steps, I used the Wolfram Cloud.


It's your exercise, so you should solve it yourself... but I will give you two hints.

Study the methods used in Grammar for a language with 1/3 of a's.  They are helpful.
Use non-determinism.  Build a non-deterministic PDA.  (How do you think non-determinism might help here?)


Is the given language finite or infinite?

(0 U 1)((0 U 1)^p)((0 U 1)^p)(0U1))  is not a language, but a regular expression. Moreover, to be well-defined, you must specify what $p$ is.

Is $p$ a specific value?  Then, this expression generates a finite number of words -> it generates a finite language.

But maybe you look at the language generated by the above expression for any p? then, there will be infinitely many generated words.

you need to tell us what is $p$ and what is the language under consideration.


Decoding cyclic code, assuming we have no errors

Let us start with generator matrix $G$, a matrix of $k$ rows and $n$ columns where $n\ge k$. Given any input row vector $s$ of $k$ characters, we can generate the codeword for $s$, a row vector of $n$ entries by
$$w=sG$$
If given $s$, how can we get back $w$? Suppose we can find a matrix $G'$ of $n$ rows and $k$ columns such that
$$GG'=I_k$$
where $I_k$ is the identity matrix of $k$, we will have
$$s=sI_k=s(GG')=(sG)G'=wG'$$

So the question becomes how to find such matrix $G'$ from $G$. You should be able to find in your course material the procedure or technique to accomplish that. Note that $G'$ is not a square matrix. In general $G'$ is not unique, either.

Now suppose you are given a generator polynomial instead. You can form the generator matrix from the generator polynomial and proceed as above. There might be a shortcut procedure for generator polynomial because of its special form.


Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

It seems you're looking for a symmetric set similarity measure.  (Symmetric since, as you point out, $A$ should match $B$ as much as $B$ matches $A$.  Set similarity since each person's preference is defined by a set of objects.)

A number of these are used in the CS literature.  Probably the most common is Jaccard similarity, defined by $|A\cap B|/|A\cup B|$.  In your example, $A$ and $B$ have 7 elements in common, and there are 103 elements between them, leading to a similarity of $7/103$.  A similar metric is Braun-Blanquet similarity, $|A\cap B|/\max\{|A|,|B|\}$; in your example this gives $7/100$.  With these as starting points you may be able to find further metrics that capture what you want better.  For example, here's a list I found while writing this.

What's notable about these metrics is that they don't take each person's dislikes into account---the similarity is defined only by what's on their list, not what's not on it.  (So you may think it makes a better match if two people don't like fish.)  Incorporating this would require a universe of elements (so any element in the universe not on the list is considered a dislike).  In this case you can use the classic Hamming Distance.  You have other options as well, like Euclidean distance or even the Sørensen-Dice similarity.

One benefit of using one of the above, well-known similarity measures is that you can use known algorithms to compute nearest neighbors quickly.


Turing machines express all computation, so studying turing machines is studying computation in general; theorems that are true about all turing machines are true about all computations. Necessarily, these have to be extremely general and rather vague or weak theorems. If the only thing you know about a computation is that it's implementable using a Turing machine, that's very little knowledge to work with.

Finite automata are a very particular class of computations. Because they are so restricted, you can do less using a finite automaton, but you can say/know more about one. There are tons of very useful theorems that are only true for finite automata but not for arbitrary computations; algorithms and data structures for working specifically with finite automata. E.g., in practical terms, if you compile a regular expression to a finite automaton, you know for sure that it terminates in linear time on every input, you can optimize that automaton, you can think of very efficient ways to write finite-automata evaluators, seek ways to implement incremental evaluation, etc. - none of these problems are solvable or even make sense for "computations in general".

Think of the difference between turing machines and finite automata as the difference between all natural numbers and prime numbers. How would you answer if someone asked you why do we need to study prime numbers, when we already have the concept of natural numbers?


Why do derivation tree not make sense for context-sensitive grammars?

For context-free grammars, the order in which you execute rules does not matter. Formally, let

$\qquad \gamma = w_1 A_1 w_2 \dots w_{n-1} A_{n-1} w_n$

with $A_i \in N$ and $w_i \in T^*$ for all $i$. Then, any order of applying rules $A_i \to \alpha_i$ yields the same sentential form. Thus, it makes sense to identify $\gamma$ with a level in a syntax tree -- the children of all the nodes (if any) are independent of each other.

For context-sensitive grammars, this is not true. Consider this grammar¹:

$\qquad\begin{align*} S\ \ &\to AS \mid A \\ AS &\to a \\ SA &\to b \\ A\ \ \ &\to c \end{align*}$

Observe how the set of applicable rules changes as soon as you start applying them! Therefore, while you can still imagine a tree structure here, the children are no longer independent.

Also, you'd have to connect two nodes from higher levels each node -- and arbitrarily many for general CSGs. Since any symbol may influence the picking of many rules, this will give you a DAG, but no tree.

As has been aptly noted by commentes chi and fade2black, this grammar is not context-sensitive in the strict sense of the definition. I find it clearer to illustrate the issue; but still, this is a clearly context-sensitive variant:

$\qquad\begin{align*}
  S\ \ &\to AS \mid AB \\
  AS &\to CC \\
  SA &\to DD \\
  A\ \ \ &\to c \\
  B \ \ \ &\to d \\
  C \ \ \ &\to a \\
  D \ \ \ &\to b
\end{align*}$


Are link-cut trees ever used in practice, for max flow computation or other applications?

There is a paper titled "Dynamic Trees in Practice" which reviews the practical implementation.

The other categories that Link-Cut tree could be used efficiently is in Database Indexing.
You can find this in the book "Database Index Techniques".


Where am I wrong?: "countability" and "recursive enumerability"

Your algorithm for recursively enumerating any given set doesn't work since the bijection between a countable set $X$ and the natural numbers can be arbitrarily complicated. For example, consider the following set $X$:
$$ X = \{ P : \text{the program coded by $P$ doesn't halt on the empty string as input} \}. $$
The set $X$ is countable: there are only countably many programs. However, there is no computable bijection between $X$ and the natural numbers, since otherwise RE=coRE (as your argument shows; $X$ is coRE-complete).

Here is a more tangible example of a countable set for which there is no computable bijection:
$$ Y = \{ 2P : \text{program $P$ halts on the empty string} \} \cup \{ 2P+1 : \text{program $P$ doesn't halt on the empty string} \}. $$
If there was a computable bijection between $Y$ and the natural numbers, then you could solve the halting problem (how?).


anonymous lambda functions (functional programming)

In the lambda calculus, all functions (terms) are anonymous. This is an essential property of the lambda calculus: you can compose complex functions from simpler ones without giving them names.

In programming languages, it is in most cases desirable to give names to functions, because this is the way we think and it makes code readable for humans. But compilation eventually removes the names when producing an executable (if we disregard debugging information).

If a language allows expressing anonymous functions (that is functions without names), it can give an advantage to both programmers and compilers: Programmers can often write shorter code, and compilers can better optimize, knowing that an anonymous function is used just at the given place and not anywhere else.


Possible results of two programs running on a symmetric multicore system

x has 4 possible values throughout the execution of the program, but only two after execution is finished. x could be x = 2, or x = 0 + 1, or x = 2 + 1, or x = 0. If x = 0 + 1 executes first, then x = 2 executes second and x will be 2, but if x = 2 executes first, then x will be 3. But z could either receive 0, 1, 2, or 3 for x. Y is only ever either 0 or 2, with 2 being the value at the end always. So you have z = 3 + 2, z = 2 + 2, z = 1 + 2, z = 0 + 2, z = 3 + 0, z = 2 + 0, z = 1 + 0, or z = 0 + 0.


There exist countably many enumerable disjoint and inseparable sets

Let $\phi$ be an enumeration of the set of recursive partial functions.

For each $i\in\mathbb N$, let $X_i = \{ n\ |\ \phi_n(0)=i \}$.

These sets are pairwise disjoint by construction. Each $X_i$ is recursively enumerable but not recursive.

These sets are pairwise inseparable. By contradiction assume there exist $i\neq j$, and a recursive set $A$ with $X_i \subseteq A$ and $X_j \subseteq \mathbb N\setminus A$. We reach a contradiction as follows. The function

$$
g(k,y) = \begin{cases}
  j & \mbox{if } k \in A \\
  i & \mbox{o.w.}
\end{cases}
$$
is computable, hence $g=\phi_c$ for some $c$. Now
exploit the s-m-n lemma to define $h(k) = \mathsf s(c,k)$, so that
$\phi_{h(k)}(y) = g(k,y)$.
Since $h$ is recursive total, by the second recursion theorem for
some $k$ we have $\phi_{h(k)} = \phi_k$.
Let us take one such $k$.
Finally,

$$
\phi_k(0) = \phi_{h(k)}(0) = g(k,0) = \begin{cases}
  j & \mbox{if } k \in A \\
  i & \mbox{o.w.}
\end{cases}
$$

Now, the result above is either $j$ or $i$. If it is $j$, then $k\in X_j$, hence $k\notin A$, hence the result above is $i$ -- contradiction.
If it is $i$, then $k\in X_i$, hence $k\in A$, hence the result above is $j$ -- contradiction.


Partial path known in Single source shortest path problem

Your question is strongly related to the idea of macro-moves which are defined as follows: $M(p, q)=\langle p, n_1, n_2, \ldots, n_k, q\rangle$, i.e., as a list of successive states which are known to get to $q$ from $p$. Additionally, macro moves might guarantee that the path they store is also optimal, i.e., that the path $\langle p, n_1, n_2, \ldots, n_k, q\rangle$ is the shortest path between $p$ and $q$. Let us denote such macro-moves as $M^*(p, q)$.

In the following I'll assume you are interested in computing the optimal path from a start state $s$ to an arbitrary goal state $t$ ---as you actually mention the "shortest path" at the beginning.

So now, regarding your question:

In case that $M^*(p,q)$ is known to be a subpath of the optimal path from $s$ to $t$, or if alternatively, it is known that the optimal path from $s$ to $t$ does not go through $p$, then you can safely substitute each generation of $p$ in OPEN by $q$ with a cost equal to the cost of the path to generate $p$ plus the cost of the path $M^*(p,q)$.
In case none of the preceding conditions hold then you can still use the macro-moves but you have then to store each node in $M(p,q)$, but $p$ of course, into the OPEN list ---i.e., the intermediate milestones you mention.

Hold on! You might think then that the second case is a waste of time/space, but it ain't if you break ties in favour of nodes with larger $g$-values, i.e., while nodes in OPEN are sorted in increasing order of their $f$-value, breaking ties in favour of nodes with larger $g$-values place those nodes with larger $g$-values first ---within the same $f$-layer. This way, in case that an optimal path (as there might be several paths with the same cost and equal to the minimum cost) goes through $p$ there is an opportunity that you will find it without generating other descendants.

To see why, consider that a subpath of $M^*(p,q)$ is part of the optimal path from $s$ to $t$, $\langle p, n_1, n_2, ...,n_\ell\rangle$, such that $\ell\leq k$, and let $g(n)$ denote the cost of the path from $s$ to $n$ and $g(p, n_i)$ denote the cost of the path $\langle p, n_1, n_2, ..., n_i\rangle$ where $\langle p, n_1, n_2, ..., n_i\rangle\subset M^*(p,q)$. The second case suggests to insert into open $n_1, n_2, ..., n_\ell$ each with a cost equal to $g(p)+g(p,n_i)$, $1\leq i\leq\ell$. If the heuristic function is consistent (as you mention) there is a good opportunity that $f(n_\ell)=f(n_i)$, $\forall i, 1\leq i<\ell$. Now, breaking ties in favour of nodes with larger $g$-values, $n_\ell$ will be placed before the others so that A$^*$ will expand it first. If $f(n_\ell)$ equals the cost of the optimal path then A$^*$ will find the optimal solution with out expanding nodes $n_i$.

Maybe you think there are many "maybes and ifs" here but consider: first, breaking ties in favour of larger $g$-values is customary practice; second, inserting the intermediate states of $M^*(p, q)$ causes no harm so that proceeding as in the second case is usually a good idea.

Hope this helps,


Minimum Clique Cover - Mixed Integer Programming

I think I have some suggestions.
You can make a binary variable $e_{ij}$ per edge corresponding to if those two vertices are in a clique together or not. Being in a clique is a transitive property. $e_{ij} \wedge e_{jk} = e_{ik}$. This "and" constraint is expressible as a MIP. This can be achieved with the constraint $e_{ik} <= e_{ij}$, $e_{ik} <= e_{jk}$, $
e_{ij} + e_{jk} - 1 <= e_{ik}$ link. This is the polytope generated by the truth table vertices (0,0,0) (0,1,0) (1,0,0) (1,1,1).  This makes only vertex clique covers feasible. For maximizing edge weights you're good to go.

I don't have an elegant way to minimize the total number of cliques. Just maximizing the sum of all edges is a reasonable heuristic if heuristics are acceptable.
Another possibility is to take the sum of all the edges coming out of a vertex. This is the size of the clique it belongs to and is bounded by the total number of edges connected to that vertex.
$\sum_j e_{ij} = c_i - 1$, where $c_i$ is the size of the clique vertex $i$ belongs to. The sum over all vertices $\sum_j \frac{1}{c_i} = C$ is the total number of cliques $C$.
I don't have a good way to perform this inversion, except by MIP brute force.

This can be done by generating as many binary variables $a_{in}$ per vertex as it has neighbors, setting $\sum_n n a_{ni}=c_i$, enforcing that only one $a_{ni}$ is nonzero $\sum_n a_{ni} = 1$, and then making the objective $\sum_{jn}\frac{1}{n}a_{nj}$. This is rather dissatisfying to me and I hope there is a better way.


Are there any context-free languages that are not known to be in $\mathrm{DTIME}(O(n))$?

Theorem 1 in "If the Current Clique Algorithms are Optimal,
so is Valiant’s Parser" shows an explicit context-free grammar $G$ such that if $G$ can be parsed in linear time (or even a bit slower), then there's a surprisingly fast algorithm for the $k$-clique problem. As the paper says, no such algorithm for $k$-clique is known to exist and it would be a breakthrough if it was discovered; therefore, there's no known linear-time algorithm for this grammar $G$.


Some explanations needed about Negation in Gentzen's Natural Deduction rules

I'm guessing your first rule is:

  \begin{align*}
&[A]\\
&~~\vdots\\
&~\bot\\
&\overline{\lnot A}\qquad (I\lnot)
\end{align*}

This means that in order to derive $\lnot A$ one must first assume $A$ (that is $[A]$) and derive a contradiction ($\bot$), the dots between mean a finite number of steps.

  $$ \frac{A \quad \lnot A}{D} \qquad (E\lnot) $$

This latter rule with $D$ seems to be ex falso quodlibet, since:

$$ \frac{A \quad \lnot A}{\bot} \qquad (E\lnot) $$

therefore:

$$ \frac{\bot}{D} $$

it says that you can derive anything (some $D$) from a contradiction.

Those $(I\circ)$ and $(E\circ)$, where $\circ$ is some operation mean Introduction-Elimination rules. In Gentzen's formulations all rules come in pairs.


Choosing a production with $\lambda$ in Context-Free Grammars

I think you have understood this backwards. The CFG defines the language. All strings that can be derived by using the rules defined in the CFG are present in the language. The empty string itself is a terminal variable. You would substitute it in the string that you're deriving and is just empty.

What you are arriving at with the parse trees is called ambiguity of the grammar that you have defined. When the same string can be derived in more than one leftmost derivation, then the grammar is ambiguous. You could use two different substitutions and still arrive at the same string. So, yes, you could use either derivation, but the string itself does not change.

I would say the formal way to derive your string in exactly one particular way is to use a grammar without ambiguity.


Are these three subset sum problems hard? How to solve them?

Your work is mostly correct:

SSP1 is clearly in NP. Moreover, it is NP-hard by reduction from SUBSET-SUM: given an instance of SUBSET-SUM, reduce it to the corresponding instance of SSP1 with $k = n$.
SSP2: Let $m$ be the number of negative elements in $\{a_1,\ldots,a_n\}$, and let $S$ be the sum of the $\min(m,k)$ smallest of them. Check whether $S \leq \sigma$. This is a polynomial time algorithm.
SSP3: Can be reduced to SSP2 by negating the set and $\sigma$. (We can also solve it directly just like SSP2.)


Max sum cyclic path of fixed length in matrix

problem with this is that you can't be sure [which path] you can come from.

Indeed. So do it exhaustively for all feasible paths. That is, work on subproblems where you vary $t$ up to $K$, and store their results, at least for a little while. It should be possible to discard partial results corresponding to clearly bad solutions, and consume just $O(t^2)$ memory to remember the cells we should avoid.

Naively one could access a dense matrix opt by dereferencing opt[i][j]. To access the $n$th variant of a matrix with sparse edits applied to it, first probe a mapping to see if edit[(i, j, n)] exists, and if not fall back to dereferencing the dense matrix in the usual way. You may find it convenient to build up a path for the $n$th variant as a list of (i, j, value) tuples.

Additionally, we can decompose into the "outbound" and "inbound" sub-problems. Visiting a cell essentially sets that cell to zero, so each candidate outbound path gives rise to a new matrix. In the end the outbound path length will be $\frac{K}{2}$ and each new matrix gives rise to another $\frac{K}{2}$ inbound problems. The inbound solver would probe a hash map, and would add zero to the reward for any cell appearing in the outbound path.

Consider the Manhattan distance between current cell and origin. A decent heuristic for 1st stage search would be to make that distance strictly increasing on the outbound path, then strictly decreasing on the inbound path, which reduces the search space a little. Your idea about storing optimal values is a good one for further pruning the search space.

Please do keep us posted on your progress, especially on any pruning techniques that seem promising.


Why is this language over {a,b,c} regular?

All you need to keep track of is the value "number of $a$s seen minus number of $c$s seen", modulo 3 – call that $X$. There are only three different values that $X$ can take. When you see the next character of the input, it's either $a$, $b$ or $c$. Think about how each one affects $X$ and you should be very close to a 3-state automaton that accepts the language you're interested in.


Two Step Verification. 4 digits vs 6 digits

The number of digits in such a one-time password is determined by the acceptable risk that an attacker who doesn't receive the verification code will be able to guess it (lucky guess). This risk takes into account several factors:

the probability that an attacker will be able to guess;
the negative consequences of an correct guess by an attacker;
the probability and the negative consequences if the code is too long and this discourages the user to use the service.

For an $n$-digit code, if there is a single valid code and the code is generated at random, then the probability of a lucky guess is $10^{-n}$. That's 1/10,000 for a 4-digit code, 1/1,000,000 for a 6-digit code. These are usually acceptable figures when the one-time code is a second factor (usually complemented by knowing a static password or possessing a physical device); they would be grossly insufficient if the code alone was enough to access a service.

When the code is sent from a remote server to the user's device, there is generally a single valid code which is randomly generated. Some one-time password schemes don't require communication between the server and the user's device, but instead have both sides generate a pseudo-random code in the same way using a shared secret key and a counter. In this case, there are usually several valid codes, to allow for desynchronization between the client and the server; this requires a slightly longer code to compensate for the increased number of possible lucky guesses.


Given your definition, the answer is "no". JavaScript syntax is not a subset of JavaScript's literal syntax. The fact that a value a literal represents can be produced by evaluating the literal is what makes a literal a literal and is true in any language. The only real difference is JavaScript has a richer literal syntax than many common programming languages, though this is certainly not a rare thing.

The answer is "no" for pretty much any reasonable definition that doesn't make practically every language "homoiconic".

My impression is there is not a clear consensus of what "homoiconic" means within the Lisp community. Part of that is it seems many Lispers are confused1 about "homoiconicity"2. I recommend this article which goes over the variety of possible definitions of "homoiconic" and the issues with each. As the title of that article is "Don't Say 'Homoiconic'", this suggests worrying about whether a language is "homoiconic" is not a great idea and you should be more specific about what it is you are care about.

If we use the definition referenced in the article, namely "having the internal and external representations be the same", then this definitely doesn't apply to JavaScript (to the extent that it even makes sense). It arguably doesn't apply to Lisp either, but there are various ways where Lisp gets closer to this. One small indicator is that Lisp's eval takes in Lisp lists while JavaScript's takes in strings. This separation holds for the actual Lisp implementation as well as parsing is viewed as conceptually outside of the implementation and so the implementation conceptually works upon Lisp lists. This has non-trivial consequences like being able to provide circular syntax and an abstract syntax graph in general.

1 Frankly, understandably so as the explanations tend to be vague. There is also, at this point, a lot of misinformation.2

2 There are many definitions floating around that whatever "homoiconic" should mean if anything doesn't mean these things such as "supports higher-order functions".


How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I think you are on the right track but things need to be made more explicit. First, what machine exactly is $A$? Any machine? Where does your contradiction appear?
First, you need to explicitly say that $A$ is a machine for an undecidable language, for example, let $A$ be the universal machine, that on inputs $\langle M \rangle w$ simulates $M$ on $w$, and accepts if $M$ accepts $w$.
Then, say explicitly that $S$ is a decider (a machine that always halts), and include the simple extra steps that show that $S$ accepts $\langle M \rangle w$ if and only if $w \in L(M)$. Finally, recall that $S$ is then a decider for a problem we already know is undecidable; a contradiction.
Edit: Sorry, it seems that $A_{TM}$ is standard notation for the universal machine. Forget about that comment if that is the notation used in your context.


Would it be possible to use the cloud for RAM?

Network latency is orders of magnitude too high for a remote server to usefully share its RAM directly, even if you could cobble together a virtualization layer to make it work.  However, today's network speeds are high enough that remote RAM based key/value stores like memcached can compete favorably with hammering a local database due to insufficient local memory for caching.

Since this question has the virtual-memory tag, I'll also point out that network servers (which is what "cloud computing" is the latest name for) have been used for virtual memory (also known as "swap") since the diskless workstations of the late 1980's.  These machines are called "thin clients" today.


It is an open problem if you can do selection with $O(n)$ time and $O(1)$ extra memory cells without changing the input (see here). But you can come pretty close to this.

Munro and Raman proposed an algorithm for selection that runs in $O(n^{1+\varepsilon})$ time while using only $O(1/\varepsilon)$ extra storage (cells). This algorithm leaves the input unchanged. You can pick any small $\varepsilon>0$.

At its core, Munro and Raman's algorithm works as the classical $O(n)$ algorithm: It maintains a left and right bound (called filter), which are two elements with known rank. The requested element is contained between the two filters (rank-wise). By picking a good pivot element $p$ we can check all numbers against the filters and $p$. This makes it possible to update the filters and decreases the number of elements left to check (rank-wise). We repeat until we have found the request element.

What is different to the classical algorithm is the choice of $p$. Let $A(k)$ be the algorithm that solves selection for $\varepsilon=1/k$.  The algorithm $A(k)$  divides the array in equally-sized blocks and identifies a block where many elements are, whose ranks are in between the filters (existence by pigeon-hole principle). This block will then be scanned for a good pivot element with help of the algorithm $A(k-1)$. The recursion anchor is the trivial $A(1)$ algorithm. The right block size (and doing the math) gives you running time and space requirements as stated above.

Btw, the algorithms you are looking for, were recently named constant-work-space algorithms.

I am not aware of any lower bound.


Approximate value iteration for continuous state space MDPs

There are two primary methods to deal with continuous state MDPs.
1. State-space discretization.
2. Value function approximation.
As for value function approximation, you can either go for a deterministic/stochastic black-box model or opt for fitted value iteration. You can find the algorithm for the same in pages 10-13 of this link.


String matching algorithm - check if a string matches a pattern

There are various algorithms for pattern matching in string.

Exact String matching algorithms

Brute Force
Rabin Karp
Boyer-Moree
KMP
Aho Corasick etc.

Approximate String Matching Algorithm

Approximate String matching is applied in text searching, pattern
recognition and signal processing applications. For a
text T[1..n] and pattern P[1...m], we are supposed to
find all the occurrences of pattern in the text whose edit
distance to the pattern is at most K. The edit distance
between two strings is defined as minimum number of
character insertion, deletion and replacements needed to
make them equal.

Approximate string matching problem is solved with the
help of dynamic programming.

You can have a look through all these algorithms.
These algorithms will take optimum complexity like O(m),O(n+m) (in case of KMP for example).


Hamming Weight to find the sum of 1 bits in the range between A and B inclusive

The basic idea is not to manually go over all numbers from $A$ to $B$. For example, suppose $A = 0$ and $B = 2^n-1$. The $k$th bit of a number in $\{0,\ldots,2^n-1\}$ is $1$ exactly half the time, so the total number of $1$s is $n2^{n-1}$. Similarly, if $A = x2^n$ and $B = x2^n + 2^n-1$ then the number of $1$s is $n2^{n-1} + 2^nH(x)$, where $H(x)$ is the Hamming weight of $x$. In the general case, you have to decompose the range $[A,B]$ into a small number of ranges of the form just described. You should be able to do this with at most $2n$ or so ranges, where $n$ is the length of $B$ in bits.


Why postfix arithmetic expression is not ambiguous?

With operator precedence infix is not ambiguous.  Brackets are a convenience but not necessary to form an expression.  However when parsing you have to resolve each precedence level in precedence order (e.g., $^,[*,/],[+,-]$).

A postfix expression is written exactly in computation order:
$e0\ e1\ o1\ ... (ek\ ok) ... eN\ oN$
Computation is

$r[1] = o1(e0,e1)$
...
$rk = ok(r[k-1],ek)$
...
$rN = oN(r[N-1],eN)$

Infix is subjectively thought by many to be easier for humans to read and write.

There is no reason why brackets couldn't be added to postfix or prefix with the obvious meaning, but it is generally not done as those formats are intended for machines rather than humans.


It is correct that writing the Buchi automaton to memory takes exponential space.....which is why you don't do that.

The construction for the Buchi automaton is however very regular and can be done in a forward manner. This allows you to construct it on-the-fly while you search for an accepting lasso in the product between the Buchi automaton and $T$.

In this way, you can find an accepting lasso in NPSPACE (it is exists): you build a Turing machine that builds the product on-the-fly, searches for a lasso by non-deterministically guessing which transition in the product to take, and non-determinstically guesses the lasso knot to store (which, w.l.o.g., could also be the required accepting state). If it finds a path to such a knot and then a path from the knot back to the knot, you know that there is a word in the product.

To make this algorithm always terminate, you also have a counter to keep track of the number of transitions observed so far. If it exceeds two times the size of the product, then the algorithm aborts with a "no" answer. Such a counter also only needs space polynomial in the size of the LTL formula.

Since PSPACE=NPSPACE, it follows that you only need polynomial space for such a Turing machine.


There is a definite dearth of literature on how to add let bindings to PTSes or dependently typed systems, though I do seem to recall this reference:

Paolo Severi, Pure Type Systems with Definitions.

From a theoretical perspective, you want to have the intuitive rule:

$$\frac{\Gamma\vdash t[M/x] : A[M/x]\qquad \Gamma\vdash M:B}{\Gamma\vdash\mbox{let}\ x :B :=M\ \mbox{in}\ t\ :\ A} $$

But this doesn't help explain much about how to perform type checking and conversion, which is a quite subtle subject.


It is equivalent to the set cover problem. You can regard each vertex in the right side as a set of its neighbors in the left side. In your example, $e,f,g$ correspond respectively to the sets $\{d\},\{d\},\{a,b,c,d\}$. Now a minimum vertex cover in your problem is equivalent to a minimum set cover.


Amdahl's Law is perhaps most associated with computer architecture (Gene Amdahl was a computer architect).  Although initially applied to the potential speedup from partial parallelization of a task, the formula applies to the benefit from any partial improvement.

In its general form, it can be applied to many different types of problems.  E.g., the improvement in voter turn out by getting a fraction of potential voters to always vote.

Since it is a rule of thumb intended to compensate for excessive expectations from dramatic improvements in part of a system, it is most useful when the improvement factor is large and is intended more for quick estimation (and generally the best case--though sometimes an improvement can unexpectedly benefit other aspects) than an exact measurement (as systems tend to have complex and subtle interactions).  (Quick estimation facilitates quick pruning of paths of exploration.)

As a mathematically based rule of thumb, it is not an especially deep topic (rules of thumb based on history, economics, etc. are generally more susceptible to discussion), though Gustafson's Law points out that context is important.  However, Amdahl's Law is an important corrective to optimism with respect to dramatic (but partial) improvements.


Measuring the Probability of Error for a Potential BPP Algorithm

The class BPP (and related classes such as RP, coRP, and ZPP) deal with decision problems. This means the algorithms corresponding to these classes may only produce "yes" or "no" answers. This notion does not quite match your algorithm, which is actually solving a search problem (i.e., the solution set is a subset of some arbitrary set of outputs).

At any rate, what you are actually trying to refer to as a "BPP algorithm" is a randomized algorithm with two-sided error. Such an algorithm produces correct and incorrect answers for both instances that have and do not have a solution, and, usually, it is also required that the algorithm be correct "most of the time" (where this is defined by bounding the error by some probability constant).

However, your algorithm has not actually two-sided nor one-sided error. This is because your problem instances all have solutions (and your algorithm does not claim otherwise). Thus, your algorithm only really fails to find solutions with some probability, which makes it have zero-sided error, that is, it always outputs correct answers, but may also output a "could not find" or "don't know" answer (with some bounded probability). As a result, what you have is a Las Vegas algorithm, which is a type of probabilistic algorithm with applications well beyond complexity theory. Incidentally, the alternative definition for a Las Vegas algorithm (i.e., a probabilistic algorithm with expected polynomial time complexity) is quite consistent with your remark that you need to run your algorithm "a bunch of times until it produces the solution."

On a side note, the complexity class associated with decision problems solvable with zero-sided error probabilistic TMs is the class ZPP (though this is only tangential to your question since, as I have explained above, you are not working in the realm of decision problems anyway).


difference between multilayer perceptron and linear regression

If you have a neural network (aka a multilayer perceptron) with only an input and an output layer and with no activation function, that is exactly equal to linear regression. In your case, each attribute corresponds to an input node and your network has one output node, which represents the target value you're trying to predict.

However, most neural networks are more complex. Usually, the input nodes first feed into a layer of hidden units. These hidden units take the sum of their weighted inputs, as the output node did in the simple network, but apply an activation function to them (usually a sigmoid function which compresses the domain $(-\infty, \infty)$ to $(-1, 1)$). The output nodes are each a linear combination of all the nodes in the hidden layer. These days there are even effective methods to train networks with many hidden layer each feeding into the next.

Practically, there are two important differences:

Linear regression (and the linear network with no hidden layers) have a closed form solution. You can compute the optimal model directly and efficiently. Once you add an activation function, and possibly hidden layers, you cannot compute an optimal model directly anymore, and you're forced to use an iterative solution: an algorithm that goes through steps, usually improving the model with each step. There are no guarantees that the process will converge, or that you'll find the best model. It's also a lot slower than the direct solution.
The flipside is that with a hidden layer and activation function, you have a much more powerful model. You can even show that so long as you have enough nodes in your hidden layer, you can approximate any continuous function with an abritrarily small error. Linear regression and the simple neural network can only model linear functions. You can however use a design matrix (or basis functions, in neural network terminology) to increase the power of linear regression without losing the closed form solution.

Glossary

Neural Network: A collection of nodes and arrows. Computation flows through the network along the arrows. The value of node $n$ is determined by the nodes which have arrows from them to $n$. Each arrow contains a weight which determines the strength of the connection.
Activation function: A node in a neural network works as follows: it takes all the values of all nodes which are connected to it by an arrow, multiplies all these by their respective weights, and then sums them. It then passes this sum through an activation function to ensure that its output stays in the range $(-1, 1)$. Common activations functions are the logistic function and tanh.
Hidden layers: The nodes and arrows in a neural network can be arranged in any way, but the most common arrangement is in layers. This is called a multilayer perceptron. It groups the nodes into layers. Each node in layer $i$ takes all nodes in layer $i-1$ as input. The nodes in the first layer are the input nodes and the nodes in the last layer are the output nodes. The rest of the layers are called hidden layers.

The following image comes from this tutorial.


Upper bound and lower bound of a custom function T(n)

For $n$ satisfying $\log n > 1$, we have $\log^* \log n = \log^* n - 1$ (exercise). On the other hand, $\log \log^* n $ is much smaller than $\log^* n$. Hence $\log \log^* n = o(\log^* \log n)$.


There isn't going to be a fast algorithm for this problem.

The class of graphs you're dealing with is, in some of the literature, called grid graphs.  That is, they're finite induced subgraphs of the infinite graph with vertices $\mathbb{Z}\times\mathbb{Z}$ with an edge from $(x,y)$ to $(x',y')$ if, and only if, $|x-x'|+|y-y'|=1$.

Itai, Papadimitriou and Szwarcfiter (Hamiltonian Paths in Grid Graphs, SIAM Journal on Computing, 11(4):676–686, 1982) showed that it's NP-complete to determine whether a grid graph has a Hamiltonian path. Your problem is NP-hard (under Cook reductions, and possibly also under the more usual Karp reductions): if you can determine the length of the longest path from a vertex, just do that for each vertex in turn and see if any of the longest paths is Hamiltonian.


This is just Bubble-Sort in disguise. Each time, you get the biggest element pushed to the end of the array, then you sort the remaining of the array.

Your recurrence is correct.

An upper bound would be $T(n) = O(2^n)$.

Proof: For large enough $n$, we have $T(n)\leq 2^n$. This is the base case for induction. Induction hypothesis is $T(n)\leq 2^n$. So, we have $$2\sqrt{2^n}+\frac{2^n}2+O(1)\leq 2^n$$.


The language $\{ww \mid w \in \{0,1\}^{*} \}$ is not a CFL

You're assuming that, when you expand $S\to S_1S_1$, the two copies of $S_1$ must be expanded in the same way, to give two copies of some string $w$. But it doesn't have to be that way.  For example, you could do
$$S\to S_1S_1 \to 0S_1S_1 \to 0 S_1 \to 01S_1\to 01\,.$$


Relationship between complexity classes XP and W[1]?

1) Yes, you are right: W[1] is a subset of XP. As you noticed, $k$-clique is in XP. The class W[1] is (usually by definition) the closure of that problem under FPT-reductions. XP is closed under these reductions. Hence the subsetship.

2) Citing another answer of mine, here is a bit of intuition about XP:

  The practical importance of XP is as a door to parameterized
  complexity analysis. Once a problem is recognized as belonging to XP
  it makes sense to investigate its exact parameterized complexity. If
  it does not even belong to XP, parameterized analysis doesn't make
  much sense. It can also be argued that in that case the
  parameterization is not meaningful.

In that sense, XP is the hardest intractable class of parameterized complexity theory. In an even fuzzier sense, on the very opposite side of the spectrum, W[1] is the easiest parameterized version of NP.

Gaining an intuition for W[1] is not exactly made easy (in the past I tried in this answer). As said, it is usually defined by completeness of a problem (like $k$-clique). Definitions using machine models exist (e.g. Chen, Flum, Grohe: Machine-based methods in parameterized complexity theory. TCS 339(2-3), 2005). But that does not imply they are suitable for entry-level understanding of the class. I suggest you just take W[1] as the sum of the facts you know about it.


How many times can you divide a list of n elements in 1/2

You haven't explained what "divide in half" means, but let's assume that it means to divide the list into two halves of as equal size as possible (equal if the number of elements is even, almost equal if it's odd).

You can draw recursive "division in half" as a tree. The root is labelled by the original number of vertices, $n$. A node labelled $1$ is a leaf. Any other node labelled $m > 2$ has two children labelled $\lfloor m/2 \rfloor$ and $\lceil m/2 \rceil$ (this is the "division in half"). As yemelitc shows in their answer, the number of leaves is $n-1$; this is irrespective of the division being "in half". On the other hand, the depth of the tree (number of edges in longest path from root to leaf) is $\lceil \log_2 n \rceil$. You can try to prove this in the case where $n = 2^k$ (you can use induction on $k$).


Best data structure for storing an ordered list, where each item is located on a separate server?

A standard approach is to have a distributed data structure, and then use a cache for efficiency.  The cache remembers the results of common queries; if you ask the same query again, and the underlying data structure hasn't changed, then you can return the same remembered answer without needing to re-compute it.

For instance, you might store the items spread across networked machines however you like, as a singly linked list.  Then, you'd have a single machine M that is responsible for keeping a cache of the 10 items at the head of the list.  Each time you insert a new item to the head of the list, you also need to notify M to let it know to invalidate its cache.  (As an optimization, instead of throwing away all cached data, M might be able to update the cached information when it receives a notification -- though this does introduce some additional concurrency challenges.)

Now any attempt to read the first items from the queue goes first to M, which can check whether it has the answer cached, before traversing the linked list through the network.

You'll then need to analyze how strict your consistency requirements are.  Do you require that M always return the absolutely correct result?  Or can the cache be temporarily inconsistent with the backing data structure for a short period of time?  That will affect whether you need to use coordination mechanisms like 2-phase commit or whether you can use simpler, higher-performing mechanisms.

I've described this in a particularly simple form, but you can generalize to (a) other backing data structures (not just a singly linked list), and (b) other caches for other kinds of queries that might be performed (not just the top 10 items from the head of the list).


What is a bicriteria approximation algorithm?

I'll expand on the answer by Yuval Filmus by providing an interpretation based on multi-objective optimization problems.

Single-objective optimization and approximation

In computer science we often study optimization problems with a single objective (for example, minimize f(x) subject to some constraint). When proving, say, NP-completeness, it is common to consider the corresponding budget problem. For example, in the maximum clique problem, the objective is to maximize the cardinality of the clique, and the budget problem is the problem of deciding whether there is a clique of size at least k, where k is given as part of the input to the problem.

When it is not possible to compute an optimal solution efficiently, as in the case of the maximum clique problem, we seek an approximation algorithm, a function that outputs a solution within a multiplicative factor of an optimal solution. You could also consider an approximation algorithm for the budget problem, a function that outputs a solution that satisfies f(x) ≥ ck in the case of a maximization problem, where c is a number less than one. In this situation, the solution may violate the hard constraint f(x) ≥ k, but the "severity" of the violation is bounded by c.

Multi-objective optimization and bi-criterion approximation

In some cases, you may want to optimize two objectives simultaneously. For a rough example, I may want to maximize my "revenue" while minimizing my "cost". In such a situation, there is no single optimal value, as there is a tradeoff between the two objectives; for more information, see the Wikipedia article on Pareto efficiency.

One way of turning a two-objective optimization problem into a single-objective optimization problem (for which we can reason about the optimal value of the objective function) is to consider the two constraint problems, one for each objective. If the problem is to simultaneously maximize f(x) while minimizing g(x), the first constraint problem is to minimize g(x) subject to the constraint f(x) ≥ k, where k is given as part of the input to this single-objective optimization problem. The second constraint problem is defined similarly.

An (α, β)-bicriteria approximation algorithm for the first constraint problem is a function that takes a budget parameter k as input and outputs a solution x such that

$f(x) \geq \alpha k$,
$g(x) \leq \beta g(x^*)$,

where $x^*$ is a solution that achieves the optimal value for g. A bicriteria approximation algorithm for the second constraint problem outputs a solution such that

$f(x) \geq \alpha f(x^*)$,
$g(x) \leq \beta \ell$,

In other words, the bicriteria approximation algorithm is simultaneously an appoximation for the budget problem in the first objective and the optimization problem in the second objective. (This definition was adapted from page four of "Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints", by Iyer and Bilmes, 2013.)

The inequalities switch directions when the objectives switch from maximum to minimum or vice versa.


Finding set of disjoint sets with additional value optimization

Your problem is polynomially equivalent to the maximum-weight independent set problem problem, and the standard results for that problem apply directly to your problem as well.

If all the values were the same (say, $v=1$ for all pairs), then your problem would equivalent to the independent set problem.  In particular, treat each pair as its own vertex, and build an undirected graph $G$ where you have an edge between two pairs if they are disjoint.  Then the solution to your problem is exactly the largest independent set in $G$.    One can also construct a reduction the other way as well: given any undirected graph $G$, we can form an instance of your problem by construct a set corresponding to each vertex of $G$ (namely, the set of edges incident on that vertex), each of value 1; then the solution to your problem is the maximum independent set of $G$.

The independent set problem is NP-complete, so it follows that your problem is NP-complete as well.  Therefore, you should not expect any polynomial-time solution to your problem.

Because you allow arbitrary values to be associated with each set, your problem is basically equivalent to a slight generalization of the independent set problem, namely, the maximum-weight independent set problem.  Each vertex has a weight associated with it, and the weight of an independent set is the sum of the weights of the vertices in the independent set, and the problem is to find the heaviest independent set in the graph.  This is obviously at least as hard as the standard independent set problem, so also NP-complete.

Fortunately, there are standard algorithms for the independent set problem, and they can be extended to the maximum-weight independent set problem as well.  For instance, you can formulate the problem as an integer linear programming (ILP) instance and then try to solve it using an off-the-shelf ILP solver.  There are also exponential-time algorithms for independent set whose running time is asymptotically faster than $\Theta(2^n)$; I don't know whether they extend to the maximum-weight independent set problem as well, but you could check the literature to see, if this is of interest.  You could try applying them to your problem.

Unfortunately, the independent set problem is known to be hard to approximate to within a constant factor (unless P = NP), so you should not expect efficient approximation algorithms for your problem, either.


Reducing the Hamiltonian cycle to the travelling salesman problem and self loops

Suppose your original graph $G$ has a Hamiltonian cycle $C$.
Then the cost of the tour induced by $C$ in the new graph $G'$ you defined is indeed $0$ and conversely, any TSP tour of cost $0$ can only use edges of cost $0$ as you did not introduce any edges with a negative cost.
Adding the loops does not change this, so the reduction works out if we are willing to allow non-simple graphs which isn't done usually as the definition of the TSP asks for a tour visiting each vertex exactly once, i.e. no valid tour would include loop edges anyways.
Given this, we also see that you can remove the loop edges in $G'$ to make it a simple graph to obtain an equally valid reduction.
From a technical standpoint this doesn't make much of a difference but since people like simple graphs, I would personally prefer the reduction yielding a simple graph.


Writing a Context-Free-Grammar using Backus Naur Form for a for-loop?

I've usually seen it expressed as something like:

forExpression ::= for ( <declExpression> <expression>; <expression> ) <blockStatement>

blockStatement ::= <statement> |  { <statementlist> }

statement ::= <declExpression> | <forExpression> | <ifExpression> | ...

<declExpression> includes the semi colon

You want to be very careful of the details like where you define where things like the semi colon are required,

In your <number> you don't have any priorities set up, there is also no option for parenthesis, ...

Creating a good CFG is hard which is why so many languages start out as a dialect of C and just take that grammar and adapt it.


A < HPL < Complement(A) What can you say about A and Complement(A)?

Your analysis appears to be correct. But some clarity may help you.
Let's analyse each case and check whether it is consistent with given information.
As $\text{HPL} \leq \overline{A}$, $\overline{A}$ cannot be finite or recursive.

\begin{array}{|l|l|}
\hline
\textbf{If A is }  & \textbf{Then }\overline{A} \textbf{ is}\\
\hline
\mbox{Finite} & \mbox{Contradiction - }\overline{A} \text{ has to be FA; Violates HPL} \leq \overline{A} \\
\hline
\mbox{Recursive} & \mbox{Contradiction - }\overline{A} \text{ has to be recursive; Violates HPL} \leq \overline{A}\\
\hline
\mbox{Recursively Enumerable} & \text{Non-Recursively Enumerable}\\
\mbox{but not Recursive} & \\
\hline
\mbox{Non-Recursively Enumerable} & \mbox{Contradiction - Violates } A \leq \text{HPL}\\
\hline
\end{array}

You can now infer countability based on this information.


It isn't a matter of implementation. It's a matter of different approaches to parsing that unfortunately have similar names.
NFAs and DFAs (finite-state machines) can only recognize regular languages. Regular expressions are a way of specifying regular languages, and they can be compiled into efficient NFAs or DFAs that recognize the language. This is all taught in undergraduate CS courses.
The so-called "regexes" in Perl and its many imitators have a name that sounds like an abbreviation of "regular expression", and they syntactically resemble the regular expressions of sed and awk, but they are not regular expressions. They are really specifications of backtracking parsers. Backtracking parsers aren't limited to recognizing regular languages. (The name "regex" is Larry Wall's fault. He made a deliberate decision to not call them "regular expressions" because he knew that they weren't, but he should have invented an entirely different name.)
You don't need a Jurassic implementation of NFA/DFA based regular expression matching; modern maintained libraries are available for popular languages. But they lack many features of Perl-style regexes, and they don't offer much in exchange. They certainly have much better worst-case performance, but the pathological worst cases of backtracking parsers can be fixed by modifying the regexes, without losing the extra flexibility of backtracking.
The article by Cox is disingenuous. He evidently wants you to believe that the authors of regex libraries are ignorant of the theory of regular languages, and if they had just studied the standard undergraduate CS curriculum then they would have implemented their libraries in a different way and made them faster. That's false. It's impossible to implement Perl-style regexes that way, and he knows it. The popularity of Perl-style regexes is probably due in large part to their flexible feature set that goes far beyond what's available in any true regular expression library.


Is a Turing Machine that only takes strings of the form $0^*$ Turing Complete?

It looks like Turing machines remain Turing-complete when the alphabet is restricted to have one symbol, $0$. First, preprocess your input by replacing every $0$ with $0\square$, where $\square$ is the blank symbol. Now, you can simulate a 2-symbol alphabet by using $0\square$ to represent zero and $\square0$ to represent one.

  My understanding of undecidable problems with regards to Turing machines is that they arise because there are languages that have a cardinality strictly greater than the natural numbers

This is incorrect. A language is, by definition, a set of finite strings and there are only countably many finite strings over any finite alphabet (proof: you get a bijection with the natural numbers by treating each string as a number written in base-$k$, where $k$ is the size of the alphabet). However, there are uncountably many different languages and that observation along with the countability of the set of Turing machines lets you deduce that there must be some undecidable langauges.

  It seems to me that, although you can encode any integer with the language 0∗, you can't encode an arbitrary language.

This is also incorrect. You can encode any natural number $n$ with the single string $0^n$ and, therefore, you can code any set of natural numbers with a unary language, i.e., a subset of $0^*$.  And you can code any set of natural numbers as a language. You can also code any language over an alphabet of size $k>1$ by using the base-$k$ trick I described above.


Can anyone explain how look-up tables are used for optimal Rubik's cube solvers such as Thistlethwaite's or Kociemba?

In case it's still relevant, the idea is to get indices based on cube states and store the distance (number of moves it takes) to reach the next group from the given state.
For example - G0->G1 only looks at edge orientations. This means, that if you only consider the orientation of an edge at a given position, there are 2^11 possible states (2 ways each of the 11 edges can be oriented, because the orientation of the 12th edge is "forced" in place by the other 11 edges, so the orientation can be assumed).
For G0->G1, it's easy to generate these indices because you can assign each edge position to a bit in a 11-bit integer, and convert it to decimal.
For a state which satisfies G1, the index would be 0 (00000000000) and for a state with all edges oriented badly, the index would be 2047 (11111111111) which gives unique index for each state from 0 to 2047.
Using this logic, run your IDDFS from a solved cube only using the available moves of the group until all permutations were visited. for G0->G1 it should be done in 7 depths.


Fast k mismatch string matching algorithm

Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA.

Once the suffix array has been constructed, we need to construct a Longest Common Prefix (LCP) array for the suffix array. The LCP array stores the length of the longest common prefix between two consecutive prefixes in the suffix array (lexicographic consecutive suffixes). Thus, LCP[i] contains the length of the longest common prefix between SA[i] and SA[i+1]. This array can also be constructed in linear time: see here, here and here for some good references.

Now, to compute the length of the longest prefix common to any two suffixes in the suffix tree (instead of consecutive suffixes), we need to use some RMQ data structure. It has been shown in the references above (and can be seen easily if the array is visualized as a suffix tree), that the length of the longest common prefix between two suffixes having positions $u$ and $v$ ($u < v$) in the suffix array, can be obtained as $min_{u<=k<=v-1}{LCP[k]}$. A good RMQ can pre-process the $LCP$ array in $O(n)$ or $O(n\log n)$ time and respond to queries of the form $LCP[u, v]$ in $O(1)$ time. See here for a succint RMQ algorithm, and here for a good tutorial on RMQ's, and the relationship (and reductions) between LCA and RMQs. This has another nice alternative approach.

With this information, we construct the suffix array and associated arrays (as described above) for the concatenation of the two strings with a delimiter in between (such as T#P, where '#' does not occur in either string). Then, we can perform k mismatch string matching using the "kangaroo" method. This and this explain the kangaroo method in the context of suffix trees, but can be directly applied to suffix arrays too. For every index $i$ of the text $T$, find the $LCP$ of the suffix of $T$ starting at $i$ and the suffix of $P$ starting at 0. This gives the location after which the first mismatch occurs when matching $P$ with $T[i]$. Let this length be $l_0$. Skip the mismatching character in both $T$ and $P$ and try to match the remaining strings. That is, again find the $LCP$ of $T[i + l_0 + 1]$ and $P[l_0 + 1]$. Repeat this till you obtain $k$ mismatches, or either string finishes. Each $LCP$ is $O(1)$. There are $O(k)$ $LCP$'s for each index $i$ of $T$, giving this a total complexity of $O(nk)$.

I used an easier to implement RMQ giving a total complexity of $O(nk + (n+m)\log(n+m))$, or $O(nk + n\log n)$ if $m = O(n)$, but it can be done in $O(nk)$ too as described above. There may be other direct methods for this problem, but this is a powerful and generic approach that can be applied to a lot of similar problems.


I'd suggest formulating this as an instance of SAT or ILP, then using an off-the-shelf SAT or ILP solver.  This smells like the kind of problem that might be NP-hard in general and thus it might not be reasonable to expect a general, efficient algorithm that always outputs the optimal solution.

For example, if you only wanted to find a solution that meets all of the constraints, and you ignore the priorities, then you could express this as a SAT instance easily.  You could use a one-hot encoding, where the boolean variable $x_{i,j,k}$ if representative $i$ is assigned to seat $j$ in session $k$.  Then each constraint can be translated into a logical predicate on these boolean variables and thus into SAT.  I find the Z3 solver convenient for expressing these kinds of constraints.

To capture the priorities, you could introduce additional boolean variables, say $y_{i,k}$ is 1 (true) if representative $i$ changes seat after session $k$ or 0 (false) otherwise, and then add constraints to capture the relationship between the $x$'s and $y$'s, and finally minimize the sum of the $y$'s, or require that the sum of the $y$'s be below some threshold $\tau$ and use binary search on $\tau$.  For that, pseudo-boolean inequalities or integer linear programming might be useful.

There are many details that would need to be filled in. I'll let you work out the details.

See, e.g., Express boolean logic operations in zero-one integer linear programming (ILP), Encoding 1-out-of-n constraint for SAT solvers, Reduce the following problem to SAT, When to use SAT vs Constraint Satisfaction?, https://stackoverflow.com/q/43081929/781723 for some relevant reading.  The operations research community and tools (e.g., OR-Tools) might also be relevant.


We can think of a BPP algorithm $A$ for a language $L$ as accepting two inputs, the real input $x$ and a random string $r$, whose length is polynomial in $x$. Now take the Boolean circuit evaluation problem, which is P-complete. Since $A(x,r) \in P$, we can reduce $A$ to this problem, substituting random $r$. Then if $x \in L$ then the reduction yields a YES instance with probability at least $2/3$, and if $x \notin L$ then it yields a NO instance with probability at least $2/3$.


Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of $\sqrt{n}$ finds on the bottom nodes in each list will take time $\Theta(n)$, which means that the bound of $O(m \log n)$ (here, $O(\sqrt{n} \log n)$) is incorrect. A more correct bound would be to claim that the runtime will be $O(m \log n + n)$, which accounts for the "startup cost" of doing some initially-expensive compresses.

Here's one way that you can see the runtime is $O(m \log n + n)$ without using the potential argument you mentioned in your question. Let's begin with an initial disjoint-set forest. We're going to color all the edges in the forest one of three colors: gold, blue, or red. The colors are given as follows:

Any edge from a node u to a node v, where the number of nodes in u's subtree is less than half the number of nodes in v's subtree, is colored blue.
Every other edge is red.

To understand blue and red edges, imagine that you're not going from some node up to the root, but from the root down to some node. Every time you follow a blue path, the number of nodes in the current subtree decreases by at least a factor of two. This means that if there are $n$ total nodes in the graph, any path from a node up to its root can have at most $O(\log n)$ blue edges on it, since the number of nodes in the subtree keeps dropping geometrically. That leaves red edges as everything else.

So now imagine that you start doing a find operation beginning at some node. Look at the path that you'll take up to the root. You're going to go through some number of red edges, some number of blue edges, and some number of gold edges. We don't know a priori how many red edges you'll walk through, but we can guarantee that you'll go through at most one gold edge (remember, they have to be directly pointing to the root) and at most $O(\log n)$ blue edges. This means that the cost of performing a find operation is $O(r + \log n)$, where $r$ is the total number of red edges that you pass through.

The reason that this coloring scheme is interesting is that something magic happens when you do a find. Remember, every node on the path is going to have its parent pointer changed to be the ultimate representative in the partition. Imagine that you use the potential function that you described in the question. Every time you follow a red edge (other than one that already points to the root directly), you change the node so that it points directly to the root. This means that its old parent must lose at least half the weight in its tree, which means that $\log[w_i]$ decreases by at least one. No node's weight increases, since we only move edges from descendants up to the root. This means that the drop in potential is at least $r - 1$, where $r$ is the number of red edges followed. Therefore, even though the runtime of any individual find is $O(r + \log n)$, the amortized cost of a single find is $O(\log n)$.

Now, this analysis completely ignores the costs of doing a union operation, and that's important. The good news is that it's not a problem. A union does two finds - each of which cost amortized $O(\log n)$ - and then links one tree to another. This increases the size of the root of that tree by the number of nodes in the linked tree, which is at most $n$. This means that the potential increases by at most $\log n$, so the amortized cost is $O(\log n)$.