Proof that type does not have decidable equality in Agda

ℕ→ℕ-undecidable is not provable in Agda. If we postulate the law of excluded middle (LEM), it follows that equality on every set is decidable, contradicting ℕ→ℕ-undecidable. Since Agda is consistent with LEM, it follows that ℕ→ℕ-undecidable is not provable in base Agda. This holds the same for cubical and vanilla Agda.


Matrix multiplication randomised verification - error probability

If that's the whole algorithm, only one iteration, then the only bound on the probability of error you can get is that it is smaller than $1-1/n^2$.

Hint 1) Notice that the algorithm only can fail when it enters in the first case you describe, why?

Hint 2) What is the worst possible case for A, B and C so you get the worse probability of error?


Why ⊢ for affirmative predicates and ⊨ for ¬negations?

The answer is really in the first paragraph of the quoted text, so what I'm about to attempt is really a rephrasing of that.

Remember that $\Gamma \vdash \psi$ means that there exists a formal proof of $\psi$ (in the system from $\Gamma$ blah blah blah). That is, there's some way, starting from the axioms, to syntactically manipulate the symbols according to the rules of the system to end up with $\psi$.

On the other hand, $\Gamma \models \psi$ is a statement about the semantics  of the system, i.e. the interpretation of what the symbols `mean', so $\Gamma \models \psi$ when there's no interpretation that renders all of $\Gamma$ true and $\psi$ false.

So, back to the question. When we want to show that $\Gamma \vdash \psi$ is valid, a formal proof is very nice, because it has no dependence on the meaning (semantics) of the symbols, it is simply a consequence of the rules of the system. On the other hand, if we suspect $\Gamma \vdash \psi$ is not valid, it's very hard to give a formal proof - you would have to show that every possible route to a formal proof doesn't work, i.e. that no matter what potentially-very-convoluted order you apply the rules of the system in, starting from the members of $\Gamma$, you can't get to $\psi$. Just to reiterate, you would effectively have to consider every possible proof, and show that it didn't work.

Semantic entailment kind of works the other way around. To show that $\Gamma \models \psi$ is not valid, `all' we need to find is some interpretation such that everything in $\Gamma$ is true, but $\psi$ is false - i.e. we just have to find that one counterexample. Showing that $\Gamma \models \psi$ is valid is the part that requires lots of cases - we have to show that $\psi$ holds for every interpretation for which everything in $\Gamma$ also holds.


Numerical ratio between the length of a string and the transited states

The way you have defined S, we will always have $S \ge |w|$.  Why?  Because each time the automaton reads one symbol from $w$, it follows one transition and visits the state at the end of that transition, incrementing $S$ by one.  In other words, we add one to $S$ for each symbol in $w$.  Thus $S$ is at least as large to the number of symbols in $w$.  (It might be larger if you follow $\epsilon$-transitions, as they don't consume any symbols in $w$ but do visit a state.)

Try working through a few examples and it should become clearer.


Is there a name/algorithm for this problem related to set cover and CSP?

Just to be sure, I assume that $\mathcal{G}^* = 2^\mathcal{G}$, i.e. that $\mathcal{G}^*$ is the power set of $\mathcal{G}$.

Alright, we can use the following flow network $(V,E,\text{cap})$: let $V = \{s\} \uplus \mathcal{T} \uplus \mathcal{G} \uplus \{t\}$. Now let $E = \{(s, c) : c \in \mathcal{T}\} \uplus \{(g,t) : g \in \mathcal{G}\} \uplus \{(c,g) : c\in \mathcal{T} \wedge g \in \mathcal{G} \wedge g \in \mathcal{M}(c)\}$. Finally, we need capacity constraints:

\begin{align}\text{cap}(s,c) &= \min\{|\mathcal{M}(c)|,2\} \qquad &\text{(every class covers at most 2 requirements)}\\
\text{cap}(g,t) &= 1\\
\text{cap}(c,g) &= 1
\end{align}

Now we run maxflow to find an $s-t-$flow and we are done; while there may be fractional maximum flows, finding an integral one is easily done via an augmenting path algorithm (since all capacities are integral).

The problem reminds me of maximum matching, but I can't reduce it to matching off the cuff. Maybe some generalization, not sure.


In the whole floating point number the MSB is a sign bit and LSB is in the mantisa (last bit).

In all floating point formats with exception of 10 byte IEEE real the mantissa MSB of normalised number is not stored because it is implicitly set to $1$ (and used in calculations).

So in the case of your significand (mantissa) $0011010000$ the MSB is $1$ (implicit) and LSB is $0$ (explicit).


For the 2 by 2 block version in the edit, consider the promise problem where there is guaranteed to be just one block in each 3 by 3 region, where the regions have coordinates $(3i+1,3j+1)$ to $(3i+3,3j+3)$ for non-negative integers $i$ and $j$.  By an adversary argument, in the worst case one may have to probe one square in each of the first $\lfloor n/3\rfloor^2-m$ regions and then two squares in each of the last $m$ regions, so in the worst case at least $\lfloor n/3\rfloor^2+m \ge ((n-2)/3)^2+m\ge \Omega(n^2)$ probes.


Proving the decidability of whether a CFG generates a particular string or not

If you give a word $w$ not in the language, then the TM is not guaranteed to halt as an NPDA isn't always guaranteed to terminate in finite steps for a finite word.

So, you can produce a counter example in which your construction doesn't work. Take an NPDA which doesn't terminate for a given word (exists, of course) and run your algorithm on that word. Since that word is not in the language your TM won't ever produce any output as simulation will never end. You were supposed to output a "NO" here.

On the other hand, the CNF algorithm works because it guarantees execution in finite steps for every word, whether it belongs to the language or not.


How does an enumerator for machines for languages work?

Kozen answers this in your quote: what you enumerate is Turing machines that accept all languages in P. This makes sense in many contexts, for example if you want to diagonalize against all languages in P.

It is not a priori clear how to enumerate P (as Turing machines). The problem is that given a Turing machine, it is (provably) impossible to tell whether it halts in polynomial time. The trick is to force the machine to halt in polynomial time.

The enumerator goes over all pairs $(T,p)$, where $T$ is a Turing machine and $p$ is a polynomial. For each such pair, it creates a new machine $M(T,p)$ which simulates $T$ for $p(n)$ steps (where $n$ is the input length), and then halts. The machine $M(T,p)$ is guaranteed to run in polynomial time, and so whatever language it accepts is in P. Conversely, for any P-time machine $T$, there is a polynomial $p$ such that $T$ and $M(T,p)$ are equivalent, and so the enumerator goes over all languages in P.


Efficient algorithm for iterated find/replace

This isn't a complete answer, but it provides some context that's far too long to put in a comment. What you've described is an instance of a string rewriting system, also known as a semi-Thue system. Start with a finite alphabet, $\Sigma$, and a binary relation, $R$, on strings over $\Sigma$. For your example, we'll have $R$ defined by

$$
ba\, R\, b,\quad aaa\, R\, ab,\quad aba\, R\, bb
$$
We can then define another relation, $\Rightarrow$, on strings by, basically, applying $R$ to substrings. For two strings $x, y$, define $x\Rightarrow y$ if and only if
$$
\text{there exist strings }p, q, r, s\text{ such that } x=prq, y=psq,\text{ and }r\, R\ s
$$
In your example, we have, for instance, the chain of rewrites $aaaaa\Rightarrow abaa\Rightarrow aba\Rightarrow bb$, and there we stop, since we cannot reduce $bb$ any further. In a rewriting system, a string like $bb$ which cannot be rewritten is called irreducible or sometimes a normal form. If there is a chain of rewrites starting from a seed string $x$ that leads to a normal form we denote the result by $x\downarrow$. Again, in your example, the normal forms derivable from $aaaaa$ are $ab, bb, aab, abb$.

Your question in its most general form is

  Question 1. In a string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

In general, the answer is no, there isn't. The problem comes in part from the fact that some (or all) seed strings might never lead to a normal form. This could arise in a rewriting system that permits chains like
$$
x_1\Rightarrow x_2\Rightarrow \cdots\Rightarrow x_i\Rightarrow x_{i+1}\Rightarrow\cdots\Rightarrow x_i
$$
Fortunately, you've imposed a helpful constraint, namely that whenever $x\,R\,y$ then the lengths satisfy $|x|>|y|$. We'll call such a system monotone or length-reducing. In a monotone rewriting system we're always going to have a normal form for any seed string, since every rewrite operation strictly decreases the length of the string. A rewriting system for which every string has at least one normal form is called noetherian, by the way. Refining the question gives us

  Question 2. In a monotone string rewriting system, is there a computationally efficient way to find a normal form for a given string $x$?

The answer to this question is yes, of course: given a seed string $x$, simply apply rewrite rules until you reach a normal form. More systematically, if $|x| = n$ and you have $m$ base rewrite rules $\{w_1\,R\,z_1,w_2\,R\,z_2,\dots w_m\,R\,z_m\}$ with $M=\max\{|w_i|\}$, then we'll require $O(nmM)$ character comparisons, even if we don't use efficient string search algorithms.

We haven't quite gotten to your real question, though, since you also stipulate that at each step you will choose to apply your base rewrite rules in order of the lengths of their left-hand sided, |w_i|, from shortest to longest. It's not clear that this is a useful constraint; in fact, some string search algorithms (Boyer-Moore, in particular) are more efficient when searching for longer substrings than they are for shorter ones. It might be helpful to impose another constraint, though: when searching for a substring to replace, always choose the leftmost substring, regardless of length. This would put you in a situation involving prefixes and there's a fair amount known about this. Choosing rightmost substrings as replacement candidates might also be a useful avenue.

Finally, we come to the most interesting question:

  Question 3. In a monotone string rewriting system, is there a computationally efficient way to find a normal form of minimal length?

This should help you to find answers. There's good news for your search, namely that there's a lot of material out there, both in books (yes, whole books have been written on string rewriting systems) and online. I did a search for "string rewriting systems" and got a million and a half hits. The bad news is that there's a lot of material out there, so finding an answer is likely going to take some serious drilling. Frankly, I don't know the answer to Question 3, but my uninformed guess is that the answer is affirmative. If you haven't gotten a definitive answer in a few days, you might want to ask your question, suitably reworded, over at theoretical computer science.


How to use adversary arguments for selection and insertion sort?

From your comment, it seems you are confusing the meaning of lower bounds, upper bounds and asymptotic notation. For instance, take Insertion Sort. Its best-case running time is $\Theta(n)$ (this happens when the input is already sorted). Its worst-case running time is $\Theta(n^2)$ (this happens when the input is in reverse sorted order). So, since the running time falls between a linear function of $n$ and a quadratic function of $n$, you can say that the running time of Insertion Sort is both $\Omega(n)$ and $O(n^2)$. It's important to understand in this case that you cannot say that the running time is $\Omega(n^2)$. Why? Because there exists an input that causes the algorithm to run in $O(n)$. However, you may say that the worst-case running time is $\Omega(n^2)$, again because there exists an input that causes the algorithm to run in $\Omega(n^2)$. We usually use the $O$ notation for the worst-case though, since we are interested in an upper bound on the number of operations done by the algorithm.

Now, let's think about an adversary argument for Insertion Sort (you may try to derive one for Selection Sort by applying the same ideas).

Consider the Insertion Sort algorithm playing against an opponent that we will call the adversary. The aim of the adversary is to provide an input X for the algorithm that maximizes the number of comparisons done by the algorithm. This is usually analyzed in the context of decision trees. A decision tree shows all possible sequences of comparisons that the algorithm could make. Each interior node of a decision tree represents a single comparison. The two children of a node represent the two outcomes of the comparison (yes/no or true/false). Each leaf represents a possible output. For sorting algorithms, the leaves are permutations of the keys. The algorithm starts at the root and follows a path down to a leaf. At each internal node, the answer for the comparison done tells the algorithm which node must be visited next. When the algorithm reaches a leaf, it outputs its corresponding permutation. The running time of an algorithm (seen as a decision tree) for a given input is the number of comparisons done in the path from the root to the output leaf. Now, the adversary has a simple strategy that will work against any comparison-based sorting algorithm, including Insertion Sort: whenever the algorithm makes a comparison, the adversary chooses the answer that will eliminate the fewest possible permutations.

In general, owing to the fact that with $n$ elements there are $n!$ possible permutations, any decision tree for sorting must have at least $n!$ leaves, and so must have depth $\Omega(\log(n!)) = \Omega(n\log n)$ (by Stirling’s approximation).
For Insertion Sort, the adversary may craft a particular input that causes the corresponding decision tree to have depth of at least $\Omega(n^2)$.

The algorithm uses an array $A[1 .. n]$ to store the input elements and is based on the following invariant:

At the start of each iteration of the for loop, the subarray $A[1 .. j-1]$ consists of the elements originally in $A[1 .. j-1]$, but in sorted order.

In each iteration, the elements in $A[1 .. j-1]$ are therefore already in sorted order, and the algorithm examines $A[j]$ and inserts it in its final proper place, by comparing the value of $A[j]$ against the value of the elements in $A[1 .. j-1]$, starting from $A[j-1]$ and proceeding back to $A[j-2]$ and so on until $A[j]$ is no longer the greatest one in the comparison. The elements in $A[j+1  .. n]$ are in an unknown state (with regard to the sort order) and will be processed in later iterations.

Here is the strategy of the adversary. Knowing that the algorithm works by inserting $A[j]$ in its proper place by moving the elements in $A[1 .. j-1]$, then the obvious strategy is to maximize in the $j$-th iteration the number of elements that must be moved in order to accommodate $A[j]$. This is easily accomplished by carefully choosing the input so that it is in reverse sorted order. Indeed, in this case, the number of elements that must be moved in each iteration is $j-1$. This leads to the $\Omega(n^2)$ worst-case running time (determined by the corresponding arithmetic series).


CYK is still relevant, afaik, as the simplest example of a family of general
parsing algorithm based on dynamic programming, ranging over all
parsing technique (that I know of) and many syntactic formalisms. There is a simpler
general parsing algorithm (below), but where the dynamic programming (DP)
aspect is no longer visible. as things are defined more globally.

What I mean by general parsing algorithm, is a parsing algorithm that
can parse all memeber of a family of languages, according to their
given grammar, and produce all the possible parse structures when the
parsed string is ambiguous, combined in a condensed form called a
(shared-)parse-forest. Though this is often considered only for
context-free (CF) grammars, it does generalize to other formalisms.

Most known such algorithms are for CF grammars: such as CYK, Earley,
GLR, GLL with diverse variants. They are also known as chart parsers,
and extend beyond formal languages to some logical formalisms, often introduced by computational linguists via so-called feature structures. They can all be seen as extensions or refinement of CYK, though that is often a subjective assessment. They can also be seen as extensions or refinement of the more basic algorithm presented below.

My experience (but new research might prove me wrong) is that the DP
structure of CYK is a proper route to understand, in a simple context,
some of the issues raised by the various techniques for improving the
performance of those parsers in the structured context of the DP
calculation, or to introduce various features such as Viterbi selection of the best parses.

Some of the most basic issues, such as the grammatical forms to be
used to keep a low time and space complexity (cubic), or how to
represent parse-forests. can be more readily viewed and understood
from the simplest algorithm, which is the old cross-product
construction (Bar-Hillel, Perles and Shamir, 1961) between a CF grammar and
a FSA, to produce the grammar of the CF intersection of their
languages. This view is developed in a paper by (Lang 1995) along with extensions to other formal languages.

From a practical point of view, i.e. for use in actual parsers, some
of the more recent general parsers may be better tool. But I believe
that CYK remains an important and simple educational step, more so in
my opinion than Earley's algorithm that is much more complex. Which of
the other DP algorithm should be used for actual systems remains the
object of some debate, as performance issues are somewhat subtle.

I discuss some aspects a bit more in depth in another answer.


Enumerate all valid orders of subset sums

Here is one algorithm that runs in doubly exponential time -- so probably useless.  In other words, this answer is probably not useful.

You can check whether an order is valid in $2^{O(n)}$ time (i.e., $\text{poly}(2^n)$ time) by reducing to linear programming: you obtain $2^n+n-2$ linear inequalities in $n$ variables, and you can test for feasibility in time polynomial in the number of inequalities and variables.  Then, enumerating over all possible sums and checking if each is valid would yield a $(2^n)! 2^{O(n)} = 2^{n 2^n + O(2^n)}$ time algorithm.  This will be ridiculously slow in practice.

To improve this, you could use an iterative pruning / branch-and-bound style algorithm.  Given a prefix $S_1,\dots,S_k$ of an order, we can test whether it is valid using linear programming as above.  If it is not, we don't consider any order that starts with this prefix.  In other words, do breadth-first search: first choose $S_1$, then choose $S_2$, then choose $S_3$, and so on, at each step checking whether the prefix obtained so far is valid.

This may still be extremely slow, as there is the possibility that a prefix $S_1,\dots,S_k$ is valid but there is no way to complete it to a full order $S_1,\dots,S_{2^n}$ that is valid, so this might do a lot of wasted work.


Can you come up with a Turing machine that writes the decimal expansion of $\pi$ to tape?
Can you come up with a Turing machine that, given a string,
a separator, and the decimal expansion of $\pi$ on the tape,
determines whether the string occurs as a subsequence of $\pi$? (see this question).
Given such machines, can you 'weave' them into a single machine?


Algorithmic problem with many different time/space complexity solutions

I like this one: given a string $S$, find the longest substring that appears two or more times in $S$.

There are plausible algorithms with running time $O(n^3)$, $O(n^2)$, $O(nk \log n)$, $O(nk \log k)$, $O(nk)$, $O(n \log n)$, $O(n \log k)$, and even $O(n)$, where $n$ is the length of $S$ and $k$ is the length of the longest such substring.

However I don't know if it has practical applications.

Computational biology is a good source of practical algorithm problems.


Why the restriction on the length of the proof in a $(r,q)$-verifier in PCP is inconsequential?

The formal version of "the limitation on the proof length is inconsequential" is the following:

If $L$ has a $(r(n),q(n))$ PCP verifier, then it also has an $(r(n),q(n))$ verifier with proof length bounded by $q(n)2^{r(n)}$.

The above holds since as you mentioned, the verifier can ask $2^{r(n)}q(n)$ different queries on a length $n$ input ($q(n)$ queries for each possible outcome of the verifier coins). Let $f_x$ be an embedding (one to one mapping) of the possible verifier queries on input $x$ in the set $\{1,2,...,q(|x|)2^{r(|x|)}\}$. Let $V'$ be the verifier who acts like $V$, with the sole difference that when $V$ asks for index $i$, $V'$ requests $f_x(i)$. It is easy to see that $V'$ is a verifier for $L$ with the same properties, and bounded length proofs.


Local search: Problem with neighborhood definition

The metric used for the definition of the neighborhood is the size of the symmetric difference. The symmetric difference $A\triangle B$ of two sets $A,B$ is the number of elements which are in exactly one of the sets $A,B$. So $A\triangle B = (A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)$. A matching is considered a set of edges, so $M\triangle M'$ is the set of edges that are found in exactly one of the matchings. The metric is $d(M,M') = |M \triangle M'|$, and the $k$th neighborhood of a matching $M$ is the set of matchings $M'$ at distance at most $k$ from $M$.

As an example, if $M'$ results from adding an edge to $M$ or from removing an edge from $M$ then $d(M,M') = 1$, and if $M'$ results from replacing one edge of $M$ with another then $d(M,M') = 2$.


Would time travel be useful for optimization?

Yes.  If time travel were possible, it would be a huge win for optimization and computation: it would enable us to solve computational problems that today seem very hard to solve with existing computers.

To formalize this, we must first agree on a model of physics that allows time travel and that describes what happens when you try.  There are various plausible ways to do that.  Under one plausible set of assumptions about the physics, the set of problems you can solve in polynomial time using time travel is all of PSPACE.  (If you're not familiar with it, PSPACE is the set of problems solvable by classical no-time-travel computers in  any amount of running time you want, subject only the restriction that the space usage must be polynomial.)  For instance, every problem in NP could be solved in polynomial time if time travel were possible.

For instance, there are problems that today seem to require exponential time to solve (with classical no-time-travel computers), but could be solved in polynomial time if time travel were possible.

To learn more about this subject, I suggest you take a look at Scott Aaronson's lecture notes: http://www.scottaaronson.com/democritus/lec19.html


What you have asked: "Do I  need to understand more than this to write a compiler?" then answer is basically, No - but it does depend on the compiler!

You need to know a lot of theory about a lot of other things, and you could eventually ask about them too. For example, when you get to parsing you might ask "Do I need to know about top-down and bottom-up parsing". Do I need to know the difference between LL, LR, LALR parsing? Do I need to know about Chomsky Level 1 Grammars? Does it matter who Noam Chomsky actually is? Do I need to be able to know how to parse ambiguous languages? Do I need to know about data-flow in optimisation, do I need to know about flow-graphs? Do I need to know about machine architecture? Do I need to know about both register based machine code and stack based machine code?

Just so many things that one could question the need for!

You can write some kind of compiler without knowing any of this, but you wouldn't be fully equipped with all the background knowledge to be able to write any compiler!

If your task was to write a very straightforward compiler for a straight forward language then you can get away without knowing a lot of the background theory. There are some class exercises like that. If your jobs was as a compiler writer then you might be expected to be able to do a bit more.

The next part of your question to address are the textbooks you have used. Most of the textbooks are written for use on undergraduate Computer Science courses. In many/most those courses the background theory behind the practice of writing compilers is included because that is what most course curricula need. This then permits the students to use their wider knowledge to implement compilers for the as-yet-to-be-specified languages to solve the problems of the future. If you could only tackle the simple subset problems from introductory classes that did not require thinking outside the box you knowledge would be rather useless; or rather only useful for class credit, but not much beyond.

I hope that gives the view of a compiler writer and computer scientist. My students sometimes ask the same questions.


Is it possible to partially decide when will halt given any arbitrary input?

The halting problem is not decidable, but it is still partially decidable (other terms for this are "recursively enumerable" and "Turing recognizable"). So, you are right that both of these problems are equivalent to the halting problem. That is why they are undecidable, but still partially decidable.

You may want to review the definition of "partially decidable" in your textbook or notes.


For proving that L is in NPC, why do we reduce a known L' into L and not the other way around?

Saying that a problem is NP complete is, approximately, saying that there is no good algorithm for it.

Saying that $L$ reduces to $L'$ means, approximately, that one way of producing an algorithm for $L$ is to use an algorithm for $L'$ as a subroutine.

Now, if $L$ reduces to $L'$ and $L$ is has no good algorithm, then we know that $L'$ also has no good algorithm – if it did, then "use $L'$ as a subroutine" would be a good algorithm for $L$, but no good algorithm exists. However, if $L'$ reduces to $L$ and $L$ has no good algorithm, we know that "use $L$ as a subroutine" isn't a good algorithm for $L'$ but so what? There are infinitely many other algorithms and we know nothing about whether those are good or bad.


What is the difference between Babbage's analytical and difference engine?

They would be different from each other in a very significant way. In the comments there is a link to the Wikipedia articles on both machines - which are quite informative - but I'll assume they weren't useful to you.

You can think of the Analytical Engine basically as a regular computer, which would have a program coded in punched cards, that were attached to each other forming a chain (there would actually be three kinds of cards, each with its own reader, check this out). The machine also had a control unit whose job was to decode the instructions of this program and perform them on the data that was stored in a memory capable of holding a thousand numbers.

The Difference Engine, on the other hand, would have been exactly a calculator, and one that could perform just one kind of operation, repeatedly, on a sequence of numbers. In the "Sketch of the Analytical Engine", authored by Luigi Menabrea, and famously translated by Ada Lovelace, the nature and general applicability of this operation is detailed:

  The theorem on which is based the construction of the machine we have just been describing, is a particular case of the following more general theorem: that if in any polynomial whatever, the highest power of whose variable is m, this same variable be increased by equal degrees; the corresponding values of the polynomial then calculated, and the first, second, third, &c. differences of these be taken (as for the preceding series of squares); the mth differences will all be equal to each other. So that, in order to reproduce the series of values of the polynomial by means of a machine analogous to the one above described, it is sufficient that there be (m+1) dials, having the mutual relations we have indicated. As the differences may be either positive or negative, the machine will have a contrivance for either advancing or retrograding each needle, according as the number to be algebraically added may have the sign plus or minus. (emphasis added)

By calculating series of values of polynomial functions many useful calculations can be approximated, including those of trigonometric and logarithmic functions. This method has its limits, though, which are explained a bit further in the document. In doing that, the justification for the construction of the new machine is given:

  We see that its use is confined to cases where the numbers required are such as can be obtained by means of simple additions or subtractions; that the machine is, so to speak, merely the expression of one particular theorem of analysis; and that, in short, its operations cannot be extended so as to embrace the solution of an infinity of other questions included within the domain of mathematical analysis. It was while contemplating the vast field which yet remained to be traversed, that Mr. Babbage, renouncing his original essays, conceived the plan of another system of mechanism whose operations should themselves possess all the generality of algebraical notation, and which, on this account, he denominates the Analytical Engine. (emphasis added)


What to infer about maximum height of AVL tree from these three different formulae

Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence
$$
m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2).
$$
The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h > 4$. It is well-known that
$$
F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].
$$
Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so
$$
\begin{align*}
n(h) &= \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right] - 1 \\ &=
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h -
\frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1.
\end{align*}
$$
The second term is very small, and in particular
$$
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 < n(h) < \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h.
$$
This shows that
$$
\log_{(1+\sqrt{5}))/2} n(h) < h + \log_{(1+\sqrt{5}))/2} < \log_{(1+\sqrt{5}))/2} [n(h)+2],
$$
from which you can deduce whichever excellent bounds you want.


What is a standard way to construct a turing machine for any function to compute

Designing a Turing machine is pretty much like writing a program. You
have to choose a representation for the data and a corresponding code
(read * transitions*) to manipulate the data. Remember how we do
arithmetics (addition, multiplication, quotient, ...) by manipulating
in strange ways strings of symbols that represent numbers, whether in
unary or positional representation, or even with Roman numerals.

The difficulty is generally that the means for data representation are
pretty elementary: symbols on a tape. So you have to find ways to
encode everything into that. Also the programming instructions are
very simple. So you have to find a way (for complex machines) to
decompose the problem into parts, and to assemble the coresponding
machine parts. Pretty much what you do when you define functions and
subprograms in usual programming.

You can make your life easier by using different sets of states for
each subprogram. But basically people rarely design Turing machines,
except for specific proofs. Then the problem is often how to combine into one several simpler machines that have been separately designed. You can find that in textbooks.

It can be amusing to find elegant solutions for simple problems. Like
puzzles. You can add constraints. For example, you second question can
be solved in several ways. Some use more tape than others.

Exercise: do long multiplication of two binary numbers, then two
ternary numbers. Well, just think about it. Where would you store the
multiplication table?


Intuition behind the Reversal Algorithm [ Rotation of Array ]

Imagine flipping a deck of cards over, then dividing it into two parts and flipping each part over. The cards in each part end up in their original order because they're flipped twice. The first flip also swaps the two parts. The net effect is the same as cutting the deck, i.e. rotating it.


A monad is just a monoid in the category of endofunctors, what's the enlightenment?

This answer may not be exactly what you are looking for. That is, I think perhaps the importance of this characterisation is being overemphasised here. The quote

a monad in X is just a monoid in the category of endofunctors of X

is originally from Mac Lane's Categories for the Working Mathematician, where it appears as a helpful intuition for the definition of monad, which, alone, can seem quite unfamiliar at first. By characterising it as a monoid in a particular monoidal category, the reader is given an alternative perspective. Note that the chapter on monads actually comes before the chapter on monoidal categories: the remark is intended to be helpful, rather than precise (it is made precise only later).
The quote was then rephrased in James Iry's infamous article Brief, Incomplete and Mostly Wrong History of Programming Languages.

A monad is just a monoid in the category of endofunctors, what's the problem?

Presented out of context, as it is in the article, it is meant to amuse. The quote has since become a meme in the functional programming community, primarily because it is amusing, rather than a key insight for functional programming (though it does also serve to pique the curiosity of functional programmers, drawing them into the wonderful world of category theory). My view is that this characterisation, while helpful and interesting, is not as important as one might imagine from its popularity.
However, this is not to say there is no insight to be gained from this characterisation. First, let me point out that, while the presentation of a monad with a multiplication and unit is clearly suggestive of a monoid, as you point out, the Kleisli presentation, with a bind and return operation, is not. It is the Kleisli presentation that is common in functional programming, so certainly the characterisation as a monoid is more interesting from this perspective.
From a theoretical perspective, one of the insights is indeed that many natural structures in computer science (and mathematics) are monoidal. From the perspective of monads (particularly with their relation to cartesian operads and Lawvere theories), monoidal structure corresponds to substitution structure (equivalently, composition structure). Substitution is ubiquitous in computer science (for example, capture-avoiding substitution in a type theory, or grafting of trees). Monads are just one more example.
While understanding formally the statement in question may not be enlightening, I suggest that it is enlightening to understand the different perspectives on monads, as it allows you to see the different ways in which monads might be used (e.g. as containers, describing algebraic structure, describing multi-compositional systems, etc.). It can be hard to appreciate just how often they pop up without having seen the different lights in which they can be seen. In this sense, monads as monoids is just one perspective (and probably not the most enlightening).
Finally, while monads themselves are inarguably very useful in pure functional programming generally, I'm not sure the perspective as monads as monoids is helpful per se. I think the Kleisli perspective, which happens to be equivalent, is the most enlightening perspective here.
In summary, this response may be a little disappointing: I don't think that understanding this relationship is all that helpful or enlightening practically (i.e. for programming). However, it is a useful perspective to keep in mind, along with the others, when considering monads theoretically.


Why is integer programming more difficult than (real) linear programming?

Given a starting solution, the Simplex algorithm will systematically find solutions with better values of your goal function. However, it runs using real numbers (or rational numbers). You can use the Simplex algorithm to find a solution for an integer programming problem that is optimal, except that it ignores the need for integer values.

Lets say you have a solution where a variable x has a value of x = 1000.525. Clearly that's not an acceptable solution. So you take your system, make two copies, and in one copy you add the condition x ≤ 1000, in the other you add the condition x ≥ 1001. You solve both copies of the problem, but then you have other non-integer values and you go on.

So starting with your non-integer solution, you have many, many ways to try to turn them into integer solutions.

The smaller the numbers, the worse it gets. In that example I gave, you'd expect that the solution doesn't change a lot. If you have a solution x = 0.7, you add the equation x = 0 or x ≥ 1, and that can make a massive change.


Actually it depends on your point of view, or level of detail.

The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it can be a linked tree or array.

The wikipedia page however is concerned with the implementation. That is even clear from the title binary heap. (You understand the binary heap by looking as if it is a tree, you implement it using an array). In this implementation it is easily seen how to program your operation find-element. Technically, that is another abstract data structure (as it has an additional operation aprt from standard heap operations).

In practice heaps (priority queues) are often used for graph algorithms like Dijkstra. There it is important that the priorities stored in the heap can be changed (if we find a shorter route). That is only possible if we are able to find the element in the heap so we can adjust its priority (and reposition the element in the heap). Usually that is done by building another structure on top of the heap so we can efficiently find the positions where elements are stored.


Pseudocode algorithm to check encoding of Turing machine

The encoding $\langle M \rangle$ of a TM, has a specific structure. All you need your algorithm to do, is to verify that the input string $w$ possesses the "correct" structure of a valid encoding.

Note, that there are many possible ways to define the encoding $\langle M \rangle$. For instance one possible such encoding, for $M=(Q,q_0,F,\Gamma,\Sigma, \sqcup, \delta)$ is
$$ 1^{|Q|}01^{|\Gamma|}01^{|\Sigma|}0\delta_100\delta_200 \ldots \delta_{last}000$$
where each $\delta_i$ is one line of the transition function, such that if, for instance $\delta(q,a) = \{ p, b, d\}$ we encode it as $1^q01^a01^p01^b01^d$ with $d$ being the direction where the head moves, say Left=1, Right=2, Stay=3.

Remember that other encodings are possible, it depends on your definition!

However, assuming the above definition, I think you should be able to come up with an algorithm to verify if the encoding is valid or not.

For instance, is the input $w=0000000$ valid ?

   no, because it contains no states $Q$, etc.

What will you need to check for validity? Basically, only the following

   0. that the formatting looks correct (no extra characters, ends with 000, etc,)
 1. that all the sets exist (and behave correctly, e.g., $|\Gamma|>|\Sigma|$)
 2. that $\delta$ is well defined (think, what does this mean)...


What does it mean when saying "we want $\Lambda$ to be $\tilde{O}(1)$ as a function of $M$"?

The notation $\tilde{O}(f(n))$ is not completely standard and is usually defined as $\tilde{O}(f(n)) = O( f(n) \cdot \text{poly} \log f(n))$. The intuition is that it drops factors that are asymptotically not larger than a polylogarithm of the argument. For example, you can write $\tilde{O}(n^2)$ in place of $O(n^2 \frac{\log^3 n}{\log \log n})$.

That said, in your paper $\tilde{O}(f(n))$ seems to be used as a shorthand for $O( f(n) \cdot \text{poly} \log n)$, although I was not able to find a definition within the paper by quickly skimming it. This only differs from the previous definition when $f(n)$ is smaller than or larger than any polynomial.

In the specific sentence you are quoting, the authors want $\Lambda$ to be in $O(\text{poly} \log M)$.


Isn't a small monolithic kernel a micro-kernel, and a big micro-kernal a monolithic kernel?

The distinction between monolithic kernels and microkernels has nothing to do with the size.
In a monolithic kernel, all services are provided by a single piece of code running in a single, flat, shared address space. There are monolithic kernels which support dynamically loadable modules now (actually most monolithic kernels do), but when these modules are loaded, they still become part of the single monolithic (hence the name!) blob of code running in the single address space. All communication between these different services is done by accessing shared memory, or another way of looking at it is that there is no communication because it's all just one singular monolithic blob of code.
In a microkernel, only the most basic, fundamental services are provided by the kernel. Everything else is provided by separate programs, which are separate pieces of code, running in separate address spaces. All communication between the services is done through a well-defined messaging protocol.
So, in a monolithic kernel, you have a single piece of code which manages memory, schedules tasks, accesses the disk, accesses the filesystem, accesses the network card, implements the TCP/IP stack, implements Ethernet, implements WiFi, access the graphics card, etc.
In a microkernel, the kernel only implements the very basics: memory management, task scheduling, and a simple messaging protocol that allows the programs to talk to each other and to the kernel. The disk driver is a separate program. The filesystem driver is a separate program. The network card driver is a separate program. The implementation of the IP protocol is a separate program, TCP is a separate program, UDP, IPv6, etc. are all separate programs. The Ethernet implementation is a separate program, actually probably a set of separate programs for the PHY layer, the LLC layer, the MAC layer, etc. Same for WiFi, that's going to be a whole set of separate programs. The graphics driver is a separate program. And so on, and so forth.
These "separate programs" are sometimes calls "services" or "deamons".
The relationship between a microkernel and its daemons is analogous to the relationship between an Operating System and the user programs: Your browser, your email program, your first-person shooter, your music software, your text editor, your chess program, your video editor, your drone controller, your video chat program, they are not part of the Operating System. They are all separate programs that run in separate processes in separate address spaces. One of them can crash without taking the entire system down.
But none of this has anything to do with size: the sum of a microkernel and many services that provide many features can be larger than a simple monolithic kernel that doesn't provide many features. If a system doesn't support networking, for example, then it doesn't need code for networking, regardless of whether that is a microkernel or a monolithic kernel. So, it is easily possible for a microkernel system that supports networking to be larger than a monolithic kernel system that does not support networking.


Best Fit Memory Allocation Algorithm Statistical Analysis

You want your "holes" to be bigger because a big hole is more likely to be useful for an allocation in the future.  For example, if you have 2 128-byte holes that are not adjacent then you can't satisfy a request for 160 bytes.  If the 2 128-byte holes are adjacent and coallesced into a single 256-byte hole, then you could satisfy a future request for 160 bytes with that hole.

Here's the best article I know of on memory allocation policies:

Paul R. Wilson, Mark S Johnstone, Michael Neely, David Boles: Dynamic Storage Allocation: A Survey and Critical Review, Int'l Workshop on Memory Mgt, 1995.

They followed up with a more detailed experimental study a few years later:

Mark S Johnstone, Paul R Wilson: The Memory Fragmentation Problem: Solved?, First Int'l Symposium on Memory Mgt, 1998.

In the papers they find that best fit works quite well in practice.  Another lesson of both papers is that statistical analyses don't work (usually).  You need to run experiments on real traces of the alloc/free calls from real workloads.

A very good public domain malloc implementation was written in the mid '90's by Doug Lea: http://g.oswego.edu/dl/html/malloc.html.  It's essentially an approximation of best fit.


Algorithm for smallest String without a given prefix

There is no solution if all characters in the input string are equal to the last character in the alphabet (this includes the case of the empty string).

Otherwise, as long as the last character in the input string is the last character in the alphabet, remove it from the string. Then replace the last character of the result with the next character in the alphabet.


Pattern classification: what goes into the sample?

First a bit about the classifier:
The knn classifier works by majority voting. It takes an input record, finds the k nearest labeled data points, looks at the class labels on each data point and assigns the current record the most common class label. For instance, if I use a 3-NN classifier and my three neighbors are of class [1 1 2], then I will select class 1 for this record.

That being said, "Training" should contain the feature vectors of your labeled dataset (probably 1 record per row). "Group" contains the class label for the corresponding record. So the $i^{th}$ value in Group is the class label associated with the $i^{th}$ record in "Training". "K" specifies the number of neighbors you'd like to look at when classifying new objects. Lastly, "Sample" will be the data point you want to classify.

Also, I've never heard of piece-wise component analysis, do you mean Principle Component Analysis? If this is the case, just note that PCA is a method commonly used for dimensionality reduction, so you'll still have to use a classifier to get labels for your data.

One more note: Matlab has an SVM classifier as well, its calls are similar to that of the Naive Bayes classifier for training and testing.


Why did MIPS include shamt and distinguish funct/opcode?

There are a few different trade-offs going on here.

First, we want the instructions to be fixed width (32-bits).  This guarantees that instructions are cache-block and page aligned which simplifies cache and page presence and permission checks.

Second we want the various instruction fields (opcode/source regs/immediates) to be fixed width and fixed position.  This makes them faster/less logic to decode and they are needed in the early stages of the pipeline.  (The destination register isn't needed until the end of the pipeline, so it can be in different places in R and I instructions.)  The position and width of the function field matters a little less because that needs to control the function of the ALU, but that's in the third pipeline stage, so you have a little time to work with it if needed.

But now we have a tension between number of possible instructions and the sizes of the immediates.  We want the immediates in the I and J instructions to be long as possible.  This is a 32-bit architecture, and the J instruction has only a 26-bit address.  It gets two zero low-order bits added to it (another benefit of fixed width instructions) but you can still only jump a maximum distance of $2^{28}$ bytes, which makes life difficult for the linker.  (A call of a procedure that is more than $2^{28}$ bytes distant needs to be done with a triple instruction: load-upper-immediate, add-immediate, jump-and-link-register, instead of just a jump-and-link.)  The 16-bit immediate in I instructions is also nice for compiler/linker writers.  (On the SPARC, where the immediate field was only 12 bits they had to add an entire special load-high instruction class with a 20 bit immediate.)

So we really don't want to make the opcode 7 bits (because it will cut into immediates) but with 6-bits we only have $2^6=64$ possible different instructions, which is way too few.  The compromise is: there are exactly two type J instructions (jump and jump-and-link), and only one or two type R instructions, with the remaining 60-or-so opcodes being used for I instructions.

But that leaves some wiggle room with the R instructions.  Aside from the 6-bit opcode, these only need 15 additional bits for register specification, which leaves 11 bits for the extended opcode and/or shift-amount.

You should think of the function field as being an extended opcode for the R instruction.  There's only one R instruction opcode, but there are 64 different functions that the R instruction can perform.

Okay.  We have 60 different I instructions and 64 different R instructions, so where should we put the shift-immediate instructions?

Well, not only are there fewer I instructions, but there are way more things we want to do with I  instructions.  Recall that all the branch instructions need to be I instructions because they have a relative (immediate) offset.  Also all the load and store instructions are I format on MIPS.  And finally we need the load-upper-immediate instruction to be an I instruction.  Not only that, but the R instructions still have 5 additional unused bits, (which is what we need for the immediate of a shift-immediate on this architecture), so this gives further incentive to making the shift-immediates into special (weird) R instructions.

A lot of these decisions are more art than science, but there is an underlying logic that can be discerned.  The key goal is not to make the number of instructions as small as possible, it is to make a high-performance pipeline fit on a single chip (so that tiny companies, like MIPS and Sun were in the 1980s, could compete with IBM and DEC).  (The name RISC, invented by David Patterson, is somewhat unfortunate.  It caught on because it was cute, not because "reduced instructions" is an accurate description of what the MIPS and SPARC architectures were really trying to do.)  So you want the instructions fixed width (and relatively small so that you get better I-cache behavior) to make fetch, paging and decode simpler and faster.  You want the parts of the instruction that need to be decoded early (the opcode, the two source registers, and the sign-extended immediate) to be a fixed width and in a fixed position.  You want immediates to be as long as possible, and you want as many different kinds of instructions as will fit, given all those other constraints.


What are the advantages of online learning when training neural networks?

Batch learning and online learning both have their place.  Generally speaking batch learning will train your neural network to a lower residual error level, because the online training can sometimes have one training undo the effect of another.  However, online training has a few advantages:

Online learning schemes learn "faster."  In some cases, determining how many samples you need can be difficult, and sample gathering may be costly.  Online learning lets you see the progress of your training as the number of samples increases, potentially saving on sample gathering costs once it reaches an acceptable error.
Online learning schemes can be done during operation, which can be valuable.
Online learning schemes are more effective for dealing with data sets that are not stationary.  It is easier for the batch methods to come up with highly specialized solutions which work well for the test samples, but do not capture a general solution.


Floating point operations; Exception, Flags, and Trap Handlers

Your problem is typographical. Look at a well-formatted copy and it should all make sense. So for example, the argument to the trap handler on overflow is $\hbox{round}(x 2^{-\alpha})$, where $x$ is the exact value.

The value of $\alpha$ comes from the fact that the exponent is 8 bits in binary32 (previously called "single") and 11 bits in binary64 (previously called "double"). You can think of $\alpha$ as an unsigned integer the size of the exponent field, with the two most significant bits set. Why it would be that number in particular is left as an exercise; think the possible range of an overflowing operation and what would be required to rescale it back into a representable range.


Explaining why FFT is faster than DFT for the general public?

FFT is an algorithm for computing the DFT. It is faster than the more obvious way of computing the DFT according to the formula.

Trying to explain DFT to the general public is already a stretch. Also, they probably don't know what an algorithm is. Perhaps you could say that there's a fast way of computing the DFT, and that's one more reason why it's so useful.


Your problem is discussed in the paper Efficient construction of a small hitting set for combinatorial rectangles in high dimension by Linial, Luby, Saks and Zuckerman. The object you're after is called a $(2,n,2^{-k})$-hitting set in the paper (this notation is not standard). They construct such a set of size $\mathrm{poly}(2^k\log n)$ in time $\mathrm{poly}(2^k n)$, and give a lower bound of $\Omega(2^{k+1} + \log n)$. Their construction certainly doesn't produce a minimal hitting set, and they're not necessarily interested in your range of parameters, but perhaps you could chase the literature from there on and find more relevant material.


Sorting array of strings (with repetitions) according to a given ordering

The other answers provide correct solutions. However, you can do a bit better considering multivariate complexity. Note that the provided running times in the other answers are not quite specific since they ignore either the size of the first array or the lengths of the strings.

Here are 2 different methods with their specific running times. The first of which is a brief description of the method in the other answers with specific analysis of the running time. The second of which has better running time and is almost optimal.

Let us call the first (ordered) list in the input $A$ and the second (to be ordered) $S$. Let $n$ be the size of $A$ and $m$ the size of $S$. Let $l$ be the maximum length of a string in the input.

The first method.
This span the methods in the other answers. Note that in both we need to find for each string the whether it lays in the original ordered array and if so at what position exactly. We need either apply a linear search which will cost something like $O(ml)$ per element or we can build some kind of a dictionary data-structure such as search trees and hashing tables or a "trie" (prefix-tree) data structure to achieve each look-up operation in linear time in the size of the strings. Using this we can achieve a running time of $O((m+n)l)$ for finding the positions over all strings. Afterwards we need to sort all strings in $O(n \log n)$ if we assign the indices directly to the strings (using pairs) or $O(l n \log n)$ by applying the look-ups while searching. So the best running time we can achieve using the methods in the other answers would be $O(l (n+m) + n \log n)$.

The second method. Note that we did not make use of the original sorted array and that is why we had to sort the strings again. We can solve the problem more efficiently by using this extra informaiton. To achieve this, let us bild a dictionary $D$ (for the sake of the theoretical bounds let us define it as a trie but in you can implement it as a hash-table as well). Let us define a new list $L$ (a linked list) and a function $C$ that counts how many times each string appeared in the first array. Assume $D$ assigns to each string a distinct number from $1$ to $m$ and $C$ is an array of length $m$.
The algorithm goes as follow:

For all i in {1, .., m}
 Set C[i] := 0
// Now build D
Set index := 0
For each string s in A do
 Set D[s] = index
 Increase index by one
// Now find how many times each string occurs
Let L be an empty list
For each string s in S do
 If s in D then
  Find index = D[s]
  Increase C[index] by one
 Else
  Append s to L
//Now output
For each string s in S do
 Find index := D[s]
 Find c := C[index]
 while c > 0
  output s
  decrease c by one
For s in L
 output s

This algorithm runs in $O(l(n+m)$ which is linear (optimal) if the lengths of the strings are bounded by a constant.


How many Turing machines are there with $c$ characters and $n$ states?

The answer is $(3(c+1)(n+2))^{(c+1)n}$. You get this by considering all functions of the type $(Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L, R, N\}$. Where $Q$ is the set of states, $F$ is the set of final states, $\Gamma$ is the alphabet including the blank character, and $L$, $R$, $N$ are the left shift, right shift, and no shift respectively. You can view this as a problem of picking $|(Q \setminus F) \times \Gamma| = (c+1)n$ elements from a set of cardinality $|Q \times \Gamma \times \{L, R, N\}| = 3(c+1)(n+2)$ with replacement.


In NLP, does the lexer have to tag the tokens before the parser?

Morphological tags can help the parser. On the other hand, the complete sentence structure, maybe even the paragraph context may help to finally disambiguate possible tags for a token. So there is no yes/no answer. Except, maybe, that tagging is, afaik, usually not attributed as work of the lexer, but rather a module of its own.


If Halting problem is decidable, are all RE languages decidable?

While we know for sure that the halting problem is (and always will be) undecidable by a Turing machine, we can take the following approach to investigate your question:

Assume that we have a magical machine that can solve the halting problem. We call this machine an oracle. We can now wire this machine into a Turing machine, creating Turing machines that can solve the halting problem.

Unfortunately, the same problem we had with the original Turing machines occurs again: we can enumerate our oracle-enriched Turing machines. We can define the function that computes $T_i(i)+1$. This function cannot occur in our enumeration, because it differs from all Turing machines. In short, if we have machines that can solve the halting problem, we get a new halting problem for those machines.

This principle gives us a hierarchy of uncomputable functions (called the Turing hierarchy). Some functions become computable if we have machines with an oracle for the first halting problem, while others stay incomputable. If we give our machines an oracle for the second level halting problems, more functions become computable, but some functions will always be uncomputable.

And yes, languages that are only recursively enumerable to regular Turing machines are fully recursive to oracle-enriched Turing machines. Let's use the following definitions:

A recursive set is one for which there exists a TM which can answer yes if a given element is in the set, and no if it isn't.
A recursively enumerable set is one for which there exists a TM which can answer yes if a given element is in the set and compute indefinitely if it isn't.

In the second case, we can create an oracle enriched TM which checks if the non-enriched TM halts. So the enriched TM can give a yes-or-no answer.

Of course, there will be new languages which are recursively enumerable in the oracle-enriched world, but not recursive. In the non-enriched world, these languages were not enumerable in any way.

NB: In general, the phrase 'oracle' can mean any addition to enrich a Turing machine, not just one to solve the halting problem. If the type of oracle isn't clear from context a phrase like "a Turing machine with an oracle for the halting problem" should be used to avoid confusion.


On the generalization of two recreational problems: request for references, if there's any

The first problem is well-known. Lots of different generalizations appear in this paper, which is listed in the Wikipedia entry on the 12 coins problem.

I've never heard of the second problem, but it is similar in spirit to the carrom board puzzle (which probably goes under other names as well), described in a note by Dijkstra. A further generalization appears in this writeup.


how does an object find the reference to its instance variables

Since the class is fixed in advance in C++-style languages, the offset to a5 or a450 is known in advance, in compile time. Each instance of the class contains a copy of each instance variable at a fixed location (relative to the address of the instance), so there is no "load factor" to talk about. So myObject.a5 translates to something like myObject[5].

Other programming languages such as python support dynamic addition of instance variables. In that case the instance variables are stored in a hash table, which as you mention has $O(1)$ amortized access time. (Perhaps some instance variables are stored in fixed locations, for the sake of optimization.)


Best sort method for median: median heap or insertion sort on a vector

You are asking many questions, and I will only answer two of them. If you have a sorted vector of length $n$ followed by $m$ unsorted elements, the best way to sort the entire vector is to use an $O(m\log m)$ sorting algorithm on the tail, and then merge the two sorted lists in $O(n+m)$. The total running time is $O(n+m\log m)$, which is $O(n)$ if $m = O(n/\log n)$. If $m = \omega(n/\log n)$ then the problem is more complicated; asymptotically optimal bounds are known in the decision tree model, but I'm not sure they can be implemented efficiently enough (see for example Kahn ad Kim, Entropy and Sorting).

Another question, which you haven't actually asked, is about lower bounds. Suppose that you have a data structure in which insert takes (amortized) time $\alpha(n)$ and median takes (amortized) time $\beta(n)$, where $n$ is the number of elements in the structure. Suppose further that $\alpha(O(n)) = O(\alpha(n))$ and $\beta(O(n)) = O(\beta(n))$, and that $\alpha,\beta$ are monotone (this is the case for functions of the type $\Theta(n^s\log^t n)$). Then $\alpha(n) + \beta(n) = \Omega(\log n)$, assuming the operations are implemented using the comparison model (two datums can be compared, but are otherwise completely opaque).

For the proof, here is how to sort a list of length $n$. First insert the list. Then, extract the median, add $-\infty$ (or the minimum value) twice, and repeat. You recover the sorted lower half of the list. Now add enough copies of $+\infty$ (or the maximum value), and recover similarly the upper half of the list. This requires at most $O(n\alpha(O(n)) + n\beta(O(n))) = O(n(\alpha(n)+\beta(n)))$. In the comparison model, there is a lower bound of $\Omega(n\log n)$, so $\alpha(n) + \beta(n) = \Omega(\log n)$.


How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

If the case arrives where you see the case of a node being already visited but it is the parent of your current node, you just have to check whether there is a double edge between them. How to do that depends on your data structure, but if your adjacency list is sorted it would just amount to searching for the edge and checking how often it is in there.

Another problem I see is that your adjacency list doesn't actually contain any information that the edge is doubled.

For directed graphs, you can just completely get rid of the "parent check", as the only time that case arrives is when you have two edges going from $u$ to $v$ and vice versa.

Additionally, be careful if the graph is not connected, your BFS will not cover all of it, so you would need to start another BFS from an unvisited vertex again. This is especially important for directed graphs, as even if the graph might be connected, your BFS will probably not cover all of it.


Analysis of time complexity of travelling salesman problem

When solving TSP using dynamic programming you get something akin to the following:

TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

(neighbors only returns target as a viable neighbor if no other choice is available)

This algorithm recursively finds the shortest tour starting from each neighbor and returns the minimum of those. If you do all this with dynamic programming you can calculate the amount of work you're doing like so:
There are $n$ possible start vertices and $2^n$ possible subgraphs. So this function will be called on at most $n\cdot2^n$ distinct arguments (the target never changes). Each call performs at most $O(n)$ work (there are at most $n$ neighbors). Hence the total work you're doing is $O(n^2\,2^n)$.


Solving recurrence relation for running time of combination formula

Let $C(n,k) = T(n,k) + 1$. Then
$$ C(n,k) = C(n-1,k-1) + C(n-1,k). $$
This is exactly the recurrence of binomial coefficients, though there are also other solutions, for example $2^n$.
You can take the initial conditions to be $T(n,n) = T(n,0) = 1$, and so $C(n,n) = C(n,0) = 2$. You can check that
$$ C(n,k) = 2\binom{n}{k} $$
satisfies both the initial conditions and the recurrence relation. Hence
$$ T(n,k) = 2\binom{n}{k} - 1. $$


Is integer sorting possible in O(n) in the transdichotomous model?

Integers can be stably sorted in $O(n)$ time with $O(1)$ additional space. More precisely, if you have $n$ integers in the range $[1, n^c]$, the can be sorted in O(n) time.

This was only shown a couple of years ago by a team including the late Mihai Pătrașcu (which should surprise nobody who is familiar with his work). It's a remarkable result which I'm surprised more people don't know about, because it means that the problem of sorting integers is (theoretically) solved.

There is a practical algorithm (given in the paper above) if you're allowed to modify keys. Basically, you can compress sorted integers more than you can compress unsorted integers, and the extra space that you gain is precisely equal to the extra memory needed to do the radix sort. They also give an impractical algorithm which supports read-only keys.


What's an example of an unsatisfiable 3-CNF formula?

Technically, you can write $x\wedge \neg x$ in 3-CNF as $(x\vee x\vee x)\wedge (\neg x\vee \neg x\vee \neg x)$, but you probably want a "real" example.

In that case, a 3CNF formula needs at least 3 variables. Since each clause rules out exactly one assignment, that means you need at least $2^3=8$ clauses in order to have a non-satisfiable formula. Indeed, the simplest one is:

$$(x\vee y\vee z)\wedge (x\vee y\vee \neg z)\wedge (x\vee \neg y\vee z)\wedge(x\vee \neg y\vee \neg z)\wedge(\neg x\vee y\vee z)\wedge(\neg x\vee y\vee \neg z)\wedge(\neg x\vee \neg y\vee z)\wedge(\neg x\vee \neg y\vee \neg z)$$
It is not hard to see that this formula is unsatsifiable.


Hashing methods for validating dowloaded files

There are several reasons why one might want to add some extra material to validate a downloaded file. Different reasons require different kinds of extra material.

Non-malicious corruption

A common type of corruption is that files get truncated. For this, the size is enough.

To detect accidental corruption of the downloaded file for hardware reasons (bits getting flipped, lost or reorderd in transit), any kind of checksum helps. It doesn't have to involve cryptography — for this purpose, MD5 is a little overkill, but suitable. Against accidental corruption, a well-designed checksum that can take $n$ different values has a probability of $1-\frac{1}{n}$ of detecting the corruption.

Malicious corruption, single-file scenario

Malicious corruption is another matter. Against malicious corruption, you need two things:

A known secure channel. Without something to bootstrap security, the recipient has no way to know that what they're getting isn't wholly coming from an adversary.
A cryptographic tie between the secure channel and the download channel.

The reason to have two separate channels is, to put it succinctly, bandwidth. The goal is to insert the downloaded file into a chain of trust that starts from a computer and its operating system, and may rely on additional assumptions, e.g. trust in a particular website.

An example of a channel separation is when you trust some website (hopefully served over HTTPS, but you don't trust the channel through which the file is downloaded. In practice, these days, often the file would be distributed on the same website, and a separate verification doesn't provide any additional security. However separate verification can still be useful, for example if you've already downloaded the file in the past, but you aren't sure whether your local copy is pristine or whether it's the right version.

To establish a cryptographic tie, the basic method is to use a cryptographic hash function: calculate the hash of the large file distributed through the insecure channel, and distribute the hash through the secure channel. One of the properties of a cryptographic hash $H$ is that it's infeasible to find $x' \neq x$ such that $H(x') = H(x)$ (second preimage resistance); here this means that it's impossible to generate a fake file that has the genuine hash.

MD5 was designed to be a cryptographic hash function, but it is now known not to be one. Its second preimage resistance is not broken yet, but due to the weaknesses that have been found in MD5, the cryptography community no longer trusts it for anything. What has been broken for MD5 is its collision resistance, i.e. there are cheap ways of generating $x \ne x'$ such that $\mathrm{MD5}(x) = \mathrm{MD5}(x')$. (Note the difference with second preimage resistance: here the adversary does not get to choose the hash value.)

In addition to the risk that an attack would be found on second preimage resistance, there's a reason not to use MD5 to verify that something is genuine. Because collisions can be generated, it's possible to perform a bait-and-switch attack:

Generate a file with “good” contents (e.g. well-behaved software), and another file with “bad” contents (e.g. malware).
Have people review the good file and give it a good reputation.
Distribute the bad file.

This attack can be performed without the distributor being aware, if they're redistributing third-party content (e.g. a picture whose bad version triggers an exploit in an image viewer).

The state of the art of cryptographic hash functions is the SHA-2 family (generally SHA-256 or SHA-512). (There are a few alternatives but they don't get used much in the real world as of 2017.) Cryptographic hash functions are designed for speed, and there is no meaningful difference between MD5 and SHA-256 in practice in most scenarios — I/O is usually the limiting factor, not computation.

Password hashes are a different kind of function (closely related to key stretching) which are used in a specific case: when the data to be hashed has to be secret and cannot be encrypted (in the case of a password, the objective is to make the password hard to guess even if the adversary obtains all the information that the legitimate verifier has, including any encryption keys). Password hashes need to be slow to limit the impact of brute force guess attempts. Hashes used in other scenarios don't need this and are designed for speed.

A cryptographic hash function is a way to expand integrity. Assuming the integrity of the channel through which you obtain the hash, you get a guarantee of integrity of the hashed data.

A hash does not guarantee authenticity: it doesn't say who made this file. Anybody can calculate the hash of a file. To know that the file is authentic, you need to trust the authenticity of the channel through which you receive the hash.

Malicious corruption: many-files scenario

There is another useful cryptographic primitive that is useful to distribute files: signatures. Where a hash propagates integrity, a signature propagates authenticity. Suppose you have a public key distributed through a secure channel (as in, a channel that guarantees the authenticity of the data, i.e. you know who the public key came from, and that it wasn't corrupted in transit). Then you can retrieve a signed file distributed through an insecure channel, and verify whether it has a correct signature. Whereas anybody can calculate the hash of a file, generating a valid signature requires the knowledge of the private key that is associated of a public key.

A signature allows distributing a single datum through the secure channel (the public key) and many large files through the insecure channel. In particular, if the distributor wants to distribute a new file, they can sign it and they don't have to update anything through the secure channel. So the secure channel can be offline, e.g. an operating system image.

The next level after signatures is signatures of signatures. For a file distribution mechanism, signatures introduce a bottleneck: the holder of the private key has to sign all the files. A mechanism where one entity signs other entities' public keys is called a public key infrastructure.

Note that signatures ensure that correctly-signed data is genuine, but they do not assure freshness — they do not protect against attacks such as replay attacks. The correctness of a signature is a mathematical property and does not decay in time. An attacker could, for example, hide a security update by continuing to distribute the old, vulnerable version of some software, even after a fix has been published. Protecting against such attacks requires verifying the freshness of a file via a secure channel (here, the security properties required from the channel are freshness and authenticity). This doesn't have to involve cryptography (beyond any cryptography that might be involved in the secure channel), it can be a simple check of a version number or publication date.


Proof of QuickSort algorithm correctness

First, you need to write down your algorithm that you call "Quicksort" precisely. The devil is in the detail, and if your code doesn't get the details right, then it won't sort correctly (or you won't be able to prove that it sorts).

And then you need to use complete induction: Take the induction statement S(N) "My algorithm will sort any subarray with n ≤ N items correctly". The more obvious statement S'(N) "My algorithm will sort any subarray with N items correctly" isn't strong enough.

Next you prove S(1): If the array has 0 or 1 elements, does your algorithm sort it correctly? Most implementations will check that there are two or more elements as their very first step, and subarrays with 0 or 1 elements are sorted, so this should be no problem.

Then you need to prove that S(N) implies S(N+1). If S(N) is true, then any subarray of size n ≤ N will be sorted correctly, so only the case of an array with N+1 elements needs to be handled. Here you have to prove that one Quicksort step will divide an array of N+1 into two subarrays of size ≤ N, with each element of the left subarray <= each element of the right subarray, and no overlap.

PS You will always end up with an induction proof, more or less disguised. For example: Assume there is an array that doesn’t get sorted correctly by Quicksort. If there is any array, then there must be a smallest array that doesn’t get sorted. Take that array, pick the pivot and create two sub arrays, a left one and a right one. Sort both sub arrays with Quicksort. Since they are both smaller than the smallest array that isn’t sorted correctly, they will be sorted correctly. So Quicksort works.

That’s a property of the integers: if a set of positive integers is not empty, then it has a smallest element. Take the set of all sizes of arrays that are not correctly sorted by Quicksort. If that set is not empty, then it has a smallest element, and therefore there is a smallest array that cannot be sorted. And then you prove that the smallest array that cannot be sorted can indeed be sorted, so your assumption that some array cannot be sorted was wrong.


Algorithmic information theory with stochastic algorithms?

One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\{\mathcal{P}_n\}_{n\in\mathbb{N}}$ where $\mathcal{P}_n$ is a distribution over $\{0,1\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial time algorithm $A$ such that $A(1^n)\sim \mathcal{P}_n$. Your white noise example translates in this case to the uniform distribution being easy (samplable). These notion often arise  in average case complexity, where one cares about the average hardness of computing a function relative to some backgroud distribution over the inputs. A straightforward generalization of this would be to restrict the distance (total variation/KL) between $A(1^n)$ and $\mathcal{P}_n$.
In any case, whenever one is interested in computational hardness, you would probably have to introduce a family of objects rather than talk about the complexity of a specific member.


Comparing coefficients of boolean functions

Consider the function $P(x_1) = x_1$. Then $P(0) = 0$, $P(1) = 1$, and the polynomial representation is $x_1$, but your formula gives $c_0 = 1$ and $c_1 = -1$. However, if we define $\hat{P}(b) = 2^{-n} \sum_{a \in \{0,1\}^n} (-1)^{\langle a,b \rangle} P(a)$ then
$$ P(x) = \sum_{b \in \{0,1\}^n} \hat{P}(b) (-1)^{\langle x,b \rangle}. $$
This is known as the Fourier expansion of $P$. To relate this to your expansion, notice that
$$ (-1)^{\langle x,b \rangle} = \prod_{i\colon b_i=1} (-1)^{x_i} = \prod_{i\colon b_i=1} (1-2x_i). $$
It is now an exercise to relate the coefficients $\hat{P}(b)$ to the coefficients $c_b$ you are interested in.


Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time?

This is variation of Longest increasing subsequence problem; this is the solution presented on Wikipedia using two auxiliary arrays $M$ and $P$:

  $M[j]$ — stores the position $k$ of the smallest value $A[k]$ such that there is an increasing subsequence of length $j$ ending at $A[k]$ on the
  range $k \leq i$ (note we have $j \leq k \leq i$ here, because $j$ represents the
  length of the increasing subsequence, and $k$ represents the position of
  its termination. Obviously, we can never have an increasing
  subsequence of length $13$ ending at position $11$. $k \leq i$ by definition).
  $P[k]$ — stores the position of the predecessor of $A[k]$ in the longest increasing subsequence ending at $A[k]$.

  In addition the algorithm stores a variable $L$ representing the length
  of the longest increasing subsequence found so far.

This algorithm runs in worst-case time $\Theta(n\log n)$. Your problem is a special case that allows you to return when $L=3$ which pushes runtime down to $O(n)$ because the binary search runs only on arrays of length at most two, which is therefore in time $O(1)$ as opposed to $\Theta(\log n)$ in the general case.

Consider the modified pseudo code:

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
   if L==3 : return true; // you can break here, and return true.
return false; // because L is smaller than 3.


All context free languages can be recognized in polynomial time:

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


Here is how to analyze a starting configuration to determine whether the message will be able to eventually reach all nodes in the grid.

Consider two adjacent nodes $u,v$.  We'll say that these two nodes are connected if at some point during the first four time steps, node $u$'s active edge points to $v$ and node $v$'s active edge points to $u$.  In other words, nodes $u,v$ are connected if one (or both) of the following two conditions holds:

In the initial configuration, $u$'s active edge points to $v$ and $v$'s active edge points to $u$.
$u$ rotates in the opposite direction as $v$.

Construct an undirected graph $G$ with one vertex per node in the cell, and an edge $(u,v)$ between two vertices iff they are connected (per the above definition).  Then a necessary and sufficient condition for the message to be able to reach all nodes in the grid is that the graph $G$ must be connected.

It's also possible to use this kind of analysis to determine the shortest time necessary before the message reaches all nodes, with running time linear in the size of the graph.

In particular, we can build a directed graph $G'$ with one vertex $(i,j,k)$ per cell $(i,j)$ and value $k \in \{0,1,2,3\}$.  (We will interpret $k$ as the time, modulo 4.)  This graph has a directed edge $(i,j,k) \to (i',j',k+1 \bmod 4)$ if $(i,j)$ is adjacent to $(i',j')$ and $(i,j)$'s active edge points to $(i',j')$ at time $k$ and $(i',j')$'s active edge points to $(i,j)$ at time $k$.

Now we use breadth-first search to find the shortest path from $(i_0,j_0,0)$ to every other vertex, where $(i_0,j_0)$ is the cell where the message starts.  We define

$$f(i,j) = \min\{d((i_0,j_0,0),(i,j,k)) : k=0,1,2,3\}$$

where $d(u,v)$ is the length of the shortest path from vertex $u$ to vertex $v$ in $G'$.  Finally, $\max_{i,j} f(i,j)$ is the shortest time necessary for the message to reach all nodes.  The running time of this algorithm is $O(mn)$, i.e., it runs in linear time (linear in the size of the input).


In what situations should a particular sorting algorithm, such as heap sort, be chosen over others?

Most programming language standard libraries come equipped with one or more built-in sort routines these days. Most of the time, that's what you want.

"Library sort" algorithms tend to use a combination of basic sort algorithms that you've seen in class, and tune themselves either at compile time or at run time.

That's why, for example, the standard library sort in C++ might use merge sort on linked lists and quick sort on arrays. And a typical industrial-strength quick sort implementation will revert to insertion sort on small intervals, or heap sort if the partitioning strategy seems to be going awry.

Most library sorts are comparison-based because of external constraints. They must work on user-defined data types, for example, and it's typically much easier for the user of such a sort algorithm to supply a comparison operation than, say, a radix extraction operation. Moreover, users often want to sort on secondary keys if primary keys are equal (e.g. surname then first name). It's much easier to express this in terms of comparison rather than some other formulation.

I've been in the business a long time, and there's really only a few times I can think of where writing my own sort was the best option. Two examples that are easy to explain:

First example: I wrote the sort subsystem for a database server. It me about six months. As with library sorts, it used a combination of sort algorithms and adjusted its behaviour depending on what situation it found itself in. Sorting database records is an interesting case because accessing the sort key is sometimes the most expensive operation; disk seeks are one of the most expensive things there is, especially if the disk is network-attached.

The main idea which cracked this problem was to use the fact that users almost always wanted to sort on multiple keys. So I used partitioning sort algorithms which discovered "ranges" where the primary sort key was the same. Secondary keys are only needed to resolve those ranges. Many sort algorithms (e.g. ternary quick sort, radix sort) can be adapted to return ranges.

Second example: I wrote some firmware which needed to read about 1000 values from a hardware device, and then do quantile extraction. The complication is that the microcontroller that this ran on had essentially no extra read-write memory available, so algorithms like radix sort or quick sort were not an option. I used Shell sort, which was by far the best tradeoff.

There's a bunch of special-case information that everyone who has worked with sorting knows, such as "bubble sort is always worse than insertion sort", and "heap sort has terrible constant factors; last resort only". But this general advice is probably all you need to know:

The best sort algorithm is the one that fits the peculiarities of your data and your platform.
The second-best sort algorithm is one you didn't have to write.
Make sure that sort is a bottleneck before getting fancy.

Knowing lots of sort algorithms is good for you, but not necessarily to the point where you can implement them from memory. Knowing that there is a tradeoff is more valuable knowledge than what the tradeoffs actually are. Then, when you come across one of those few times where you need to write your own sort, you'll know where to look.


What is the difference between the Mogensen-Scott and the Boehm-Berarducci encoding for ADTs on the Lambda Calculus?

The Boehm–Berarducci encoding is often mistakenly referred to as the "Church" encoding. They both start from the same general idea (encode data types by their iterator/catamorphism), but differ in subtle ways. In particular, the Church encoding only represents data types in the untyped setting, only covers introduction, and is not tight; whereas, the Boehm–Berarducci encoding works in System F, covers both introduction and elimination, and proves that the encoding is tight.

For an extensive discussion of the differences, see this post by Oleg Kiselyov.


Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

No.  The intermediate matrices $A^{2^t}$ don't need to be stored anywhere.  When you need a value, you just recompute it.  This might sound very inefficient -- but remember, we're only counting the space complexity here, not the time complexity, so it's fine to take a very long time to recompute the same value many times, if that saves you some space.


Assign numbers to letters with respect to lowest graph peaks

This smells like it might be hard (e.g., NP-hard).

Therefore, I suggest solving it with a SAT solver.  SAT solvers implement a number of clever optimizations.  Rather than trying to devise custom optimizations for this specific problem, you might try using an off-the-shelf SAT solver: that might be a much more efficient use of your time.  In particular, here's what I would try.  I would formulate the problem as follows:

Input: a string $S$ with $n$ unique letters, an integer $d$

Question: is there an assignment that maps each letter to a different number in $\{1,2,\dots,n\}$, such that any pair of adjacent letters are mapped to numbers that differ by at most $d$?

You can then formulate this as a SAT instance, in a fairly straightforward way.  For instance, you can use a one-hot encoding: introduce boolean variables $x_{c,j}$, where $x_{c,j}=$ True means that the letter $c$ is mapped to the number $j$.  Now if letters $c,c'$ are adjacent in the string $S$, you get a constraint $\bigvee_{|j-j'|\le d} (x_{c,j} \land x_{c',j'})$.  You also get constraints forcing different letters to map to different numbers.

Finally, throw this to an off-the-shelf SAT solver.  If it finds a solution, you know that distance $d$ is achievable.  Otherwise, it's not: distance $d$ is unattainable.  You can now iterate over $d=1$, $d=2$, $d=3$, etc., until you get the first solution.  (You can also try binary search, but I suspect it might be less efficient.)

This doesn't account for peaks, because I couldn't understand your definition of the peak stuff.


Context-freeness of $\{a^nb^mc^k \mid n \leq m \leq k\}$ and its complement

The language $L_1$ is not context-free, and you can show this using the pumping lemma. Try to pump the word $a^nb^nc^n$ where $n$ is large enough.

The language $L_2$, in turn, is context-free. This is because we can write it as a union of context-free languages:

Words not of the form $a^*b^*c^*$.
Words of the form $a^nb^mc^k$ where $n>m$.
Words of the form $a^nb^mc^k$ where $m>k$.


Assume there are 2^n symbols, n >= 2, and the frequencies of the most common and the two least common symbols are f, g, and h. We could use a code of n-1 bits for the most common and n+1 bits for the two least common symbols. This will reduce the average code length if f > g+h.
You were specifically asking for the frequencies 2^-n + c/2, 2^-n, and 2^-n - c/2, so that’s the case for c > 2^-n / 2.


I think the reference for many optimization and structural problem is Schrijver's book:

Combinatorial Optimization - Polyhedra and Efficiency

In the case, you do not have access to the book you can find his lecture notes on disjoint paths, but it's not complete, and is not comparable to the book.

Circulation is just a general definition and it's not important alone, it's important with given underling context, e.g here difference between the muticommodity circulation is just we have multiple circulation (no matter if all of them are 0), but if we want to use it for the muticommodity integer flow problem we cannot reduce it to the normal flow unless $P=NP$.

As a side note: In the Schrijver's book circulation does not include lower bound or upper bound, just flow's conservation rule holds.

This is the definition of circulation in that book:

Circulation:

  Let $D = (V,A)$ be a digraph. A function $f : A \rightarrow R$ is
  called a circulation if
       $f(\delta^{in}(v)) = f(\delta^{out}(v))$
  for each vertex $v \in V$ . So now the flow conservation law holds in
  each vertex $v$. (in page 171)

And:

  $δ^{in}(v)$ := set of arcs entering $v$, $δ^{out}(v)$ := set of arcs
  leaving $v$. (in page 29)

The corresponding problem is defined as follow:

Circulation Problem:

  Input: Let $D = (V,A)$ be a digraph and let $d, c : A → Q$ with $d ≤ c$.
  Question: Is there a circulation $f$ satisfying $d ≤ f ≤ c$. (page 175, with a little variation).

But the minimum-cost circulation problem is as follow:

Minimum-Cost Circulation Problem:

  Input: A digraph $D = (V,A)$, a demand function $d : A → Q$, a capacity function $c : A → Q$, and a cost function $k : A → Q$.
  Question: Find a circulation f subject to $d ≤ f ≤ c$, minimizing $\text{cost}(f)$. (Page 177).

Finally I should mention that, I didn't see the multicommodity circulation definition (or corresponding problem) explicitly, and in my opinion, as I mentioned at start is not important alone. But I do agree with the owner of problem, that wikipedia's definition is not good, and the definition provided in this question is better and more precise than the wiki's.


Rules to follow to create edges in graph

A graph that is both directed and undirected is called a Mixed graph.

All graph libraries that I know don't have direction dependent edge properties. Hence I would advise against introducing them if two directed edges do the job.


What is the decision version of integer programming?

It's the same was for all NP problems; the optimisation problem is

  Find a valid solution $s$ that minimises¹ $f(s)$!

and the corresponding decision problem is

  Is there a valid solution $s$ with $f(s) \leq k$?

You see that the former immediately solves the latter, and you can solve the former by using the latter with binary search over the set of feasible $k$.

Of course, you can have "maximise" here and "$\geq k$" in the decision version.


Is it possible to design a C++ like language without a Preprocessor?

Yes, it's entirely possible.

For example, you can define the language as requiring at least a minimal degree of dead-code elimination, so (for example) something like:

const bool debug = false;

if (debug)
    whatever();

...requires that not only is whatever() not called, but that it produce code that does not refer to whatever at all.

This gives roughly the same effect as something like:

#if debug
    whatever();
#endif

...would in C or C++. The only obvious difference is that by including the capability in the language, you typically require that the contents of the condition be syntactically correct for the target programming language (whereas C and C++ allow an #ifdef block to contain code that isn't syntactically correct C or C++, as long as the preprocessor can still detect the matching #endif).

Now, in some cases it's easy to require things that nobody knows how to do, thus producing a specification that nobody can implement. That would not be the case here though: compilers that can do the optimization above already exist.

Ada, for one example, includes a great deal of ability to tailor code to a specific platform without using a preprocessor like C and C++ do. In fact, it (Ada) arguably supports quite a bit more than C and C++ do in this regard.


Upper bound for set disjointness under product distributions

During the first phase of the algorithm, the players zoom in on a high-entropy coordinate. They exchange $O(1)$ bits, and stop at each step with probability $\Omega(\epsilon^2/\log^2(1/\epsilon))$ (here we use independence). Hence this phase uses up at most $O(\log^2(1/\epsilon)/\epsilon^2)$ bits in expectation. The second phase uses $O(n\epsilon)$ bits. In total, we used this many bits in expectation:
$$
O(\log^2 (1/\epsilon)/\epsilon^2 + \epsilon n).
$$
Choose $\epsilon = 1/n^{1/3}$ to obtain the stated bound.

Without independence, we don't have any control on the stopping probability at each step of the first phase. For example, it could be that $X$ is sampled uniformly at random, and $Y$ is the negation of $X$. In this case the first phase will never stop, and so the protocol will always use $2n$ bits.

As an aside, the upper bound can be improved to $O(\sqrt{n} \log n)$, which almost matches the lower bound $\Omega(\sqrt{n})$ (the gap might have been closed in the literature). See lecture notes of Prahladh Harsha.


shortest cost tiling of path to x distance

You're heading a good direction with dynamic programming, but you haven't set up the set of subproblems quite right just yet.  Don't give up on it yet.  Instead, you should keep exploring some more candidate sets of subproblems.

The art of dynamic programming lies in picking the right set of subproblems, and then identifying a suitable recurrence relation in terms of those subproblems.  Sometimes you'll have to try several possible ways of decomposing into subproblems before you find something that works, so don't give up if your first try is not a success!

Here are some hints to help you:

When one of your inputs is an array, you can try using "the set of prefixes of the array" as your set of subproblems.  In other words, if the input is an array A[0..n-1], your subproblems can be all of the prefixes A[0..j-1], where j=0,1,2,..,n-1 (this gives n subproblems).
When one of your inputs is a non-negative integer, you can try using "the set of non-negative integers no larger than the input" as your set of subproblems.  In other words, if the input is a non-negative integer m, your subproblems can be all of the integers i, where i=0,1,2,..,m.
When you have two inputs, there are some possibilities to choose a set of subproblems.  One way is to hold one of the inputs fixed and consider all subproblems for the other input.  Another way is to choose all pairs of subproblems (if $S$ is the set of subproblems for the first input, and $T$ is the set of subproblems for the second input, use $S \times T$ as your set of subproblems).

Also, you set up your dynamic programming implementation wrong.  Your goal should not be to maximize the number of price, or to maximize anything.  You are trying to minimize the total cost (so Math.max is out of place here).  Also you will need to pass in something that describes both the cost and the length of each tile; your code doesn't show anything about that.

Finally, don't write code now.  Just figure out the ideas.  Write down a recurrence relation, and try to check whether it is correct.  Then, write pseudocode and show it is correct.  Only then should you write code.  Diving straight into code is a mistake and is getting you mixed up in implementation details before you've even worked out the conceptual material.  Also, on this site, you should not be showing us code: you should be showing us algorithms and pseudocode.  This site is about algorithms, not code (StackOverflow is the place for code).

These hints should be enough to enable you to find a solution via dynamic programming (i.e., an efficient algorithm that always finds the least-cost tiling, with reasonable running time).