Why is this sequence of recurrence relevant?

Calculus of differences

We make Kaya's nice observations slightly more formal. The sequence $T^k$ is the $k$th difference sequence of the original sequence $T$. You can think of it as a discrete $k$th derivative. For example, if $T$ is a $k$th degree polynomial then $T^k$ is constant. We will see below what happens when $T$ is exponential.

For a sequence $T$ (all sequences range over the positive integers), let $\Delta(T)$ be defined by $$ \Delta(T)(n) = T(n+1)-T(n). $$
So $T^k = \Delta^{(k)}(T)$, that is $T^k$ is obtained by applying $k$ times the operator $\Delta$. The operator $\Delta$ has an inverse, which corresponds to indefinite integration:
$$ T(n) = T(1) + \sum_{k=1}^{n-1} \Delta(T)(k). $$
If we are only given the sequence $\Delta(T)$ then we don't know $T(1)$, and we can think of it as a constant of integration. For concreteness, define another operator $\Sigma$ given by
$$ \Sigma(T)(n) = \sum_{k=1}^{n-1} T(k). $$
The "fundamental theorem of calculus" then states that
$$ \Delta(\Sigma(T)) = T $$
and
$$ \Sigma(\Delta(T)) = T - T(1). $$
Another useful property of the operators $\Delta$ and $\Sigma$ is their linearity.

Furthermore, we have the nice formula $$\Delta^{(k)}(n^k) = k!,$$ which can be proved by induction on $k$. This formula also implies that $$\Delta^{(k+1)}(n^k) = 0.$$ In fact, this is true for any polynomial of degree at most $k$. Conversely, $\Sigma(n^k)$ is some polynomial of degree $k$.

We can do the same for exponentials:
$$ \Delta(c^n) = (c-1)c^n, \quad \Sigma(c^n) = \frac{c^n-1}{c-1}.$$

Finally, it will be useful to use the shift operator $S$ given by $$S(T)(n) = T(n+1).$$
This operator commutes with $\Delta$: $S(\Delta(T)) = \Delta(S(T))$.

Solving the recurrence

Now to the problem at hand. The sequence $T$ satisfies $$S(T) = 2T + (n+1)^2. $$
Taking the third difference, we get $$S(\Delta^{(3)}(T)) = 2\Delta^{(3)}(T).$$
Here we used the linearity of $\Delta$, the commutativity of $\Delta,S$, and the fact that the third derivative of $(n+1)^2$ vanishes. We can conclude that
$$ \Delta^{(3)}(T) = C 2^n, \quad C = \Delta^{(3)}(T)(1)/2. $$
We now want to repeatedly apply the operator $\Sigma$. Each time we apply $\Sigma$, we get some constant of integration. After the first time, we get
$$ \Delta^{(2)}(T) = C 2^n + C_1 $$
for some $C_1$, using $\Sigma(2^n) = 2^n-1$. While we can express $C_1$ in terms of $T$, it is better not to. The next time we apply $\Sigma$, $C_1$ turns into a linear terms, and so
$$ \Delta^{(1)}(T) = C 2^n + C_1 n + C_2 $$
for some $C_2$. The next time we apply $\Sigma$, $C_1 n$ turns into a quadratic term, and so
$$ T = C 2^n + P_2 $$
for some quadratic polynomial $P_2$.

It remains to find $C$ and $P_2$. Recall that $C = \Delta^{(3)}(T)(1)/2$. Kaya calculated $\Delta^{(3)}(T)(1) = 12$ and so $C = 6$. Therefore
$$ T = 6 \cdot 2^n + P_2. $$
The first few values in $T$ are $1,6,21$, and so $P_2(1) = -11$, $P_2(2) = -18$, $P_2(3) = -27$. Write $P_2 = B_2 n^2 + B_1 n + B_0$, and so $\Delta^{(2)}(P_2) = 2B_2$. On the other hand, $\Delta(-11,-18,-27,\ldots) = (-7,-9,\ldots)$ and so $\Delta^{(2)}(-11,-18,-27,\ldots) = (-2,\ldots)$, and we conclude that $B_2 = -1$. We can now calculate $B_1 n + B_0 = (-10,-14,\ldots)$, and so $B_1 = -4$ and $B_0 = -6$. We can conclude that $P_2 = -n^2 - 4n - 6$, and we get Kaya's formula.

Generalities

More generally, if $T$ is a sequence satisfying $T(n+1) = c T(n) + P_k(n)$ for some polynomial $P_k$ of degree $k$, then the very same method shows that
$$ T(n) = C c^n + P_{k+1}(n) $$
for some constant $C$ and polynomial $P_{k+1}$ of degree $k+1$. In order to find $C$ and $P_{k+1}$, we can either follow the route used above - express $C$ in terms of $c$, $k$ and $\Delta^{(k+1)}(T)(1)$ - or calculate $T(1),\ldots,T(k+2)$ and solve linear equations in the unknowns $C$ and the coefficients of $P_{k+1}$.

Even more generally, we can handle recurrences of the form $T(n) = c_1 T(n-1) + \cdots + c_l T(n-l) + P_k(n)$. As before, after applying $\Delta^{(k+1)}$, the inhomogeneous terms $P_k$ disappears, and we can solve the resulting recurrence relation. Applying $\Sigma^{(k+1)}$, we will get an "error term" of the form $P_{k+1}$ as before.

General recurrence relations have solutions which are sums of expressions of the form $n^r c^n$ for integer $r \geq 0$, so we also need to calculate the (iterated) discrete integrals of these functions; the result of applying $\Sigma$ once is $P_{r+1}(n) c^n$ for some polynomial $P_{r+1}$ of degree $r+1$, and so applying it $k+1$ time we obtain $P_{r+k+1}(n) c^n$ for some polynomial $P_{r+k+1}$ of degree $r+k+1$. As before, we can find the coefficients of all polynomials by solving linear equations, given enough values of the sequence $T$.


Solving/mitigating the free rider problem without requiring identification?

The term for the problem you seem most focused on is a Sybil attack whose typical solution is some form of identity.

Another mitigation is a proof of work system that makes account creation expensive. The goal is to have the cost of creating multiple accounts not be worth the gains. This is more effective when one needs many Sybil accounts to really benefit. Anything that made getting two accounts disincentivizingly costly, probably makes getting one account too annoying for legitimate users.

The Wikipedia page list another approach to dealing with this that is a bit interesting, and is described, for example, in "Sybil Detection via Distributed Sparse Cut Monitoring" by Aditya Kurve and George Kesidis referenced there. This, however, requires some way for the users to interact in your system (or in a system you have visibility into). In particular, it requires users to implicitly or explicitly "vouch" for other users. This graph of "vouchings for" will usually have atypical properties for subgraphs of Sybil accounts (e.g. being fully connected rather than a small-world graph).

In your context, you could attempt to use techniques similar to the fraud detection banks do and try to find patterns that suggest abuse, e.g. a bunch of users all transferring virtual currency to a single user in a short time frame.

Alternatively, and this is somewhat in line with a proof of work scheme, you can only provide this virtual payment when the user is doing the intended behavior. As a simple baseline, you may provide it only to users who are active a certain amount in the day. This also leads into to the fraud detection angle as many online games have similar systems to detect bots that are just pretending to behave like normal users.


Different probabilistic statement for Simple Uniform Hashing

They're not the same, but the one in Wikipedia is a consequence of the simple uniform hashing assumption.

Let $E$ be the event that $h(k_1)=h(k_2)$.  Let $F_x$ denote the event that $h(k_1)=h(k_2)=x$.  Note that

$$E = \bigcup_x F_x,$$

and the events $F_x$ are disjoint.  Therefore,

$$\Pr[E] = \sum_x \Pr[F_x].$$

Now under the simple uniform hashing assumption,

$$\begin{align*}
\Pr[F_x] &= \Pr[h(k_1)=x \land h(k_2)=x]\\
&= \Pr[h(k_1)=x | h(k_2)=x] \times \Pr[h(k_2)=x]\\
&= \frac{1}{m} \times \frac{1}{m}\\
&= \frac{1}{m^2}.
\end{align*}$$

Plugging in, we find

$$\Pr[E] = \sum_x \Pr[F_x] = \sum_x \frac{1}{m^2} = \frac{1}{m}$$

since there are $m$ possible values of $x$.

Therefore, if the simple uniform hashing assumption holds, then the equation you found in Wikipedia also holds.  The reverse isn't necessarily true.


How to leverage the fact that I'm solving 1000's of very similar SMT instances?

Some SAT solvers and SMT solvers offer an interface that lets you push clauses, and then later pop/retract them and push some new ones.  You could explore to see whether this offers a speedup in your situation.  There are no guarantees, and the only way to tell is to try it.


Context free grammar for a palindrome of even length + cc

This CFG does not work
$$\begin{aligned}
S&\to aS \mid bS\mid\epsilon\mid T\\
T&\to  cc\\
\end{aligned}$$
It generates $acc$ by $S\Rightarrow aS\Rightarrow aT\Rightarrow acc$, which is not of form $AA^Rcc$. In fact, it generates the language $(a+b)^*(\epsilon+cc)$.

You might have missed the basic mindset to write a context-free grammar (CFG).
Every non-terminal in a CFG stands for a language.
Thinking in terms of languages instead of strings should be more helpful sometimes for constructing the CFG.
Since the language $S=\{AA^Rcc: A \in \{a,b\}^*\}$ is the concatenation of the language of the palindromes of even length,  $P=\{AA^R: A \in \{a,b\}^*\}$ and the language of one word, $C=\{cc\}$, the corresponding substitution rule is
$$ S\to PC$$
to which we add the substitution rules for $P$ and $C$
$$\begin{aligned}
P&\to aPa\mid bPb\mid\epsilon\\
C&\to  cc.\\
\end{aligned}$$
The collection of all substitution rules above is the CFG wanted. Note that each of the symbols $S, P, C$ is abused to denote a non-terminal as well as the languages it stands for, i.e, the context-free language generated if we treat it as the starting symbol.
Exercise
Write a CFG for the language $\{AA^RbcBB^R: A \in \{a,b\}^*, B\in\{c,d\}^*\}$.


Your game is equivalent to the PSPACE-complete problem TQBF. The quantified Boolean formula corresponding to your example is
$$
\forall x \forall y \exists z (x \land y) \lor (y \land z) \lor (\lnot y \land \lnot z).
$$
Since it is PSPACE-complete, in particular it is NP-hard, and you there is no efficient general way to find out who wins in this game.

There is an exponential time strategy which involves constructing the game tree. While this strategy is feasible when the number of variables is small (like in your example), it is not practical when there are many variables.


I don't think that there exists a reasonable characterization of all sparse languages (for instance, it's trivial to define sparse languages that sit arbitrarily high on the arithmetical hierarchy).

However, since $\{0,1\}^*$ has exponential growth, you need to be able to derive some kind of combinatorial property from the language definition. For example, let $k$ be a constant and consider the following language:

$\qquad L = \{x \mid x \text{ contains $k$ ones}\}$

$L$ is sparse, the key observation being that $\binom{n}{k}$ for a fixed $k$ is a polynomial in $n$.


Can the effective branching factor be negative?

I don't know what effective branching factor is, but let me make a few comments anyway:

Presumably the effective branching factor is a parameter such that if the branching factor is constant, then it should equal the effective branching factor. It is some kind of average branching factor. Under this interpretation, a negative branching factor makes no sense.
You should focus on understanding what the effective branching factor is before calculating it. It is pointless to calculate something whose significance you don't understand. In real life you don't just "plug and chug" – you have a goal in mind. In this case, presumably the goal in mind is to estimate how difficult the problem is – the larger the effective branching factor is, the shallower you can afford to explore the corresponding tree. You estimate the effective branching factor in order to estimate how deep you can go, and in order to compare the difficulty of various problems. The formula itself is less important.
As $B^*$ increases monotonically from $0$ to infinity, so $1+B^*+\cdots+(B^*)^L$ increases from $1$ to infinity. Therefore your equation has a unique positive root (assuming $T > 0$).
If $B^*$ is "large", then you can estimate $1+\cdots+(B^*)^L$ by just the last term $(B^*)^L$, and so roughly speaking, $B^* \approx T^{1/L}$. You can use this estimate as a basis for an iterative algorithm for calculating $B^*$. The formula for the sum of a geometric series might be useful here.


The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.

Markov's inequality is $P[ X \geq a] \leq E[X]/a$ if $X \geq 0$. If we substitude $a = 2E[X]$ then we will have $P[ X \geq 2 E[X]] \leq 1/2$.

So, basically we run the algorithm that witnesses $L \in \textrm{ZPP}$ for at least double its expected running time. If it gives an answer, then we give that answer. If it doesn't give any answer before we stop it, we give NO answer. The probability of incorrect NO answer is $\leq 1/2$. This polynomial time algorithm proves $L \in \textrm{RP}$.

If we give answer YES on forced stoppage then that algorithm proves $L \in \textrm{co-RP}$. Thus $\textrm{ZPP} \subseteq \textrm{RP} \cap \textrm{co-RP}$.

For the sake of completeness, I also give the proof of $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

Suppose we have a language $L \in \textrm{RP} \cap \textrm{co-RP}$. Then $L$ has a polynomial time algorithm $A$ that answers YES at least 1/2 times for $x \in L$  and a polynomial time algorithm $B$ that answers NO at least 1/2 times for $x \not\in L$. In one iteration we do the following: Given an input $x$ in $L$, we run $A$ on $x$. If it returns YES, the answer must be YES, so we return YES. Otherwise, we are in doubt so we run $B$ on the input. If it returns NO, the answer must be NO, so we return NO. If neither occurs, we repeat this iteration. We can show that the expected running time of this algorithm is still polynomial. Thus
 $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.


What are analog and digital in computer science?

I'll try to answer your remaining question: what are analog and digital in computer science?
The trouble is that these terms aren't from computer science. They are from the field called "signal processing". When someone says "analog computer", they simply mean that the computer is designed on principles of analog signal processing and built from analog components. The same goes for digital computers: they are designed with digital signal processing in mind and built from digital components.
So what does "analog" means? The word is taken from Greek word "proportional". To clarify what it means, let's look at the sum operation implemented with graduated cylinders:

Say you want to compute $13 + 38$. First, you take an empty cylinder and fill it up to $13$ ml mark. Then you take another empty one and fill it up to $38$ ml mark. Then you pour one into the other and look how much ml of liquid is there, which you announce as the result of the sum operation.
This is "proportional", because if you want to use $26$ instead of $13$ as an input, you use double amount of liquid. Double amount of liquid means twice as large number. An electrical analog computer could use the voltage of electric current is a similar way.
Now let's take a look on a digital computation implemented with Soldier Crabs. Here's how you make logical OR:

And here's logical AND:

You put a swarm of crabs where you want logical $1$ as an input and you leave empty places where you want logical $0$. Then you look where the swarm ball ends up and interpret it as $0$ or $1$. This is built on principles of (binary) digital processing:

No crabs (no electric current, no water flow) means $0$.
A swarm of crabs (5V, steady water flow) means $1$.
What if you can't decide which is the case? You just say that your digital component is broken.


Shortest Path in Layerwise Complete Graph

Your problem is NP-hard, by reduction from clique. Given a graph $G=(V,E)$ and a number $k$, we construct a graph with $k$ internal layers, each containing $|V|$ vertices. All vertices in a layer are connected to all vertices in the following layer. The weight of an edge is $0$ if the corresponding edge is not in $G$, and $-1$ otherwise. We also add shortcut edges corresponding to edges in $G$ with weight $-1$. The graph $G$ has a $k$-clique iff the shortest path in the new graph has length $-k(k-1)/2$.


What makes a pseudorandom generator, a high quality one?

There are several criteria for the quality of a PRNG:

How fast it is. This includes how fast it is to setup it, and how fast it is to produce a single bit (amortized).
How difficult it is to guess the next bit given all previous bits.
How difficult it is to distinguish between output of the PRNG and truly random bits.

The last two criteria are strongly related.

If you have a bad quality PRNG, you can often make it better by hardness amplification. Take several copies of the PRNG (using different random keys) and XOR them together. In many (though not all) cases this will significantly improve its quality.


Here is a very simple algorithm. We will require the following lemma.

Lemma. Suppose that $1 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} \geq 1/2$. Then there exists $r \in \{1,\ldots,k\}$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$.

Proof. Let $r$ be the first index such that $\sum_{i=1}^r 2^{-\ell_i} \geq 1/2$. Since the $\ell_i$ are non-decreasing, there are integers $A,B$ such that
$$
\begin{align}
\sum_{i=1}^{r-1} 2^{-\ell_i} &= \frac{A}{2^{\ell_r}}, &
\sum_{i=1}^r 2^{-\ell_i} &= \frac{B}{2^{\ell_r}}.
\end{align}
$$
Moreover, $A < 2^{\ell_r-1}$ and $B \geq 2^{\ell_r-1}$. Since $B-A=1$, we conclude that $B = 2^{\ell_r-1}$, and so $\sum_{i=1}^r 2^{-\ell_i} = 1/2$. $\quad\square$

This suggests the following algorithm. We can assume that your sequence is sorted, that is, we are given a sequence $\ell_1 \leq \cdots \leq \ell_k$ such that $\sum_{i=1}^k 2^{-\ell_i} \leq 1$. We now consider three cases:

$\sum_{i=1}^k 2^{-\ell_i} = 1$. In this case, there is nothing to do.
$\sum_{i=1}^k 2^{-\ell_i} \leq 1/2$. In this case, we can decrease each $\ell_i$ by $1$.
$1/2 \leq \sum_{i=1}^k 2^{-\ell_i} \leq 1$. Applying the lemma, we find $r$ such that $\sum_{i=1}^r 2^{-\ell_i} = 1/2$, and so $\sum_{i=r+1}^k 2^{-\ell_i} \leq 1/2$. We thus have to solve the same kind of problem for the second half $\ell_{r+1},\ldots,\ell_k$, aiming at $1/2$ rather than $1$.

To implement this recursion more cleanly, we add a parameter $s$, and our goal is to correct a sequence satisfying $\sum_i 2^{-\ell_i} \leq 2^{-s}$ to one satisfying $\sum_i 2^{-\ell_i} = 2^{-s}$ by only decreasing elements.

Here is how the algorithm works in the case of the sequence $1,2,4,7,8$, which matches your example. The sum in your case is more than $1/2$, so we separate the sequence into two parts: $1$ and $2,4,7,8$. We only handle the second, aiming at a sum of $1/2$.

The sum in the case of $2,4,7,8$ is more than $1/4$, so we separate the sequence into two parts, $2$ and $4,7,8$, and only handle the second, aiming at a sum of $1/4$.

The sum in the case of $4,7,8$ is less than $1/8$, so we decrement each element, obtaining the sequence $3,6,7$, whose sum is more than $1/8$. We separate it into $3$ and $6,7$, and only handle the second, aiming at a sum of $1/8$.

We decrement $6,7$ twice, obtaining the sequence $4,5$ whose sum exceeds $1/16$. We separate it into $4$ and $5$, and decrement the latter once.

Putting everything together, we obtain the sequence $1,2,3,4,4$.

In the $q$-ary case, we have to change the problem somehow, since the result is not true in general. For example, take $q = 3$ and consider the sequence $1, 1$.

Here is another simple algorithm, based on the following lemma.

Lemma. Suppose that $0 \leq \ell_1 \leq \cdots \leq \ell_k$ and $\sum_{i=1}^k 2^{-\ell_i} < 1$. Then $\sum_{i=1}^{k-1} 2^{-\ell_i} + 2^{-(\ell_k-1)} \leq 1$.

Proof. Since the $\ell_i$ are nondecreasing, we can write $\sum_{i=1}^k 2^{-\ell_i} = A/2^{\ell_k}$, where $A < 2^{\ell_k}$. Replacing $\ell_k$ with $\ell_k-1$ increases the sum by $1/2^{\ell_k}$. Since $A+1 \leq 2^{\ell_k}$, the sum remains at most $1$. $\quad\square$

This suggests the following simple algorithm: repeatedly decrement the largest $\ell_i$. The algorithm necessarily terminates since at most $\sum_i \ell_i$ iterations can take place.

Let us apply this on our example above:
$$
\begin{align}
&1,2,4,7,8 \to 1,2,4,7,7 \to 1,2,4,6,7 \to 1,2,4,6,6 \to 1,2,4,5,6 \to \\
&1,2,4,5,5 \to 1,2,4,4,5 \to 1,2,4,4,4 \to 1,2,3,4,4
\end{align}
$$
This algorithm can be implemented easily using a heap. However, it is slower (in general) than the preceding algorithm, if the latter is implemented correctly. For example, the sequence $\ell$ takes $\ell$ steps in this algorithm, but could be handled by a single iteration of the preceding algorithm.


How to prove regular languages are closed under left quotient?

Assume $M$ is a deterministic finite state machine accepting $L$. Feed the word $w$ into $M$, which will land you in some state $q$. Construct a new machine $M'$ which is the same as $M$ but has start state $q$. I claim that $M'$ accepts $w^{-1}L$.

Now prove it.


Notations: I'll use the C notations for bitwise operations: $a \mathbin\& b$ (bitwise and), $a \mathbin| b$ (bitwise or), $a \mathbin\ll b$ (shift left), $a \mathbin\gg b$ (shift right). The shift operators are left-associative (e.g. $x \mathbin\gg m \mathbin\gg n = (x \mathbin\gg m) \mathbin\gg n$). The shift operations put zeroes in newly created bit positions: $a \mathbin\ll b = a \times 2^b$ and $a \mathbin\gg b = \lfloor a \times 2^{-b} \rfloor$. Sequences of digits with a line above (e.g. $\overline{11101000}$, $\overline{z^4z^3z^2z^1z^0}$) represent a number written in base 2 (binary).

If $x$ is an integer between $0$ and $2^N-1$, we say that $x$ is an $N$-bit number, and write $x = \overline{x^{N-1}x^{N-2}\ldots x^1x^0}$, i.e. $x^k$ is bit $k$ of $x$. Bits $k-1$ through $0$ constitute the $k$ least significant bits of $x$, and bits $N-1$ through $N-k$ constitute the $k$ most significant bits of $x$ (where $x$ is considered as an $N$-bit number).

Intuition

With 32 bits and 50 operations, an approach that looks at one bit of the input at a time isn't going to work. The next obvious thing to try is a recursive (dive-and-conquer approach) where you work on half the bits at a time. There are two simple ways to divide an $N$-bit number: into the $N/2$ most significant bits and the $N/2$ least significant bits, or into odd and even positions. Most/least significant looks promising, because the result counts how many most significant bits are 1.

Or we could approach the problem the other way: the result is a number between 0 and 32, a 6-bit number (for all but one input values, it's a 5-bit number). Can we find the bits of the result, one at a time?

Let $a$ be the input (a 32-bit number) and $z$ the output. Bit $5$ of $z$ is 1 iff $a$ is all-bits-1. Bit $4$ of $z$ is 1 iff the 16 most significant bits of $a$ are all 1 and $a$ is not all-bits-1. What about bit $3$? We have to discriminate on bit $4$: if it's 0, we look at the $8$ most significant bits of $a$ (with an exception when $a$ is all-bits-1); if it's 1, we look at bits $8$ through $15$ instead.

Expression in terms of bitwise operations

Let's express this in terms of bitwise operations. For the time being, assume we have a primitive operation $A_N$ on $N$-bit numbers such that $A_N(x) = 1$ if $x = 2^N-1$ (i.e. $x$ is all-bits-1) and $A_N(x) = 0$ otherwise.

$z^5 = A_{32}(a)$
if $z^5 = 0$ then $z^4 = 0$, else
$z^4 = A_{16}(a \mathbin\gg 16)$
if $z^5 = 0$ then $z^4 = 0$, else
if $z^4 = 0$ then $z^3 = A_8(a \mathbin\gg (16+8))$, else
$z^3 = A_8((a \mathbin\& \overline{1111111100000000}) \mathbin\gg 8)$

That's not very orderly: at this point we're looking to express $z^4$ and $z^3$ in similar way so that a recursion pattern can emerge. Furthermore we've used conditional statements which we're going to have to eliminate somehow. What seems constant is that $z^k$ is $A_{2^k}$ of some number. So what number? At each stage, we cut some number which is a slice of $a$ in half. To compute the next bit of the result we're looking at the most significant half of one of the halves from the previous step. Let's write $a_{k+1}$ for the input to the step that computes $z^k$ (so that we start with $a_6 = a$ to compute $z_5$). Then, leaving aside for a moment the case when $a = 2^{32}-1$ (in other words, we leave aside the case when $z^5=1$):

$a_5 = a_6$
$z^4 = A_{16}(a_5 \mathbin\gg 16)$
If $z^4 = 1$ then $a_4 = a_5 \mathbin\& (2^{16}-1)$, else $a_4 = a_5 \mathbin\gg 16$. It's awfully tempting to turn that 16 into $z^4 \mathbin\ll 4$, but it's on the wrong side. We could flip a bit (using xor), but this complicates the expression; instead, let's shift the other way: $a_4 = (a_5 \mathbin\& (2^{16}-1)) \mathbin\ll (z^4 \mathbin\ll 4) \mathbin\gg 4$.

And thus a pattern emerges:
$$\begin{align*}
  z^k &= A_{2^k}(a_{k+1} \mathbin\gg 2^k) \\
  a_k &= (a_{k+1} \mathbin\& (2^{2^k}-1)) \mathbin\ll (z^k \mathbin\ll k) \mathbin\gg k \\
\end{align*}$$

A simpler recursion

The initial case $z^5$ isn't right. It would be a simple matter to adjust the recursion pattern to accommodate it, but before doing that, I prefer to tweak the notation to reduce the number of shifts. When we compute $a_k$, we're aligning the extracted number to the right. Let's instead align to the left. Furthermore, let's drop the masking: we'll use a new predicate $B_m$ instead of $A_m$ which looks only at the appropriate bits. Define
$$ b_{k-1} = b_k \mathbin\ll (z^k \mathbin\ll k) $$
Define $B^n_m(x) = 1$ if the $2^n$-bit number $x$ has its $m$ most significant bits all set, and $B^n_m(x) = 0$ otherwise.
$$ z^k = B^n_{2^k}(b_k) $$

For a 32-bit number ($n=5$), we start with $b_5 = a$ and $z^5 = B^5_{32}(b_5)$ (check all 32 bits). Next we compute $b_4 = b_5 \mathbin\ll (z^5 \mathbin\ll 5)$; when $z^5=1$ (i.e. $a=2^n-1$) that sets $b_4 = 0$. We can then compute $z^4 = B^5_{16}(b_4)$ (look at the most significant 16 bits), then either $b_3 = b_4$ or $b_3 = b_4 \mathbin\ll 16$ depending on $z^4$, and so on until we find $z^0$.

Testing for all-bits-1

We're getting close. We still need to express that $B$ function in terms of bitwise operators. Note that so far, we've used 10 operations (2 shifts per step to compute $b_4$ through $b_0$). That leaves 40 operations to do the all-bits-1 check.

$B^n_1$ is easy: take the most significant bit and shift it into place, i.e. $B^n_1(x) = x \mathbin\gg (2^n-1)$. For $B^n_2$, we need to and the two most significant bits of $x$ together: $B^n_2(x) = (x \mathbin\gg (2^n-1)) \mathbin\& (x \mathbin\gg (2^n-2))$. Going on, we have $B^n_3(x) = (x \mathbin\gg (2^n-1)) \mathbin\& (x \mathbin\gg (2^n-2)) \mathbin\& (x \mathbin\gg (2^n-3))$. A recursive pattern emerges, but it's expensive: one shift and one and per bit. Linear is too slow, we need to go exponential.

Above we were taking the and of a single bit at a time. This is a waste: we can operate on $2^n$ bits in one go. Take $x$, shift left by $m$ and and with $x$: the result has its $m$ most significant bits all-1 iff $x$ has its $2m$ most significant bits all-1. Or in other words:
$$B^n_{2m}(x) = B^n_m(x \mathbin\& (x \mathbin\ll m))$$
Recall that $B^n_1(x) = x \mathbin\gg (2^n-1)$. We can compute $B^n_{2^k}$ in $2k+1$ operations. Thus we can compute $z^k$ from $b_{k+1}$ in $2k+1$; for $z^0$ through $z^n$, that's a total of $\sum_{k=0}^n (2k+1) = (n+1)^2$ operations.

Optimizing some shifts

We have a complete algorithm now, but it's a bit slow, we need to do a little optimization. Notice that we only ever use $z^k$ in the expression $z^k \mathbin\ll 2^k$. So instead of computing $z^k$, we'll directly compute that bit at its final position:
$$y_k = z^k \mathbin\ll k = \hat B^n_{2^k}(b_k) \mathbin\& (1 \mathbin\ll k)$$
where $\hat B^n_{m}(b_k)$ is computed as described above for $B^n_{2^k}(b_k)$, except that for the last shift (resulting from the expansion of $B^n_{1}(c)$ for some $c$), instead of taking $c \mathbin\gg (2^n-1)$, we take $c \mathbin\gg (2^n-1-k)$. Note that $b_{k-1} = b_k \mathbin\ll y_k$.

The cost so far:

one operation per result bit except the most significant one to compute $b_k$ (one shift) → $n$
1 operation per result bit except one to or everything together ($z = y_5 \mathbin| y_4 \mathbin| \ldots \mathbin| y_0$) → $n$
$(n+1)^2$ operations to compute the $B^n_{2^k}(b_k)$ values as seen above, plus one more to get $\hat B^n_{2^k}(b_k)$. That's one shift plus one and, times $(k+1)$ for each $k$, with $k$ ranging from $0$ to $n$. → $(n+1)(n+2)$

The total is $C(n) = (n+1)^2 + 3n + 1$ operations. For $n=5$, that's 52. We're almost there!

Further optimizations in the last steps

Let's see the last few operations once we get to $b_1$ (given here with $n=5$ as an example, but you can generalize to any $n \ge 2$).
$$\begin{gather*}
  c_1 = b_1 \mathbin\& (b_1 \mathbin\ll 1) \\
  y_1 = (c_1 \mathbin\gg 30) \mathbin\& \overline{10} \\
  b_0 = b_1 \mathbin\ll y_1 \\
  y_0 = (b_0 \mathbin\gg 31) \mathbin\& \overline{1} \\
\end{gather*}$$
Let's make this more concrete: let $u = b_1^{31}$ and $v = b_1^{30}$ be the two most significant bits of $b_1$ (i.e. $b_1 = \overline{uv\ldots}$ as a 32-bit number). We need to obtain $y_1 = 2$ if $u=v=1$ and $y_1=0$ otherwise; and $y_0 = 1$ if $u=1$ and $v=0$ and $y_0$ otherwise. At this stage, we can save some operations by aligning on the right instead of on the left. We take advantage of the fact that if you right-shift a 32-bit number by 30, you get a 2-bit number. The sequence of operations above can be replaced by the following sequence:
$$\begin{gather*}
  w = b_1 \mathbin\gg (2^n-2) \\
  y_1 = w \mathbin\& (w \mathbin\ll 1) \\
  b_0 = b_1 \mathbin\ll y_1 \\
  y_0 = b_0 \mathbin\gg (2^n-1) \\
\end{gather*}$$
That's 5 operations instead of 7, bringing us down to 50 for $n=5$, and more generally to $C'(n)=(n+1)^2+3n-1$.

Remarks

By the way, the computation of $b_{k-1}$ from $b_k$ can be done with just two temporary variables. When we obtain $y_k$, we can or it into an accumulator to obtain $z$. So we can do the whole computation with four $2^n$-bit registers.

Code

Here's the 32-bit case played out in Python syntax. The ck_j variables are temporaries used to compute $\hat B^5_{2^k}(b_k)$. I used a single-assignment style, you can get a classical imperative program by stripping all number suffixes from the variable names.

#!/usr/bin/env python
import sys

# Python does bignum arithmetic, but we absolutely need modulo 2^32 arithmetic
# in a few places.
def trim(x): return x & 0xffffffff
def bin5(x): return bin(0x100000000 | trim(x))[3:]

def f5(a, trail_optimization=True, trace=False):
    (y1, y0) = (None, None) # bring these variables to function scope
    b5 = a
    c5_5 = b5
    c5_4 = c5_5 & (c5_5 << 16)
    c5_3 = c5_4 & (c5_4 <<  8)
    c5_2 = c5_3 & (c5_3 <<  4)
    c5_1 = c5_2 & (c5_2 <<  2)
    c5_0 = c5_1 & (c5_1 <<  1)
    y5 = (c5_0 & (2**31)) >> (31 - 5)
    z5 = y5
    b4 = b5 << y5
    c4_4 = b4
    c4_3 = c4_4 & (c4_4 <<  8)
    c4_2 = c4_3 & (c4_3 <<  4)
    c4_1 = c4_2 & (c4_2 <<  2)
    c4_0 = c4_1 & (c4_1 <<  1)
    y4 = (c4_0 & (2**31)) >> (31 - 4)
    z4 = z5 | y4
    b3 = b4 << y4
    c3_3 = b3
    c3_2 = c3_3 & (c3_3 <<  4)
    c3_1 = c3_2 & (c3_2 <<  2)
    c3_0 = c3_1 & (c3_1 <<  1)
    y3 = (c3_0 & (2**31)) >> (31 - 3)
    z3 = z4 | y3
    b2 = b3 << y3
    c2_2 = b2
    c2_1 = c2_2 & (c2_2 <<  2)
    c2_0 = c2_1 & (c2_1 <<  1)
    y2 = (c2_0 & (2**31)) >> (31 - 2)

    z2 = z3 | y2
    b1 = b2 << y2
    if trail_optimization:
        b1 = trim(b1)
        w = b1 >> 30
        #if trace: print 'w=' + bin5(w)[-2:],
        y1 = w & (w << 1)
        b0 = b1 << y1
        b0 = trim(b0)
        y0 = b0 >> 31
    else:
        c1_1 = b1
        c1_0 = c1_1 & (c1_1 <<  1)
        y1 = (c1_0 & (2**31)) >> (31 - 1)
        b0 = b1 << y1
        c0_0 = b0
        y0 = (c0_0 & (2**31)) >> (31 - 0)
    z1 = z2 | y1
    z0 = z1 | y0
    if trace: print 'b5=' + bin5(b5), 'y5=' + str(y5),
    if trace: print 'b4=' + bin5(b4), 'y4=' + str(y4),
    if trace: print 'b3=' + bin5(b3), 'y3=' + str(y3),
    if trace: print 'b2=' + bin5(b2), 'y2=' + str(y2),
    if trace: print 'b1=' + bin5(b1), 'y1=' + str(y1),
    if trace: print 'b0=' + bin5(b0), 'y0=' + str(y0),
    return z0

if __name__ == '__main__':
    for i in xrange(33):
        x = (1 << 32) - (1 << i)
        print bin5(x), f5(x, trace=True)
        if 0 <= i <= 31:
            x = x - 1
            print bin5(x), f5(x, trace=True)


Sets in Mathematics are immutable but in Computer Science sets are mutable and called "Dynamic Sets" - truth of the statement

Set are at a higher level of abstraction than algorithms.  You can certainly analyze algorithms at that level of abstraction but that's not the usual level of abstraction for discussing algorithms, instead you'd refer to data structures such as stacks, vectors, lists, linked lists etc.
Sets are instead used in formal modeling contexts (Z,Coq,Agda,F-Star) to describe specifications but not algorithms.
They're also used do describe algorithms in functional programming (see e.g. Purely Functional Data Structures by Chris Okasaki ) but that is not very common in literature as most algorithms are described in terms of ephemeral data structures.
To answer your question, sets are the same both in Mathematics and CS, they're immutable.   Dynamic sets is a data structure loosely related to sets.
The author is not saying that sets are different in CS than in Mathematics.  He's saying that the data structures, as commonly described in algorithms are mutable.  CS is much more than algorithms and data structures.


Confusion regarding several time complexities including the logarithm

You are correct in thinking binary search is $O(\log n)$, it shouldn't be multiplied by $n$.
Popular (comparison-based) sorting algorithms are $O(n \log n)$.
3SUM (i.e. find 3 elements in an array that sums to zero) using binary search is $O(n^2 \log n)$.

The pseudo-code:

For each element
  For each other element
    Do a binary search for the 3rd element that will result in a zero sum.

Although the problem can be solved in $O(n^2)$ in a different way, this should still serve as a decent example.

Explanation of merge-sort complexity:

Merge-sort, for example, splits the array into 2 parts repeatedly (similar to binary search), but there are some differences:

Binary search throws away the other half, where merge-sort processes both
Binary search consists of a simple $O(1)$ check at each point, where-as merge-sort needs to do an $O(n)$ merge. This should already make the $O(\log n)$ vs $O(n \log n)$ make sense.

For a quick check, ask how many work, on average, is done for each element.
Note that a single merge is linear time, thus $O(1)$ per element.
You recurse down $O(\log n)$ times and, at each step there's a merge, so each element is involved in $O(\log n)$ merges.
And there are $O(n)$ elements.
Thus we have a time complexity of $O(n \log n)$.

There is also the more mathematical analysis: (source)

  Let $T(n)$ the time used to sort n elements. As we can perform separation and merging in linear time, it takes $cn$ time to perform these two steps, for some constant $c$. So,
  $T(n) = 2T(n/2) + cn$.

From here you work your way down to $T(1)$, and the remaining terms gives you your $O(n \log n)$ running time. Or use the master theorem.

If both of these are unclear, it should be easy enough to find another resource explaining the complexity of merge-sort.


Find a Cook Reduction from $R_{Clique}$ to its determinist problem

Your algorithm doesn't return a $k$-clique. Simply consider a connected graph $G$ that is a proper supergraph of a $k$-clique, and an isolated vertex $x$. Your algorithm with input $G+x$ returns $G$.
You can solve your problem as follows:

While $\exists $ a vertex $v$ of $G$ such that $B(G-v)$ returns true:

Delete $v$ from $G$

Return $G$.

Let $G^* = (V^*, E^*)$ be the graph returned by the algorithm.
Since the algorithm preserves the invariant "G contains a $k$-clique", $G^*$ must also contain a $k$-clique. This means that we only need to prove that $G^*$ is not a supergraph of a $k$-clique.
Suppose towards a contradiction that there exists a proper subset $C$ of $V^*$ such that $|C|=k$ and the subgraph of $G^*$ induced by $C$ is a $k$-clique. Then, for any vertex in $v \in V^* \setminus C \neq \emptyset$,  $G-v$ also contains a $k$-clique. This shows that the algorithm cannot return $G^*$ and yields the sought contradiction.


Asymptotic bound of a recursive function

The recurrence relation $T(n) = T(n-1) + T(n-2)$, with initial conditions $T(2) = T(1) = 1$, has as solution the Fibonacci numbers, whose asymptotic growth is known to be $\Theta(\phi^n)$, where $\phi = \frac{1+\sqrt{5}}{2} < 2$. The same bound holds for arbitrary positive initial conditions.


The general idea is that do ( expression ) is a statement that evaluates any expression and throws away the result.

A first attempt could be

  def evalExpr(e: ExprTree)(implicit ectx: EvaluationContext): Value =
    // ...

  def evalStatement(stmt: StatTree)(implicit ectx: EvaluationContext): Unit =
    stmt match {
      // ...
      case DoExpr(expr) =>
        evalExpr(expr)
    }
  }

but in this way, we return a Value and not a Unit, so the compiler raises a type error. We can fix that by using

      case DoExpr(expr) =>
        evalExpr(expr)
        ()  // the Unit value


A simple approach

Given that you have a DAG, and the only change you will make is to delete vertices, there is a crude but simple to implement algorithm you could use.  In addition to computing the distance from $s$ to every vertex, also compute the shortest paths tree.

Now, when you want to delete a vertex $v$, mark the entire subtree rooted at $v$ (in the shortest path tree).  Delete this from the shortest path tree, and process each of the nodes in that subtree to re-calculate their distance from $s$.  You can process those vertices in topological sorted order, and compute the updated distance for vertex $x$ by the standard formula $d(x) = \min \{1+d(w) : (w,x) \in E\}$.  The running time will be proportional to the size of the subtree you deleted.  Whether this is efficient in practice will depend on the structure of the graph and the nodes that you delete.

More sophisticated solutions

This kind of problem has been studied extensively in the literature.  The keyword you want to use is "dynamic shortest paths".  Here dynamic refers to the fact that the graph can change.  In your case, you want to support vertex deletions.  So, I suggest you spend some quality time with the research literature to review the known algorithms for dynamic shortest paths with vertex deletions.  Alternatively, look for algorithms for dynamic shortest paths with edge deletions (since when you delete a vertex you're probably going to delete all edges incident on that vertex as well).

See, e.g., Retrieving the shortest path of a dynamic graph and How to approach Dynamic graph related problems and https://cstheory.stackexchange.com/q/17135/5038 and https://cstheory.stackexchange.com/q/11855/5038 for some entry points into the literature.  Those algorithms apply to arbitrary graphs, but it might be possible to exploit the fact that your graph is actually a DAG to get even better performance.


There's a way to this in polynomial time. I'll sketch the algorithm (in reverse order ... do step 2 first and step 1 second).

if we can find a set of $nk$ agent-task pairs $(i,j)$ such that each task is in exactly $k$ pairs, each agent is in exactly $k$ pairs, and no pair appears more than once, then we can find $k$ assignments that together cover these $nk$ agent-task pairs. We do this by repeatedly using a maximum bipartite matching algorithm to find a perfect matching in the corresponding bipartite graph, and removing that assignment from the graph. Hall's marriage theorem guarantees we can do this.
We can find the minimum-cost set of $nk$ agent-task pairs as in step 1 by using min-cost flow. Consider a network with a source $s$, a sink $t$, and nodes for each of  the agents and each of the tasks. Connect the source to each agent with an edge of capacity $k$ and cost $0$. Connect each task to the sink with an edge of capacity $k$ and cost $0$. Now, connect agent $i$ to task $j$ with an edge of capacity $1$ and cost $c(i,j)$. The  minimum-cost flow in this network is guaranteed to be integral (because all capacities are integral, and there is a theorem saying that this implies that there is an optimal integral min-cost flow), so the flow on each agent-task edge is $0$ or $1$. The edges $(i,j)$ with flow $1$ form the set of pairs in step 1.

There are lots of algorithms that can solve min-cost flow; it's a special case of linear programming. For your size problem, the algorithm I sketch should not just be polynomial-time, but also practical.


How does SpaCy make its dependency tree?

Matthew Honnibal, who created Spacy, answered me :

  The full answer is rather complicated :). I've written a few blog
  posts over the years to make it more accessible. The best place to
  start is this blog post:

  https://explosion.ai/blog/parsing-english-in-python

  Since v2, we use a more complicated machine learning strategy,
  following the general architecture described here:
  https://explosion.ai/blog/deep-learning-formula-nlp . More specifics
  about the model architecture can be found in this description of the
  NER model: https://www.youtube.com/watch?v=sqDHBH9IjRU

  The transition system is mostly described by this paper:
  http://aclweb.org/anthology/D15-1162 , but with some modifications for
  sentence segmentation.

I already started with the first one which I didn't completly understand yet. I will update this post through my reading progress but leave the question open if a concise question comes to your mind.


Why is a subset of a undecidable language decidable?

An undecidable language is necessarily infinite. A finite subset of it is always trivially decidable.


What is the time complexity of the following loop?

Assuming all operations are done in constant time, this loop runs in $\Theta(n!^{-1})$ where $!^{-1}$ is the inverse factorial. Intuitively, the program will enter the loop $i$ times, $i$ being the smallest integer so that $i!\geq n$.


Theory of Turing machine which outputs Turing machine?

It depends on what your are referring as "theory" (which basically means everything or anything).

Something which is closely related to what you are referring can be the
field of Program transformations, which tries to study systematically
programs that modifies other programs. The original interest of this field is the transformers that are semantically invariants (with a bit of hand waving:  you want to study transformers $T$ such that for any program (or a TM) $p$, $T(p)$ does the same thing as $p$). Derives from these original considerations the subfield of program synthesis (here, given some input datas, you want to automatically generate a program that satisfies some conditions encoded by you input).

A good introduction can be the thesis of M. Ward "Proving Program Refinements and Transformations" with an emphasis on the proof of program side.


Search trees of various sorts can work with an arbitrary ordered domain, as all they rely on is a comparison function which is assumed to satisfies the axioms of a complete order:

If $a < b$ and $b < c$ then $a < c$.
Exactly one of $a < b$, $a = b$, $a > b$ (shorthand for $b < a$) holds.

In your case, you're probably meant to use the lexicographic order on strings. In this order, $x < y$ if:

Either $x$ and $y$ first differ in the $i$th symbol, and $x_i < y_i$;
Or $x$ is a prefix of $y$.

Symbols are probably compared in ASCII order in your case.


Initializations methods for lloyds algorithm (Kmeans++ vs Gonzalez)

Partial Answer:
Let us construct an instance where k-means++ initialization performs better than the Gonzalez initialization.
Consider the real line. Place $n$ points at the origin, i.e., position $0$. Place $n$ points at the position $1$. Lastly, place $1$ point at the position $n^{1/4}$. Let us cluster this pointset with $2$ clusters, i.e., $k = 2$.
In the optimal clustering, one center is placed at each of the two positions $0$ and $1$. The optimal k-means cost would be $\Theta(\sqrt{n})$ since the cost of $2n$ points at positions $0$ and $1$ is exactly $0$ and the cost of point at position $n^{1/4}$ is at most $\sqrt{n}$.
With the Gonzalez algorithm, only the following two center sets are possible (you can try this your own):

Center set where one center is at position $0$ and the other at $n^{1/4}$
Center set where one center is at position $1$ and the other at $n^{1/4}$

Without loss of generality, after this initialization, Lloyd's algorithm will cluster the points at positions $0$ and $1$ within the same cluster. And, the point at position $n^{1/4}$ would be clustered in a different cluster (singelton cluster). The $k$-means cost would be $\Theta(n)$.
With the k-means++ algorithm, the first center is chosen uniformly at random. With the high probability, the center would be chosen from positions $0$ or $1$. Without the loss of generality, suppose the first center is chosen from position $0$. Then, the probability that the second center will be chosen from position $1$ is $n/(n+\sqrt{n}) \geq 1/2$. And,  the probability that the second center will be chosen from position $n^{1/4}$ is at most  $\sqrt{n}/(n+\sqrt{n}) \leq 1/(2\sqrt{n})$. As you can see, the second center would be chosen from position $1$ with a high probability.
Therefore, with high probability, after this initialization, the $k$-means algorithm would open centers at positions $0$ and $1$. And, the $k$-means cost would be $\Theta(\sqrt{n})$. This cost is better than the cost with the Gonsalez algorithm that had cost $\Theta(n)$.


Maximum value of $\{ i \land n \mid a \leq i \leq b \}$

Here is how to reduce this to the case you already know how to solve.

If $a = b$, there is nothing to do. Otherwise, the binary expansion of $a,b$ is of the form $a = x0\alpha$ and $b = x1\beta$, where $|\alpha| = |\beta|$. If the bit of $n$ corresponding to the differing bit of $a,b$ is $0$, then the corresponding bit of $i$ should be $1$, and vice versa (more significant bits are forced to $x$).

In the first case, we are looking for a solution in the range $x10^{|\beta|}$ to $b$, which reduces to $0^{|\beta|}$ to $b$; that you already know how to solve.

In the second case, we are looking for a solution in the range $x0\alpha$ to $x01^{\alpha}$, which reduces to $\alpha$ to $1^{|\alpha|}$; that should have a solution analogous to the case you're familiar with.


If 2 and 3 are both true, then the red-black trees you are sudying are not the standard ones, i.e., the ones from wikipedia.

The red nodes are usually assumed to be "satellites" of the black node above. If there is at most one red node attached to a black one that means either one or to keays belong together (with altogether either two or three pointers to their children). That nicely corresponds to a 2-3 tree.

The "usual" red-black trees can have two red children (but no red child to a red node) and correspond to 2-4 trees.


Would memoization make any improvement to Strassen's algorithm?

I don't get why the other answerers don't even make an attempt to reason along the lines the question has been asked. If anything, they should explain why memoization can or cannot work.

In any case, let's think about how we can can approach memoization in the Strassen's algorithm. We know that it involves dividing our matrix into four equal quarters, calculating products of individual submatrices and combining them through addition with the following complexity:

$T(N) = 7T(N/2) +  O(N^2)$

The one place where we can apply memoization is in the product of the submatrices stage. Each time we encounter two submatrices that need to be multiplied, we can store the result hoping that we encounter the same submatrices again and don't have to recompute the product. This will take up a lot of memory of the order of $O(N^2)$ for each saved product.

That brings us to the next question - How many products are going to be there? We will be having one $N^2$ matrix in the outermost call, $7(\frac{N}{2})^2$ matrices in the next call, $49(\frac{N}{4})^2$ matrices in the subsequent call and so on until $7^{(log N)}$ individual products. You will notice that we're using more and more memory as the recursion depth increases. (The memory requirement will be greater than $O(N^2)$)

Although the memory size is large, what is really important for us is to locate a given matrix from the set of stored matrices. Naively, this would take $O(number\_of\_products \cdot N^2)$ time for iterating through all of the products computed so far. We can probably make it faster by passing the input matrices through a hash function and mapping the hash value to the matrix. This can be done in $O(N^2)$ for the right choice of hash function, and $O(1)$ for a map based lookup.

How will this affect our complexity? We now do an additional lookup before computing the product, and save the product right after as well. $T(N) = O(N^2) + 7T(N/2) + O(N^2) + O(N^2)$. This is equivalent to our original complexity.

This shows us that asymptotically, we don't do worse in terms of time complexity although the space complexity shoots up.

Will it actually speed things up? It really depends on how often we will have repeating submatrices that we need to recompute. I do not think that in any practical scenario (especially if we are dealing with floating point operands), we will see the same sets of submatrices too many times. But this is an intuition. If I were you, I'd try it out and empirically find out if it helps.


Is a balanced binary tree a complete binary tree?

A complete binary tree is a binary tree of length $h$ such that all the levels from $1$ to $h-1$ are completed and the last level gets completed from left to right. As in the image below.

A balanced binary tree is a binary tree of height $h$ such that the height of any node’s right subtree and left subtree differ no more than $1$. So it doesn't say anything about it having to be completed from left to right.

The figure above describes this trees very clearly in a recursive way.


Comparing asymptotic running time of two algorithms $\sqrt n$ and $2^{\sqrt{\log _{2}n}}$

In order to compare two quantities/expression, it is often easier if they are in the same form. Here try expressing $t_a(n)$ as $2^{s_a(n)}$ and compare $s_a(n)$ with $\sqrt{\log_2 n}$.

Additionally, beware of using a program to check asymptotic comparisons: e.g. $f(n)=n^{10^6}$ and $g(n)=(1,0000000000000001)^n$


How to formulate Traveling Salesman Problem (TSP) as Integer Linear Program (ILP)?

You must have entered your ILP program into the ILP solver wrong.  It's easy to verify that the ILP program is feasible, using the procedure I outlined in the comments.  In particular, from the tour $c_0 \to c_1 \to c_2 \to c_0$ we get the assignment $e_{0,1}=e_{1,2}=e_{2,0}=1$ and $e_{1,0}=e_{2,1}=e_{0,2}=0$.  Setting $u_1=0$ and $u_2=1$, we find a feasible solution: you can easily check by hand that every one of your equations is satisfied.  So, you've done something wrong in entering it into the tool.

In the future, you should do that kind of sanity check on your own before asking here.


There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.


How to design a top-1 select algorithm to maximize a variable and minimize other variable?

This question is not answerable.  Only you can tell us what counts as a good tradeoff, for you.  You need to pick a single objective function that combines A and B into a single quantity.  We can't tell you how to do that, because that will depend on what makes sense for your particular application domain.

For instance, maybe it's best to choose the item with the highest value of $A/B$.  Or maybe it's best to choose the item with highest value of $A-B$.  Or maybe its' best to choose the item with highest value of $100A-B$, or $A-100B$, or $A + 1/B$, or $100A + 1/B$.  We can't tell you.  You will need to analyze your application to determine what the right objective function is.  Take a look at your specific application and understand what is a measure of benefit or cost that is meaningful in your application domain, and then figure out how that depends on $A$ and $B$ ... and use that as the objective function to maximize.


Understanding the Reasoning Behind These Typing Rules

For question 1, I don't think that the $D$ carries any particular meaning, it is just part of the notation, and might refer to the name given to the corresponding calculus.

For 2, what you need to understand is that $\Gamma$ really is a set of assumptions. So if $\Gamma = x_1 : \sigma_1, \dots, x_n : \sigma_n$ then $\Gamma$ is a typing context that tells us that we will assume that $x_1$ has type $\sigma_1$, that $x_2$ has type $\sigma_2$ and so on.

Now, what might be confusing to you is that there are several different levels of implications in the syntax of typing rules.

First, the typing rules themselves are implications of the form "if the premises hold, then the conclusion hold" (the premises being the hypotheses given above the line, and the conclusion being the typing judgment below the line.
Second, a typing judgments $\Gamma \vdash e : \sigma$ is also a form of implication, meaning "if the assumptions on the types of variables given in $\Gamma$ are correct, then $e$ has type $\sigma$".
And finally, there is also the arrow type $\sigma_1 \to \sigma_2$, which is also a form of implication.

So in the end, what the [Var] rule says, is that we may assume that $x$ has type $\sigma$, provided that this is part of our assumptions. Or in other words, it is always true that $x$ has type $\sigma$ under the assumption that $x$ has type $\sigma$. Or, reformulating again: when you made an assumption, you have the right to use it.

For 3, the main thing that you need to understand is that typing rules are implications (as explained above). For example, [App] says that if we can show that $e_1$ has an arrow type and that $e_2$ has the same type as the domain of the arrow (i.e., $e_1$ and $e_2$ have compatible types), then we can perform an application.


What are the differences between LCF's Theorem and Automath's Prop?

The difference is in what kind of type theorem/Prop is.
In Isabelle, theorem is a type in the underlying implementation language, that is made abstract so that the only way to create an inhabitant of that type (i.e. a valid theorem) is in the end to resort to the primitives provided by the kernel. So it is the typing constraints of the implementation language together with the restricted primitives that forces you to inhabit only correct theorems. Also, in that setting proofs can be any program in the implementation language producing an object of type theorem, but they have no specific status, and cannot be manipulated directly.
On the contrary, Prop is a type in the theory of Coq, but not in its implementation language: if you look at the OCaml code, there is no such thing as a Prop type, only a type of terms. Verifying that a term (written in a specific language called Gallina, the proof/programming language of Coq) is indeed a valid proof is a job of a specific type-checker. This type-checker is the kernel. In that setting, proofs have a specific status, being syntactical objects of a given type of terms in the implementation, and as such can be manipulated, inspected and so on. In particular, the tactic languages are used to generate such proofs, which is not the same as directly constructing an inhabitant of theorem, because such terms will still in the end be inspected by the kernel, which is the only judge of what is a valid proof.


Convolutional Neural Network Example in Tensorflow

Your calculation would be correct if the example were following the "usual" approach of having convolution chop off the edges.

Instead the example you pointed to says:

  How do we handle the boundaries? What is our stride size? In this example, we're always going to choose the vanilla version. Our convolutions uses a stride of one and are zero padded so that the output is the same size as the input.

So they are:

zero-padding the 28x28x1 image to 32x32x1
applying 5x5x32 convolution to get 28x28x32
max-pooling down to 14x14x32
zero-padding the 14x14x32 to 18x18x32
applying 5x5x32x64 convolution to get 14x14x64
max-pooling down to 7x7x64.

They probably have an option to turn the zero padding off.  In other infrastructures I've used zero padding is not the default.  (In several of the infrastructures I've used zero-padding isn't even possible.)


Calculating time complexity of a code which may be incorrect

On a more practical level, it sounds like this probably just stems from a typo on the instructor's part. If this is in the context of a big-O exercise, I'd just fix the typos and move on. Instructors do make mistakes too!

Getting a bit more abstract, if a program won't run, it doesn't really make sense to speak of its time complexity because it has no runtime.

Getting even more abstract - you actually can use big-O analyses to show that certain pieces of code cannot be correct. For example, suppose someone proposes a new comparison-based sorting algorithm. If you do a big-O analysis and see that it runs in time O(n) in the worst case, you are guaranteed that the code has to be wrong because of the requirement that all comparison-based sorting algorithms run in time $\Omega(n \log n)$ on average. This is different than talking about code that won't even compile, but it does show that analyzing the time complexity of incorrect (here, legal but wrong) code may be worthwhile.


Adjacency is not relevant for determining Read-After-Write dependences.  You simply list all the instructions where one of the source registers reads the value produced by some previous instruction.

So (assuming that your assembly language is OPERATOR DEST SRC1 SRC2) you are missing, for example, that the first source operand of I3 dependends on the value written by I1.  (You are missing several others as well.)


Is it possible to define branches which, once taken once, will become the default forever?

Update

Based on your comment,

  I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all.

, I think that I understand the question better now.  And the answer is that you want currying to be applied on the first execution.

As a quick explanation of currying, consider a mathematical function
$$f\left(x,y,z\right)=x+y+z,$$
but you know that $x=y=z=1$, such that this could be reduced down to
$$f\left(\right)=3.$$
You want this, except in your case you want to reduce a switch function down to a single one of its branches.

This is entirely possible - you basically just need to recompile the code for that function.  Or, if you're working in an interpreted language (e.g., JavaScript), you can simply define the switch function as its branch to replace it.

In practice, you won't need to worry about it too much in typical cases because:

Most switch statements aren't executed enough to be computationally significant.
When switch statements are executed enough to be computationally significant, but continue to resolve to the same branch each time (as you're asking about), the CPU will tend to use branch prediction to optimize it away automatically.

Example:  StackOverflow: "Why is it faster to process a sorted array than an unsorted array?" is about a dramatic example of branch prediction at work.  The tl;dr there is that sorting a list caused branches to tend to evaluate the same way over time (as you're interested in), resulting in a dramatic speedup.

Still, if the switch statement's proving to be a major bottleneck or you just want to do this anyway for fun (which is a very under-valued rationale - where would we be today if people just didn't do stuff for the heck of it?!), then you have a few options:

Split up the method that calls the switch statement into several variants, each of which does a different branch.

Perform this split just high enough to be outside of the critical section.
In effect, this will be like having pre-compiled (and optimized!) versions of the code for each of the possibilities.
For a jargon description, you'd be hoisting the switch nodal point outside of the performance-critical code region.

Actually curry-and-recompile the method at runtime.

Depending on your platform, this can have some technical barriers.
When you recompile, you have to figure out what part of the program to recompile.  If you do the entire thing, then it could take a while, etc..  But if you do only the switch statement, then optimizations around that area in the code will become prohibited, plus your program will need an extra function-call step to call the switch statement and its ultimate reduction.
As with Option (1), the optimal choice here is probably to recompile the critical section, as opposed to just the switch statement or the entire program.

Specific answers

  a) This sort of optimization exists in theory ?

Sure, you're talking about splaying, such as implemented in a splay tree.

Obviously you can't implement this sort of optimization in rigid control structures like a switch statement in C/C++, so it'll take making your own implementation of something like a a splay tree that has methods as terminal nodes.

According to your description, you may want the reorganization process to stop after order's been changed once.  If so, that's a modification you can add into the splay tree's logic.  You can even instruct it to recompile itself in a more rigid, switch-like structure once the structure's determined and the splay logic's no longer needed.

  b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

Perhaps in some.  It's an implementation detail, so it may be implemented in some implementations but not others.

  c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?

Yeah, definitely!  You need to statically compile the methods, but you can have a splay tree that resolves method pointers, then run those.

Comments

Just in case there was any confusion, switch statements don't normally need to check cases one-by-one.

For example, consider:

switch (x)
{
    case 0:    foo_0();    break;
    case 1:    foo_1();    break;
    case 2:    foo_2();    break;
    case 3:    foo_3();    break;
}

I'd expect a good compiler to implement this more like:

function[] switchBranches = { foo_0, foo_1, foo_2, foo_3 };
var selectedBranch = switchBranches[x];
selectedBranch();

than as:

if      (x == 0) { foo_0(); }
else if (x == 1) { foo_1(); }
else if (x == 2) { foo_2(); }
else if (x == 3) { foo_3(); }

So if you're doing something like this, you don't really need to worry about the compiler reordering the switch statement's cases since it's already a constant-time lookup.

In more general cases, where a deterministic index isn't practical, dictionary-lookup logic can be applied.


Cormen. Red-black trees. Why do we need to rotate the tree after fixing its properties?

After recoloring in (b), the following rule is still violated:

children of a red node are black.

Recoloring while preserving black height in step (b) introduces new double red nodes 2 and 7, which remains after step (c) and finally eliminated in step (d).


Prove (non-)recursiveness of a set of Turing Machines defined by behavior

$\boxed{\mathcal R}$

Idea: If you never move right, you have a regular behaviour. And you can move right iff a "state" in which you can move right is reachable while following this regular behaviour.

Solution:

   $\mathcal R$ is decidable

Proof:

   Let $\mathcal M$ be a TM with states $Q$ and tape alphabet $\Gamma$. Build the following automaton:

 - States: $Q\times (\Gamma \sqcup \{?\})$ where the right component is whatever is on the tape at the current position (we write $?$ if it is whatever was there at the very beginning, and $a$ if we wrote an $a$ there)

 - Transitions:
 $\hspace{0.5em}$ - $(p, a)\overset{a}{\to}(q,?)$ if the TM can read $a$ while in state $p$ and move left
 $\hspace{0.5em}$ - $(p, a)\overset{\varepsilon}{\to}(q,b)$ if the MT can write a $b$ and move to state $q$ if it's in state $p$ and reads an $a$
 $\hspace{0.5em}$ - $(p, ?)\overset{\varepsilon}{\to}(p,b)$ (because since we just moved left and never moved right, replacing the letter at that position on the tape by anything wouldn't change the execution until that point).
 - The initial states are $(q_i, ?)$ where $q_i$ is an initial state of the TM.

 Then in this automaton, a state $(p,a)$ is accessible iff there is a run in the TM so that gets in a state where the TM is in state $p$ and is about to read an $a$ on the tape. So you just have to check if there is an accessible state $(p,a)$ in this automaton so that the TM can read an $a$ while in state $p$ and move right.

$\boxed{\mathcal S}$

Idea: Halting for all inputs is "For all input, there is an execution that halts" which is more complicated than the halting problem "Given this input, there is an execution that halts".

Solution:

   $\mathcal S$ is undecidable

Proof:

   Take a TM $\mathcal M$ and an input $w$. Build a new TM $\mathcal M'$ that erases its input, writes $w$ and then runs $\mathcal M$.

 $\mathcal M'$ halts on all inputs
 (iff $\mathcal M'$ halts on some input)
 iff $\mathcal M$ halts on input $w$

 So your problem is undecidable because the halting problem can be reduced to it.


Is there a way to create a "captcha"-like problem that computers can verify, but only humans can solve?

Yes.  Computer A can generate a CAPTCHA encoding a 24-digit code, and also compute a cryptographic hash of the correct response.  Computer A can give the CAPTCHA and the hash to B and C.  Now if B claims to have solved the CAPTCHA, computer C can verify the claimed answer using the cryptographic hash.  The cryptographic hash doesn't help computer C solve the challenge, because the hash is one-way and cannot be inverted (except by trying all possible codes, but that would take far too long).

In practice, this is not very effective, because no one knows how to build a CAPTCHA that humans can solve but that is expensive for computers to solve.  For one thing, there are black-market services that will solve CAPTCHAs for you at the price of about $1-2 per thousand CAPTCHAs solved, i.e., about 0.1-0.2 cents per CAPTCHA.  For another, there are algorithms that break most CAPTCHAs with probability higher than we'd like.  So ultimately, CAPTCHAs kinda suck.  But the reasons they suck have nothing to do with verifiability.  If we could make a CAPTCHA that didn't suck, we could probably build one that was verifiable in the sense you mention.

Also, if you were implementing this in real life, you'd make sure to use a slow hash (like PBKDF2, scrypt, or bcrypt) when hashing the code.  But again, because CAPTCHAs have so many limitations, I'm not sure you'd want to implement this scheme in real life anyway.


Yes, a given set can be represented by multiple red-black trees, and this works incrementally, at least some of the time.  That is, there exists more than one valid red-black tree insertion algorithm, whose outputs are not always equal.

The easiest way of seeing this is to focus on the correspondence between red-black trees and $(2, 4)$-B-trees.  A black node with its red children correspond to a B-tree node.

In particular, if you have two sibling B-tree nodes with four elements in total, they can be distributed 1/3 or 2/2.  In red-black terms, if two black nodes are cousins, it's possible for each to have one red child, or for one of them to have two red children and the other to have none.  More than that, you can shuffle the elements around between the nodes locally to transform one such pattern into the other.

As wikipedia says, "The balancing of the tree is not perfect, but it is good enough to allow it to guarantee searching in O(log n) time"; the imperfection of balancing gives room for multiple tree representations of the same set.


Difficulty understanding pre-emptive vs non-preemptive CPU scheduling

In circumstances 1 and 4, the current process can't continue running.  Therefore, there's no choice: the OS scheduler has to step in and select a different process.

In circumstances 2 and 3, the OS scheduler has a choice: it can either allow the current process to continue running, or it could step in and put the current process to sleep and select a different process to run.  The latter operation is called "preempting" the current process and scheduling a new one to run.

So, yes, your understanding sounds about right.


Selection problem on the union of two ordered dictionaries

The following algorithm uses the divide-and-conquer technique. In the course of divide-and-conquer, the lengths of both sorted arrays $S$ and $T$ will change. We denote the length of $S$ (or, $T$) by $len(S)$ (or $len(T)$) at any time. Notice that I only summarize the algorithm and have intentionally omitted the tricky things about indexes (e.g., taking floor or ceiling).

Notations and Basic Idea:

At any iteration, denote the median index of $S$ by $s_m \triangleq len(S) /2$ and the median of $S$ by $S[s_m]$.
Similarly, denote the median index of $T$ by $t_m \triangleq len(T) / 2$ and the median of $T$ by $T[t_m]$.

  The basic idea is as follows: we compare $s_m + t_m$ with $k$ and $S[s_m]$ with $T[t_m]$ to determine which (left or right) half part of which array ($S$ or $T$) can be discarded and then we can leave the smaller sub-problem to recursion.

Algorithm:

Case 1 ($s_m + t_m \geq k$):

1.1 Case 1.1 $S[s_m] \geq T[t_m]$.

We can discard the right bigger half of array $S$ (i.e., from $S[s_m]$ to its end). Then recursively find the $k$-th smallest element in $T$ and the left smaller half of $S$.

1.2 Case 1.2 $T[t_m] > S[s_m]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.
Case 2 ($s_m + t_m < k$):

2.1 Case 2.1 $S[s_m] \geq T[t_m]$.

We can discard the left smaller half of array $T$. Then recursively find the $(k - t_m)$-th smallest element in $S$ and the right larger half of $S$.

2.2 Case 2.2 $T[t_m] > S[s_m]$.

It is exactly symmetric with Case 1.1, with $T$ and $S$ exchanged.

Time Complexity:

At each iteration, we discard a half of some array. So the time complexity is $O(\lg (len(S)) + \lg (len(T)))$, which is $O(\lg n)$ for input arrays $S$ and $T$ of size $n$.

References:

How to find the kth smallest element in the union of two sorted arrays?
Finding kth smallest number from n sorted arrays A generalization to multiple sorted arrays.


Addressable cell size of one byte, in this context, means that every cell in memory contains one byte. Variables which take up more than one byte are spread across several contiguous cells.


Unrolling closures into SAT boolean formula

It's important to remember that SAT can only encode problems that are in $NP$, unless you use more than polynomial-length formulas. I'm not 100% sure, but I'm doubting your problem is in $NP$.

Consider the following function:

$F = \lambda x\ y \ldotp x x (\lambda y . y y)$

Now consider evaluating $F F (\lambda z \ldotp z)$.

This clearly runs forever, but we can also see that the argument given as $y$ will grow exponentially with the number of $\beta$ reductions you do.

Now, some things that aren't clear from the question:

  non-deterministically represented candidate program

What does this mean? Is the program non-deterministic? Or its representation? What even is a non-deterministic representation?

  static once created and have a small number of predefined variables within each combinator

Again, what does this mean? My example doesn't seem to fit this, but if whatever you're dealing with us Turing Complete, my gut says your problem is likely to be $EXPTIME$-hard.


How page table base register (PTBR) is used to locate the correct frame using Page Number?

I'll take x86 32 bits PCs as an example. On 32 bits x86 PCs, the CR3 register is used as the PTBR. The CR3 register contains the 4KB aligned address of the page directory. The page directory contains addresses of the different page tables. The x86 processors have virtual addresses which are separated in 3 parts. The 10 most significant bits are the offset in the page directory, the 10 bits in the middle are the offset in the page table and the 12 last bits (to the right) is the offset in the physical page in RAM. Let's look at an example. Let's take address 0x12345678. This is a 32 bits address which translates in binary to 0001 0010 0011 0100 0101 0110 0111 1000. Now let's look at the different parts of this address.
Page directory offset        Page table offset        Physical page offset
   00 0100 1000                11 0100 0101             0110 0111 1000

So in the end this virtual address will translate to page directory entry 0b0001001000 = 0x72 = 114 decimal, page table entry 0b1101000101 = 0x345 = 837 decimal and the offset in the physical page will be 0b011001111000 = 0x678 = 1656 decimal
Depending on what is the content of each selected entries by this virtual address, the actual physical address can be anywhere in RAM. In this example we have entry 114 in the page directory. If at entry 114 is written 0x1234, the MMU of the CPU will look there for the page table. It will use address 0x1234 as the bottom of the page table and then find entry 837 which could contain 0x12345. So the final physical address translated will be 0x12345 + offset_in_physical_page = 0x12345 + 0x678 = 0x129BD. This will be the final physical address once translated using the example that we have here.
On more modern processors you will have 4 levels of page tables so the virtual address will be split in 5 parts. 4 parts of 9 bits to the left and 1 part of 12 bits. Only 48 bits are used for now with the leftover bits to be used later (once there are more page table levels).


Turing NP complete but not Karp NP complete?

The complement of any NP-complete problem (including SAT itself) is polynomial-time Turing-interreducible with SAT but, there's a Karp reduction if, and only if, NP$\,=\,$co-NP.


How is this lamda function beeing executed in an example for the Y combinator

I am just going to write h for almost-factorial because long names can sometimes obscure math.

We consider:

((lambda (x) (x x))
 (lambda (self)
   (h (self self))))

Write foo for ((lambda (x) (x x)) and write bar for (lambda (self) (h (self self)))). Then our expression is just

(foo bar)

Using the definition of foo we see that this is equal to

(bar bar)

Then we use the definition of bar on the first occurrence of bar to see that this is equal to

((lambda (self) (h (self self)))) bar)

which in turn is just

(h (bar bar))

We discovered that (bar bar) is equal to (h (bar bar)). Let us write g for (bar bar), so g is equal to (h g). Taking into account the definition of h (which is jsut almost-factorial from your question) we see that (h g), and therefore g, is equal to

(lambda (n)
  (if (= n 0)
      1
      (* n (g (- n 1)))))

In other words, g is the usual factorial function. I hope I got all the silly lisp parentheses where they are supposed to be.


No, it is not. If you have a look at the Decomposition theorem for example, then you will find, that there are properties you cannot express as neither a SP or LP, but as an intersection of a SP and LP.

There exist such SP and LP, that their intersection is a safety property. For example the property of all possible traces, the result is again the property of all possible traces. Which incidentally is the only property that is both safety and liveness.


Can the definition of regular languages be simplified?

No. Closure under concatenation means that, if $A$ and $B$ are regular languages, then so is the language of strings formed by concatenating taking one string from $A$ and one from $B$. Closure under Kleene star means that, if $A$ is a regular language, then so is the langauge formed by taking any finite number of strings from $A$ and concatenating them.

If you delete Kleene star then every regular language would be finite. The reason is that any given regular language must be formed by a finite number of operations from the basic languages ($\emptyset$ and singletons). But any language whose definition involves no Kleene stars and only $k$ concatenations can only contain strings of length at most $k$, so it must be finite (it has at most $|\Sigma|^k$ strings in it).

Since there are infinite regular languages, the languages formed without Kleene star are a strict subset of the regular languages.


Understanding $\epsilon$ transitions on NFA

$\epsilon$ is an empty string just like "". It is not a symbol of the alphabet. It simply means (in the NFA in your picture) that if you are on state $q_1$, without consuming any symbol you can move to state $q_3$ but you are not obliged to do so. but if you are on $q_1$ and you read $b$, then you must go to $q_2$.

Note that a word is accepted in a NFA if there exists a path from the initial state to an accepting state labelled by the symbols of this words. if should be rejected if no such a path exists.

When $a$ is entered then the possible path is move to $q_3$ without consuming anything and then consume $a$. This lead to the accepting state $q_1$.


Query on consequences of $\mathsf{P=BPP}$

The conclusion is that the permanent does not have polynomial-size (constant-free) arithmetic circuits or $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$. Permanent not having polynomial-size constant-free arithmetic circuits is not known to imply $\mathsf{NEXP} \not\subseteq \mathsf{P/poly}$.

However, there are a couple more recent similar results whose conclusion is not a disjunction, but simply a lower bound on some polynomial family in $\mathsf{NEXP}$:

Jansen and Santhanam showed that if PIT is in $\mathsf{NSUBEXP}$ then there is a family of polynomial whose integer evaluation problem is in $\mathsf{NEXP}$ but which do not have poly-size constant-free arithmetic circuits.
Carmosino, Impagliazzo, Kabanets, and Kolokolova show that if PIT over a fixed finite field is in $\mathsf{NSUBEXP}$ then there is a multilinear polynomial whose evaluation problem over that same finite field is in $\mathsf{NE}$ that does not have poly-size arithmetic circuits. (This paper also has many other results of interest, including true hardness-to-randomness equivalences, avoiding many of the usual caveats.)


Any ideas on implementation of a certain image process?

The first effect that appears at the video is a hue change. Later this is morphing, which is a feature based operation.

It seems like some similarity between images is used to set the morphing points (looking at the consecutive changes the points that do not move are chosen separately per transition).

The part of comparing two images (your last sentence) is used to make transition smoother, otherwise it would resemble warp. This is known as the Temporal Coherence, another technique includes Structural Similarity. Techniques yielding the best results are semi-automatic or manual due to a big complexity involved in finding smooth, minimal transition well perceived by people and also lack of good formula evaluating "how natural" transition looks like. The optimal transition calculated as minimal sum of changes does not yield nice looking morphing.

Sometimes a motion blur is added on top of the morphing (between patches) to make transition look better.


Factorial algorithm more efficient than naive multiplication

The best algorithm that is known is to express the factorial as a product of prime powers.  One can quickly determine the primes as well as the right power for each prime using a sieve approach.  Computing each power can be done efficiently using repeated squaring, and then the factors are multiplied together.  This was described by Peter B. Borwein, On the Complexity of Calculating Factorials, Journal of Algorithms 6 376–380, 1985. (PDF)  In short, $n!$ can be computed in $O(n(\log n)^3\log \log n)$ time, compared to the $\Omega(n^2 \log n)$ time required when using the definition.

What the textbook perhaps meant was the divide-and-conquer method.  One can reduce the $n-1$ multiplications by using the regular pattern of the product.

Let $n?$ denote $1 \cdot 3 \cdot 5 \dotsm (2n-1)$ as a convenient notation.
Rearrange the factors of $(2n)! = 1 \cdot 2 \cdot 3 \dotsm (2n)$ as
$$(2n)! = n! \cdot 2^n \cdot 3 \cdot 5 \cdot 7 \dotsm (2n-1).$$
Now suppose $n = 2^k$ for some integer $k>0$.
(This is a useful assumption to avoid complications in the following discussion, and the idea can be extended to general $n$.)
Then $(2^k)! = (2^{k-1})!2^{2^{k-1}}(2^{k-1})?$ and by expanding this recurrence,
$$(2^k)! =  \left(2^{2^{k-1}+2^{k-2}+\dots+2^0}\right) \prod_{i=0}^{k-1} (2^i)? = \left(2^{2^k - 1}\right) \prod_{i=1}^{k-1} (2^i)?.$$
Computing $(2^{k-1})?$ and multiplying the partial products at each stage takes $(k-2) + 2^{k-1} - 2$ multiplications.  This is an improvement of a factor of nearly $2$ from $2^k-2$ multiplications just using the definition.  Some additional operations are required to compute the power of $2$, but in binary arithmetic this can be done cheaply (depending on what precisely is required, it may just require adding a suffix of $2^k-1$ zeroes).

The following Ruby code implements a simplified version of this.  This does not avoid recomputing $n?$ even where it could do so:

def oddprod(l,h)
  p = 1
  ml = (l%2>0) ? l : (l+1)
  mh = (h%2>0) ? h : (h-1)
  while ml <= mh do
    p = p * ml
    ml = ml + 2
  end
  p
end

def fact(k)
  f = 1
  for i in 1..k-1
    f *= oddprod(3, 2 ** (i + 1) - 1)
  end
  2 ** (2 ** k - 1) * f
end

print fact(15)

Even this first-pass code improves on the trivial

f = 1; (1..32768).map{ |i| f *= i }; print f

by about 20% in my testing.

With a bit of work, this can be improved further, also removing the requirement that $n$ be a power of $2$ (see the extensive discussion).


It probably depends on what $\mathcal{F}$ is -- the text tells you.
Each $f\in\mathcal{F}$ is a build-in/primitive function (such as $+$) and [pur7] gives the result of applying it to some arguments. $[\![ f]\!]$ gives the semantic interpretation of the function, and applying that to the arguments $v_1,\ldots,v_n$ gives the result of the function.


Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

This phenomenon is known in computer science as a time-space tradeoff. For example, Ryan Williams proved that if a computer solves SAT on instances of size $n$ in time $T$ and using memory $S$ then $T \cdot S \geq n^{1.8}$. (We don't expect this to be tight.) A classical result states that when recognizing palindromes on a Turing machine, $T \cdot S = \Omega(n^2)$.


What is the intuition on why the longest path problem does not have optimal substructure?

The longest path problem does have optimal substructure, and this can be used to improve the trivial $O(n!)$ algorithm to an $\tilde{O}(2^n)$ algorithm. First we have to generalize the problem:

  Generalized longest path: Given a graph $G=(V,E)$, two vertices $s,t \in V$, and a set of vertices $A \subseteq V \setminus \{s,t\}$, find the longest path in $G$ from $s$ to $t$ avoiding the vertices in $A$.

Denoting the solution to this problem by $\ell(s,t,A)$ (the graph is understood), we have the recurrence
$$
\begin{align*}
&\ell(s,t,A) = 1 + \max_{\substack{x \notin A \cup \{s\}: \\ (s,x) \in E}} \ell(x,t,A \cup \{s\}) \qquad (s \neq t), \\
&\ell(t,t,A) = 0.
\end{align*}
$$
If the maximum in the first case is over the empty set (that is, if there is no path from $s$ to $t$ avoiding $A$), we assign $\ell(s,t,A) = -\infty$.

You can solve this recurrence using dynamic programming in time $\tilde{O}(2^n)$.

While there is optimal substructure here, there are too many parameters to keep track of, and this is what makes the problem intractable.


Find a hole while travelling along an infinite wall

If you can go only left or right, than you can do the following strategy:

DIRECTION = Right
For i = 0 to infinity do:
    Go 2^i steps to DIRECTION.
    Go back to the initial place.
    CHANGE_DIRECTION
    STOP if you found the hole

If the distance between the start place and the hole is n, you will find the hole within O(n) steps. You can easily calculate the exact average number of steps given this algorithm.


One-dimensional k-center problem. Finding minimum distance

Hint: Turn the problem upside down and ask yourself: can I easily check if the answer is less than or equal to $t$?


Indeed, there is such a Turing Machine. First, realize that it's computable to convert any integer $k$ into the $k$th Turing Machine description, just by enumerating them. Then, once we have the Turing Machine description, we can use a Universal Turing Machine to compute the function described.

The key is that, while there are less states in the $n$-state machine than in one with $n^2$, any number of additional states can be encoded on the tape of the Turing Machine. So there's no limit to the amount of information we have when computing the $k$th function, since an arbitrary amount of information can be encoded on the tape.


Why is the following language undecidable?

This is a direct consequence of Rice's theorem. A word $w$ is in $L$ if $T(M_w)$ satisfies the following semantic property:

$T(M_w)$ is non-empty, and for any $x \in T(M_w)$, we have $x^2 \in T(M_w)$ and $x^3 \notin T(M_w)$.

In order to show that this language is undecidable according to Rice's theorem, we need to exhibit two Turing machines $w_1$ and $w_2$: one which doesn't satisfy the property, and another one which does satisfy it. We can take $w_1$ to be some machine such that $T(M_{w_1}) = \emptyset$, and $w_2$ to be some machine such that $T(M_{w_2}) = \{ a^{2^n} : n \geq 0 \}$.


How does DNS work if there is no recursive querying?

If a resolver tries to send its recursive DNS queries to a server that refuses those queries, or the queries time out, then the resolver was originally supposed to try to do an iterative query itself: ask the roots, follow referrals until an error is detected or an answer is seen.  However, nearly all resolvers are stub resolvers and simply choke at this point: they rely on being pointed to a short list of DNS servers where they can send recursive queries, and don't support doing iterative queries.  Moreover, some networks only allow DNS queries to go to a small list of approved DNS servers providing recursive service.  In this case iterative resolution wouldn't help.

(As Martin Berger points out, if the DNS server where a recursive query is sent happens to have the answer in its cache, and it is prepared to handle the recursive query, then it will supply the answer from its cache.  Presumably your phrase "if there is no recursive querying" rules this out.)

The root servers answer recursive queries with referrals to other servers.  This usually does not answer the query, and further queries are required.

If the DNS servers to which the resolver sends queries are not reachable, a DHCP lease refresh may provide a new list of servers and fix the problem.

A packet capture tool like Wireshark can show the DNS queries generated by your machine and the answers it receives.

For completeness, this is how the DNS works.

Usually the resolver is set up as a stub resolver, to send all DNS queries to a server.  This is often done by including the IP address of this server in the DHCP negotiation when connecting to the network.  The server's IP address can also be in /etc/resolv.conf or some equivalent configuration entry.  When a DNS server sees a recursive query, and it is willing to provide an answer to that recursive query, then it usually does iterative resolution.

Iterative resolution works by sending the query to the servers for the root domain.  This is a list of servers that changes infrequently; the latest one is available by FTP.

Queries to the servers for the root domain result in a referral, giving a list of name servers that are more likely to be able to answer.  The resolver picks one of these, and sends the query there.  This continues until it receives an answer, or something goes wrong: a loop occurs, a server responds with "NXDOMAIN" (no such entry exists in the DNS), or the query times out.

Name servers also keep a cache of previously seen name servers.  When a DNS server is started, the first query works as above, but subsequent iterative queries will use the cache to short-circuit the process and will be sent directly to the best server, if one is known.

Instead of the term "recursive server", it is more correct to refer to a DNS server being prepared to answer recursive queries.  Many DNS servers are prepared to answer recursive queries for some "trusted" clients but not for the Internet as a whole.


Determine if there is a subset of the given set with sum divisible by a given integer

Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a[12] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0.
So if you have n integers, create a two dimensional array of size m * (n + 1), then fill array [i, 0] for all i, then fill array a [i, 1] for all i, and so on until you filled a [i, n] for all i. And there you have the solution.
Next you figure out how to do this without using an array of (n+1) * m elements, and you figure out when you can stop early because you know the answer already.
And I would be curious if there is any reason why these numbers would have to be a set.


How Can I Recognize When to Use ε-Transitions in an NFA?

Your first drawing is a DFA (and thus an NFA) and does match the language described.  The NFA with $\varepsilon$ transitions is a fairly natural (and mechanical) translation of the regular expression, but other than that, it isn't inherently "more correct" than the NFA you started with.

The only confusion I see here other than uncertainty is once you validated that your NFA was a DFA you seemed to have just taken it for granted that it was minimal.  Starting from your DFA, you could have noticed that S4 has the same out-transitions as S2 and that they might possibly be joined.  Doing so would have immediately produced the final DFA.


How can we get a Las Vegas algorithm from a Monte Carlo one?

First, the algorithm should run forever; since you are going to stop when you have a correct answer. By this way you can guarantee that you never outputs a wrong answer. So, probability of error is zero.

So, the algorithm should be as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     if solMC is correct
4)         return solMC
5)     else
6)         solMC = MC(n)
7)     end
8) end

Also, verify the solution from MC(n) by the given in the question which takes t(n) running time; because you don't know that monte carlo algorithm outputs correct or not. Also I removed the else condition, I don't see it is important here. So, the algorithm should be edited as following:

Algorithm LA
1) for i = 1 to infinity do
2)     solMC = MC(n)
3)     answer_from_verifier = output_Verify(solMC)
3)     if answer_from_verifier is correct
4)         return solMC
7)     end
8) end

Now, the expected running time is:

$E[X]= \sum_{i=0}^{\infty} (1-\gamma)^i \gamma (i+1) (T(n)+t(n)) $

$= \gamma (T(n) + t(n)) \sum_{i=0}^{\infty} (1-\gamma)^i (i+1)$

$= \gamma (T(n) + t(n)) . 1/\gamma^2$

$= \frac{T(n)+t(n)}{\gamma} $


Possible partitions, for k-means problem(k=2)

If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$.
That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$.
If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity).


Reachability queries on uncertain graphs

I edited your question to make it self-contained.

The literature on uncertain graphs is really rich for this problem. What you are looking for is "reachability in uncertain graphs", which has been studied extensively in database community [1].

Basically, you have an edge between two vertices $u$ and $v$ with probability $p_{uv} \in (0,1]$. You need to find whether two given vertices are reachable, therefore, lie in the same connected component or disjoint set. I suggest you take a look at the following paper as starting point, which describes the basics and can lead you to more works that have been done on this problem:

[1] Jin, Ruoming, et al. "Distance-constraint reachability computation in uncertain graphs." Proceedings of the VLDB Endowment 4.9 (2011): 551-562.


Circuit of constant depth that takes three binary numbers and outputs two binaries?

A circuit which would satisfy this requirement is a carry-save adder.  I'm sure you can find a reference for the gate layout somewhere.


Infinite prefix-closed context-free languages contain an infinite regular subset

Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.


Are there lossless data compression techniques that do not exploit repetitive patterns?

Modeling data compression as a combination of statistical modeling and encoding seems a bit obsolete these days. In many compression algorithms, the most important step is combinatorial modeling, which finds structure in the data and uses the structure to transform the data into something that can be compressed with statistical methods. For example:

Burrows-Wheeler transform permutes the characters based on the lexicographic ordering of the suffixes starting after them.
Algorithms in the Lempel-Ziv family describe the text in terms of exact and/or inexact repeats.
A graph can be described in terms of bicliques (subgraphs with an edge from every node in vertex set $A$ to every node in vertex set $B$).
A text can be represented by a context-free grammar.
A collection of similar strings can be described by the edit operations required to transform a reference string into each of the individual strings.
The collection can also be described by a finite automaton recognizing a more general language, plus the paths used to produce each of the strings.
A suffix array has self-repetitions, where each pointer in the source substring is incremented by 1 in the target substring.
A (multi)set of integers can be represented as a binary sequence.

In principle, one can describe these combinatorial models in statistical terms, but the statistical viewpoint may not be very useful. Furthermore, many practical algorithms skip the statistical modeling/encoding part completely or do them in a naive way, as decompression speed may be more important than maximal compression.

All of these methods take advantage of the redundancy in the data or make it more explicit for the subsequent compression steps. After all, data compression is basically just getting rid of the redundancy in the data.


Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'?

You're understanding of "solve all instances of the Halting Problem" is flawed. All instances means ALL instances. Every single one, ever.

For example, no human knows if a Turing Machine verifying the Collatz Conjecture will halt. Bam, right there, your premise that humans can solve "all" incarnations of the Halting problem is flawed.

There is no reason to think that a sufficiently good AI wouldn't be able to solve the same, or more, instances of the Halting Problem that humans can.

The undecidability of the Halting problem means that there is no algorithm which solves the halting problem. That means there is no algorithm Humans can use, and no algorithm machines can use. The proof doesn't rely on what the algorithm runs on.

Another way to look at it is that the halting problem, and other undecidable problems, essentially boil down to searching an infinite space. The inability of humans to time travel and examine an infinite number of instances doesn't negate our intelligence, so there's no reason it would for machines either.


An axiomatic theory of computational models?

The question "what is a computational model" is quite open ended and is difficult to answer definitely. It's a bit like asking "what is geometry". But people have given some answers.

As far as I can understand you, you are looking for a general theory of computation (so, not a model that "contains other, for what's that supposed to mean, nor an "axiomatization" of a specific thing). One such theory is offered by partial combinatory algebras (PCA), which are very simple structures that subsume many models of computation, including: Turing machines (with and without oracles), $\lambda$-calculus (with many of its extensions), enumeration operators, and even topological models of computation. There are further variants of PCAs: ordered PCAs, typed PCAs, etc.

One should never just "collect models of computation" but also ask how to relate them, so we should think about transformations between PCAs. John Longley gave a very good account of these, namely the applicative morphisms. Speaking a bit vaguely, an applicative morphism is an interpretr of one PCA implemented in another PCA.

If you are interested in this topic you can consul Jaap van Oosten's book on realizability.


In general cummulative universes are a bit nasty. To see what is really going on, at the very least it makes sense to have explicit lifting maps $\mathsf{lift}_{i,j} : \mathcal{U}_i \to \mathcal{U}_j$ for $i \leq j$. With these in place, your question is: how do the types
$$\mathsf{lift}_{i,i+1}(A =_{\mathcal{U}_i} B)$$
and
$$(\mathsf{lift}_{i,i+1} A) =_{\mathcal{U}_{i+1}}(\mathsf{lift}_{i,i+1} B)$$
relate?
The answer is: unless we make further assumptions, we cannot show them to be equivalent. In fact, when type theory is given with explicit $\mathsf{lift}_{i,j}$ maps, we include judgemental equalities which say "lifting maps commute with type constructions", such as, for $i < j$,
$$\mathsf{lift}_{i,j}(A =_{\mathcal{U}_i} B)
\equiv
(\mathsf{lift}_{i,j} A =_{\mathcal{U}_{j}} \mathsf{lift}_{i,j} B).$$
These sorts of details are usually skipped in informal presentations of type theory. In particular the HoTT book is a bit sloppy on this point. (But the formalizations of HoTT in Coq, Agda and Lean are not.)