Number of Function Calls In Recursive Code

First, let me correct the program:

1 function win(n)
2     if memo(n) exists:
3         return memo(n)
4     if n ≤ 3:
5         memo(n) = true
6     else:
7         memo(n) = not win(n-2) or not win(n-3)
8     return memo(n)

Compared to your code, there are two main differences:

If the value of the function is already known, that it is immediately returned (lines 2–3).
Otherwise, we compute the value of the function recursively by invoking win rather than memo (line 7).

The running time of win depends on which values have already been calculated. For example, if you already computed the value of win on $n-2$ and $n-3$, then computing it on $n$ takes time $O(1)$. We can also bound the running time of win on input $n$ by $O(n)$, since lines 4–8 run at most once for every value of the input.

We could also implement win without any memoization:

1 function win(n)
2     if n ≤ 3:
3          return true
4     else:
5          return not win(n-2) or not win(n-3)

The running time of this implementation satisfies the recurrence
$$ T(n) = T(n-2) + T(n-3) + O(1), $$
with base case $T(n) = O(1)$ for $n \leq 3$. Using standard techniques, we determine that the running time is $\Theta(c^n)$, where $c \approx 1.3247$ is the unique real root of $c^3=c+1$.

Finally, let us take a look at some values of win:
$$
\begin{array}{c|cccccccccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\\hline
\mathit{win}(n) & T & T & T & T & F & F & T & T & T & F & F & T & T & T & F & F
\end{array}
$$
Notice the period of 5. We can easily prove the following formula by induction: for $n \neq 1$, $\mathit{win}(n)$ holds iff $n \bmod 5 \in \{0,1\}$. This gives an $O(1)$ algorithm for computing win.


What is the correct time complexity of the following code

$$n+\frac{n}{2}+\cdots +\frac{n}{n}$$

$$= n(1+\frac{1}{2}+\cdots +\frac{1}{n})$$

Now it is a well-known fact that $1+\frac{1}{2}+\cdots +\frac{1}{n} \le c \log n$, where $c$ is some constant.

$$\le cn(\log n)$$

So the overall Runtime is $\mathcal{O}{(n \log n)}$.


Classical local search works as follows. We're trying to optimize some function under some constraints. We start with some feasible point (a point satisfying all constraints). At each step, we consider small changes to the current point which (1) keep it feasible, (2) improve the objective function. If we find such a small change, we modify the point accordingly. Eventually, we reach a local optimum, and we hope that it's not too bad relative to the global optimum.

A classical example is the simplex algorithm for linear programming. The algorithm starts with some feasible point (it's not immediately obvious how to do it; a trick is required). At each step, we try to modify the point by switching one tight constraint with another in a way that improves the objective function while keeping the point feasible. Eventually we reach a local optimum, which turns out to be a global optimum (in this particular case).

The interior-point algorithm for linear programming work differently. They start at some point, and move in a direction that (1) makes the point more feasible, and (2) improves the objective function. In the end, you get close to a feasible local optimum, which turns out to be a global optimum. This is not local search, but it's an example of an algorithm which does not maintain a feasible solution.

Non-oblivious local search is a variant on the theme of local search, in which instead of trying to optimize the actual objective function, you direct the local search using an auxiliary objective function. Sometimes this improves the quality of the local optimum. You can read all about it in a recent PhD thesis by Justin Ward.


Dynamic linking is performed at the time of program loading only and uses compile-time established names.  Dynamic loading can be done at any point in program execution.

From wikipedia:

  Unlike static linking and loadtime linking, this mechanism allows a computer program to startup in the absence of these libraries, to discover available libraries, and to potentially gain additional functionality.


Print (not count) all possible path classic climbing stair problem)

Here is pseudocode for solving this, using a recursive procedure:
All-Solutions($n$):
If $n=0$, return the solution (empty sequence).
If $n=1$, return the solution $1$.
Otherwise:

Run All-Solutions($n-1$), and prefix $1$ to all results.

Run All-Solutions($n-2$), and prefix $2$ to all results.

There is also a simple iterative solution. Start with the solution composed of $n$ many $1$s, and iteratively try to increase it, until getting stuck. How to increase a solution?

If a solution ends with $1,1$, replace this with $2$.
If a solution ends with $2,1$, consider the suffix of the form $1,2,\ldots,2,1$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell$ many $1$s.
If a solution ends with $2$, consider the suffix of the form $1,2,\ldots,2$; if none exists, then the process terminates. If the suffix contains $\ell$ many $2$s, replace it with $2$ followed by $2\ell-1$ many $1$s.

Here is an example, $n=5$:
\begin{align}
&1,1,1,1,1 \\
&1,1,1,2 \\
&1,1,2,1 \\
&1,2,1,1 \\
&1,2,2 \\
&2,1,1,1 \\
&2,1,2 \\
&2,2,1
\end{align}
Both solutions output the list in lexicographic order. The iterative one has $O(1)$ amortized update time. Indeed, the length of the list is $F_{n+1}$, and the total length of suffixes is $F_{n+3}-2$, and so the average length of a suffix is roughly $\phi^2 = \phi + 1 \approx 2.618$.


What you're calling $w^{-1}$ is a special case of what's known as a homomorphism, where, informally speaking, we define a map $h$, from an alphabet $\Sigma$ to strings over an alphabet $\Gamma$ and then extend this in a natural way to maps of words. In your case, the map is particularly simple: $h(a)=b$ and $h(b)=a$. There's quite a bit known about such maps; for instance both regular and context-free languages are closed under homomorphisms.

(For what it's worth, your $ww^{-1}$ language isn't regular.)


The important sentence in the first quote is

  In case of overriding, if a method with the same name is declared in the superclass then it must have the same type.

So if you have

class C1 { ... }
class C2 { ... }

class Cls {
    C1 foo(C2 x) { ... }
}

override(foo, Cls, (C2)->C1) holds but override(foo, Cls, (C2)->C2) doesn't; the subclass

class SubCls extends Cls {
    C2 foo(C2 x) { ... }
}

is illegal. In FJ, you can't have

class SubCls extends Cls {
    C2 foo() { ... }
}

either, unlike in Java.

  If mtype(m, D) = E→E0 implies C = E and C0 = E0, then override(m, D, C→C0 )

This is implicitly quantified "for all E and E0". If mtype(m, D) is undefined, then mtype(m, D) = E→E0 is always false, so it implies anything. If it's defined, then "mtype(m, D) = E→E0 implies C = E and C0 = E0" is equivalent to mtype(m, D) = C→C0.

So it ends up being the same as

    If mtype(m, D) = C→C0 or mtype(m, D) is undefined, then override(m, D, C→C0)

(unless I went wrong somewhere)


There are many ways to solve this. Here are some:

If $L = \{c^m b^n a^n : n>0, m\geq 0\}$ were regular then so would $L \cap b^*a^*$ be.
The words $\{ b^n : n > 0 \}$ are pairwise inequivalent modulo $L$, so $L$ is irregular according to Myhill-Nerode.
The pumping lemma works if you ignore the $c$ part.


Are all non-terminals of the CFG given by the LHS of productions?

No. Not all non-terminals necessarily appear at the LHS of productions, that is, not every non-terminal must have productions for it.

Of course, such non-terminals are rather useless and can be removed from the grammar without changing the language. Also the dual is actually possible: there might be terminal symbols that do not appear at the RHS of productions. For example $a^*$ is a context-free language over the alphabet $\{a,b\}$.


What is the semantics of a Turing machine?

The usual definitions of Turing machines are given in terms of formal semantics. For instance, the Wikipedia definition describes Turing machines in precise mathematical formalism. If you are looking for something even more formal, have a look at this Coq formalization of Turing machines.


Solving a recurrence relation involving square roots

Dividing both sides by $n$ then introducing $S(m):=\frac{T(2^n)}{2^n}$ yields:

$$S(m)=S(m/2)+1+\frac{1}{m}$$

It follows that:
$$1<S(m)-S(m/2)\leq 2$$
And further:
$$\forall k, 1<S(m/2^k)-S(m/2^{k+1})\leq 2$$
Now summing for $k=1\dots \log(m)-1$ gives us:
$$S(m)=\Theta(\log(m))$$
And so:
$$T(n)=\Theta(n\cdot\log\log n)$$


Halting problem for turing machines with one input

What you call a "liar" program is typically called a diagonalization argument, since it somehow resembles Cantor's diagonalization argument.
Usually what we mean by that is that if we try to enumerate all elements with a certain property, then we can point out, by construction, an element that is necessarily "incorrect", and we do so by showing that it does not satisfy the property with regards to itself (this is completely hand-wavy, but if you've seen the argument, you'll hopefully understand what I mean).
Now, what you're asking is whether we can do the same in order to show that ALL_TM (TM universality) is not decidable by a TM with oracle to HALT_TM.
Well, not really. At least not in a natural way: the argument would have to start by assuming there exists an oracle machine M that decides ALL_TM, and then constructing from M some other machine N (what you call a "liar" machine), which would yield a contradiction when we run N on N.
However, the machine N would have to be an oracle machine, not a standard TM (or you would essentially lose the power of the oracle in M). But since the oracle in N takes as input standard TMs, then the inner working of N would somehow need to create a standard TM to feed to the oracle. This doesn't seem like a natural construction, and it would certainly not be simple.
Now, perhaps there is some convoluted way of giving a direct diagonalization argument for this claim, but it's not well motivated, given that proving the claim directly (namely that ALL_TM is not decidable by a TM with oracle to HALT) is not difficult using standard tools, such as reductions.


Order notation subtractions in Fibonacci Heap

As you point out your first equation is not necessarily correct.

Let me rewrite it by explicitly adding the multiplicative constants:
$\alpha D(n) + \beta t(H) - \gamma t(H) = O(D(n))$, where $\gamma =1$.
Here the problem is that $\beta$ might be larger than $\gamma = 1$.

What the authors are saying is that instead of thinking that one unit
in the value of your potential function $\Phi(H)$ contributes one unit of potential, you can imagine that it is actually representing $\gamma$ units of potential.
This amounts to redoing the analysis with a new potential function $\Phi'(H)$ defined as $\Phi'(H) = \gamma \cdot \Phi(H)$. If you do so, then you are able to control the value of $\gamma$ in the above equation, while $\beta$ stays the same.

Picking a value of $\gamma \ge \beta$ ensures that
$\alpha D(n) + \beta t(H) - \gamma t(H) = \alpha D(n) -  \underbrace{(\gamma -\beta)}_{\ge 0} t(H) \le \alpha D(n) = O(D(n))$, as desired.


LP - given m constraints for 2 variables find maximal radius of circle

You're close to the solution, but aren't there yet. Your third inequality should look like this (no absolute values!):

$$d_i x_1 + e_i x_2 + \sqrt{{e_i}^2 +{d_i}^2}R \le b_i$$

And yes, the maximal inner circle radius can be zero, and even more - this circle might not exist at all. Please see the following explanation to grasp that.

Let's use vector notation to simplify algebraic expressions:

$$a_i=(d_i,e_i)$$
$$x=(x_1,x_2)$$

Then your constraints can be written using Dot Product:

$$a_i \cdot x \le b_i,  i \in [1,m]$$

Let's denote the inner circle center $y$ and focus on the $i$-th constraint for now. Imagine a shortest segment, connecting the point $y$ and the line $a_i \cdot x = b_i$. It's easy to see that this segment will be perpendicular to this line and collinear with vector $a_i$.

Let's find the point $z_i$, lying on the segment above, with the distance from the point $y$ equal to the $R$ (radius of the inner circle). This point is given by the following vector expression:

$$z_i = y + \frac{a_i}{\lVert a_i \rVert}R$$

Now we have to make sure that all the points $z_i$ are located in correct halfplanes:

$$a_i \cdot z_i \le b_i,  i \in [1,m]$$

Simplifying these equations using the expression for the point $z_i$ (above) we'll get:

$$a_i \cdot y + \lVert a_i \rVert R \le b_i,  i \in [1,m]$$

So, now you have an LP problem with three variables $(y_1, y_2, R)$, $m$ constraints (above), an additional constraint $R \ge 0$ and optimization function, which is simply $R$.

Please see the Chebyshev Center page for more information, in particular the reference #4.


If $g = O(g')$ and $h$ is nonnegative then $h \cdot g = O(h \cdot g')$ — in English, if $g$ grows slower than $g'$ then multiplying by a positive function doesn't affect that fact. (If you aren't sure about this, do the proof with quantifiers).

Since $\log(n) = O(n^{0.000001})$, $n^{0.999999} \cdot \log(n) = O(n^{0.999999} \cdot n^{0.000001})$. Since $n^{0.999999} \cdot n^{0.000001} = n$, we have $f_1(n) = O(n)$.

While it is true that $f_2(n) = O(n)$, this is not relevant here. What you need is $n = O(f_2(n))$, which is also true.

Intuitively, a higher exponent trumps a logarithm. A multiplicative constant is not significant.


Finding the equivalence classes of a language

Your language is $01^*0(0+1)^*$, i.e., all words starting with 0 and containing at least one more 0.

Indeed, a word of the form $0y0z$ is in $A$ since we can take $n=1$ and $x = y0z$. Conversely, if $w = 0^nx \in A$ then $w$ contains at least $2n \geq 2$ many 0's, and starts with a 0.

Therefore the Myhill–Nerode equivalence classes of your language are:
$$
\epsilon, 1(0+1)^*, 01^*, 01^*0(0+1)^*.
$$


In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$.
Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} < 2n$. We can extract the product of the original matrices from the product of the new matrices. The two new matrices can be multiplied using at most this many operations:
$$
CN^{\log_2 7} < C (2n)^{\log_2 7} = 7C n^{\log_2 7} = O(n^{\log_2 7}).
$$


When can a greedy algorithm solve the coin change problem?

A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts.

The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of different kinds of coins. From the abstract:

  We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.

The paper is quite short.

For a non-canonical coin system, there is an amount $c$ for which the greedy algorithm produces a suboptimal number of coins; $c$ is called a counterexample.  A coin system is tight if its smallest counterexample is larger than the largest single coin.

The paper Canonical Coin Systems for Change-Making
Problems provides necessary and sufficient conditions for coin systems of up to five coins to be canonical, and an $O(n^2)$ algorithm for deciding whether a tight coin system of $n$ coins is canonical.

There is also some discussion in this se.math question.


No hash function can guarantee a good distribution. All you can do is finding a hash function that will usually create a good distribution.
The table size is quite important for this: If the table size is a prime p, then just using n modulo p as the hash value is usually quite good. Note that in your case, 4 is not a prime. Actually all your values are multiples of the table size. And if you has pointers for example, then it is quite possible that all pointers are multiples of 8 or 16, so having a table size of 4, 8 or 16 is not clever.
Obviously if your integers are multiples of 4, but with all four possible values modulo 16 being equally minded, then (n / 4) modulo 4 would work quite well. But in general, you should avoid an unfortunate table size like the one you have.


Proof that TAUT is coNP-complete (or that a problem is coNP-complete if its complement is NP-complete)

I take it that we call $TAUT$ the problem of given a DNF formula, decide if it is a tautology (if you do not want to restrict to DNF, this will still work as this only makes the problem more general).

The answer of your questions easily follows from the definition of $coNP$. Remember that a language $L \subseteq \{0,1\}^*$ is in $coNP$ is $\bar{L} = \{x \in \{0,1\}^* \mid x \notin L\} \in NP$. For example, $\overline{TAUT}$ is the set of DNF that are not a tautology. To prove that a DNF is not a tautology, you only have to find an assignment that does not satisfy your formula, which can be done in polynomial time with a NTM (just "bruteforce" the assignments). Hence, it is in $NP$. In other words, $\overline{TAUT} \in NP$ thus $TAUT \in coNP$.

Now take an $NP$-complete language $L$. By definition, $\bar{L} \in coNP$. We show that $\bar{L}$ is $coNP$-complete, that is, for every language $A \in coNP$, $A \leq \bar{L}$. Let $A \in coNP$. Then $\bar{A}$ is in $NP$. By $NP$-completeness of $L$, there exists a function $f$, computable in polynomial time such that $x \in \bar{A}$ iff $f(x) \in L$. This is equivalent to say that $x \notin \bar{A}$ iff $f(x) \notin L$. Which in turn, is equivalent to $x \in A$ iff $f(x) \in \bar{L}$. Thus, $f$ is also a reduction from $A$ to $\bar{L}$, meaning that $A \leq \bar{L}$. In other words, $\bar{L}$ is $coNP$-complete.

Now, if you want to show that $TAUT$ is $coNP$-complete, you only have to show that $\overline{TAUT}$ is $NP$-complete. And it is not hard to see that $SAT \leq \overline{TAUT}$. Indeed, a CNF $F$ is satisfiable iff $\neg F$, which is a DNF, is not a tautology.


For simplicity, let us define that if $L$ is some language, $pref(L)$ to be the described language generated from $L$ (do not not to be confused with the language prefix operator)
Let us also define $\Sigma = \{a,b,c,e\}$.
We know that the language $L=\{a^nb^nc^n|n\in\mathbb N\}$ is not CFL, so we may want to use it.
Lets think in terms of your idea: we will want some other language $\hat L$ where $pref(\hat L)$ is similar to $L$ itself.
First, notice that simply applying your idea is not very useful: we may start with a word $aaabbbccc\in L$ and after we add to its the $y$ at the end, we can find ourselves with the word $aaabbbccccccccccccc\in \hat L$. This will make everything much harder to do, as this word could as well end up in $pref(\hat L)$ (think why!) and therefore in this case $pref(\hat L)$ is not very similar to $L$.
So how do we fix it? We can just add a new letter that will seperate our words in $L$ from the rest. This letter will be $e$ (short for "end") - so our new definition for $L$ would be as follows: $L=\{a^nb^nc^ne|n\in\mathbb N\}$. Now, if we would have taken a look at $\hat L = L\Sigma^*$ (concatenation of those two languages) we would have $pref(\hat L)=\hat L$  but also $\hat L$ is very similar to $L$ in its core structure (and also is not a CFL for the same reason $L$ isn't).
Now we have a different problem, since $pref(\hat L)=\hat L$ we obviously can't have $\hat L$ being a CFL with $pref(\hat L)$ not a CFL. To fix this, we need a key observation: if we add some arbitrary word to $\hat L$, for example the word $ababa$ - then since it wasn't in $L$ already, it won't be in $pref(\hat L)$ too! (find a $y\in \Sigma^*$ where this word concatenation with $y$ is not in $\hat L$)
This means, we may somehow be able to add things to $\hat L$ while keeping $pref(\hat L)$ the same (and not a CFL). Adding all words of the form $we$ where $w\in\Sigma^*\setminus\{e\}$ with $|w|=3n$ for some $n\in\mathbb N$ should do the trick, but I will leave proving that $pref(\hat L)$ didnt change with those additions. Notice now that this language not is CFL, but its also regular! the automata that solves this language is simple: it checks whether the first occurrence of the letter $e$ is in a position that is a multiple of 3.
So finally, the language $\hat L=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*\bigcup \{we|w\in\Sigma^*\setminus\{e\}\land \exists n\in\mathbb N .|w|=3n\}$ is regular (and hence a CFL) while $pref(\hat L)=\{a^nb^nc^ne|n\in\mathbb N\}\Sigma^*$ is not a CFL.

Sorry if this post was too long! I hope it helped you understand the problem and its solution on all of their steps and thinking methods.


Your best bet is probably to start with a value that seems reasonable and improve it by trial and error.


Selecting optimal order of questions to minimize total time

Counterexample: Students are $x_1\dots x_n$ and $y_1\dots y_m$ and questions are $Q_0, \dots Q_m$. Students $x_i$ only want $Q_0$ to be answered while the $y_i$ students want question $Q_1,\dots, Q_m$ to be answered.

Let's say you place $Q_0$ as the $k^{th}$ question. Then the total time waited by students is:

$L(n,m)=n(m+1)+m^2$ if $Q_0$ is last
$nk + m(m+1)$ if $Q_0$ is $k^{th}$

Clearly, if you want to not put $Q_0$ last, then you might as well put it first so that the cost is $F(n,m)=n + m(m+1)$.

Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n>1$ and $m>0$, we'll have $L(n,m)>F(n,m)$. So placing it first is better.

But your greedy algorithm would put it last if we take $m>n$.


Understanding a boolean expression in λ-calculus

It's a very bad idea to omit parentheses. Correct is:
$$\lambda b . b (\lambda x y . y) (\lambda x y . x)$$
Next, it is confusing to reuse bound variables, so let me rename them:
$$\lambda b . b (\lambda x y . y) (\lambda u v . u)$$
And now we can apply this to $\lambda p q . p$ (which is just "true" with bound vraiables renamed yet again):
\begin{align*}
(\lambda b . b (\lambda x y . y) (\lambda u v . u)) (\lambda p q . p)
&=_\beta (\lambda p q . p) (\lambda x y . y) (\lambda u v . u) \\
&=_\beta (\lambda q . (\lambda x y . y)) (\lambda u v . u) \\
&=_\beta (\lambda x y . y).
\end{align*}
So we did get false. In every step there was exactly one $\beta$-redex. By the way, writing $A B C$ in $\lambda$-calculus means $(A B) C$ by convention.

I will leave the other one as exercise.


Finding simple cycle of minimal weight in directed bipartite complete graph with negative cycles

No.

That is, there is no polynomial time algorithm in $m\times n$ that can find a simple cycle with minimal weight in any given weighted complete bipartite directed graph K_$\{m, n\}$ in the sense that it is a NP-complete problem.

To prove it, let us reduce the undirected Hamiltonian cycle problem, one of Karp's 21 NP-complete problems, to the current problem by a polynomial-time reduction.

Let $G$ be an undirected graph with vertices $V$ and edges $E$. For each vertex $u$ in $G$, we create two new vertices, $u_{in}$ and $u_{out}$. Let $V_{in}=\{u_{in}|u\in V\}$. Let $V_{out}=\{u_{out}|u\in V\}$. Let $K$ be the complete bipartite digraph connecting the vertex sets $V_{in}$ and $V_{out}$. For every vertex $u\in G$, both edges $(u_{in},u_{out})$ and $(u_{out}, u_{in})$ in $K$ weigh 0. If edge $(u, v)$ is in $G$, then the both edge $(u_{out},v_{in})$ and edge $(v_{out},u_{in})$ in $K$ weigh $-1$. Any other edge in $K$ weigh $|V|$. $K$ with its edge-weights thus defined is a weighted complete bipartite directed graph with $|V|$ vertices in each of its two vertex sets (that is, $m=n=|V|$ for $K$).

Each simple cycle in $G$ corresponds to a simple cycle in $K$ with the same weight in the natural way as illustrated by the following example. A cycle $a, b, c, a$ in $G$ corresponds to the cycle $a_{in}, a_{out}, b_{in}, b_{out}, c_{in}, c_{out}, a_{in}$ in $K$. In particular, a Hamiltonian Cycle in $G$ corresponds to a simple cycle in $K$ of weight $-|V|$. Conversely, it is easy to see that a simple cycle of weight $-|V|$ in $K$ corresponds to a Hamiltonian Cycle in $G$ under the same correspondence. Note that a simple cycle of weight $-|V|$ in $K$ must be simple cycle of minimal weight in $K$.

Assume we can find a simple cycle $C$ of the minimal weight in $K$ by some algorithm. We can then check the weight of $C$. If the weight of $C$ is $-|V|$, the simple cycle in $G$ that corresponds to $C$ is a Hamiltonian Cycle. Otherwise, there is no Hamiltonian Cycle in $G$. So we have reduced the undirected Hamiltonian cycle problem to the current problem. We can see easily that this reduction is a polynomial-time reduction.


Best way to translate while loops to functions for software verification

I recommend that you translate

while(c) b

to

def myWhile() = if (c) then (b ; myWhile())
myWhile()

With this translation, the precondition of myWhile is the loop invariant of the original while loop.  So, this becomes the question of how to find the loop invariant of a loop.  In general, that requires manual annotation.  If you do a search, you should be able to find a lot of information on finding loop invariants.


Does transforming a CFG to Chomsky normal form make it unambiguous?

There are inherently ambiguous context-free languages, and like all context-free languages they have grammars in Chomsky normal form, so transforming a CFG to Chomsky normal form doesn't necessarily make it unambiguous. For the same reason there is no technique to convert an arbitrary context-free grammar to one which in unambiguous.

Deciding whether a given context-free grammar is ambiguous, or whether a given context-free grammar generates an inherently ambiguous language, is undecidable. This doesn't necessarily mean that there is no procedure that converts any context-free grammar into an unambiguous one given that the language isn't inherently unambiguous, but it does make the existence of such an algorithm somewhat doubtful.


Proving laws of take and drop functions using structural induction on lists

You can prove the second law by induction on n:

Base case:

drop m (drop 0 xs) = drop m xs (definition of drop, base case)

= drop (m + 0) xs (since m + 0 = m)

Inductive step:

We have to consider two cases: when the input list is empty, and when it's not empty. When it's empty, we have

drop m (drop n []) = drop m [] = [] = drop (m + n) [] (definition of drop, base case)

When the input list is not empty, we have

drop (m + n) (x:xs) = drop (m + n - 1) xs (definition of drop, inductive case)

= drop m (drop (n - 1) xs) (inductive hypothesis)

= drop m (drop n (x:xs)) (definition of drop, inductive case)

I imagine that the first law is not much more difficult. Try to prove it by induction on n, and if it doesn't work, try induction on m. One of them will probably work.


Both problems you mention have the stated complexity only when edge weights are non-negative. With these constraints, the reduction you describe no longer works.


Confluence proof for a simple rewriting system

Okay, so let's consider the case that $r = \mathtt{if}\: t_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$, $s$ has been derived by applying the E-If rule and $t$ has been derived by applying the E-Funny rule: So $s = \mathtt{if}\: t'_1 \:\mathtt{then}\: t_2 \:\mathtt{else}\: t_3$ where $t_1 \rightarrow t'_1$ and $t = \mathtt{if}\: t_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$ where $t_2 \rightarrow t'_2$.

The $u$ we're looking for is $u = \mathtt{if}\: t'_1 \:\mathtt{then}\: t'_2 \:\mathtt{else}\: t_3$. $s \rightarrow u$ follows from rule E-Funny and $t \rightarrow u$ follows from rule E-If.


The solutions to some problems are more naturally expressed using recursion.

For example, assume that you have a tree data structure with two kinds of nodes: leaves, which store an integer value; and branches, which have a left and right subtree in their fields. Assume that the leaves are ordered, so that the lowest value is in the leftmost leaf.

Suppose the task is to print out the values of the tree in order. A recursive algorithm for doing this is quite natural:

class Node { abstract void traverse(); }
class Leaf extends Node {
  int val;
  void traverse() { print(val); }
}
class Branch extends Node {
  Node left, right;
  void traverse() { left.traverse(); right.traverse(); }
}

Writing equivalent code without recursion would be much more difficult. Try it!

More generally, recursion works well for algorithms on recursive data structures like trees, or for problems that can naturally be broken into sub-problems. Check out, for instance, divide and conquer algorithms.

If you really want to see recursion in its most natural environment, then you should look at a functional programming language like Haskell. In such a language, there is no looping construct, so everything is expressed using recursion (or higher-order functions, but that's another story, one worth knowing about too).

Note also that functional programming languages perform optimized tail recursion. This means that they do not lay down a stack frame unless they do not need to --- essentially, recursion can be converted to a loop. From a practical perspective, you can write code in a natural fashion, but get the performance of iterative code. For the record, it seems that C++ compilers also optimize tail calls, so there is no additional overhead of using recursion in C++.


Is there an algorithm to find all connected sub-graphs of size K?

There can be exponentially many such subgraphs, so any such algorithm will necessarily be slow.

To enumerate all of them, choose any number $i$ in the range $[1,k]$, choose any subset $S$ of $i$ of the vertices, discard all edges that have an endpoint not in $S$, choose any subset of the remaining edges, then check if the graph with vertex set $S$ and the chosen edge subset is connected; if not, discard the graph; if yes, output the subgraph.  If you implement each "choose" with an for-loop that enumerates over all possibilities, this will enumerate over all graphs.  There are standard ways to enumerate all subsets of a set.

You can make it a bit more efficient by choosing the edges in a particular order:

for each $i \in [1,k]$:

for each subset $S$ of exactly $i$ of the vertices: (*)

let $E_1 = \{(u,v) \in E : u \in S, v \in S\}$ and $T := \emptyset$.
for each $v \in S$:

let $E_2 = \{(u,v) \in E : u \in S\}$.
if $E_2$ is empty and $T$ has no edge incident on $V$, go to the next iteration of the loop marked (*).
if $E_2$ is non-empty:

choose a non-empty subset $E_3$ of $E_2$.
set $T := T \cup E_3$ and $E_1 := E_1 \setminus E_2$.

if the graph $(S,T)$ with vertex set $S$ and edge set $T$ is connected, output it

I don't know how to guarantee polynomial delay, but this might be fine for your particular application.


NP-hardness of an optimization problem with real value

No, you can not say that your problem is NP-complete.

The reason is that it is not in NP: there is no Turing machine at all (let alone a poly-time (non-deterministic) one) that can solve it because TMs can not handle real numbers.

The reduction may still go through and show that the problem is NP-hard; a subset of the reals should certainly suffice to model the naturals in Vertex Cover or whatever NP-complete problem you use. So it is, in principle, possible to define a computable, poly-time reduction function that does the job. It will output naturals (or integers, rationals, ...), of course, but as long as you are willing to accept these as real numbers you are fine.

This reduction is likely to carry over to restricted versions of your problem (e.g. finite precision) which can be classified in the framework of computabilty/complexity theory.


Examples of exact computation of Kolmogorov complexity?

The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that it is known what "$e$" is?

Formally, Kolmogorov complexity is defined with respect to a particular encoding of Turing machines.  If you fix an encoding, then the Kolmogorov complexity of a string $x$ is $K(x)$, the length of the shortest encoding of a Turing machine that prints that string when started with empty input.  (Informally, but still reasonably precisely, you can think of Turing machine encodings as programming languages, and the encoding of a specific Turing machine is a program in that language.)

A key point is that, if we choose different encodings, we get different values for the Kolmogorov complexity.  At the level of the informal example, we could both agree that "DO IT!!" means "Print out the first 1,239,875,981,825,931 bits of the square root of e", so now that has very low Kolmogorov complexity. Because of this, it's very unlikely that anyone has sat down and figured out the exact Kolmogorov complexity of some nontrivial string with respect to some specific Turing machine encoding. It would be very difficult to do, and nobody cares about the answer because, in a sense, it's just an artefact of the choice of Turing machine encoding. Unlike actual programming languages, there isn't really any standard scheme of coding Turing machines as strings, so all your hard work would just be proving an uninteresting fact about your arbitrary choice of coding.


Is it possible to find a supersequence of a single array?

What about the array $[1, 3, 5]$? The supersequence $[0,1,0,3,0,5]$ is oscillating while the original sequence isn’t. In fact you can make an oscillating supersequence of any array by inserting $\min(arr)-1$ before every element of the original array.


There is a unique shortest path $P_T(u,v)$ between two nodes $u$ and $v$ in a tree $T$. Such a shortest path goes from $u$ to the lowest common ancestor (LCA) $z$ of $u$ and $v$ in $T$, and then goes from $z$ to $v$. Notice that it might be possible for $z$ to coincide with $u$ or $v$.

To find the length $d_T(u,v)$ of $P_T(u,v)$ is therefore sufficient to find the LCA $z$ of $u$ and $v$ in $T$.

There are several ways to do this. One straightforward way that requires time $O(n)$, where $n$ is the number of nodes of $T$, is the following:

Initially all the vertices of $T$ are unmarked.
Start from $u$ and iteratively walk towards the root of $T$. Mark all the encountered vertices.
Start from $v$ and iteratively walk towards the root of $T$. The LCA of $u$
and $v$ is the first marked vertex encountered during this walk.

An easy way to reduce the running time to $O(d_T(u,v))$ is that of alternating the steps of the walk from $u$ with those of the walk from $v$. Assume that $u \neq v$ (otherwise the answer is trivial) and do the following:

Initially all the vertices of $T$ are unmarked except for $u$ and $v$.
Let $p_u = u$, and $p_v = v$.
Repeat the following:

If $p_u$ is not the root of $T$:

Move $p_u$ to its parent in $T$.
If $p_u$ is marked, return $p_u$ as the LCA of $u$ and $v$. Otherwise mark $p_u$.

If $p_v$ is not the root of $T$:

Move $p_v$ to its parent in $T$.
If $p_v$ is marked, return $p_v$ as the LCA of $u$ and $v$. Otherwise mark $p_v$.

Once the LCA $z$ of $u$ and $v$ is known, it takes time $O(d_T(u,v))$ to find the distances from $z$ to $u$ and from $z$ to $v$ in $T$. Therefore $d_T(u,v)$ can be found in time $O(d_T(u,v)) = O(n)$.

If you have to frequently report the distance between pairs of vertices in a static tree then you can do so in constant time per query after a linear time preprocessing:

Build a LCA oracle: a data structure that can report the LCA between two vertces in $T$ in contant time. This data structure can be constructed in time $O(n)$. The construction is very clever and elegant. See this paper for the details.
Augment each node $v$ in the tree by storing its depth depth($v$) in $T$.
Answer a query for the distance between $u$ and $v$ in $T$ by: 1) finding the LCA of $z$ of $u$ and $v$ using the oracle; 2) returning $(\text{depth}(u) - \text{depth}(z)) + (\text{depth}(u) - \text{depth}(z))$.


Let $T_1,T_2,\ldots$ be an enumeration of all timed polytime machines, machine $T_i$ running in time $p_i(n)$. We will construct $A$ in stages. At each stage, the truth value of $A$ is defined on only finitely many inputs.

Stage $i$ handles $T_i$. Choose an input length $n$ such that (i) $A$ is completely undefined and (ii) $p_i(n) < 2^{n-1}$. Run $T_i$ on $0^n$. Each time $T_i$ queries some yet undefined string in $A$, answer arbitrarily and fix the value of this string in $A$. Since $p_i(n) < 2^{n-1}$, in particular $T_i$ queries fewer than $2^{n-1}$ strings of length $n$. If $T_i$ answered "Yes", then define all remaining strings of length $n$ to be outside $A$. If $T_i$ answered "No", then define all remaining strings of length $n$ to be inside $A$. Either way, the machine $T_i$ is wrong on input $0^n$.

After infinitely many steps, we have defined $A$ at infinitely many strings, but probably not all strings. Define $A$ arbitrarily on all remaining strings.

We note that the same proof works for every (time constructible) complexity class in which a machine cannot make at least $2^{n-1}$ queries on input of length $n$.


What mathmatical model shall be used for describing P2P processes interaction?

If you're looking for a single model that describes all relevant aspects of your system, you'll have a hard time. And building the model will take as much effort as implementing the system itself, if not more. Therefore, break the system down into different aspects, and consider different modelling techniques for each. Examples for aspects might be:

The protocol between two of the peers. This could detect deadlocks or pointless messages in the protocol.
Repeat for every combination of two types of peers.
Behavior of a single peer as it connects with different types of peers.
Could there be problems if a message from peer type X comes in while processing another message from peer type Y?
Behavior of the network as peers come and go. Will it stay connected?
Here, you'd just model "peer connects" and "peer disconnects", rather than the sequence of messages for connecting and disconnecting.
Performance depending on the number of peers of each type.
...


How can a machine with fixed output for all inputs be considered a Turing machine?

There's no notion of "can be considered to be a Turing machine".  Something either is a Turing machine, or it isn't.  There's a formal mathematical definition of what a Turing machine is: https://en.wikipedia.org/wiki/Turing_machine#Formal_definition
I never claimed that just because some process always produces the same output, that process must be a Turing machine.
There might be some confusion about Turing machines vs DFAs.  A computer could be modelled as a DFA (if we treat its memory size as fixed), or it could be modelled as a Turing machine (if we imagine that it's possible to gain more memory; or we just don't care to make use of the fact that memory size is fixed).  These two different ways to think about a computer have different advantages and disadvantages.  I suggest reading Is a PDA as powerful as a CPU? and How many gates until Turing Complete and How does an automaton model a computer or something else? and How does an automaton actually "compute"?, as I suspect they get at the core issue you are struggling with.


Finding invariant when detecting a cycle

Assuming we execute line 3 when you first visit a node, and assuming you are working with directed graphs, this algorithm is incorrect (consider what happens with a cross edge discovered by DFS).

Alternatively, assuming you are working with undirected graphs:

The missing part of your argument is the "thus" part; why does the existence of two such nodes imply the existence of a cycle?

To work out the proof, I suggest categorizing what types of edges can exist in the search tree for an undirected graph: tree edges? forward edges? back edges/ cross edges?  Then, categorize what type of edge caused you to visit x when seen[x] was true.  What does that mean the search tree has to look like?


Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

If $n > k$ then $n \neq k-1$ (since $k-1 \not> k$), so your language is really $L = \{ a^n b^k \mid n \neq k-1 \}$. If $L$ were regular then so would be the following language $a(a^*b^* \setminus L) \cup \{\epsilon\} = \{ a^n b^n \mid n \geq 0 \}$, which is known not to be regular.


Logspace algorithm for s-t connectivity in undirected forests

This is proved by Cook and McKenzie. We make use of the following notation:

$\deg(v)$ is the degree of a vertex $v$.
$N(v,1),\ldots,N(v,\deg(v))$ is some fixed ordering of the neighbors of $v$.

We construct a sequence $v_1,v_2,\ldots$ of nodes starting with $v_1 = s$ and $v_2 = N(s,1)$ (if $\deg(s) = 0$ then $s$ is connected to $t$ iff $s = t$). Given $v_{i-2},v_{i-1}$, we construct $v_i$ as follows:

  Suppose that $v_{i-2} = N(v_{i-1},j)$. Then $v_i = N(v_{i-1},j+1)$.

(If $j = \deg(v_{i-1})$ then $j+1 = 1$.)

It turns out that if the connected component of $s$ has size $m$ then the first $2(m-1)$ vertices contain each vertex $v$ in the connected component exactly $\deg(v)$ times, and after that the sequence repeats indefinitely. This is because the sequence essentially performs a depth-first search, as the following image from Wikipedia illustrates (the arrows should be ignored):

Here $s = F$ and the neighbors are ordered from left to right. The first 16 elements of the sequence are F,B,A,B,D,C,D,E,D,B,F,G,I,H,I,G. The sequence then repeats.

This implies the following simple algorithm: calculate the first $2(n-1)$ members of the sequence, and check whether $t$ ever appears. This can be implemented in logarithmic space.

Reingold gave a (significantly) more complicated algorithm that works for any undirected graph, still using only logarithmic space. If the graph is directed then the problem is complete for NL, and so probably cannot be solved using only logarithmic space (at least not on deterministic Turing machines!).


The $\sum$ notation is specifically summation. There is also product notation:
$$n! = \prod_{i=1}^{n} i $$
But I think what you want is some kind of Zermelo-Fraenkel notation?
$$\left\{ f(a,b)\,|\,a,b \in P \right\}$$


Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency

This can be easily handled using a standard balanced tree data structure, augmented with a Fenwick tree and a hashmap:

Store the items in a binary tree.  Each leaf stores information about a single item.  The leaves should be stored in increasing frequency, i.e., sorted by frequency, from least frequent to most frequent.
To help compute the cumulative frequency, augment the binary tree to store some additional information in each node.  In each node, store the sum of the frequencies of all of the items underneath it (i.e., of all of the leaves under that node).  These values can be easily updated as the tree changes.  This is basically the idea behind Fenwick trees for computing prefix sums.
Also, add a hashmap that maps from the value (what you call "index") to the associated leaf where that index is found in the binary tree.

Now you can support all of the operations you mentioned efficiently.  If you use a standard balanced binary tree data structure, the running time for all operations is $O(\log n)$:

Sort: All of the items are already stored in sorted order, sorted by increasing frequency, so this happens automatically.
Insert: You can insert a new item into the tree in $O(\log n)$ time.
Update: You can increase the frequency of a particular item by deleting it from the tree, increasing its frequency, and inserting it into the new location.  In a balanced binary tree, this takes $O(\log n)$ time, since deletion can be done in $O(\log n)$ time, as can insertion.
Query: You can now find the first index $i$ where the sum of the frequencies of the first $i$ leaves is at least $t$, by using binary search.  Note that you can efficiently compute prefix sums of the frequencies by using the extra values stored in each node of the tree.  Therefore, binary search suffices, and can be done in $O(\log n)$ time.

There are many balanced binary tree data structures, including red-black trees, AVL trees, 2-3 trees, etc.  They all have the property that standard operations are guaranteed to take at most $O(\log n)$ time.  You can use any of them for your purposes.


Doubt regarding address calculation in two-dimensional arrays

For the first question, you can calculate an address for it -- languages that don't do array bounds checking will gladly calculate an address and read/write there, even if it is out of bounds.  Of course, if the program is accessing an out-of-bounds element, that's typically a bug of some sort.

For your second question, you are right.

You probably won't run into arrays that start at an index other than 0 in practice very often (if ever), so I wouldn't worry too much about it.  Your understanding seems solid.


How/when is calculus used in Computer Science?

I can think of a few courses that would need Calculus, directly. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones.

Computer Graphics/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, heavily!  If you go down this path, you may also want to study some Differential Geometry (which has multivariate Calculus as a minimum prerequisite). But you'll need Calculus here even for very basic things: try searching for "Fourier Transform" or "Wavelets", for example -- these are two very fundamental tools for people working with images.
Optimization, non-linear mostly, where multivariate Calculus is the fundamental language used to develop everything.  But even linear optimization benefits from Calculus (the derivative of the objective function is absolutely important)
Probability/Statistics. These cannot be seriously studied without multivariate Calculus.
Machine Learning, which makes heavy use of Statistics (and consequently, multivariate Calculus)
Data Science and related subjects, which also use lots of Statistics;
Robotics, where you will need to model physical movements of a robot, so you will need to know partial derivatives and gradients.
Discrete Math and Combinatorics (yes!, you may need Calculus for discrete counting!) -- if you get serious enough about generating functions, you'll need to know how to integrate and derivate certain formulas. And that is useful for Analysis of Algorithms (see the book by Sedgewick and Flajolet, "Analysis of Algorithms"). Similarly, Taylor Series and calculus can be useful in solving certain kinds of recurrence relations, which are used in algorithm analysis.
Analysis of Algorithms, where you use the notion of limit right from the start (see Landau notation, "little $o$" -- it's defined using a limit)

There may be others -- this is just off the top of my head.

And, besides that, one benefits indirectly from a Calculus course by   learning how to reason and explain arguments with technical rigor. This is more valuable than students usually think.

Finally -- you will need Calculus in order to, well, interact with people from other Exact Sciences and Engineering. And it's not uncommon that a Computer Scientist needs to not only talk but also work together with a Physicist or an Engineer.


If you just keep applying FIRST, it not hard to understand where to stop.

FIRST($\mathtt{S}$) =  FIRST($\mathtt {A(S)B}$) ∪ {ε}

In your example, FIRST($\mathtt{A}$) includes ε, so

FIRST($\mathtt{S}$) = FIRST($\mathtt {A}$)\{ε} ∪  FIRST($\mathtt {(S)B}$) ∪ {ε} = FIRST($\mathtt {A}$)\{ε} ∪ {$\mathtt{(}$} ∪ {ε}

Now, as FIRST($\mathtt{A}$)\{ε} = FIRST($\mathtt{S}$)\{ε} ∪ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$}, then

FIRST($\mathtt{S}$) = FIRST($\mathtt{S}$)\{ε} $\cup$ FIRST($\mathtt{SB}$)\{ε} ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

Notice that the appearances of $\mathtt{S}$ on the left side are redundant here, so we get (again, because FIRST($\mathtt{S}$) includes ε):

FIRST($\mathtt{S}$) = FIRST($\mathtt{B}$)\FIRST($\mathtt{S}$) ∪ {$\mathtt{x}$} ∪ {$\mathtt{(}$} ∪ {ε}

The end result is FIRST($\mathtt{S}$) = {$\mathtt{y}$, $\mathtt{x}$, $\mathtt{(}$, ε}


Show that the language of words with even sum of positions of a letter is regular

If the sum of positions at which $a$s occur is even, that just means that there are an even number of $a$s in odd positions. It's straightforward to design an automaton to accept this criterion: it's a minor variant of requiring an odd number of $a$s.


Run-time of a summation function and its complexity

The body of the inner for loop is executed in constant time per iteration and it does not affect the number of iterations of the outer loops.
Let $n$ be the length of array. The outer for loop iterates $n$ times. During the $i$-th iteration of the outer loop, the inner for loop iterates $i$ times.
The overall time complexity is therefore:
$$
\Theta(1) \cdot \sum_{i=1}^{n} i = \Theta(1) \cdot \Theta(n^2) = \Theta(n^2).
$$


Why do most books say that a 1 bit branch predictor mispredicts on the first loop iteration?

I believe the assumption is that the loop has been encountered previously (i.e., assuming a long-running program with the loop encountered multiple times and assuming no aliasing in the branch predictor), so the first iteration has the predictor set based on the last iteration of the previous encounter (i.e., not-taken) and, of course, the last iteration has the predictor set based on the previous iteration (i.e., taken).  This results in two mispredictions.

In general, a one-bit branch predictor will have two mispredictions per instance of unusual branch direction; first for the unusual instance and second for the instance immediately after that unusual instance.  By providing some form of hysteresis (as with a 2-bit predictor) or resistance to change (e.g., by randomly dropping misprediction information, possibly with probabilities determined by static branch prediction--so far as I know, a technique that is only theoretical), such unusual branch behavior is less likely to cause mispredictions for the usual behavior of a branch.


Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

I have found the answer for this problem. One way is, as suggested in the comment, to stack the matrix $\mathbf{A_i}$ and $\mathbf{b_i}$ together and apply first-order convex optimization algorithm, such as Primal-Dual Hybrid Gradient (PDHG), inexact ADMM, or their variants.
For PDHG, the problem to solve is
\begin{align}
\mathrm{min}_{\mathbf{x},\mathbf{y}} &~ F(\mathbf{y}) + G(\mathbf{x}) \\
\mathrm{s.t.} & ~ \mathbf{Ax} = \mathbf{y}
\end{align}
where
\begin{align}
F(\mathbf{y}) &= ||\mathbf{y} - \mathbf{b}||_1 \\
G(\mathbf{x}) &= 0 \\
\mathbf{A} &= [\mathbf{A_1}^T, \mathbf{A_2}^T, ..., \mathbf{A_n}^T]^T \\
\mathbf{b} &= [\mathbf{b_1}^T, \mathbf{b_2}^T, ..., \mathbf{b_n}^T]^T. \\
\end{align}
Thus, the convex conjugate of $F(\mathbf{y})$ is
\begin{align}
F^*(\mathbf{y}^*) &= \mathrm{sup}_{\mathbf{y}} \left[\left<\mathbf{y},\mathbf{y}^*\right> - F(\mathbf{y})\right] \\
F^*(\mathbf{y}^*) &= \left<\mathbf{b},\mathbf{y^*}\right> + \mathcal{I}_{\mathbf{y^*}<\mathbf{b}}
\end{align}
where $\mathcal{I}_\mathcal{C}$ is an indicator function with value $0$ if the condition $\mathcal{C}$ fulfilled, otherwise $\infty$.
As the algorithm uses proximal operator, we need to get the proximal operator for $F$ and $G$,
\begin{align}
\mathrm{prox}_{F^*\sigma}(\mathbf{y}^*) &= \arg\min_{\mathbf{y}'}\left\{\frac{||\mathbf{y}'-\mathbf{y}^*||^2}{2\sigma} + F^*(\mathbf{y}^*)\right\} \\
\mathrm{prox}_{F^*\sigma}(\mathbf{y}^*) &= \max(\mathbf{y}^* + \sigma \mathbf{b}, \mathbf{b}) \\
\mathrm{prox}_{G\tau}(\mathbf{x}) &= \mathbf{x} \\
\end{align}
Thus, the algorithm in this case reads
\begin{align}
\mathbf{y}^{n+1} &= \max(\mathbf{y}^n + \sigma \mathbf{A} \mathbf{w}^n + \sigma \mathbf{b}, \mathbf{b}) \\
\mathbf{x}^{n+1} &= \mathbf{x}^n - \tau \mathbf{A}^T \mathbf{y}^{n+1} \\
\mathbf{w}^{n+1} &= \mathbf{x}^{n+1} + \theta (\mathbf{x}^{n+1} - \mathbf{x}^n),
\end{align}
with $\theta = 1$, and $\sigma \tau ||A||^2 < 1$.
All the operations do not need the direct access to the element of the matrix $\mathbf{A}$ and only require the operation of $\mathbf{A} \cdot$ and $\mathbf{A}^T \cdot$.


Is lazy evaluation required for do-notation?

It is not required that the language is lazy. The do notation exists in SML family of languages (for instance OCaml), which are eager. In these languages the do-notation is written as the let-notation, that is, instead of writing

do x1 <- e1
   x2 <- e2
   ...
   return e

we write

let x1 = e1 in
let x2 = e2 in
...
e

Note however that let in OCaml has a fixed monad (what in Haskell would be the IO monad), whereas the do notation in Haskell works for any monad. There are extensions of OCaml which allow you to use any monad.


Does the OS create its own bootstrapped stack frame when running a program?

I have no idea how each system operates, and do not inquire since I
usually do not need to know. However it seems rather easy to make an
educated guess, based on whatever experience I have. There are
many variants that exist. For example a program is often
byte code to be interpreted by a virtual machine. It is all very flexible.

Usually, the program will have its own run time environment, for which
some inital space can be allocated at the
bottom of the stack, or anywhere else, since it will not have to move
while the program executes, and also because it will exist in only one
copy for a run of the program (it is not called recursively). But
bottom of stack is probably simpler. Whether you want to consider that
space as a frame or not is probably not very important. However, it
may be simpler for the compiler/interpreter to maintain a structural
consistency with frames at least for that part which may be visible to or
accessed by the rest of the program, so that access is always done consistently.

This is set up by code inserted by the compiler in the compiled code (or linked to it), and is supposed to respect some
standards of communication with the OS (operating system) it is
intended for, so that data can be passed by the OS to the application,
and returned from the application to the OS.

Such standards are usually OS dependant, and must be conformed to by
the language compiler. The standard may simply imply agreement on the
location were the information to be passed is stored, and possibly
ways of specifying its size, upon call to or return from the program.

The stack of frame policy is needed for recursion, and it is possible only as long as you do not have
functions (called also methods, sub-program, procedure ...) that can
return functions as result. The first important recursive  language with that
property was Algol 60, and the stack of frames was invented for the
implementation of Algol 60.

The stack of frame was invented to implement recursion. However it is
useful even for allocating space to non-recursive function, as it is a
convenient, simple, fast and easy way to allocate storage for the
function only for the exact duration of that function execution.

Note that the stack policy no longer work as simply if functions can
have functions as result. Then frames may have to be allocated on a
heap (managed with a garbage collector) or occasionally transfered
from the stack to the heap.

The OS does not create an initial frame, whether on stack or anywhere
else. There must be a separation of responsibility. Some languages (at least older ones) do not even use frames, while others do use frames, but not organized as a stack. The role of the OS
is to allocate some space for the program to run, to place the data
to be passed to the program in some predetermined place in that space,
and then to pass control to the program code (if compiled), or to the
interpreter of the program (if interpreted)  with a reference to the
program as additional argument.

The code of the application program will then organize the allocated
space, initialize what has to be, possibly move data passed by the OS
in a more convenient location, etc, and then start with the code that
is specific to the application, what you call main method or main
program, thus creating its frame on the stack. This is usually done by a standard piece of code included by
the compiler with proper parameters.

In the case of interpreted code, the program that is actually called
is the interpreter, and the address of the program to be excuted is
passed to it as additional data. The interpreter will organize the
space, and reserve some for its own needs. Then it will start
interpreting your main method/program, thus creating the stack frame
for it.

But, as I said, there are many variants.
Does this answer your question? or did I miss a point?


What to call a script that runs other scripts?

It's called a "driver". A program in C or C++ is a program just as much as a script is I would think. A script usually isn't compiled like the heavy-duty programs of the world like Java and C.


Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$

Let's start with the case $n = 2^k$. We have
\begin{align}
c_{2^k} &= 2^k + 4c_{2^{k-1}} \\ &= 2^k + 4 \cdot 2^{k-1} + 16c_{2^{k-2}} \\ &= \cdots \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2^1 + 4^k c_1 \\ &= 2^k + 4 \cdot 2^{k-1} + 4^2 \cdot 2^{k-2} + \cdots + 4^{k-1} \cdot 2 = \\ &= 2^k(1 + 2 + 2^2 + \cdots + 2^{k-1}) \\ &= 2^k(2^k-1).
\end{align}
It is easy to prove by induction that the sequence $c_n$ is monotone. Therefore, if $2^k \leq n < 2^{k+1}$,
$$
c_n \geq c_{2^k} = 2^k(2^k-1) > \frac{n}{2}\left(\frac{n}{2}-1\right).
$$
Now
$$
\frac{n}{2}\left(\frac{n}{2}-1\right) \geq \frac{(n+1)^2}{8} \Longleftrightarrow
2n(n-2) \geq (n+1)^2 \Longleftrightarrow n^2 \geq 6n + 1.
$$
This holds for all $n \geq 7$. You can check that your inequality holds for $n=2,3,4,5,6$ directly.

You can also likely prove the inequality directly by induction, but the argument above is more similar to stuff you might actually see later on. The idea is that we find a specific type of $n$ for which $c_n$ is particular easy to calculate and to compare to $n$, and then we try to understand $c_n$ for all $n$ using these specific values.


Are finite state transducers and Mealy machines the same machines?

Mealy machine (by G. Mealy) is a deterministic finite state transducer with output associated with transition (edge) instead of state. It could handle multiple inputs and multiple outputs but by definition cannot be non-deterministic. According to definition it must be defined for all possible combinations of states and inputs.

Finite State Transducer is a generalization of Finite State Machine (M. Rabin, D. Scott) which can be both deterministic and non-deterministic. The output is associated with states, not all combinations of states and input must be present. Not all NFST can be determinized.

The computational power of both is equal in the Chomsky hierarchy, but there exist machines that cannot be expressed by other type. In special transduction hierarchy FST is higher than Mealy.
There are extensions to create nondeterministic Mealy machines, but nondeterminism for transducers is not really exploited, it would generate the family of outputs when one is really needed, unless it was the goal then NFST wins here.

From physical point of view it makes difference, Mealy equivalent machines are shifted in time, but considering only the result it does not matter.


Dijkstra's algorithm for undirected graphs with negative edges

Think about a "triangle"(3-clique): an undirected graph $G(V,E)$ with three vertices $a,b,c$ and edges $(a,b),(b,c),(c,a)$. Assign cost $w_{a,b} = 1$, $w_{b,c} = -100$, $w_{c,a} = 100$. If we want to find the shortest path from $a$ to $b$, Dijikstra greedily chooses $b$ via edge $(a,b)$, which has cost one. However, the shortest path from $a$ to $b$ is $(a,c),(c,b)$, which has cost only 0.

In fact, the proof of the correctness of Dijikstra algorithm relies on the fact that all edges have non-negative weights such that the greedy algorithm always stays ahead.


Understanding Interval Schedulling problem requirement

Let us check some simple examples.

Suppose there are three intervals [1,3], [2,5], [4, 6]. Then the wanted number is 1. Here is how. Let $T$ be any two of the intervals. Then every interval will has a nonempty intersection with one of the intervals in $T$. For example, you can let $T$ be {[1,3], [2,5]}. You can also let $T$ be {[1,3], [4,6]}. On the other hand, Let $M$ be the set of [2,5], i.e., $M$={[2,5]}. Then every interval will has a nonempty intersection with the only one interval in $M$, [2,5]. Since the wanted number can not be smaller than 1, it is 1.

For a slightly more interesting example, suppose there are 5 intervals [1, 3], [2,5], [4, 7], [6,9], [8,10], where each interval intersects its two neighboring intervals.

The wanted number is 2. Why? Firstly, any interval will not intersect either [1,3] or [8,10]. So one interval is not enough. Secondly, consider intervals [2,5] and [8,10]. We can see that every interval will intersect one of [2,5] and [8,10]. So two intervals are enough.
If you name those five intervals A, B, C, D, E respectively and connect a pair of letters if the corresponding two intervals intersects, you get a graph with vertices {A,B,C,D,E} with edges AB, BC, CD, DE. (Graphs obtained this way are called interval graphs.) Now it is easy to translate our problem about intersecting intervals into a problem about graphs. The new problem is called the minimum dominating set of a graph.

Here is an equivalent version of the problem that is much simpler.

  Given $n$ fixed intervals all of whose endpoints are distinct. Select some intervals such that the intersection of every original interval and the union of selected intervals is nonempty. How to minimize the number of intervals selected?


Gramatical evolution doesn't result on creating good constants

It sounds like you're saying that your approach is able to effectively find the shape of the expression, but it takes it a lot longer to find the right constants.

One possible approach is to generate an expression of the correct shape using your genetic programming method, then fill in the constants using a different method.  I would recommend trying numerical optimization techniques.  Replace each constant in your expression with a symbolic value $\alpha$.  Each different constant (at each different syntactic position) gets its own symbolic value.  Then, use numerical optimization to find the value of the constants.

Example 1. For instance, consider your complex expression $x^2 + x - (\text{stuff})$.  Replace this with $x^2 + x - \alpha$ (when you have an entire subtree that contains only constants, no variables, replace the entire subtree with a single symbolic value).  We now get a function $f(x,\alpha) = x^2 + x - \alpha$.  Use the training set $(x_1,y_n),\dots,(x_n,y_n)$ to define an objective function:

$$\Phi(\alpha) = \sum_{i=1}^n (f(x_i,\alpha) - y_i)^2.$$

Finally, use numerical optimization methods to search for $\alpha$ that minimizes $\Phi(\alpha)$.  You could try gradient descent, Newton's method, or other techniques.  The value for that subtree deriving using genetic programming supplies a reasonable starting point for the search.

Example 2. In some cases, you will have more than one constant.  For instance, you might get the expression $x^2 + 2x - 3$.  Replace each constant with a symbolic value, so we get $f(x,\alpha,\beta) = x^2 + \alpha x - \beta$.  Now you can derive an objective function as above:

$$\Phi(\alpha,\beta) = \sum_{i=1}^n (f(x_i,\alpha,\beta)-y_i)^2,$$

and use optimization methods to search for $\alpha,\beta$ that minimize $\Phi(\alpha,\beta)$.


categories of registers and and storage in them

RAM addresses or addresses of I/O devices. For example, in x86 architecture an IP (instruction pointer) register holds the memory address of the next instruction that is going to be read and executed. This register cannot be accessed directly (it can be modified by jumps though). Also, in x86 an SP (stack pointer) register shows the top of the stack structure (mostly used to hold local variables of functions) and is implicitly modified by push, pop, call, ret instructions (and interrupts). Of course, there are more examples.


A recurring application for SAT model counting in the literature is extracting predictions from Bayesian networks. See "Algorithms and Complexity Results for #SAT and Bayesian Inference" and
"On probabilistic inference by weighted model counting".


Can any memory-less computer operation be represented in propositional logic?

Well you can just make a giant truth table for $f$ and then convert that to a Boolean formula. Boolean formulas are propositional formulas, are they not?


Proof of an Optimal substructure in Dynammic Programming?

There is no (one) formal definition of "optimal substructure" (or the Bellman optimality criterion) so you can not possibly hope to (formally) prove you have it.

You should do the following:

Set up your (candidate) dynamic programming recurrence.
Prove it correct by induction.
Formulate the (iterative, memoizing) algorithm following the recurrence.


Complexity of general polynomial map evaluation is polynomial?

You are basically doing an induction definition on $k$, where you evaluate a polynomial in $k+1$ variables by evaluation two polynomials of $k$ variables (by removing $x_1$.) So you have that the complexity $f(k+1)\approx 2f(k)$, which doesn't look polynomial to me.


proof of correctness for greedy knapsack algorithm

Slides are not a substitute for a textbook or careful exposition.  This is especially true when reading a proof.  Slides are intended for presentation in real-time, and as a result often leave out some details.  If there is some aspect you don't understand when reading a set of slides, usually the best thing to do is to find a proper written exposition of the subject -- usually a textbook (but sometimes written lecture notes can be adequate, if written in enough detail).

In this case, on the previous slide, the statement of the theorem mentions "nonincreasing order of $p_i/w_i$", which means that $p_1/w_1 \ge p_2/w_2 \ge \cdots$.  In particular, $p_k/w_k \ge p_i/w_i$ when $k<i$.  The inequality you are referencing then follows.


Any proof that the Wang tiling problem is undecidable by reduction from undecidability of the halting problem of Turing machines will contain instructions on how the Wang tiles simulate the operation of the machine, and indeed a proof that a tiling exists if and only if the machine doesn't halt.

There is more than one such proof. If you look at different proofs, you will see different reductions. There is absolutely no reason to expect that different reductions correspond to the same tiling placements. Indeed, there is no canonical way of converting Turing machines to tiling problems. Therefore there is no "reliable algorithm" for the problem; any specific proof should include such an algorithm that works for the specific proof.

I suggest you try to look up a technical paper with such a proof. Perhaps you can find a university library with Berger's original paper, or one of the later papers cited in the Wikipedia article.


Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Actually I did not get exactly what you are trying to do in Step 1 but complexity of this algorithm should be $O(n^{2} log(n))$ because you will get $(n*(n-1)/2)-c$ elements i.e $O(n^{2})$ elements and then to sort them you will get $O(n' log(n'))$ complexity where $n'=O(n^{2})$.

Their is a full proof solution for this problem and it also has complexity of $O(n^2 log(n))$.

Step 1. Lets assume all co-ordinates are nodes from 1,2.....N.First find
 distance b/w all the vertices in O(n^2).
Step 3. Find minimum spanning tree which can be formed using Prim's
 algorithm or Kruskal's algorithm whose complexity is O(E log(E))
 where 'E' is the number of edges and in our case E=n^2.

Hope that helps.


Term rewriting is a rewriting formalism. Starting with a term we rewrite the term according to the term rewriting rules until a normal form is found. Unification is finding a solution (substitution with specific properties) to a problem (a pair of terms).

Term rewriting uses a notion called "pattern matching". What you probably meant is: what is the difference between matching and unification?

Let two terms $t_1$ and $t_2$ be given.

If we want to unify $t_1$ and $t_2$, we search for a substitution $\sigma$ such that $t_1\sigma = t_2\sigma$. On the other hand, if we want to match $t_1$ into $t_2$, we are looking for a substitution such that $t_1\sigma = t_2$. That is, we apply the substitution only on $t_1$.

Logic programming is a programming paradigm which is based on resolution, which is a proof method for logics. In logic programming unification plays an important role.


Responsive input sliders - is there a better way?

I like John L's suggestion.  Have the app compute the view for the current position of all sliders.  Also, for each of the 6 other sliders, for each other 9 positions of that slider, precompute the view obtained from that.  In other words, you precompute all views that can be obtained by changing the position of a single slider.  That involves precomputing 6*9 = 54 other views.  Now, when the user clicks on a slider and changes its position, you'll be able to immediately display that view, and you can start precomputing 54 more views (for all combinations of changing one other slider to a different position).  As long as you can compute 54 views in the it takes for a user to move their mouse from one slider to another, you'll be able to keep up in a responsive way.


Why we don't consider cycles in path problems?

When solving most optimization problems on paths (e. g. shortest, longest path) a cycle is either useless or makes the optimum not exist (allowing infinitely long or short paths). Thus there's generally no point in allowing cycles.


Regular Languages in $ \mathsf{\text{}NC^1}$

Let $L$ be a regular language. Take some DFA $\langle q_0, Q, \delta, F \rangle$ that accepts $L$. There is a constant size circuit whose input is a symbol $\sigma$, and whose output is the function $q \mapsto \delta(q,\sigma)$. In other words, if $Q = \{q_1,\ldots,q_m\}$, then in input $\sigma$, the circuit computes the sequence $\delta(q_1,\sigma), \ldots, \delta(q_m,\sigma)$.

There is another constant size circuit whose inputs are two functions $f,g\colon Q \to Q$ (such as the outputs of the circuit above), and whose output is their composition $q \mapsto f(g(q))$. As before, we encode the inputs and outputs as sequences of $m$ states.

Given $n$, construct a circuit that computes whether a given input word $\sigma_1 \ldots \sigma_n$ belongs to $L$ as follows. Assume by simplicity that $n = 2^t$.

Compute the functions $q \mapsto \delta(q,\sigma_1), \ldots, q \mapsto \delta(q,\sigma_n)$ using the constant size circuit from the first paragraph.
Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2), \ldots, q \mapsto \delta(q,\sigma_{n-1}\sigma_n)$ using the constant size composition circuit from the second paragraph.
Compute the functions $q \mapsto \delta(q,\sigma_1\sigma_2\sigma_3\sigma_4), \ldots, q \mapsto \delta(q,\sigma_{n-3} \sigma_{n-2} \sigma_{n-1} \sigma_n)$ using the constant size composition circuit.
Continue in the same way for $t-2$ more levels, until you compute the function $\varphi$ given by $q \mapsto \delta(q, \sigma_1\ldots\sigma_n)$.
Using a constant size circuit, determine whether $\varphi(q_0) \in F$.

This circuit has depth $O(\log n)$ and size $O(n)$, and moreover it is uniform in $n$. This shows that $L \in \mathsf{NC^1}$.


TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

In the proof of the $\textit{PSPACE-}$completeness of TQBF, we need to construct a formula of some specific type. The recursive midpoint algorithm is easy to implement (and Savitch's Theorem requires finding the $\textit{algorithm}$), while the same idea, if performed in a similar manner, results in an exponential formula (and the completeness proof requires the $\textit{formula}$).

More generally, suppose there's some language $\textit{L}$, an optimal algorithm $A$ deciding $L$, and the smallest formula (maybe quantified) $\varphi$, s.t. $\varphi(x) = 1 \Leftrightarrow x \in L$. For me, it's not very clear why $A\in \textit{PSPACE}$ would imply that  $\varphi$ is small (I only see it as a consequence of the $\textit{PSPACE}-$completeness theorem)


Computing Von Neumann Entropy Efficiently

A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix to sum the results of applying that polynomial to each of the eigenvalues.

(The polynomial-via-power-and-trace thing works because density matrices have orthogonal eigenvectors. Raising the matrix to a power will raise its eigenvalues to that power. Then the trace gives you the sum of the eigenvalues at that power.)

Sounds fun. Not going to let the paper spoil it.

The derivatives of $f(x) = x \ln x$ are:

$$\begin{align}
f^0(x) &= x \ln x\\
f^1(x) &= 1 + \ln x\\
f^2(x) &= x^{-1} \\
f^3(x) &= -x^{-2}\\
f^4(x) &= 2 x^{-3}\\\
f^5(x) &= -6 x^{-4}\\\
...\\
f^k(x) &= (-1)^k \cdot (k-2)! \cdot x^{1-k}
\end{align}$$

The derivatives don't always exist at $x=0$, but they do at $x=1$, so we can make a Taylor series from there:

$$\begin{align}
x \ln x &= \sum_{k=0}^\infty \frac{(x-1)^k}{k!} f^k(1)
\\
&=
(1 \ln 1)\frac{(x-1)^0}{0!} + (1 + \ln 1)\frac{(x-1)^1}{1!} +  \sum_{k=2}^\infty \frac{(x-1)^k}{k!} (-1)^k 1^{1-k}(k-2)!
\\
&=
x - 1 + \sum_{k=2}^\infty \frac{(1-x)^k}{k(k-1)}
\end{align}$$

So now we have a nice series $\frac{(1-x)^1}{-1} + \frac{(1-x)^2}{2} + \frac{(1-x)^3}{6} + \frac{(1-x)^4}{12} + \frac{(1-x)^5}{24} + ...$ that we can approximate by cutting off at some index $c$. Except that would converge like $O(c^{-1})$ when $x=0$, so we should probably try to account for the excess when the numerator is stuck at $1$:

$\begin{align} x \ln x
&=
x - 1 + \sum_{k=2}^\infty \frac{(1-x)^k}{k(k-1)}
\\
&=
x - 1 + \sum_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum_{k=c}^\infty \frac{(1-x)^k}{k(k-1)}
\\
&\approx
x - 1 + \sum_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum_{k=c}^\infty \frac{(1-x)^{\Huge c}}{k(k-1)}
\\
&=
x - 1 + \left( \sum_{k=2}^c \frac{(1-x)^k}{k(k-1)} \right) + \frac{(1-x)^c}{c-1}
\end{align}$

Here's a graph of the difference between $x \ln x$ and the approximation when $c=10$:

And voila, just write code to evaluate that polynomial over the eigenvalues by using traces of the matrix powers:

import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)
    result -= numpy.trace(power) / (cutoff - 1)
    return result / math.log(2)  # convert from nats to bits

The convergence is still kinda terrible near $x \approx 0$, though. I tried replacing the last correction with some doubling steps like this:

import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)

    # Twiddly hacky magic.
    a = cutoff
    for k in range(3):
        d = (a+1) / (4*a*(a-1))
        result -= numpy.trace(power) * d
        power = power.dot(power)
        result -= numpy.trace(power) * d
        a *= 2
     result -= numpy.trace(power) / (a-1) * 0.75

     return result / math.log(2)  # convert from nats to bits

And that improved things a bit more, so that the maximum offset vs $-x \ln x$ across the [0, 1] range was $3.5 \cdot 10^{-3}$ instead of $2.9 \cdot 10^{-2}$ (for the given cutoff of 10).

(The plot is reversed.)

Of course, the paper I linked at the start of the answer probably has a much better polynomial.

For example, my error analysis should have been in terms of the total entropy instead of the individual value. And I should have used tricks like computing the trace of $AB$ from $A$ and $B$ in $O(n^2)$ time without doing the multiplication. And I should have thrown some simulated annealing at the coefficients.


Non-trivial tractable properties of triples

I think your "non-trivial" property would need to be a property of sets of triples, not of triples themselves; i.e. you need that there are an infinite number of sets of triples that satisfy and do not satisfy the property.

Call a triple consists of 3 identical elements a 3-clone. Checking that a triple is a 3-clone can obviously be done in linear time, and checking that a set of triples are all 3-clones can also be done in linear time, because checking each triple is independent of every other triple. And there are an infinite number of 3-clones, and an infinite number of non-3-clone triples; so straightforwardly there are infinite numbers of sets of 3-clones and sets that aren't sets of 3-clones.

I think you need to strengthen the definition of non-triviality; any property of triples that is non-trivial can be lifted to a fairly boring non-trivial property of sets of triples, and there are lots of non-trivial properties of triples that are trivially easy to decide. Even the property of whether the first element of the triple is 1 works. I think the "interesting" properties of sets of triples are not just independently decidable for each triple and then combining the decisions. I'm not sure how to go about expressing that constraint in a rigorous way though.

As for a survey on the subject, I'm afraid I'd never heard of characterising NP-complete problems as properties of sets of triples, so I can't do much for you there.


Let's solve this exercise "by induction". Suppose first that the alphabet is only $a,b$. In this case, the only possible words are $ababab\ldots$ and $bababa\ldots$, and you can write a simple regular expressions for them. Now take such a word over the alphabet $a,b,c$. You can break it apart as $w_1 c w_2 c w_3 c \ldots$, in which $w_i \in \{a,b\}^*$. We already have a regular expression describing the $w_i$, so we can write one for the language in question. This approach is general, and you can apply it to any alphabet size.


Is there a language that cannot be polynomially reduced to?

As stated in the comments, every problem is reducible to itself (under any notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...).

It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider:

No nonempty set is many-one reducible to $\emptyset$.
No set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$.

I'll prove the first, since the second is identical. Suppose $A\not=\emptyset$, and pick $a\in A$. Fixing any function $f$ whatsoever, we have $a\in A$ but $f(a)\not\in \emptyset$, so $f$ is not a many-one reduction of $A$ to $\emptyset$. This doesn't impact your main question, but it does illustrate a subtlety of many-one reductions. (Note that this doesn't apply to more complex reductions like Turing or truth-table: with respect to such notions, all computable sets are reducible to each other.)

You also ask in the comments whether there is some $X$ such that every set is reducible to $X$. The answer is no, regardless of what reducibility we use:

One natural example, applicable to all the usual reducibility notions in complexity theory, is provided by the Turing jump: every language $A$ has a "halting problem analogue," $A'$. The usual proof that the halting problem is not computable relativizes to show that $A'$ is not Turing-reducible to $A$, and a very simple argument shows additionally that $A$ is $1$-reducible to $A'$ - even logtime-$1$-reducible, under a mild assumption on the enumeration of oracle Turing machines we use. So in a very strong sense every set is strictly less complicated than its jump.

Incidentally the "complexity interval" between a set and its jump is always quite rich: the jump is very much not a successor operation. So in some sense using the jump here is massive overkill. However, there's no "natural" way so far as we know to build such "intermediate" sets (and this is why the halting problem is the canonical example of a non-computable set!). Indeed it's broadly conjectured that there are no "natural" sets $A,B$ such that $B$ is strictly between $A$ and $A'$ in terms of Turing reducibility, and we know some technical results along these lines. So introducing the Turing jump here is kind of unavoidable if we don't want to do weird stuff.

More coarsely, basically all of the reductions we consider in the context of computability theory have the property that they're indexed by natural numbers: for any $A$, there are only countably many $B$ which are reducible to $A$ according to that notion. Now apply Cantor.

This applies even to very strong reducibilities like hyperarithmetic reducibility (which in particular is so strong that the halting problem and the Turing jump in general is totally irrelevant). To break out of this situation we need to either look at "ambiguous" reducibilities like generic or coarse reductions or set-theoretic reducibilities like relative constructibility which are consistently fairly trivial. But the former are still subject to the "no-top-element" issue in a coarse manner by only slightly messier arguments, and the latter are generally only studied under additional assumptions which make them nontrivial (and in particular, lacking a top element).


How to use structural induction to prove law on lists

You'll want a helper lemma to make this endeavor more digestible.

Notations for map and subs:

I'm going to condense the map notation a bit so that we can express it as the binary operator $f \diamond l = \mathrm{map} ~ f ~ l$. Similarly, we will express the subs as a unary operation $\lfloor\!\!\lfloor l \rfloor\!\!\rfloor = \mathrm{subs} ~ l$.

This might seem terse at the moment, but it's useful to visually capture a "commutativity" property we will illustrate in a moment that sits at the core of the proof of this extensional equation.

Reformulation of the problem:

We want to show that
$$
\lfloor\!\!\lfloor f \diamond l \rfloor\!\!\rfloor = (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor
$$

which basically states that if we try to hoist the $f$ outside of the brackets, then we have to turn it into a map.

Now, if we follow your original blueprint, your inductive hypothesis establishes that
$$
\lfloor\!\!\lfloor f \diamond x ::l \rfloor\!\!\rfloor = (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor)
$$

In order for this proof to proceed, you need to tame the term on the righthand side of the concatenation. But what would you want it to look like?

Well, recall that maps distribute into concatenations:
$$
(f \diamond l_1) +\!\!\!+ ~(f \diamond l_2) = f \diamond (l_1 +\!\!\!+~ l_2)
$$

which suggests that we might be able to get our equation into an amenable form if we can rewrite the second term so that it is of the form $(f \diamond) \diamond \cdot$.

Here's where our helper lemma comes in to save the day:

Lemma ("Commutativity"):You have to use finger quotes when you read the name of this lemma out loud.
$$
(f ~x ::) \diamond ((f \diamond) \diamond l) = (f \diamond) \diamond ((x ::) \diamond l)
$$
Proof: Structural induction on $l$. This is actually a pretty easy proof, so I'll leave it to the reader™. However, the core of this proof is essentially showing that
\begin{align*}
(f~x ::) \diamond ((f \diamond) \diamond a :: [...]) &= (f~x ::) \diamond ((f \diamond a) :: \underbrace{((f \diamond) \diamond [...])}_{\text{induction hypothesis}}) \\
&= \underbrace{(f~x :: f \diamond a)}_{\text{map distributivity}} :: (f~x ::) \diamond((f \diamond) \diamond [...])) \\
&= (f \diamond (x :: a)) :: (f~x ::) \diamond((f \diamond) \diamond [...])) \\
& \text{discharge the induction hypothesis} \\
&= (f \diamond (x :: a)) :: (f \diamond) \diamond ((x ::) \diamond [...]) \\
& \text{distributivity} \\
&= (f \diamond) \diamond ((x :: a) :: ((x ::) \diamond [...])) \\
& \text{distributivity} \\
&= (f \diamond) \diamond ((x ::) \diamond (a :: [...]))
\end{align*}
which concludes the proof of the lemma. $\square$

Finishing your inductive proof:

Once we have this gem, we can continue your structural induction proof.

\begin{align*}
\lfloor\!\!\lfloor f \diamond x ::l \rfloor\!\!\rfloor &= (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f ~x ::) \diamond ((f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by the lemma} \\
&= (f \diamond) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~(f\diamond) \diamond ((x ::) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by distributivity of map} \\
&= (f \diamond) \diamond (\lfloor\!\!\lfloor l \rfloor\!\!\rfloor +\!\!\!+ ~ (x::) \diamond \lfloor\!\!\lfloor l \rfloor\!\!\rfloor) \\
& \text{by the definiton of } \lfloor\!\!\lfloor x :: l \rfloor\!\!\rfloor \\
&= (f \diamond) \diamond \lfloor\!\!\lfloor x :: l \rfloor\!\!\rfloor
\end{align*}

which satisfies your goal.

The equational acrobatics we've just performed seems a bit excessive, which is why I'm willing to bet that there's some elegant fusion law, recursion scheme, or some other representation (probably some categorical law given the nature of the problem) that nicely unwraps this proof. Unfortunately, AFAIK, I'm not aware of more elegant approaches. While this is a valid proof, it's somewhat unsatisfying. It is as much of a proof of this theorem as my performances of Taylor Swift is considered entertainment: it is technically correct, just not in the way that I intend it to be.


Randomized and Deterministic Communication Complexity of a function

Hint: The condition $x + y + xy = 0$ is equivalent to the condition $1 + x + y + xy = 1$, i.e. $(1 + x)(1 + y) = 1$, or in other words,
$$
(1+x)^{-1} = 1+y.
$$


What do Arora and Barak mean by $x|_S$ in their definition of certificate complexity?

It is a typo. $S$ indeed should be a subset of $[n] = \{1,2,\ldots,n\}$. On page 263, in the second sentence of their proof of Theorem 12.5, they list a 0-certificate (or 1-certificate) as a subset of $[n]$.

Because $S \subseteq [n]$, it is easy to understand $x|_S$ (as is stated in the question). This is just the usual notation for the restriction of a function on a subset of its domain. Note that an $x \in \{0,1\}^n$ can be thought of as a function from $[n]$ to $\{0,1\}$.


Does the closure of a function include the actual parameter passed to the function?

No. A closure is a function, and, as such, its parameters are passed when the function is called. The main difference between closures and plain functions is that closures are associated with an environment. This environment stores the values of the free variables* that were in scope when the function was created.

* The term free variable refers to those variables which are used locally within a function but are defined outside of this function (i.e., in an enclosing scope).


Maximizing total value given bound on total cost

Your problem is KNAPSACK, one of the classic NP-complete problems. Wikipedia contains a wealth of information about the problem, include exact and approximation algorithms.


If I understand your question correctly, you want to determine the binary representation of a floating-point number by hand. I assume you are talking about the IEEE 754 floating-point format, since this is the most common format.

You can indeed do this by successively multiplying with 2. However, just multiplying does not result in anything useful, you should also subtract one (1) every time the intermediate result is greater than or equal to 1. To understand this, you must understand how floating-point numbers are stored. This is explained pretty well on Wikipedia (and probably many other sources), including the algorithm you mean (see here).

To do this by hand is quite painful indeed. It's normal that you have to do more than 20 multiplications. You first need a few multiplications to normalize the number and determine the exponent (i.e. scale the number such that it has the form 1.xxxxx * 2^exponent). After that, each multiplication yields exactly one bit of the mantissa. A single-precision floating-point number has a 23-bit mantissa, so to convert the number 0.347 to single-precision floating-point, you need to do 25 multiplications. A double-precision floating-point has a 52-bit mantissa, so you'll need 54 multiplications!

NB: For sake of simplicity, I did not take into account numbers larger than 1, negative numbers, special numbers (such as NaN, +/- infinity, denormal numbers, etc.) and other aspects such as rounding. These cases seem to be out of the scope of your question.


If the integer representation used is "0 through 4,294,967,295 (2^32 − 1)", so does this mean the register cannot handle negative numbers?

The contents of a register don't have any inherent semantics.
Some instructions might assume certain semantics. For example, the x86 ADD instruction assumes that the registers represent integers, either unsigned or signed using two's complement. There are signed and unsigned versions in the x86 architecture for the multiplication instructions. Another unlikely place in which sign makes a difference is promotion instruction, in which a smaller register is assigned to a larger register – you want either zero extension (in the unsigned case) or sign extension (in the signed case, assuming two's complement).
What this all means is that certain the instruct set favors some interpretations by having instructions that assume them, but beyond that, the interpretation of the data stored in a register is completely up to the user. Moreover, in x86 at least, the same register can be used for both signed and unsigned operations. The register doesn't "know" which type of data it stores – it is completely up to the programmer. (One could imagine different architectures with different conventions.)


if I want only one element of the inverse matrix, does there exist a fast algorithm?

I have not seen exactly this in Mathematica but I think being able to solve an equation set for only one unknown may be supported.

The direct way would be of course to implement the inverse matrix algorithms and have them stop when the particular element is determined. It would probably be interesting to see what optimizations you can have for each algorithm if the goal is to get one element only.

But according to the first paragraph, one idea could be to express your matrix inverse as unknowns in equation system and then try solving only for the unknown you need (since solving equation set for a single unknown should be supported). If you get better memory and CPU performance then it may be safe to say that Mathematica did not actually solve the whole equation but just did its optimizations to determine only your unknown. You may get worse performance of course since you are not using inverse algorithms directly. If you decide to try let us know if it worked!


Is Vertex Cover of size $k >100$ polynomial time solvable?

We don't actually iterate over subsets $V'$ of size $C$, because that would be running in time $\Theta (n^k)$.  While that is polynomial for fixed $k$, there is an algorithm that runs in time $O(2^k \cdot n)$, which is much better.
The problem you have stated is not really very well defined, so let's try to clear it up.
The Vertex Cover problem is given a graph $G$ and a number $k$ and asks whether there exists a vertex cover in $G$ of size at most $k$.  This problem is NP-complete (as long as $k$ is not a constant).
However, if you ask to find any vertex cover in $G$, then you can reply with $V(G)$, which has size $n$.  This version is of course polynomial time solvable and uninteresting.
The answer is therefore: Vertex Cover is NP-complete.  If you fix the bounds, however, you can solve the problem in time "polynomial" time (exponential in the bounds).


Clear interrupt instruction in a pipelined CPU

Such a control hazard can be handled effectively the same way that a branch misprediction is handled. Either the CLI instruction commits and the interrupt handler fetch is treated as the mispredicted path and fetch is restarted after the CLI or the CLI instruction is not committed and the interrupt handler is treated as the correct path.


Finding row wise sum of transpose of hv-convex binary matrix

A non-increasing sequence of integers is known as a partition. The operation you are describing is known as conjugation. Given a partition $\lambda_1,\ldots,\lambda_n$, you can compute its conjugate $\lambda'_1,\ldots,\lambda'_m$ as follows:

Initialize a pointer $i$ at $n$.
Set $\lambda'_1 = i$.
Advance $i$ backwards until $\lambda_i \geq 2$.
Set $\lambda'_2 = i$.
Advance $i$ backwards until $\lambda_i \geq 3$.
Set $\lambda'_3 = i$.
...
Stop once $i = 1$.

As an example, here is how you apply this algorithm on $4,3,2,2,1$.
$$
\begin{align*}
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&&& \uparrow \\
&&&& 5
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{ccccc}
4 & 3 & 2 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$
It might happen that at some point $i$ doesn't advance at all. This is what happens if we apply this algorithm on $5,4,2,1$:
$$
\begin{align*}
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&&& \uparrow \\
&&& 4
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
&& \uparrow \\
&& 3
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
& \uparrow \\
& 2
\end{array} \\\hline
&\begin{array}{cccc}
5 & 4 & 2 & 1 \\
\uparrow \\
1
\end{array}
\end{align*}
$$


Two linear time approximation algorithms in the two-dimensional case are due to Bentely, Preparata and Faust and Stojmenović and Soisalon-Soininen.

A fast exact algorithm which works in expected linear time is due to Bentley, Clarkson and Levine. The paper is quite old, so maybe there are newer developments.


Fetching multi word instruction from memory

The answer: It depends on the implementation in that particular processor architecture. If this is just a made up example of an architecture, it probably hasn't been thought through properly, so nobody knows the answer.

That said, if I had to implement instruction fetch, then it would fetch the whole instruction.


Standard constructive definitions of integers, rationals, and reals?

Gilles answer is a good one, except for the paragraph on the real numbers, which is completely false, except for the fact that the real numbers are indeed a different kettle of fish. Because this sort of misinformation seems to be quite widespread, I would like to record here a detailed rebuttal.

It is not true that all inductive types are denumerable. For example, the inductive type

Inductive cow :=
   | nose : cow
   | horn : (nat -> cow) -> cow.

is not denumerable, for given any sequence c : nat -> cow we may form horn c which is not in the sequence by well-foundedness of cattle. If you want a correct statement of the form "all inductive types are countable" you have to severely limit the allowed constructions.

The real numbers cannot be easily constructed as an inductive type, except that in homotopy type theory they can be constructed as a higher inductive-inductive type, see Chapter 11 of the HoTT book. It could be argued that this is cheating.

There are a number of constructive definitions and constructions of the reals, contrary to Gilles claim. They can be broadly divided into two classes:

Cauchy-type constructions in which the reals as seen as a metric completion of the rational numbers. This sort of construction often requires quotients, although one may be able to get away with a coiunductive definition, dependig on how one treats equality. A naive construction typically requires countable choice as well, but Fred Richman gave a completion procedure which works constructively without choice, see his Real numbers and other completions.
Dedekind-type construction in which the reals are seen as (two-sided) cuts of rationals. This sort of construction usually requires powersets or a similar device, although it is possible to do it just with some basic $\lambda$-calculus and the axiomatization of the Sierpinski space $\Sigma$, see Dedekind reals in Abstract Stone Duality.

On the implementation side, we have various constructive formalizations of reals (but not the one in the Coq standard library which is just awful), for instance Robbert Krebbers's and Bas Spitters's Computer certified efficient exact reals in Coq.

For an actual implementation of exact real numbers I point you to Norbert Müller's iRRAM.

Lastly, Gilles remark about denumerable subsets of reals is off the mark. It is perfectly possible to construct or define uncountable sets, in whatever constructive setting you live. For example, the Baire space $\mathbb{N} \to \mathbb{N}$ of all sequences of numbers is alway uncountable, even if you think that every function is Turing-computable -- see my blog post for an explanation.


A reduction can be thought of a way to "rephrase" a problem in terms
of another. This can be denoted using $A \to B$, $A$ reduces to
$B$. This means that if you have an algorithm that solves $B$
then you also have an algorithm that solves $A$, since $A$ reduces
to $B$, $A \to B$. Now you also have $B \to A$ so in some way, your
problems are equivalent since they can be reduced to each other.

However, this does not imply much about the algorithms themselves
because they can be arbitrarily bad. For example, the sorting problem
has time complexity $O(n \log n)$. But an awful algorithm that sorts by
testing all possible permutations has time complexity $O(n!)$.

The only thing we can say is that the algorithms aren't better (their
time complexity isn't lower than) the problems themselves.