Proving correctness of the algorithm for convex polygon minimum cost triangulation

There are two parts to understanding here.

The algorithm is a straight-forward implementation of equation (5) using memoisation.
Equation (5) is correct, that is $A[i,j]$ is

  the minimum cost triangulation of the polygon spanned by vertices
    $i,i+1,...,j$

as the author claims. They give a reasoning right there:

  Formulating the subproblem this way we are enumerating all the possible
  diagonals such that the diagonals do not cross each other. Since we are
  only considering in clockwise directions, diagonals generated by the
  subproblems can not cross each other.

They argue that

all feasible solutions are considered and
all considered solutions are feasible.

If this is true, then choosing the minimum out all considered solutions is clearly the correct answer. Proving the bullets now needs insight into the problem, and the author gives the basic idea.

In terms of an induction, what I sketch above amounts to the inductive step. The anchor is trivial and covered in the text. The induction hypothesis has to be phrased such that you know for $i,j$ fixed that all $A[i,k]$ and $A[k,j]$ for $k=i,\dots,j$ are optimal.


Your answer is correct.
The alternative with $E\to ee$ is incorrect, as it might generate 'ee' in between 'd's. You must first shift all the E's to the end and only then make them into $ee$.
I would generate $cc$ and $ee$ together, and play with the $D$'s, i.e., $Y\to cc YD ee$, etc. This will be slightly more simple, though equivalent.


Fibonacci Sequence recursion algorithm and the time complexity

You can prove that $T(n) \geq F_n$ by induction. For $n = 0$ and $n = 1$ we have $T(n) \geq 1$ and $F_n \leq 1$. Suppose that the claim holds for $n-1$ and $n-2$. Then
$$
T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n).
$$


To use such a parser, you need some external way to select among the possible trees in the forest.  Typically there are additional constraints beyond what is encoded in the context-free grammar, which can be used to identify the correct parse.  In other words, there are some rules that are part of the syntax (they are part of the context-free grammar, and thus handled by the parser), and some rules that are part of the semantics; there may be multiple parses that are compatable with the syntax rules, and then the semantic rules are used to select which one complies with the semantic rules.


Solving second-order ODEs with Taylor series approximation of second derivative and linear algebra

What you have there is the central difference approximation to the second derivative. The Wikipedia article on finite differences explains this pretty well.

Of course, this isn't a method as such; that depends on the exact problem being solved. If this were an initial value problem, then a simple rearrangement of this equation is typically known as Störmer–Verlet integration (or just Verlet integration depending on whom you ask).

If it was a bounding-value problem, then this discretisation of the derivative gives you a tridiagonal system, and you don't have a complete "method" until you have a method to solve it. A small modification of Gaussian elimination is quite efficient on matrices of this form.

As to competitors... that's a very long discussion. Any introductory textbook on numerical analysis should give you a good start.


Confused by extremely high autocorrelation

Most of the values of the random walk $x$ are large ($\omega(1)$) with high probability. Therefore the difference between $x_i$ and $x_{i+1}$, which is $\pm 1$, is small. So the random walk correlates well with itself.

You can get results even closer to $1$ if you start your random walk from some position far away from the origin. Try it out!


Why do we need "potential” for amortized analysis?

As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is.

The idea of amortized analysis is that while operations may have a bad worst case cost, their average cost could be much lower. Average cost means different things in different circumstances. In amortized analysis, here is what it means:

  Suppose that you have a data structure supporting operations $O_1,\ldots,O_r$. We say that these operations have amortized cost $c_1,\ldots,c_r$ if the cost of the sequence $O_{i_1},\ldots,O_{i_n}$ of operations is at most
  $$
c_{i_1} + \cdots + c_{i_n}.
$$

This definition is a bit simplistic, since sometimes the amortized cost depends on other auxiliary parameters such as the overall number of operations or the number of operations of a specific type.

The potential method is one way of carrying out amortized analysis, that is, of proving that the operations in a certain data structure have some amortized cost. Stated differently, if you want to prove that the amortized cost of $O_1,\ldots,O_r$ is $c_1,\ldots,c_r$, then one of the techniques is the potential method. There are other techniques as well.

How does the potential method work? You define a potential function $\Phi$ on the state of the data structure. The potential function must be always non-negative, and for the initial data structure it must be zero. You then prove that if at state $S_{\text{before}}$ you execute operation $O_i$ which leads to state $S_{\text{after}}$, then the cost $T_{\text{actual}}$ of the operation satisfies
$$
T_{\text{actual}} \leq c_i + \Phi(S_{\text{before}}) - \Phi(S_{\text{after}}).
$$
Given that this holds for all $i$, consider a sequence of operations $O_{i_1},\ldots,O_{i_n}$, and denote the corresponding states of the data structure by $S_0,\ldots,S_n$. The upper bound on $T_{\text{actual}}$ implies that the total cost of these operations is at most
$$
\begin{align*}
\sum_{t=1}^n [c_{i_t} + \Phi(S_{t-1}) - \Phi(S_t)] &= \sum_{t=1}^n c_{i_t} + \sum_{t=1}^n [\Phi(S_{t-1}) - \Phi(S_t)] \\ &=
\sum_{t=1}^n c_{i_t} + \Phi(S_0) - \Phi(S_n) \\ &=
\sum_{t=1}^n c_{i_t} - \Phi(S_n) \\ &\leq
\sum_{t=1}^n c_{i_t},
\end{align*}
$$
which was to be proven.


Maximum entropy probability distribution among Solomonoff priors

All versions of Solomonoff's prior have infinite entropy.
We supply a proof.
Let $m: \mathbb{Z}_+ \to [0,1]$ be Solomonoff's prior, where inputs are
encoded as integers.
Then there is $c>0$ such that
$$m(n) \geq c\frac{1}{n (\log n)^2},$$
Let $S$ be the set of all $n$ such that
$$m(n) \geq \frac{1}{n}.$$
Since $\sum m(n)$ is convergent,
$$\sum_{s \in S} \frac{1}{s} \leq \sum_n m(n) < \infty.$$

The entropy of $m$ is
$$
\begin{align*}
\sum_n m(n) \log(1/m(n)) &\geq \sum_n c\frac{1}{n (\log n)^2} \log(1/m(n)) \\
&\geq \sum_{n \not\in S} c\frac{1}{n (\log n)^2} \log(1/m(n)) \\
&\geq \sum_{n \not\in S} c\frac{1}{n \log n}.
\end{align*}
$$

Now
$$
\infty = \sum_{n} c\frac{1}{n \log n} =
\sum_{n \in S} c\frac{1}{n \log n} +
\sum_{n \not\in S} c\frac{1}{n \log n},
$$
and
$$\sum_{s \in S} \frac{1}{s \log s} \leq \sum_{s \in S} \frac{1}{s} < \infty,$$
so
$$
\sum_{n \not\in S} c\frac{1}{n (\log n)} = \infty.
$$


This problem is the same as the problem of finding the maximum matching in bipartite graphs, which can be solved by the Ford-Fulkerson algorithm in $O((n+m)s)$ time or the Hopcroft-Karp algorithm in $O(\sqrt{n+m}s)$ time, where $s$ is the number of elements in all $S_i$ combined.

Given a collection of subsets $\{S_1,\ldots,S_m\}$ where each $S_i\subset \{1,\ldots,n\}$, let $G$ be the graph with nodes $\{1, 2, \cdots, n, S_1,S_2,\cdots,S_m\}$. Whenever $j\in S_i$, there is an edge $e_{j,S_i}$ in $G$ that connects node $j$ and node $S_i$. $G$ is a bipartite graph with vertex sets $X=\{1, 2, \cdots, n\}$ and $Y=\{S_1,S_2,\cdots,S_m\}$

Suppose we have selected $k_i$ from $S_i$ for all $i$. Having removed duplicate numbers among ${k_1}, {k_2}, \cdots, {k_m}$, we can assume $\{k_i\mid i\in I\}$ for some $I\subseteq
\{1,2,\cdots,m\}$ is the set of distinct numbers among them. Then $\{e_{k_i, S_i}\mid i\in I\}$ is a matching in $G$.

Conversely, if we have a matching $\{e_{k_i, S_i}\mid i\in I\}$ in $G$ for some $I\subseteq \{1,2,\cdots,m\}$, we can select $k_i$ from $S_i$ when $i\in I$ while selecting any element from $S_i$ when $i\not\in I$.

The above two conversions show that the problem in the question, finding the maximal number of selected elements is the same as the problem of find the cardinality of the maximum matching in a bipartite graph. Note that the conversion takes linear time or polynomial time depending on which parameters are used.

Here is a variation for which I do not know if there exists a polynomial algorithm.

Problem. What if we select two elements from each set, assuming each set has at least two elements?


Having a formal ISA specification - What does correctness mean?

An ISA spec says how a processor should behave. A processor either conforms to such a spec (behaves exactly like the spec says it should), or it doesn’t (behaves differently in some situations).

ISA has nothing to do with correctness of programs. If a processor conforms to its ISA spec then all programs will behave as they should behave according to the spec, both correct and incorrect programs. If a processor does not conform to the ISA spec then programs can behave different from how they should behave.

A spec cannot be wrong, by definition. It can be nonsensical (like if the spec says that an “add” instruction should subtract, but it’s never wrong.

Reasons for having an ISA spec:

Instructing the team that designs the processor.
Instructing the team that writes test code to test the processor for conformance.
Instructing the team that writes a simulator for the processor which can be used before processors are available.
Instructing teams that write compilers for this processor.
Instructing support teams who handle customer complains about the processor behaviour, so they can check that the processor conforms to the spec.


Inference rule with two conclusions or rather inverse function application

Let us introduce an auxiliary predicate $t \downarrow$ whose intended meaning is "$t$ evaluates to something". Its inference rule is
$$\frac{t \Downarrow v}{t \downarrow}.$$
Now you can express your condition with the following two rules:

If $\Delta(t)$ evaluates to $v$ and $t$ evaluates $v'$ then $v$ equals $\Delta(v')$:
$$\frac{\Delta(t) \Downarrow v \qquad t \Downarrow v'}{\Delta(v') = v}$$
If $\Delta(t)$ evaluates to something then so does $t$:
$$\frac{\Delta(t) \downarrow}{t \downarrow}$$.

This is not quite the same as using first-order logic and writing $(\exists v . \Delta(t) \Downarrow v) \implies \exists v' . t \Downarrow v'$. You have to go "meta" and use inversion to conclude from $t \downarrow$ that there exists $v'$ such that $t \Downarrow v'$.

By the way, you said that "since the implication operator $\Rightarrow$ is already used in my dynamic semantics, I'd rather use an inference rule to express the implication" That's a pretty awful reason to choose inference rules over axioms (which is what an implication would give you). You should ask instead what your semantics is for. If you are interested in operational semantics, i.e., you want to express how your programs will be executed, then the rule you are talking about does not really contribute anything. If you want your semantics for reasoning about $\Delta$ and $\Downarrow$, then it might actually be use good old first-order logic.


Your question reminds me of an old joke:

If the Atlantic can be crossed in 7 days with one boat, you can cross it in
one day, if you have seven boats available. (there are actually many variants)

Your problem is the problem of assembly lines in general, and that is the technical model of a pipelined processor.

On the assembly line for making car (I am of course simplifying), you
will have one fellow placing the doors, another one placing the
bumpers, one placing the wheels, another painting the car. They all
work at the same time, doing their job in the duration of a single
car making cycle, fixed by the big clock on the factory wall.

Every cycle, the last worker of the line finishes one car, while the first
does the initial steps of making a new one. So there is exactly one
car produced for each cycle. There is a single assmbly line (read:
a single processor), producing one car with each cycle.

But it does not mean that it takes only one cycle to produce a car. It
takes as many as there are stages in the assembly line. The rate of
production (read processing rate) of one car per cycle is only a
average over time.

The idea that that it is more efficient to have specialized workers
working independently. But you do not want to keep them idle, when it
is not their turn on a given car.

And, it may not be necessary that each car is built identically to the
previous one. All you need is that each worker gets his part of the
instruction(s), such as the diameter of the wheels to be placed, or
the color of the paint. So the instructions may change, while going
through the same assembly line to produce cars.

No one ever preempts the line to get something done. But all contributing workers are synchronized.


Probabilistic adaptive algorithm that can explore only $k$ bits of input can’t distinguish $k$-independent distribution from uniform

$$
\Pr[A(x)=1]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr[A(x)=1 | \text{A requested bits $i_1,...,i_j$}]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]=\sum\limits_{i_1,...,i_j \\0\le j\le k} \Pr\left[A\left(x_{i_1,i_2,...,i_j}\right)=1\right]\cdot\Pr[\text{A requested bits $i_1,...,i_j$}]
$$
Here you already see that if $A$ is non adaptive this becomes immediate, as only one summand is non zero, and $A(x_{i_1},...,x_{i_j})$ has the same distribution as $A(U_j)$. If one considers randomized $A$ then change this argument to claim that the bits requested do not depend on the input, and thus the probability of requesting a certain set of indices does not depend on the distribution of the input. For the adaptive case, try the following. Denote by $a_i$ the index of the $i'th$ bit requested by $A$.
$$
\Pr[\text{A requested bits $i_1,...,i_j$}]=\Pr\left[\bigwedge\limits_{l=1}^j a_l=i_l\right]=\Pr\left[a_j=i_j \Bigg| \bigwedge\limits_{l=1}^{j-1}a_l=i_l\right]\cdot
\Pr\left[a_{j-1}=i_{j-1} \Bigg| \bigwedge\limits_{l=1}^{j-2}a_l=i_l\right]\cdot...\cdot\Pr\left[a_2=i_2 |a_1=i_1\right]\cdot\Pr[a_1=i_1].
$$
Note that in each term the probability is both over the internal randomness of $A$ and the randomness of the input $x$ (which is implicit in the above). You can now prove by induction that in each multiplier, you can switch $x$ with a uniformly distributed string. More formally, for all $1\le l\le j$, the random variable $a_l$ conditioned on $a_1,...,a_{l-1}$ has the same distribution as $a_l$ when $x$ is uniformly random. Finally, plug this back to the above sum, and now every occurence of the input $x$ was switched by a uniformly distributed string.


Hardness of maximizing difference of functions

I suspect there's not likely to be any characterization that is very useful.  The optimization problems can be hard or easy depending on $g$.
To give an analogy: you could ask for a characterization of functions $f$ for which it is NP-hard to maximize $f$.  Well, you're probably not going to find a useful one.


Efficient algorithm for graph canonization for directed acyclic graphs?

According to Wikipedia (which references lecture notes of Zemlyachenko, Korneenko and Tyshkevic), isomorphism of directed acyclic graphs is GI-complete. Therefore any polynomial time canonicalization algorithm for directed acyclic graphs would result in a polynomial time algorithm for graph isomorphism. Since no such algorithm is known, one concludes that no polynomial time canonicalization algorithm for directed acyclic graphs is known, and it is conjectured that none exists.


Is memorization necessary in learning computer science?

It's hard to answer what you "need", as that depends on your purpose, and hard to answer this question concretely, as it is very broad.  I recommend you focus on learning concepts and ideas, as these are more likely to be of lasting use.  Sometimes, though, to understand how some interesting capability is achieved, you will need to understand the details of how it is implemented.  In general, if you pick a good textbook, then it's likely that there will be a lot of worthwhile material in there.  Saying much more might require getting into specifics.


Is reservoir sampling unnecessary if you know the length of the stream of integers?

There is no particular downside. It's a perfectly valid approach.


Find an upper bound for a Linear Recurrence

You say that $N=\lfloor\tfrac{n}{logn}\rfloor$. But since you have a linear recurrence in N, not n, you really want n as a function of N.

We have $n ≈ N \log n$.

You substitute this for n and get $n ≈ N \log (N \log n) = N \log N + N \log \log n$.

$\log \log n$ is small compared to $\log N$, so we ignore it and get $T(N)=T(N-1)+\mathcal{O}(N \log N)$

We get $T(N)$ by summing $\mathcal{O}(k \log k)$ for k = 1 to N, which will be $\mathcal{O}(N^2 \log N)$.


Condition for perfect matching in bipartite graphs

Here is a proof for the following related result:

  A $d$-regular bipartite graph contains a perfect matching.

According to Hall's criterion, a perfect matching exists if for all $A \subseteq S$, $|N(A)| \geq |A|$. Take any $A \subseteq S$. There are $d|A|$ edges connecting vertices in $A$ to $T$. A given vertex $t \in T$ can be the target of at most $d$ such edges. Hence there are at least $d|A|/d = |A|$ such targets, that is, $|N(A)| \geq |A|$.

Try modifying this proof for your case.


Difference between time complexity and computational complexity

Computational complexity is just a more general term, as time is not the only resource we might want to consider. The next most obvious is the space that an algorithm uses, and hence we can talk about space complexity, also as a part of computational complexity. Indeed we can do this for any measure you care you use, of course some measures are more useful than others.

So counting the number of steps that an algorithm takes in the worst case gives a time complexity bound for the problem it solves, counting how much memory/how many tape cells it uses gives a space complexity bound etc. etc.

Remember also that if you want to be strict, complexity refers to the problem, not the algorithm, so a problem has complexity bounds, an algorithm has resource bounds (running time, space use...).  It's just a matter of definitional formality, complexity theory deals with problems. Yes, algorithms are a key tool for analysing problems and complexity and algorithmics are closely tied together, but formally we wouldn't say Merge-Sort (an algorithm) is in $P$, it's the problem $\mathsf{Sorting}$ which is in $P$. Merge-Sort uses certain resources ($O(n\log n)$ steps for example). The resource bound and correctness of the algorithm imply the complexity (upper) bound for the problem, but they're different things. $\mathsf{Sorting}$ is also $TC^{0}$-complete under $AC^{0}$-reductions, this complexity bound can only really be stated for a problem (but does have algorithmic implications).


Does an Operating System inject its own machine code when you open a program?

No. The operating system does not mess around with the program's code injecting new code into it. That would have a number of disadvantages.

It would be time-consuming, as the OS would have to scan through the entire executable making its changes. Normally, part of the executable are only loaded as needed. Also, inserting is expensive as you have to move a load of stuff out of the way.
Because of the undecidability of the halting problem, it's impossible to know where to insert your "Jump back to the OS" instructions. For example, if the code includes something like while (true) {i++;}, you definitely need to insert a hook inside that loop but the condition on the loop (true, here) could be arbitrarily complicated so you can't decide how long it loops for. On the other hand, it would be very inefficient to insert hooks into every loop: for example, jumping back out to the OS during for (i=0; i<3; i++) {j=j+i;} would slow down the process a lot. And, for the same reason, you can't detect short loops to leave them alone.
Because of the undecidability of the halting problem, it's impossible to know if the code injections changed the meaning of the program. For example, suppose you use function pointers in your C program. Injecting new code would move the locations of the functions so, when you called one through the pointer, you'd jump to the wrong place. If the programmer was sick enough to use computed jumps, those would fail, too.
It would play merry hell with any anti-virus system, since it would change virus code, too and muck up all your checksums.

You could get around the halting-problem problem by simulating the code and inserting hooks in any loop that executes more than a certain fixed number of times. However, that would require extremely expensive simulation of the whole program before it was allowed to execute.

Actually, if you wanted to inject code, the compiler would be the natural place to do it. That way, you'd only have to do it once but it still wouldn't work for the second and third reasons given above. (And somebody could write a compiler that didn't play along.)

There are three main ways that the OS regains control from processes.

In co-operative (or non-preemptive) systems, there's a yield function that a process can call to give control back to the OS. Of course, if that's your only mechanism, you're reliant on the processes behaving nicely and a process that doesn't yield will hog the CPU until it terminates.
To avoid that problem, a timer interrupt is used. CPUs allow the OS to register callbacks for all the different types of interrupts that the CPU implements. The OS uses this mechanism to register a callback for a timer interrupt that is fired periodically, which allows it to execute its own code.
Every time a process tries to read from a file or interact with the hardware in any other way, it's asking the OS to do work for it. When the OS is asked to do something by a process, it can decide to put that process on hold and start running a different one. This might sound a bit Machiavellian but it's the right thing to do: disk I/O is slow so you may as well let process B run while process A is waiting for the spinning lumps of metal to move to the right place. Network I/O is even slower. Keyboard I/O is glacial because people are not gigahertz beings.


Algorithm for blending/merging shapes together like liquid

The Povray raytracer has an object like this, the blob. You find its code with some explanations at https://github.com/POV-Ray/povray/blob/master/source/core/shape/blob.cpp .


Stratification of Bisimilarity : $\sim$ does not coincide with $\sim_\omega$

I found the answer of my question when writting it, which once again prove the effectiveness of writting down properly the question we have.

To show that $s \sim_1 t$, to map $a^\omega$, one can take any $a^i$ we want (e.g. $a^0$): by definition,
$\sim_0 \overset{\text{def}}{=} W\times W$, and therefore we indeed have that $s\overset{a}{\rightarrow} a^0$ and $a^0\sim_0 a^\omega$.
Something to notice is that, for each $n$, we have $a^\omega \sim_n a^m$ for $m\geq n$. Therefore, to show that $s\sim_{n+1} t$, to show item (2), one can simply take $a^n$ as $s^\prime$ when we take $a^\omega$ as $t^\prime$. The rest of the proof is trivial.


how to deal with mismatched tag bits in cache

For every cache set, there are $2^t$ blocks that can potentially be stored in there. However, only $E$ of them are actually stored at any particular time - typically, these would be the "most recently used" ones.
Incidentally, the whole reason for storing the tags themselves inside the cache is to be able to tell which ones are currently cached. The block's tag is not the "index" of a cache line, it's a $t$-bit identifier which is literally compared against every tag in the set in order to check whether this block is available or not.


What does this language notation specify?

Language concatenation is defined as follows:
$$
L_1 L_2 = \{ w_1 w_2 : w_1 \in L_1, w_2 \in L_2 \}.
$$
In other words, a word $w$ belongs to $L_1 L_2$ if it can be written as the concatenation of two words, $w_1 \in L_1$ and $w_2 \in L_2$.
This definition should suffice for solving the exercise.


Why is the usual simulated annealing algorithm using a Boltzmann probability?

This formula can more insightfully be written as

$$ p = \frac{1}{e^{\dfrac{\Delta E}{T}}}$$

where, in the context of SA, $\Delta E$ is the difference between the "energy" (or quality) of two possible solutions and $T$ is the temperature (which is either a constant or a function of the input size).

So, the higher the energy difference $\Delta E$, the smaller the probability $p$. In the context of SA, if the cost of the current solution is greater than the cost of the new solution, then you replace the current solution with the new solution. However, if the cost of the current solution is smaller than the new solution, then you do not automatically discard the new solution. More concretely, with probability $p$, you accept the new worse solution. This the stochastic action taken by SA. So, the higher the diffence between the costs of the current and new solutions, the smaller the probability of accepting the new worse solution.

The Boltzman distribution only happens to capture this idea of accepting new worse solutions, provided that they are not extremely worse than the current solution. In theory, you can use other (similar) distributions.


It is nice that you have checked your idea on some random samples.

To see why your idea work, let us find the simplest but non-trivial case and then take a look at it.  For simplicity and WLOG, the weight of a node will be used to denote that node. For example, if $A$ contains a node with weight $42$, that node will be referred to as node 42.
The case of $n=1$ is trivial.
Let $n=2$. If we happens to look at to $A=\{1, 2\}$ and $B=\{3,4\}$, then however we choose the mapping, the sum will be $1+2=3$. This sample is apparently not enlightening.
How about $A=\{1, 3\}$ and $B=\{2,4\}$?

If we connect 1 with 2 and 3 with 4, the sum is $\min(1,2) + \min(3,4)=1+3=4$.
If we connect 1 with 4 and 3 with 2, the sum is $\min(1,4) + \min(3,2)=1+2=3$.

So this is a non-trivial example. Now we should ask the basic question, why does the second choice produce a smaller sum?
To answer the question, we should observe how those two sums come up. Note that 1 appears in both sums. Is that coincidence? Think for a moment and you will know it is not. 1 is the minimum number of all numbers. So whatever it is connected to, it will be selected as the weight of the connection.
That means, whatever number 1 is connected to, which is 3 in this case, that number will be missing from later computations, i.e., it will be "wasted". The bigger the "waste" is, the less the remaining numbers will be and hence the less weight the remaining connection will produce, since function $\min(\cdot, \cdot)$ is decreasing with respect to both variables.  So 1 should be connected to a number as big as possible. That is why 1 is connected to 4 instead of 3 so as to produce the minimum total sum.
In the case of $n=2$, there are only two choices of the mapping. Either the smaller number in $A$ is mapped to the smaller number in $B$, dubbed "forward mapping", or to the bigger number in $B$, dubbed "reverse mapping".  To make the mapping produce smaller total weight, we should always choose the "reverse mapping", so that a large number will be wasted (or, what is the same, a smaller number will be kept to be used.)

To prove your idea is correct, we first show that for any mapping from $A$ to $B$, there is a mapping that maps $\min(A)$ to $\max(B)$ with no greater total weight. Suppose map $f$ maps $\min(A)$ to some $b_j$ and some number $a_i$ to $\max(B)$. Then we can make another map $f'$, which is the same as $f$ except for these 4 number, $f'$ maps $\min(A)$ to $\max(B)$ and $a_i$ to $b_j$. Since, as we have shown above, for four numbers $\min(A), a_i$ and $b_j$, $\max(B)$, we have
$$ \min(\min(A), \max(B)) + \min(a_i, b_j)\le \min(\min(A), b_j) + \min(a_i, \max(B)),$$
the total weight of $f'$ is not greater than that of $f$.
So we know,

the minimum total weight comes from a mappings that maps $\min(A)$ to $\max(B)$.
For all mappings that map $\min(A)$ to $\max(B)$, the minimum total weight comes from, by the same argument, a mapping that maps the minimum of the remaining numbers in $A$ (i.e. the second minimum number in $A$) to the maximum of the remaining numbers in $B$ (i.e., the second minimum number in $B$).
For all mappings that map $\min(A)$ to $\max(B)$ and the second minimum number in $A$ to the second maximum number in $B$, the minimum total weight comes from a mapping that maps the third minimum number in $A$ to the third maximum number in $B$.
And so on, until the last minimum number in $A$ is mapped to the last maximum number in $B$, i.e., the maximum number in $A$ is mapped to the minimum number in $B$.  $\checkmark$

An even more formal proof could be given. However, the above reasoning might be easier to understand. It should, I believe, convince an ordinary human.

Here is another straightforward way to prove your idea.
First assume all numbers are distinct. Let us prove by reductio ad absurdum. Suppose the minimum total weight can be reached by a mapping $g$ other than the mapping described in your idea. Then $g$ must contain a sub-mapping that is a "forward mapping", i.e., there must be two numbers $\alpha_1\lt \alpha_2$ in $A$ and two numbers $\beta_1\lt \beta_2$ in $B$ such that $g(\alpha_1)=\beta_1$ and $g(\alpha_2)=\beta_2$.
Now we can make another mapping $g'$ which is the same as $g$ everywhere else except that the sub-mapping of $g'$ on $\alpha_1$ and $\alpha_2$ is a "reverse mapping", i.e., $g'(\alpha_1)=\beta_2$ and $g'(\alpha_2)=\beta_1$. Now we can, as before, verify that the total weight of $g'$ is smaller than that of $g$, which contradicts our assumption.
If all numbers are not distinct, we will use the technique of approaching by limit. Perturb all numbers slightly so that they become distinct. Now all weights will be slightly off their original weights. That means the total weight obtained from your idea should not be far from the optimal solution. Let the perturbation go to zero, we see that it is, in fact, the optimal solution.

You might be interested in a similar problem, how to prove the greedy algorithm that minimize the maximum sum of a pairing.


Do all algorithms aim to solve decision problems?

There is a class of problems called decision problems that have an yes/no answer. These problems can be further be classified in decidable, where we have a way to solve them, or undecidable, for which there cannot be or has not been yet discovered a way to solve them.

However, there is another set of problems where we are not interested in a yes/no answer, but rather in a more specific solution. For example, there are optimisation problems, where we are searching for the best value according to some parameters, or counting problems, where we are interested in counting the number of instances where certain property occurs.

To sum it up, decision problems are a specific class of problems, a subset of which can be solved by algorithms. However, algorithms can be used to solve problems in other classes.

Now, given an algorithm for a specific problem, one can solve multiple problems equivalent to the original one (there are ways of "translating" a problem in the terms of another one, and having a solution to one problem means having a solution for all such problems).


Issues with using greedy algorithm (Interval scheduling variant)

It is clear from your edited post that you will need to use dynamic programming.

Consider solution with the recurrence based on minimum number of time intervals necessary to conflict with all other time intervals, and include a parent pointer so that you can create the set after the algorithm completes.


What does "satisfactory definition" mean?

It means nothing in particular.  You can read it as "good enough".  It is not encoding some specific technical meaning.


How can I take advantage of the capabilities of a cluster

According to my experience, clusters usually work like this: you submit a job to it (a program), and it allocates a node to run your job. You don't worry about allocating the nodes yourself.

So in your case, simply submit multiple jobs (usually they provide some method to submit batch jobs), and the cluster will allocate different nodes to each of them.


What are these questions in the PoplMark challenge asking?

The reduction relation is beta reduction (for term and type variables) as defined in the description of Challenge 2B. It's a single reduction step, not repeated reduction until a value is reached.

(3) says to find a term $t'$ such that $t \to t'$ because if one exists, then there are infinitely many such terms in $F_{<:}$: all the terms in the same alpha equivalence class. Usually we say that beta reduction is deterministic, i.e. $t'$ is unique, but that's because we reason on alpha equivalence classes. PoplMark is concerned with the representation of variable binding, so here terms are a concrete representation where variable binding is treated explicitly. For example, in a nominal representation, $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{x}. \texttt{x})$, and $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{z}. \texttt{z})$; (3) allows finding any of these since they are all equally valid.

Similarly (1) asks to check whether $t'$ is a possible result of reducing $t$, not the result: the implementation of the reduction (item (3)) might find a different representative of the alpha equivalence class from the one submitted by the user.

Only (2) is about reducing to a value. It says so explicitly: $t$ reduces to $t'$ in any number of steps, and $t'$ cannot be reduced.


A program running in space $f(n)$ can take up to $2^{O(f(n))}$ time (the constant depends on the alphabet size). Hence, it could potentially make up to $2^{O(f(n))}$ non-deterministic choices. Naively, going over all of them requires that many steps. Savitch's theorem shows how this can be accomplished using only $O(f(n)^2)$ space. The idea is to use a recursive "meet in the middle" approach. Let an upper bound on the running time of the machine be $T$. The initial tape is the the state of the tape when the machine is started up. The final tape is the state of the tape at the end of the execution. We "guess" (i.e., go over all possibilities) the final tape, and try to verify that this final tape can be reached from the initial tape. At the first level of the recursion, we "guess" the contents $X$ of the tape at time $T/2$. We then recurse into two similar tasks:

Verify that $X$ can be reached in $T/2$ steps from the initial tape.
Verify that the final tape can be reached from $X$ in $T/2$ steps.

Each of these is solved by recursion. We can reuse the space of the first task when we execute the second task. The base of the recursion is when the number of steps is one, in which case we can verify the claim directly. If it checks out, great. Otherwise, we signal failure, and this signal prompts us to make the next guess (at the appropriate level of recursion).

Each level of the recursion requires storage space of size $f(n)$, and there are $\log T = O(f(n))$ levels, so the total space consumption is $O(f(n)^2)$.


Number of operations performed in increment operators

Depends. For the purpose of formal analysis, this is usually below our threshold of modelling. Just make a reasonable assumption, or forbid syntactic sugar in your model syntax.

Note that, if you are analysing at this level of detail, working with higher-level languages can be painful. If you want to follow Donald Knuth's lead,

fix a (manageable) machine model and
fix a low-level machine language.

The express your algorithms and this language and analyse. They may not look as nice as high-level pseudocode versions, but analysis is unambiguous.


In the divide and conquer approach, we break the problem into subproblems and we try to solve these subproblems.
So, you can divide your problem into two subproblems till you reach one element. Now you can combine these subproblems but in each step, you know the 3 smallest elements of these subproblems.
Fortunately, Merge Sort uses the divide and conquer idea to sort an array. Please note that in each step of combining subproblems, it is sufficient to hold only three elements of each sub-lists. So, it is not necessary to sort all elements. (Just the 3 smallest elements)
Check Merge sort here:
https://www.geeksforgeeks.org/merge-sort/


An initial algebra is an initial object in the category of $F$-algebras for a given endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$.

This construction is widely used to gives semantics to data-structures in (functional) programming languages. Intuitively, the functor $F$ captures the "shape" of the data-structure (e.g., $F(X) = 1 + A \times X$, with $A$ a fixed set for instance).

The underlying set $\mu F$ of the initial algebra
$\langle \mu F, \alpha \rangle$ intuitively captures the set of syntactic expressions you can build by induction on the shape functor (e.g., for the previous functor with $A = \{a,b \}$, $\mu F = \{(1), (a,1), (b,1), (a,a,1), (a,b,1) \ldots \}$ is the set of finite lists of $A$-elements).

The initiality is the key property to construct inductive function (see catamorphism). Some excellent references on this topic:

Lectures on Semantics: The initial algebra and final coalgebra perspectives
A Tutorial on (Co)Algebras and (Co)Induction


can a machine generate truly random numbers?

What is true randomness, and is it necessary? Algorithms cannot distinguish truly random bits from pseudorandom bits (by definition!), and so in practice we are only interested in generating strongly pseudorandom bits. As indicated above, true randomness ensures that even if we run the same algorithm twice, we get different results.
True randomness is required only in highly classified cryptographic applications, such as one-time pads, used for strategic communication. Although pseudorandom bits are still enough, now the bar is a lot higher, due to the importance of the data being encoded. Nevertheless, by crunching more pseudorandom and truly random (but biased and correlated) bits together, we can create highly secure one-time pads.
High-quality randomness is generated by combining physical noise and "bit crushers"; stated differently, by injecting "true" randomness into a pseudorandom number generator.
The idea is to start with a high-quality pseudorandom generator, and stick a "pipe" of low-quality true noise into it. The low-quality true noise is truly random, but not iid: it could be highly biased, there could be significant correlations, and so on. By combining it with a good "bit cruncher", the resulting stream of random bits combines the advantages of both sources: it is more unpredictable than the already highly unpredictable pseudorandom generator, and it does not suffer from the bias and correlations of the actual physical source of noise.
Is this "true randomness"? No. But computers won't be able to distinguish the difference. This is already true for high-quality pseudorandom generators, so what did we gain? Two things. First, we may think that the pseudorandom generator is strong, but perhaps it's weak; by injecting true randomness, we strengthen it. Second, even a high-quality stream of pseudorandom bits can be predicted if you know the initial seed. For this reason, when reproducibility is not required, pseudorandom generators are initialized with a seed produced from actual (although low-quality) physical randomness.
The pseudorandom generator used in Unix systems employs this methodology. It keeps an "entropy pool" — a source of true, low-quality randomness — and mixes it into a pseudorandom generator. In practice, it works quite well, although it's not completely bullet-proof. Using a dedicated physical random noise generator would result in a much enhanced stream of random bits which should be difficult to attack.


Books for the Mathematical Theory of AI/ML

My favorite is Understanding Machine Learning: From Theory to Algorithms. It’s presentation is very probability oriented and introduces concepts in a very concise, yet insightful way. It covers the foundations of a lot of Statistical Learning Theory and thanks to the rigorous introduction, I found it is easy to build on certain directions that interest me.


Understanding Correctness of Bidirectional Dijkstra

I came across these slides where on slide 23 another proof is given, however the idea of this proof is the same as in the slides of my original post.

But this still doesn't show, why $dist(s,v)$ and $dist(w,t)$ need to be less than $top_f$ and $top_b$ respectively.

EDIT: Note that with this proof $dist(s,v) \leq top_f$ and $dist(w,t) \leq top_b$ hold, since both vertices have already been settled. I'm in doubt, whether the original statement $dist(s,v) < top_f$ and $dist(w,t) < top_b$ is actually correct and therefore I'm marking this question as 'answered'. However if anyone finds an explanation, feel free to answer!


Should a pure function take all of the functions it calls as arguments?

No, f doesn't have to take g as an argument.  Wikipedia's definition is a bit informal.  Also informally, the behavior of a pure function is also allowed to depend on the code of the program.  Or, to put it another way, the code of the program is considered fixed, not something we vary, so we don't try to track dependences on it.

So, something like f(x) = 2*g(x) is fine: if g is pure, f will be too.


Why does the Huffman coding algorithm produce a valid tree?

Let $v$ be a vertex of the tree. If $\pi_v$ is the path from the root of the tree to $v$, then the string $s(v)$ constructed from the labels of $\pi_v$ is unique (if you really want, you can prove this by induction on the depth of $v$).
If $s'$ is a proper prefix of $s(v)$  then there is a node $u$ in $\pi_v$ such that $s(u)=s'$ and, by the above observation, this node is unique.  Moreover, $u$ cannot be a leaf (since it precedes $v$ in $\pi_v$).
This means that, for each leaf $v$ there is no prefix of $s(v)$ that matches the code $s(v')$ of another leaf $v'$. Since the symbols only appear as leaves of the tree, this means that the code is not ambiguous.


Indices must not appear in relational algebra. That is because relational algebra is just a formal language which describes what you must do, but not how you must do it.

It is comparable to the multiplication and other operations of the elementary arithmetic.
There is a definition of what multiplying is but not of the way how you have to do it. There are several algorithms to multiply two numbers but the results are all equal. For further information see Wikipedia (What does it mean to multiply two natural numbers?).

Relating to your question that means that the result of an operation is the same with or without indices. The only difference is the increasing performance if you use indices.


How do you prove that $A = \{ x \in \mathbb{N} | W_{x} = [0..x]\}$ is a productive set through functional reduction?

You likely need to exploit the second recursion theorem, which states that for any total recursive function $f$ there is some $n$ such that $\varphi_n = \varphi_{f(n)}$.

Given any $k$, using s-m-n you can first construct $f_k$ as follows, where $\#(\ldots)$ stands for "some index of".
$$
f_k(x) = \#\left(y \mapsto
   \begin{cases}
   0 & \mbox{if } y \leq x \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
\right)
$$

This is recursive total, since it always returns an index (the fact that the index is for a partial function is irrelevant). So, by the second recursion theorem, there must exist $n_k$ for which $\varphi_{n_k} = \varphi_{f(n_k)}$.

By examining the proof of the second recursion theorem, we can also note that $n_k$ is effectively computable from $k$, that is there is a total recursive function $g$ such that $\varphi_{g(k)} = \varphi_{f(g(k))}$.

Let's verify that $g$ m-reduces $\bar K$ to your set $A$.

Assume $k \in \bar K$, and let's prove $g(k) \in A$. The latter means $W_{g(k)} = [0..g(k)]$, which is true because
$$
\varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) =
\begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
= \begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \uparrow & \mbox{otherwise}
   \end{cases}
$$

Now, assume $k \notin \bar K$, and let's prove $g(k) \notin A$. The latter means $W_{g(k)} \neq [0..g(k)]$, which is true because

$$
\varphi_{g(k)}(y) = \varphi_{f(g(k))}(y) =
\begin{cases}
   0 & \mbox{if } y \leq g(k) \\
   \varphi_k(k) & \mbox{otherwise}
   \end{cases}
$$
Since $\varphi_k(k)\downarrow$, we have that $W_{g(k)} = \mathbb N \neq [0..g(k)]$

As a thumb rule, when you are defining a recursive function $f=\varphi_i$ and you need to use its own index $i$ in the definition of the function itself, you need the second recursion theorem.

From a more practical point of view, the second recursion theorem allows one to program in a programming language featuring a function getMyOwnCode() : String which returns the whole source code (the index) of the program calling the function.


Find longest common substring using a rolling hash

In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t$, look it up on the table. This takes expected linear time for a large enough hash table.


Context Free Grammar for {a^ib^j | i,j ≥ 0; i ≠ 2j}

Consider the two languages:
$L_1 = \{a^ib^j \mid i, j \ge 0 \text{ and } i > 2j\}$
$L_2 = \{a^ib^j \mid i, j \ge 0 \text{ and } i < 2j\}$

Convince yourself that $L = L_1 \cup L_2$.

In $L_1$, the number of $a$'s are more than double of $b$'s, so there has to be atleast one $a$ (when there are no $b$'s). Also, for every addition of $b$, atleast 2 $a$'s must be added. You can generate $L_1$ as:

$
S_1 \rightarrow aA \\
A \rightarrow aaAb \mid aA \mid \varepsilon
$

$L_2$ is a little more tricky. The number of $a$'s are less than double the number of $b$'s, so there can be $0$ $a$'s, but non-zero $b$'s. Consider the "base case" of $1$ $b$. The string can be either $b$ or $ab$. We will let the first rule generate this base case. After that, notice that for every addition of $b$, we can increase the number of $a$'s by at most $2$. So we can add $0$, $1$, or $2$ $a$'s for every addition of $b$. We'll let the second rule handle this. So, the CFG for $L_2$ becomes:

$
S_2 \rightarrow Bb \mid aBb \\
B \rightarrow Bb \mid aBb \mid aaBb \mid \varepsilon
$

Note that CFG's are closed under union, that is, the union of two CFG's is also a CFG. So, to get the CFG for $L$, let the starting state $S$ of $L$ lead to either the starting state of $L_1$, or of $L_2$:

$S \rightarrow S_1 \mid S_2$

The rest of the rules remain the same as in the two languages. There may be a simpler grammar, but this was the first that came to mind.


Need to remove indirect left recursion from CFG

You should focus on trying to only modify productions that aren't "good". A production is "good" if it :

Starts with a terminal,
Is an epsilon production, or
Is in the form A->B (followed by a series of terminals and non-terminals) and we can partially order the non-terminals so that A<B. We'd also have to do some extra checks if B being nullable. That is, if B is nullable, we'd have to consider all productions in which B occurs and is nulled. For example, suppose we have the grammar:

A -> BAa
B -> b | esp

At first glance, the rule A->BAa might appear good (because we can assert that A<B), but if B is nulled, we end up with the production A->Aa which is bad. This is usually not a big problem, but you've got to make sure you cover all your cases. Note that this doesn't apply to your example, but I'd figure I'd be thorough.

For your grammar:

A->Ba is good since we can assert that A<B.
b is good because this is a terminal.
For similar reasons, all the productions of B and C are also "good", so we shouldn't change them.
For D, there are several problems. Obviously, we cannot assert that D<D, and we also can't assert that D<A or D<C (since we assumed that A<B<C<D in our previous step). However, the productions for A, B, and C are all "good", so we can substitute those in and expose the hidden left recursion (as you've done in your work).

In short, you should only worry about modifying "bad" productions and leaving any "good" ones as they are. It's not always possible to do this, but in general, it'll save you work.


PDA recognising all strings with a $1$ in the second half

The problem with your approach is that you are not checking that $|u| \geq |v|$ - for example the string $0100$ would be accepted. Remember that the 'magic' of non-determinism is that if there is a way to reach an accept state, it will find it, it makes no guarantee that it accepts only the things you want it to.

So in this case, you still need to check that the size of the two parts are suitable, for which we need1 a stack.

As a side note, $B$ can also be expressed as $\{u1v\mid u \in \Sigma^{\ast}, v \in \{0\}^{\ast}, |u| \geq |v|\}$, not that this really changes much, but it's a little simpler (in terms of the PDA).

Footnotes:

As Babou points out in his answer, you don't need a stack as such, a simple counter suffices, but you do need something beyond what a DFA/NFA can manage.


Non-deterministic algorithm to check if a list has some given value

If the only way you have to access the last element is to step through the whole list, one item at a time, you can't possibly use less than $O(n)$ time, even nondeterministically. If you used less than that, none of the paths through the computation would be able to access the end of the list, so none of them would be able to check whether it contained the desired entry.


Irregularity of L = {a^i b^(j+3)| i!=j }

When you get stuck trying to prove a language is not regular by the Pumping Lemma, as in this example, because there doesn't seem to be a good choice of $u,v,w$, it's sometimes helpful to use closure properties first, to transform the problem. This is a good example of when this paradigm is useful.

We'll do this by contradiction. Suppose that $L$ were regular. Then since regular languages are closed under complement, $\overline{L}$ would be regular. Now $\overline{L}$ isn't particularly easy to describe, since it contains strings like $bababbba$, but what is $\overline{L}\cap a^*b^*$? This is just $a^nb^{n+3}=a^nb^nb^3$. Since regular languages are closed under intersection and $a^*b^*$ is regular, that would mean that $a^nb^nb^3$ would be regular. I'll bet you can now do a pumping lemma proof to show that this language wasn't regular.


What are the difference between and consequences of using type parameters and type indexes?

ListP t and ListI t are isomorphic: they have exactly the same constructors.

<prompt>Coq < 12 || 0 < </prompt>Check (NilP, NilI).
(NilP, NilI)
     : (forall t : Type, ListP t) *
       (forall t : Type, ListI t)

<prompt>Coq < 13 || 0 < </prompt>Check (ConsP, ConsI).
(ConsP, ConsI)
     : (forall t : Type, t -> ListP t -> ListP t) *
       (forall t : Type, t -> ListI t -> ListI t)

However Coq generates different induction principles.

<prompt>Coq < 14 || 0 < </prompt>Check (ListP_ind, ListI_ind).
(ListP_ind, ListI_ind)
     : (forall (t : Type) (P : ListP t -> Prop),
        P (NilP t) ->
        (forall (t0 : t) (l : ListP t), P l -> P (ConsP t t0 l)) ->
        forall l : ListP t, P l) *
       (forall P : forall T : Type, ListI T -> Prop,
        (forall t : Type, P t (NilI t)) ->
        (forall (t : Type) (t0 : t) (l : ListI t),
         P t l -> P t (ConsI t t0 l)) ->
        forall (T : Type) (l : ListI T), P T l)

The induction principle of ListI requires the property to be parameteric in the element type (P : forall T, ListI T -> Prop) whereas the induction principle of ListP can be instantiated at any type t (P : ListP t -> Prop). This is a weakness of Coq's front-end, in that it is not smart about non-uniform recursive types; you can manually define the same induction principle (the typechecker accepts it, which is unsurprising given that it is ListP_ind transformed by the obvious isomorphism between ListP and ListI).

The parametric form ListP is simpler and easier to use out of the box. The ListI form can generalize to non-uniform recursion, where the parameters in the recursive calls are not the original. See Polymorphism and Inductive datatypes for an example.


These kinds of problems are usually studied under the banner of Operations Research or Operational Research, and this is still an active area after several decades.
See the Graham et al. survey from 1979 (doi:10.1016/S0167-5060(08)70356-X) for the standard terminology and many older references.
It looks like your problem is $P|\text{prec},p_{ij}=1|\sum_j C_{ij}$ which seems too general to have been studied back then.

You don't describe the kinds of task graphs you work with, but in my experience many practical task graphs from computer science lead to an explosion of chains of tasks to consider, making it hard to do dynamic programming, while task graphs from other fields often are more amenable to dynamic programming.
When the structure of the task graph is "nice", then one can do better.
For instance, series-parallel task graphs often lead to polynomial-time algorithms.

Without knowing more about the details of your problem, I'd say it sounds NP-hard on general task graphs due to the costs, but it may well be possible to exploit special features of the task graphs (or perhaps the costs) to design an efficient algorithm.


Show that functions in O(1) can't grow faster than their composition with themselves

To complete the first approach and show that $\sqrt{n}\notin O(1)$, you just need to show that the statement "There exist constants $c$ and $n_0$ such that, for all $n\geq n_0$, $\sqrt{n}\leq c\cdot1$" is false. That is, you need to show that, for any $c$ and $n_0$, there is an $n\geq n_0$ such that $\sqrt{n}>c$.  For example, you can take $n=n_0+c^2$ (or $\max\,\{n_0,c^2\}$, if you prefer).

I don't really understand your second approach. If $f(n)=O(1)$, it's perfectly possible that $f(n)\in \omega(f(f(n)))$: take any constant function, for example.


Iterative and/or tail-recursive implementations of merge sort?

An iterative implementation is easy: you just introduce an explicit stack (instead of using the call stack as the implicit stack).  You can always convert any recursive algorithm to be in iterative form by using an explicit stack; each recursive call is translated into pushing something onto the stack.

However, I don't know of any reason why you'd want to do that, in this case; the resulting algorithm just becomes harder to understand.  The amount of stack space used by merge-sort is $O(\lg n)$, where $n$ is the length of the list, so you're not going to exhaust the size of the available stack.

Merge-sort is not purely tail-recursive.  First of all, the result of a call to merge-sort is not the result of either recursive call; the results of the two recursive calls must be further processed (by merging the sorted sublists).  Second of all, merge-sort contains two recursive calls, so even if there were some way to convert the last call to a tail-call (there isn't), you'd still be left with one other recursive call inside the body of the function.  So, no, merge-sort is not tail-recursive.  And there's little or no benefit to try to rewrite it in a form that is tail-recursive.

(Technically speaking, just as any algorithm can be transformed to be iterative,
anything can be transformed to be tail-recursive form by using continuation-passing style.  This includes merge-sort.  Nonetheless, in this case there is no reason why anyone would want to do that.  It's unlikely to make the code noticeably faster, and it's sure to make the code harder to understand.  Therefore, this is a technicality that can be safely ignored.  If you don't know what continuation-passing style is, don't worry about it, you can just pretend that merge-sort cannot be made tail-recursive, and that'll be close enough.)


Why can't we exploite finiteness to prove incompleteness in NP?

Here is a good reason why finiteness does not help: Let $P_{inf}$ and $NP_{inf}$ be the sets of infinite languages in $P$ and $NP$. Then we may focus on proving $P_{inf}\not=NP_{inf}$, rather than $P\not=NP$. But $P_{inf}=NP_{inf}$ if and only if $P=NP$!

The question as I understand it is, why can't we exploit the fact that these languages are finite in a proof of $P\not=NP$, like we did when we proved $R\not=RE$? But the premise is wrong: the proof that $R\not=RE$, that the Halting Problem is undecidable, does not reference the fact that there are finite languages in $R$. Of course it makes intuitive sense that, since $R$ contains finite languages, it cannot contain $RE$, but in fact $R\not=RE$ follows from the fact that Turing Machines cannot be analysed by other Turing Machines, and, in my view, the fact about finite languages is a quirk which follows from the definitions, as we may as well have considered $R_{inf}\not=RE_{inf}$.

If $R\not=RE$ comes from the fact that undecidability cannot be eliminated, then $P\not=NP$, if true, comes from the fact that nondeterminism cannot be efficiently eliminated.

I should clear up some technicalities. If a language contains a finite amount of strings, it can be decided in constant time, $O(1)$, so it is definitely in P, as you note. If P=NP, then every language in P is also NP-Complete (the reduction is simple: given a string, solve it in polynomial time, and then print a fixed yes/no instance of the other problem). So not only is there some finite NP-Complete language, all nontrivial* finite languages are NP-Complete if P=NP. On the other hand, if $P\not=NP$, then no finite language is NP-Complete. Your intuition about RE-Complete languages containing infinite strings is wrong: those languages contain an infinite number of finite strings.

*A nontrivial language is one with both yes- and no-instances. The two trivial languages are the empty language $\emptyset$ and the full language $\Sigma^{*}$, which have no yes- and no no-instances, respectively, which is why no other language can many-one reduce to them.


What is the name the class of functions described by O(n log n)?

It's called linearithmic time, and is a special case of a more general class known as quasi linear.  As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k > 1$.


Let's suppose that you want to do comparison-based sorting of $n$ distinct elements.

You can interpret the problem in terms of information theory. You want to discover which permutation the sequence is currently in. That is, you need to discover a number between $1$ and $n!$.

The comparison operator gives you one bit of information. But to discover a number between $1$ and $n!$, you need at least $\log_2 n!$ bits of information. Therefore, you need at least $\log_2 n!$ comparisons.

By Stirling's approximation:

$$\log_2 n! = n \log_2 n - \frac{n}{\ln 2} + O(\log n)$$

This is the number of comparisons you need. You cannot do better than this. For any comparison-based sort which takes $k n \log_2 n + o(n \log n)$ comparisons, $k \ge 1$. In particular, there is no comparison-based sort which uses $\frac{1}{2} n \log_2 n$ comparisons.

So no, you can't reduce constants arbitrarily.

We usually don't do this kind of analysis for time complexity, because in practice, "time" depends on many factors like the compiler settings, the CPU architecture, the laws of physics, and so on. However, it becomes very important when analysing space complexity; we do measure time in physical units ("this program will take three hours to run"), but we don't typically measure space the same way ("I need a cubic metre of disk").


NP and verifiability equivalence - does this guarantee that any certificate can be verified in polynomial time?

A non-deterministic Turing machine has a special instruction that allows it to non-deterministically "guess" a bit. The list of bits guessed by the machine is sometimes called a certificate. You can imagine that the guessed bits are taken from an auxiliary tape, whose contents you can think of as a certificate.

Here is an example. Consider the problem SAT: the input is a formula, and wish to find out whether the formula is satisfiable. A non-deterministic Turing machine for this problem "guesses" an assignment, and then checks ("verifies") that it satisfies the given formula. Alternatively, the machine gets a certificate and verifies that it is a satisfying assignment for the input formula. This is exactly the same Turing machine, only the process of non-deterministic guessing is visualized as reading from an auxiliary input, which we think of as a certificate.


How to prove a bound function for a sequence of numbers?

If you have tried, you will find that
$$\begin{aligned}
G_5&=6\\
G_6&=7\\
G_7&=8\\
G_8&=9\\
G_9&=10.\\
\end{aligned}$$

By now, you should have probably guessed that $G_{n}=n+1$. Now you can try proving it, using induction on $n$.

Once that formula has been proved, $f(n)=n$ is of course a lower bound for $G_n$.


Why shift means push terminal symbol and state into the stack? Why not push only state?

You are talking about the typical description of LR parsing. And you are completely right, the "state" (if you look closely, it is the state of the DFA that recognizes left hand sides of productions when processing the current stack's contents) encodes all information needed. Adding the symbol is redundant. As far as I can tell, it is usually added to clarify what is going on (just a list of state numbers would be completely opaque).


Why is binary search called binary search?

I tried to look up the Mauchly reference cited by Knuth but my library seems to have misplaced their copy.

In the meantime, consider the following early-ish citations for "binary search":

Halpern, Mark. "Variable-width tables with binary-search facility." Communications of the ACM 1.2 (1958): 1-4.

  The family of subroutines described in this report was designed to create, search and maintain tables which are to contain entries of different lengths, and yet be amenable to search by partition, or “binary” search.

Nagler, H. "An estimation of the relative efficiency of two internal sorting methods." Communications of the ACM 3.11 (1960): 618-620.

  This report concerns the IBM 705, models I and II. It is a study of the machine time required by two internal sorting methods, the conventional two-way merge, and a form of the binary search, which is due to D. Mordy, of the IBM Corporation.

Petersen, T. L. RE-ENTRY VEHICLE SYNTHESIS PROGRAM. No. STL/TR-60-0000-09103 (pdf link). TRW SPACE TECHNOLOGY LABS LOS ANGELES CA, 1960.

  The value of ${V_0}^*$ for which $g({V_0}^*) = 0$ must now be found. It is easily seen that $g(0) = K_3 - 1$ and $g(K_1) = -1$, so that the required value of  ${V_0}^*$ lies between 0 and $K_1$ if $K_3>1$. A binary search is conducted for the root of $g({V_0}^*)$; the ${V_0}^*$ selected is that for which the absolute value of the difference between consecutive values of ${V_0}^*$ is less than $0.01$.

I'll note how the first 1958 citation uses quotation marks around "binary" but by the third citation in 1960, a binary search is mentioned without any further description or explanation. The allusion to "search by partition" would tend to suggest that explanation 2) is closer, but further verification is required.


Why do more powerful programming languages tend to have slower implementations?

This is simply not true. And part of why it's false is that the premise isn't well formed.
There is no such thing as a fast or slow language. The expressive power of a language is purely a function of its semantics. It is independent of any particular implementation.
You can talk about the performance of code generated by GCC, or about the performance of the CPython interpreter. But these are specific implementations of the language. You could write a very slow C compiler, and you can write Python interpreters that are quite fast (like PyPy).
So the answer to the question of "is more power necessarily slower" is no, purely because you or I can go write a slow C compiler, that has the same expressive power as GCC, but that is slower than Python.
The real question is "why do more powerful languages tend to have slower implementations." The reason is that, if you're considering the C vs Python, the difference in power is abstraction. When you do something in Python, there is a lot more that is implicit that is happening behind the scenes. More stuff to do means more time.
But there's also lots of social elements at play. People who need high performance choose low level languages, so they have fine grained control of what the machine is doing. This has led to the idea that low level languages are faster. But for most people, writing in C vs Python will have pretty comparable performance, because most applications don't require that you eke out every last millisecond. This is particularly true when you consider the extra checks that are manually added to program defensively in C. So just because lots of specialists have built fast things in C and C++ doesn't mean they're faster for everything.
Finally, some languages have zero cost abstraction. Rust does this, using a type system to ensure memory safety without needing runtime garbage collection. And Go has garbage collection, but it's so fast that you get performance on par with C while still getting extra power.
The TLDR is that more powerful languages are sometimes faster in some cases, but this is not a firm rule, and there are exceptions and complications.


Irregularity of $\{a^iba^j : i \neq j\}$ using pumping lemma

Here is the contrapositive form of the pumping lemma, which is what we use to prove that a language is not regular:

  Let $L$ be a language. Suppose that for all $p \geq 1$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

Using the pumping lemma directly for the language $L$ in the question is a bit tricky. Given $p \geq 1$, let $w = a^p b a^{p+p!} \in L$; note that $|w| \geq p$. We have to show that for every decomposition $w = xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Consider any such decomposition. It is easy to check that $y = a^\ell$ for some $1 \leq \ell \leq p$, and that $xy^ij = a^{p+(i-1)\ell}ba^{p+p!}$. For $i = p!/\ell+1$ (which is an integer!), $xy^ij = a^{p+p!}ba^{p+p!} \notin L$. Thus the condition in the pumping lemma is satisfied, and we conclude that $L$ is not regular.


Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own

I think this can be solved the same way that knapsack problem is solved using dynamic programming.
I present the problem for the case where type 1 items are to be selected in pairs, but the other case is solvable in a similar way.
Suppose the weights are $\{w_1, …, w_n\}$, the profits are $\{p_1, …, p_n\}$ and the types are $\{t_1, …, t_n\}$. Let's define, for $w\in [\![0, W]\!], i \in [\![1, n]\!], j\in\{0,1\}$, $K(w, i, j)$ representing the maximum profit using a knapsack of capacity $w$, using items $1, …, i$, with a parity of type 1 items equal to $j$.
We want to determine $K(W, n, 0)$. Using this definition, we can calculate $K(w, i, j)$ by distinguishing if we take or not the $i$-th item:
$K(w, i, j) = \max(K(w-w_i, i - 1, j \oplus t_i) + p_i, K(w, i - 1, j))$ (where $\oplus$ is the addition modulo 2)
With this formula, we can then compute $K(W, n, 0)$ in time complexity $O(nW)$.
In the case you just need to pick at least two items of type 1 if you want any, $K(w, i, j)$ could represent the maximum profit with $j\in \{0, 1,2\}$ representing respectively exactly zero type 1 item, exactly one type 1 item or at least 2 type 1 items.


Notation for a Kleene fixed point with a starting element

Suppose $Q$ is a join semilattice.  Define $g:Q \to Q$ by

$$g(x) = f(x) \sqcup q.$$

Then $\text{fix} \; g$ is equal to the least fixpoint of $q,f(q),f^2(q),\dots$.  So, at least for cpo's that form a join semilattice, you can indicate it pretty naturally using existing notation -- there's not a strong need to invent a new notation (though you could of course introduce one if you wanted).

If $Q$ is not a join semilattice, I think you can still define

$$g(x) = \sup \{ f(x), q \}$$

and then do the same thing.  The least fixpoint of $q,f(q),f^2(q),\dots$ will be $\text{fix} \; g$.


Solving subgraph isomorphism in polynomial time

Here is a more general theorem:

  Let $X$ be some NP-complete problem. Then $X$ can be solved in polynomial time iff all problems in NP can be solved in polynomial time.

Indeed, if all problems in NP can be solved in polynomial time, then since $X$ is in NP, then $X$ can be solved in polynomial time.

In the other direction, suppose that $X$ can be solved in polynomial time. Let $Y$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction $f$ from $Y$ to $X$. Using this reduction, we can reduce $Y$ to $X$, and so solve $Y$ in polynomial time. (I'm only sketching this part, since this is a standard argument which I assume you were shown in class.)


Having a problem understanding the execution of I/O in Von Neumann model

You are not wrong in stating that you went too deep in your search.

To counter these confusions, you might want to study how instructions are executed electronically in a computer.

The one thing worth remembering is: In a computer everything is controlled by the CPU. That includes the IO devices, their interfaces, the instructions put forth by them and the ones relegated to them.

Typically, what happens is that a program or a facility in your machine generates interrupts. Generally, the interrupt itself is an instruction to the CPU coming from the memory, loaded in the memory by the CPU itself at a prior time. When the CPU executes the interrupt, it checks the status of I/O device (like a key press), registers it and manipulates it as per instructions that follow. When modern computers turn on, BIOS - Basic Input Output System, that is - is used for generating interrupts and is used as an interface/liaison between the CPU and I/O devices. BIOS itself is a program (set of instructions) that resides on ROM and is read by the CPU at time zero. After the boot up is complete and OS is loaded to the memory, this facility is provided by the Operating System.

  How does a program communicate with an I/O device?

That depends upon the level of abstraction you are working on. If you want to see the program as a single and lone set of instructions to the CPU then the I/O interrupts are a part of the program. They are executed and tell the processor which device is to be contacted and in what manner. A little knowledge of assembly would be helpful for clarification in this context. But a small example of instructions to CPU is as follows:

1. Load integer 8 in Register 1.  //Instruction 'Load', Data '8'
2. Check keyboard for key press.  //An interrupt to Keyboard
3. Store key press value in Register 2.
4. Add contents of Register 1 and Register 2 in Register 3.
5. Pass contents of Register 3 to Display. //An output interrupt.

In the case of an operating system like Windows, the interrupts are a part of operating system program and are used to call the CPU's attention not only to I/O devices, but also to other programs in the memory. The IO interrupts here are in driver domain present in the memory as an interface. The user applications or the other programs in memory make calls to the operating system to make these interrupts, they can not directly make interrupts. Following is an example of a simple program in MSIL assembly.

.maxstack 2
.entrypoint   //begins here.
ldc.i4 8      //load integer 8 to stack.
ldc.i4 9      //load integer 9 to stack too.
add           //Add last two integers.
call void [mscorlib]System.Console.WriteLine(int32)  //A call to windows to
              //display the answer in console. Windows does the rest.

  How will you explain the data transfer between memory and I/O devices?

An instruction by a program to check the status of IO device. An instruction to get the data from the device and store it into a register. An instruction to store the value of that register into a memory location at a certain address in RAM. That location can be read by the program when required.


Is "promoting a key" a part of deleting internal node key in B+ Tree?

I'd not attach too much importance to such kind of boundary cases: both solutions here are valid according to the definition of B+-Tree and depending on the order of operations, it is very common that B-Trees have different shapes for the same data.  Here the difference between the two results is just the one between $<$ and $\leq$ in some condition and the choice is not imposed by an invariant of the data structure.

It seems to have a drastically different result because the tree is so close to be as sparse as possible and so close to be collapsible -- at most two more deletions will trigger that.  The reason is not that trees close to the boundary are typical, it is because making readable pictures is easier in that case, in practice the number of buckets per node is greater than 4 and fewer nodes are just half-full. Being able to steal one element from the neighbor is more typical than having to merge with it.

Obviously if you know something about the patterns of insertion and deletions, you may prefer one version over other, but it will be a second order effect.


Viterbi algorithm recursive justification

The maximum is over the entire expression $\pi(k-1,w,u) \cdot q(v|w,u) \cdot e(x_k|v)$, for exactly the same reason that is worrying you. Moreover, under your original interpretation, there is no reason to keep $\pi(k-1,w,u)$ for the non-optimal $w$. We are forced to store $\pi(k-1,w,u)$ for all $w$ exactly for the reason you mention.


Can nodes in red-black trees have one nil child and one non-nil child?

Yes. A red-black tree is a special case of binary search tree: each node is colored red or black. In red-black tree, if a child does not exist, the corresponding pointer field of that node contains the value NIL. NILs are treated as leaves.

  red-black trees have a worst-case height of $2 \log 2(n+1)$

The fact that the height is of $O(\lg n)$ is guaranteed by the red/black coloring rules (copied from CLRS):

A node is either red or black.
The root is black.
All leaves (NIL) are black.
If a node is red, then both its children are black.
For each node, all paths from the node to descendant leaves contain the same number of black nodes.

These rules, especially rules 4 and 5, ensure that the tree is approximately balanced: no any path is more than twice as long as any other. In terms of tree height, we have

  A red-black tree with $n$ internal nodes has height at most $2 \lg (n+1)$.

Finally,

  how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of $n$.

By the red/black coloring rules, a non-trivial (with enough number of nodes) red-black tree cannot be a straight line/linked list.

For more details, you may want to read the book "Introduction to Algorithms" by CLRS.


Reduce variant of Vertex Cover to original decision-version Vertex cover problem

Your reduction works. A more efficient version would be to use binary search to find the optimal value through a series of queries "Is there a vertex covers of size $k$?"

However, note that this is a polynomial-time Turing reduction (also known as a Cook reduction): you're solving the vertex cover optimization problem by making multiple queries to an oracle for the decision version. On the other hand, NP-completeness is defined in terms of polynomial-time many-one reductions (a.k.a. Karp reductions): here, you're only allowed to make one to the decision version.  I'm not aware of a many-one reduction between these two problems.

Cook reductions have the advantage that they correspond more closely to the idea of "If I have an efficient algorithm for problem A and a reduction from B to A, I have an efficient algorithm for B, too. On the other hand, Karp reductions allow for finer-grained distinctions in complexity theory. For example, there are Cook reductions between NP-complete problems and coNP-complete problems but a Karp reduction between an NP-complete problem and a coNP-complete problem would prove that NP=coNP.


Decidability of a language of Turing Machine descriptions

Given a Turing Machine M (with its finite number of tape symbols,
finite number of states, etc...), how hard is it to prove that there
is an input on which it will run for more than 10 steps? How much of
the input will be read in 10 steps at most? How many different
computations have to be checked to see whether one takes more than 10
steps?

added later: I was editing this when the reference to question Is the set of Turing machines which stop in at most 50 steps on all inputs, decideable? was given as comment.


what is CFG of $\{a^i b^j c^k \mid k = |i-j| \}$

Use the fact that CF are closed under union, and start by considering cases, whether $i\ge j$ or $j\ge i$.

In the first case we get the language $L_1 = \{ a^i b^j c^k \mid k+j=i\}$, which is the same as $L_1 = \{ a^{k+j} b^j c^k \mid k,j \ge 0\}$.

Make a grammar for $L_1$, and then consider the second case.


How do Functional Reactive Programming and the Actor model relate to each other?

Neither actors nor FRP are about streaming. Actors don't even support external configuration of an output stream.

FRP is strongly characterized by its modeling signals and events on a linear timeline, which enables FRP behaviors to compose in a deterministic manner. Actors are strongly characterized by processing messages in non-deterministic order, and have scarcely any compositional properties (i.e. you can't treat an arrangement of two actors as a larger actor).

If you're seeking similarities, both actors and FRP have a close relationship to lambda calculus. Both can model systems responsive to human input. Both support modeling of internal (local) state.

FRP supports local state through integrals or accumulators (fold over time), while actors model supports state by allowing each actor to specify its behavior for the next message in response to the current one. This pervasive support for local state makes both FRP and Actors inadequate for live programming (or runtime upgrade of program code); it becomes too easy to lose important state.

Regarding application domains:

Actors model is well suited for open systems, where we might wish to install or maintain actors at runtime. Actors model is also weakly suited to distributed systems, as the non-deterministic ordering of messages can make a conforming implementation easier. (The reason actors are not more strongly suited to distributed systems is that ensuring a message arrives 'once and only once' is quite difficult in the face of disruption, and actors also tend to require distributed GC, which is a pain.)

FRP is well suited to closed systems that operate over time - e.g. robotic controllers, music programming, computational toys. The determinism and compositional features make FRP more convenient to work with than actors, at least in those cases where FRP can directly model a solution. Integrating FRP with effects (elegantly, without hacking the model with impurity) has proven difficult. There has been recent work on effectful FRP via 'wormholes' - effectively, unique or linear typed access to resources.

There are other models that lie somewhere between FRP and Actors.

Flow Based Programming (FBP), developed by John Paul Morrison, really does support streaming of messages.

Time Warp protocols (or the more recent work on Lightweight Time Warp (LTW)) places actors-like messages on a logical timeline to provide a more controlled and compositional notion of message passing. Time warp is often used for large parallel and distributed systems, e.g. scientific computing. The original time warp was unsuited for interactive simulatons (responsiveness to human input), and LTW is only marginally suited.

I am developing Reactive Demand Programming (RDP) which enables responsive, compositional, FRP-like manipulation and processing of signals in open and distributed systems, and eliminates local state. RDP is achieved by constraining side-effects to commutative, idempotent influence on resource state by signals over time. RDP requires rethinking of resource and state models.


Does the time complexity of a problem change with encoding of the problem?

Yes, the complexity depends on the encoding. The only thing you can be sure of is that if translating from encoding $L$ to encoding $L'$ or vice versa has the complexity $f$, and $D$ can be solved with complexity $g$, then $D'$ (same problem expressed with the encoding $L'$) can be solved with complexity $O(f+g)$ by going back and forth between encodings.

It isn't just a matter of length of the encoding. To give a simple example, let $L$ be positive integers represented in binary, and $L'$ be positive integers represented by their prime factorization. There is a polynomial bound in the size of one representation in terms of the other. Yet for a long time, it was not known whether primality testing can be solved in polynomial time in the binary representation; but in the factorization representation, it's trivially polynomial (probably $O(1)$ depending on the representation details).

Or consider the decision problem “is integer $n$ a member of set $S$”. If the set is represented by an unordered list of integers, this problem evidently requires at least linear time. But if the set is represented by a balanced search tree, lookup time is polylogarithmic in the size of the set.

In most concrete cases, there is an evident representation that everyone assumes, or more precisely there is a class of representations that are all equivalent up to a transformation that takes negligible time. But sometimes the representation is relevant, most frequently when analyzing data structures with more precision than polynomial time.


$T(n)=2T(n/2)+n\log n$ and the Master theorem

$\log n$ grows slower than $n^\epsilon$ for any $\epsilon>0$. Thus $n\log n$ grows slower than $n^c$ for any $c>1$. However, the third case of the Master theorem requires the existance of a $c>1$ so that $n\log n$ grows at least as fast as $n^c$ (up to a constant factor).

The function is covered by the second case of the Master theorem as given in Wikipedia.


By what criteria is the base value selected in Rabin Karp algorithm?

You can use any value you want, but it is best to choose a value that is relatively prime to the modulus, as that reduces the number of hash collisions.

For efficiency you might want to choose a value that is small (like 3), as that may make some computations faster.


Problems that feel exponential but are P

For me one of the most efficient algorithms is the Blossom V algorithm that find maximum weight perfect matching in a general graph:

https://en.m.wikipedia.org/wiki/Blossom_algorithm


Not as light as you think.

Thread pooling is orders of magnitudes lighter, so you can use pooled threads for gazillions of tiny tasks and still be efficient, while the same with freshly created threads would be inefficient.

In my environment, I can use five different threads in ten lines of code (without you even seeing that I'm using threads), which is possible because of highly efficient thread pooling).


Deciding whether the language of a CFG equals some specific regular language

It depends on your choice of $A$. For example, the problem $\{\langle G \rangle \mid L(G) = \Sigma^* \}$ is undecidable, while $\{\langle G \rangle \mid L(G) = \phi \}$ is decidable.

Also, the two languages that you have given (the one with $A$ and the other with $\overline{A}$) are equivalent since regular languages are closed under complementation.


What equivalence relation does this algorithm produce for an cyclic directed graph with labeled edges?

For graph isomorphism, there are many heuristics that work in well in practice on most graphs.  You could try adapting any of them to your setting.

Here's one example of a simple heuristic that might often work well in practice (but with no guarantees on worst-case performance).  Let $f_0:V \to \mathbb{N}$ be the original values of the graph, so $f_0(v)$ is the value on vertex $v$.  Now construct a new set of values $f_1:V \to \mathbb{N}$ from $f_0$, as follows.  For each vertex $v$, apply your two-step algorithm to get a description for $f$ using breadth-first search---but crucially, stop the breadth-first search after depth 1.  Take the resulting description, hash it with any hash function, and use the resulting hash as $f_1(v)$.  You can do this again, and construct $f_2$ from $f_1$ (note that we are now ignoring the original values on the nodes, and using the values from $f_1$, when computing $f_2$), and then construct $f_3$ from $f_2$, and so on. Do this for a few steps, say 100 steps.  Each iteration can be done in $O(n)$ time, so the total running time will be $O(n)$ to compute all of the values $f_{100}$.

Now we have a nice property: if $f_i(v_1) \ne f_i(v_2)$, then $v_1$ is not equivalent to $v_2$.  Thus, if $f_{100}(v)$ is a singleton ($v$ is the only vertex with that value; i.e., there does not exist $w$ such that $f_{100}(v)=f_{100}(w)$), then there is no need to compute a full description for your $v$.  We can apply your full algorithm to compute a full description for only the vertices $v$ whose value appears multiple times in $f_{100}$.  Heuristically, for most graphs, there probably won't be many of them.  Thus, you won't have to compute the full description for many vertices, and you might avoid quadratic running time.

There are degenerate graphs where this might fall apart, and where the running time becomes quadratic, but for "most" graphs, hopefully this won't happen.


generic way to convert imperative if-then-else statements into functional style?

As was mentioned in comments to the other question, any imperative program with side-effects can be trivially transformed into a pure program by simply lifting it into the IO monad, for example.

Or, by implementing an interpreter for an imperative language in a pure language.

That is, however, not good functional design. (Although, embedding a Domain Specific Language for side-effects into a program to provide limited and isolated side-effects in clearly demarcated sections of the code could certainly be considered good design.)

There is no general way of doing this translation. You need to understand what the original problem is that the program is solving, then solve that problem in a functional manner.


Algorithm for multiplying multivariate polynomials

There is a general method for efficient multiplication in any ring. This would cover the case where the degree is bounded in each dimension separately, because a polynomial $p\in R[x,y]$ in variables $x$, $y$ over the ring $R$ can be interpreted as a polynomial $p\in R[x][y]$ in the variable $y$ over the ring $R[x]$. This is essentially the case I thought about in my comment above. However, the total degree limitation from the question requires a different method. Such total degree limitations occur for determinants and permanents, but have little to do with convolution. It is not even covered in the general overview of multiplication algorithms. At least we may assume WLOG that the ring has has characteristic $p^m$ or 0, because it is easy and canonical to decompose a ring into simpler rings (and because factoring the characteristic is not part of the cost of multiplying two polynomials, even if it might be more expensive than the multiplication itself).

For $n\geq 2\delta$, the resulting polynomial $fg$ can have up to $2^{2\delta}$ monomial terms. For $R=\mathbb Z$, the coefficients of the monomial terms can all be different, so we can't do better than $O(2^{2\delta})$. The question had probably something like $O(N^2)$ versus $O(N \log N \log \log N)$ in mind. But if $N$ would measure the number of coefficients (of monomial terms) of the input polynomials $f$ and $g$, then $O(N^2)$ would be the optimal worst case bound. But what should $N$ measure instead?

Let's assume that $fg$ is determined uniquely by its values $fg(\underline{x}^1),\ldots,fg(\underline{x}^N)$ for suitable points $\underline{x}^1,\ldots,\underline{x}^N$. Then a possible way to compute $fg$ is to evaluate $f$ and $g$ at the points $\underline{x}^1,\ldots,\underline{x}^N$, multiply these values pointwise, and then determine $fg$ from these products. This is more or less also what happens when the FFT is used to compute a convolution.

The paper On Zeros of a Polynomial in a Finite Grid cited in the recent answer by Anurag Bishnoi gives sharp bounds on the number of zeros of a polynomial on a finite grid satisfying condition (D). A nonempty subset $S \subset R$ is said to satisfy Condition (D) if for all $x\neq y\in S$, the element $x−y\in R$ is not a zero divisor. For $n \in \mathbb Z^+$ we put $[n] = \{1,2,\ldots,n\}$. We have

  Theorem 1.2 (Generalized Alon-Füredi Theorem). Let $R$ be a ring, and let $A_1, \ldots, A_n$ be non-empty finite subsets of $R$ that satisfy Condition (D).
  For $i \in [n]$, let $b_i$ be an integer such that $1 \leq b_i \leq \#A_i$. Let $f \in R[\underline{t}] = R[t_1,\ldots,t_n]$ be a non-zero polynomial such that $\deg_{t_i} f \leq \# A_i − b_i$ for all $i \in [n]$. Let $\mathfrak U_A = \{x \in A : f(x)\neq 0\}$ where $A=A_1 \times\dots\times A_n \subseteq R^n$. Then we have (see §2.1 for the notation)
  $$\# \mathfrak U_A \geq \mathfrak m(\#A_1,\ldots,\#A_n;b_1,\ldots, b_n;\sum_{i=1}^n\#A_i −\deg f).$$
  Moreover, this bound is sharp in all cases.


Does domination rule apply for inadmissible heuristics?

First things first. In your question you put together two different concepts, namely admissibility and optimality of heuristic functions:

Optimality: A heuristic function $h(n)$ is optimal if and only if $h(n)=h^*(n)$ for every state $n$ of your state space, i.e., it returns the cost of an optimal path from $n$ to the goal.
Admissibility: A heuristic function $h(n)$ is said to be admissible if and only if $h(n)\leq h^*(n)$, i.e., it never overestimates the effort to reach the goal.

Clearly, optimality is a stronger property than admissibility. Also their impoortance comes from different factors:

Optimality: It can be proven (under a rather restricted model) that a specific class of search algorithms (such A$^*$, IDA$^*$, RBFS, DFBnB, etc.) only expand nodes along an optimal path when a perfect heuristic is used.
Admissibility: It can be proven (under a very general model) that a specific class of search algorithms (as those aforementioned) will return optimal solutions when using an admissible heuristic functions.

This said, dominance is an orthogonal property to these as it does refer neither to the accuracy of heuristic functions nor their ability to return optimal solutions. Your definition is correct:

Dominance: $h_1(n)$ is said to dominate $h_2(n)$ if and only if $h_1(n) \geq h_2(n)$ for all states $n$ in your state space. Note that this is a strong definition as it should be fulfilled for all states. In general it is said that $h_1(n)$ is more informed than $h_2(n)$.

And its importance is relative to the performance of the search algorithm when using one heuristic function or another:

Dominance: It can be proven (again under a rather restricted model) that a search algorithm (from the class of search algorithms mentioned above which are known as admissible search algorithms) expands less nodes when using a more informed heuristic function $h_1(n)$.

There is a lot to say here. First, that this property refers only to the must-expand nodes, that tie-breaking is assumed to be applied in the same way when using one heuristic or another, etc. There is no need to go in much deep detail to note however that this property makes a lot of sense when $h_1(n)$ and $h_2(n)$ are both admissible -optimality, as you say is disregarded here. If you put all conditions together you'll note that: $h_2(n) \leq h_1(n) \leq h^*(n)$ so that $h_1(n)$ provides better estimates for all nodes $n$ in the state space, i.e., the values returned by $h_1(n)$ are closer to the cost of the optimal path. This argument lies at the core of the proof of the effectiveness of $h_1(n)$ when being compared to $h_2(n)$.

Now, if neither $h_1(n)$ nor $h_2(n)$ are admisible, then:

Weak inadmissibility: $h_1(n)$ and $h_2(n)$ are inadmissible but they might return admissible estimates for some nodes. In this case, nothing can be said about the relative performance of these heuristics. It can be proven, however, that there is no guarantee about the optimality of the solutions returned by any of the search algorithms mentioned above.
Strong inadmissibility $h_1(n)$ and $h_2(n)$ always return inadmissible estimates, i.e., $h_1(n), h_2(n) \geq h^*(n)$ for all states $n$. If $h_1(n)\geq h_2(n)$ then $h_1(n) \geq h_2(n)\geq h^*(n)$ so that the opposite observation applies now and $h_2(n)$ returns estimates which are closer to the cost of the optimal solution. This does not imply that $h_2(n)$ will serve to expand less nodes but in general one should expect better solutions to be obtained with $h_2(n)$.

Concluding, domination is an orthogonal property to admissibility. They, when being put together serve to make observations about the optimality of the solutions returned and the expected number of necessary expansions to find them, but they can be used in different contexts as well.

As for extra material, I do highly recommend you a couple of books:

Judeal Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesly, 1984.
Stefan Edelkamp, Stefan Schr\"odl, Heuristic Search: Theory and Applications, Morgan Kaufmann, 2012.


How do I solve interdependent recurrence relations?

Eliminate one recurrence at a time, by plugging in.

For instance, you can use the equation $P(i)=5 M(i-1)$ to eliminate every instance of $P(\cdot)$ in each of the other recurrences.  Plugging in, we get

$$M(i) = R(i-1) + 10 M(i-2)$$
$$R(i) = R(i-1) + 15 M(i-2).$$

Now you have two inter-related recurrence relations, instead of three; you've eliminated one.

Do it one more time, say to remove each instance of $M(\cdot)$.  You get something like

$$R(i) = R(i-1) + 15 R(i-3) + 150 M(i-4).$$

Do it again, to remove the $M(\cdot)$:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + 1500 M(i-7).$$

Keep doing this, and you'll get a summation, say something like:

$$R(i) = R(i-1) + 15 R(i-3) + 150 R(i-5) + \cdots + 15 \times 10^{(i-3)/2} \times M(0)$$

(if $i$ is odd.)

Now you're down to a single recurrence relation.  Solve it.  Then, use the equations above to derive the solutions for $P(\cdot)$ and $M(\cdot)$.


Code to count number of leaves of a tree?

Using this recursive algorithm is indeed a correct way. But your code is wrong, and it could use some improvements.

First of all, you are using a pointer for head so you should use -> instead of . to access the left and right element.

Then, using a static variable is not the cleanest way to store the result. You could use the recursion and simply return the result, like so:

int Count_leaf(Tree* head)
{
    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}

Finally, you should check if the tree is empty before starting any counting. You can add a simple condition at the start of your fonction to do that:

if(head == NULL)
    return 0;

Here is the final program:

int Count_leaf(Tree* head)
{
    if(head == NULL)
        return 0;

    if(head->left == NULL && head->right == NULL)
        return 1;
    else
        return Count_leaf(head->left) + Count_leaf(head->right);
}


Is protein folding really NP-hard and how to show that?

It follows immediately from the fact that protein folding is NP-hard that there exists a reduction from 3SAT to protein folding.   The definition of NP-hard says that there is a reduction from every NP problem to protein folding; and 3SAT is a NP problem.
There are papers in the literature that state that protein folding is NP-hard.  I'm not an expert on them, so I don't know to what extent they do or don't address your specific concerns, but you should be able to find them immediately and review their proof.  See, e.g.,
P. Crescenzi et al. "On the complexity of protein folding." Journal of computational biology 5.3 (1998): 423-465.
B. Berger et al. "Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete." Proceedings of the second annual international conference on Computational molecular biology, pp. 30-39. 1998.
Our normal rules are to ask only one question per post.


How are these problem variants that ask about the size of optimal solutions in NP?

Any vertex cover of size $k$ is a witness that the smallest one has at most size $k$. Hence, the questions

  Is there a vertex cover of size at most $k$?

and

  Does a smallest vertex have size at most $k$?

are equivalent.


Data-structure for dynamic disjoint-sets

For Magic the Gathering, the number of cards is so small that the simplest data structure is probably the best.  Just have a list of all cards (each card records its name, location, properties, etc.).  Then to answer a query, scan through all cards and see which ones match the query.  Since you'll probably have very few cards in the data structure at a time (like, at most a few hundred), all operations should be very fast.

There are more sophisticated schemes, but they probably aren't worth the implementation effort.  You could think of this as a table in a relational database (one row per card, one column per attribute), and build an index for each column.  In other words, you have an ordered list of cards.  You also have a hashmap that maps from location to a list of all cards in that location.  These lists are stored as balanced search trees, with links between them (i.e., given a card in one tree, you can follow pointers to find where that card is stored in each of the other trees). This will let you do queries quickly.  Also to update the data structure, you can remove a card by finding it, then removing it from all of the linked trees; and you can insert a card similarly.  But in your case it won't be worth the effort.