Can a total programming language be Turing-complete?

I'm pretty sure McBride isn't claiming that a total programming language can be Turing complete, just that it's a useless distinction in practice. You can take any program in a partial language and replace all not-provably-terminating loops with loops that run at most $2^{128}$ times, and the result is theoretically different but not observably different.

You exactly get to say “we know how to run it for as long as we’re willing to wait, but we can’t promise you it will stop”, which is [...] exactly the deal when you work in a partial language.

I.e. maximum run times are bounded in the real world.

The only difference is that when you promise something does work, you’re believable. The expressive weakness is on the partial side.

I.e. there's an expressivity tradeoff in using total vs partial languages, but the expressive advantage of total languages is useful in practice, while the theoretical expressive advantage of partial languages has no practical consequence.

Edit: In response to OP's comment, I think ruakh's comment is correct. McBride is implicitly suggesting that a better notion of completeness ought to not only replace Turing completeness as the de facto standard for real-world languages, but also take the name of Turing completeness and the brand identity associated with it, because it's more deserving of it. Maybe it would be more accurate to say he thinks the better notion of completeness ought to have been called Turing completeness from the beginning. It matters because the perception that total languages are deficient in some practical way, due to their lack of Turing completeness, may have actually hindered their real-world adoption.


No, it is not true. Consider the graph with vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 34, 45, 46, 56, 61. The dfs starting at vertex 1 yields two back egdes for the cycle (1,2,3,4,6).


Existence of NP problems with complexity intermediate between P and NP-hard

The result you're describing is called 'Ladner's Theorem.'  The Wikipedia article on 'NP-Intermediate' is probably a good place to start - you can find references to Ladner's original paper there.

There's also an extensive list of such problems on the cstheory Stackexchange.

For a couple of proofs of Ladner's Theorem, check out this note adapted from Downy & Fortnow's paper 'Uniformly Hard Languages'.


does order matter when two different derivations are to be made for ambiguous grammar

You are deriving different strings. The definition of ambiguity asks for the very same string.

In this case, that they "mean the same thing" in algebra, due to the commutative law for multiplication, is completely off topic.


Maximum value a variable can hold without documentation

The first step should be

count = 0
while (x*2 > x)
  x = x*2
  count++

to find the largest power of 2 that can fit into the variable. Note that doing +1 instead of *2 is not only much slower but also fails for floating point numbers (the gaps between large consecutive floating point numbers are bigger than 1). The above procedure should work for both numbers that roll over and numbers that reach infinity.

Once you have a rough estimate, you may perform a binary search in the range from estimate, to 2*estimate to find an exact bound.


Sum number of times statement is executed in triple nested loop

The Wolfram Alpha answer isn't quite correct - you're off by one in each sum - the loop will iterate over $\{1,...,n-1\}$, not $\{1,...,n\}$, though other than that your reasoning is sound. What you should be asking W/A for is:

$$
\sum^{n-1}_{i=0}\sum^{i-1}_{j=0}\sum^{j-1}_{k=0} 1
$$

If you break the sums down bit by bit it gets a little easier to swallow, just start at the innermost sum and work outwards. It's probably fairly obvious that $\sum^{j-1}_{k=0}1 = j$, which breaks the triple-sum down into $\sum^{n-1}_{i=0}\sum^{i-1}_{j=0}j$.

We have that $\sum^{i-1}_{j=0}j = \frac{1}{2}(i^2-i)$, so what was a double sum is now the difference of two sums, $\frac{1}{2}(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i)$.

The second term has already been worked out, and we have that $\sum^{n-1}_{i=0}i^2 = \frac{n(n-1)(2n-1)}{6}$. From there, you should be able to work out your answer;

\begin{align*}
\frac{1}{2}\left(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i\right)
&= \frac{1}{2}\left(\frac{n(n-1)(2n-1)}{6} - \frac{3n(n-1)}{6} \right)\\
&= \frac{1}{2}\left((2n-1)\frac{n(n-1)}{6} - 3\frac{n(n-1)}{6} \right)\\
&= \frac{n(n-1)(2n-4)}{12}\\
&= \frac{n(n-1)(n-2)}{6}
\end{align*}

The results about the sum of the first $n-1$ numbers and the sum of the first $n-1$ square numbers are fairly standard ones - if you want some proofs of them then this page gives some nice arguments, though note that their sums end at $n$ and not $n-1$.


Proof that there are same number rotation moves in any binary tree with both children compulsory

Each rotation involves a node and its left or right child. We can associate this rotation with the child – the rotation is fixed once the child is known. In your case, a child can be rotated as long as it is an internal node. So the number of possible rotations is the number of non-root internal nodes. A simple induction shows that a full binary tree having $n$ leaves has exactly $n-1$ internal nodes, and so $n-2$ non-root internal nodes.


Assigning keys to the nodes of a Binary search tree given its shape

Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.


Oh my. This seems like a confusion caused by the (old school) terminology of "finite-state language" as a synonym for what is known today as "regular language".

Anyways, the standard definitions for finite/infinite accepted these days regard only the size of the language:

a finite language is any set $L$ of strings, of finite cardinality, $|L|<\infty$.
an infinite language is any set $L$ of strings, of infinite ($\aleph_0$) cardinality $|L|=\infty$.

A finite $L$ is always regular.

An infinite $L$ can be regular (sometimes called "finite-state"), decidable (sometimes called "recursive"), non-regular (non-finite-state), non-decidable, etc.,


Find a minimum-weight perfect b-matching, where b is even

A subgraph in which each vertex has degree exactly $b$ is known as a $b$-factor. You are asking for something similar (but not identical) to the minimum weight $b$-factor.

Tutte showed how to reduce minimum weight $b$-factor to minimum weight perfect matching in his paper A short proof of the factor theorem for finite graphs.

We will split each vertex $v$ of degree $d(v)$ into $2d(v) - b$ vertices: $v_1,\ldots,v_{d(v)},v'_1,\ldots,v'_{d(v)-b}$ (we can assume that $d(v) \geq b$, since otherwise the graph has no $b$-factor). We lift each edge $(x,y)$ to an edge $(x_i,y_j)$ of the same weight in such a way that each $x_i$ and $y_j$ participates in exactly one such edge. We furthermore connect each $v_i$ to each $v'_j$ with a zero-weight edge, for all $i \in [d(v)]$ and $j \in [d(v)-b]$.

Each $b$-factor of the original graph corresponds to a matching in the new graph of the same weight. Indeed, lift the $b$-factor to the new graph, and for each vertex $v$, add an arbitrary matching between $v'_1,\ldots,v'_{d(v)-b}$ and the $d(v)-b$ new vertices corresponding to "unused ports".

Conversely, we can convert every matching in the new graph to a $b$-factor of the same weight in the original graph by undoing this construction.


Languages such that DFA requires $\Omega(c^k)$ states but NFA needs only $O(k)$ states?

The language $L_k$ that you list doesn't work.

There is a straightforward NFA for the language $L_k$ you list, with $k+1$ states.  It guesses where the suffix starts, then checks that the suffix is equal to $s_k$.

In particular, the NFA has states $0,1,\dots,k$, with transitions $0 \to 0$ on each symbol, transitions $i-1 \to i$ on the symbol that matches the $i$th character of $s_k$, and $k$ being an accepting state.

It follows, using the subset construction, that there exists a DFA with $2^{k+1}$ states.

Consequently, that language does not meet your requirements, if $c>2$.


Both suggestions in the comments in the OP were excellent and I agree with the users who provided them.  I have included these comments below for continuity:

There is en.wikipedia.org/wiki/Logic_synthesis but the general way of solving exercises in university is by understanding the material or asking your TAs if you have problems. – adrianN

Work with your peers. Students manage to pass the class somehow, so there must be a principled way. The course is designed to impart the mode of thinking which enables you to solve such exercises, but unfortunately the only way to accomplish this is by actually solving the exercises, on your own or together with friends. – Yuval Filmus

To assist you, look at the Wikipedia pages here and here on digital circuits/adders.

Also, ask your instructor and/or TA for suggestions on a good computer architecture and design book.


How can one search in O(log n) time in a red-black tree?

The search operation is the same for all binary search trees - recurse into the left or right branch depending on whether the element is smaller or larger than the current root. Red-black trees are not special.

The complexity of the search operation is equal to the height of the tree.

Different varieties of binary search trees differ in what guarantees on height of the tree they give, and in how exactly they maintain these guarantees. Red-black trees and AVL trees give you guaranteed O(log n) height, which is why search is O(log n).


Independence of order of insertion hashtable with open addressing

You can get from any order to any other order by making a series of swaps (see e.g., https://en.wikipedia.org/wiki/Cyclic_permutation#Transpositions).  So, if you can prove that making a single swap never changes the number of attempts, then it follows that the number of attempts does not depend on the order.


What does it mean when each individual array is sorted in different array but bear no relationship to each other

What they mean is exactly that: the invariant maintained by the data structure is that each of the arrays $A_0,\ldots,A_{k-1}$ is sorted. Nothing is maintained regarding the relative order of elements in different arrays.

The text probably goes on to describe how to perform the search, insert and delete operations. The search operation is simple: you just search the individual arrays. To insert an element, there are two cases: if $n$ is even, we just add a new array $A_0$ with the new element. Otherwise, choose the smallest $i$ such that $n_i = 0$ (possibly $i=k$). We add the new element to $A_0$, and then merge $A_0,\ldots,A_{i-1}$ to $A_i$ (in this order: merge $A_0$ and $A_1$ to $B_1$; merge $B_1$ and $A_2$ to $B_2$; and so on). Element deletion is more complicated; the data structure is only supposed to support search and insert.

The key idea is that when inserting an element, it is we (the designers of the data structure) who choose where to put it.

The text probably goes on to analyze the amortized cost of these operations. I'll leave these details to the text. (Unless it's an exercise, in which case you should work them out!)


$k$-coloring in BPP, implies $k$-coloring in ZPP

This statement is to my knowledge unknown. If this is an exercise, then it is likely an error: did they mean $RP$ instead of $ZPP$?

Since $k$-coloring is NP-complete, what you are asked to show is:

  If $NP \subseteq BPP$, then $NP = ZPP$.

First, let's review what is known: the basic inclusions are the following:
\begin{align*}
P \subseteq ZPP \subseteq RP &\subseteq NP \\
P \subseteq ZPP \subseteq coRP &\subseteq coNP \\
                          RP &\subseteq BPP \\
                          coRP &\subseteq BPP.
\end{align*}

That is, $P$ is contained in $ZPP = RP \cap coRP$, which is contained in $BPP$. Moreover, $RP$ is contained in $NP$ and $coRP$ is contained in $coNP$.
But we don't know how $NP$ and $coNP$ relate to $BPP$ (it is conjectured that $P = ZPP = BPP$, which implies that $NP$ and $coNP$ contain $BPP$).

Now, what happens if (as in your exercise) $NP \subseteq BPP$? It follows (and is a common exercise to show) that
$$
NP = RP.
$$

(see e.g. here).
That means that
$$
coRP = coNP \\
ZPP = NP \cap coNP \\
$$
So basically in this case, we have $P$, which contains $NP$ and $coNP$, and those are both contained in $BPP$ (which also equals the polynomial hierarchy $PH$).

But there is no reason to believe that this implies that $NP = coNP$, which is what you would need to then show that your $NP$-complete language, $k$-col, is in $ZPP = NP \cap coNP$. In particular, we can imagine that $BPP$ is equal to the second level of the polynomial hierarchy (you don't need to be familiar with this, but it's just some level that contains both $NP$ and $coNP$). That would imply that $NP$ is contained in $BPP$, but it doesn't mean that $NP$ and $coNP$ are equal.

TL;DR The statement you are trying to show appears to be unknown.


Longest common subsequence (not necessarily continuous) is the solution for the second problem, not for the first. (For the first problem it is not only slower than necessary, but also gives the wrong result. Consider e.g. $A=[1,2]$, $B=[2,1]$: LCS would give only 1 couple, while actually 2 can be formed.)

For the first problem, as @sai_preet pointed out in a comment, you can sort both arrays and then find the couples with a procedure analoguous to merge. This will take $\Theta(n\log n)$ time.


We define $S(m)$ to be $T(2^m)$, for every possible value of $m$. Changing the name of the variable, $S(M) = T(2^M)$ for every value of $M$. Substituting $M := m/2$, we get $S(m/2) = T(2^{m/2})$.

As an example, suppose that $T$ is the identity function: $T(n) = n$. We define $S(m) = T(2^m) = 2^m$. Then $S(m/2) = 2^{m/2}$.


Maximal minimal DFA for some language of n-bit strings

Your question is solved in Cezar Câmpeanu and Wing Hong Ho, The Maximum State Complexity for Finite Languages, Corollary 10.


Real world applications of first order logic

If you want a specific example, IBM Watson should qualify. Check the links for details on how they use Prolog. I'd say that Prolog made a huge hype in its day, and most real today's system are based on different principles rather than "first-order logic programming" in narrow sense. However, there is definitely a niche for this approach. We live in the age of other hypes, that's it.


How to simulate this randomized "finite" sum?

Let me give you some basic principles that seem helpful for your problem:

How to estimate an expected value. You want to estimate $\mathbb{E}[Y]$.  Here's a standard fact: if you can sample from the distribution of $Y$, then you can estimate $\mathbb{E}[Y]$.  Concisely, what you do is sample $n$ values according to the distribution of $Y$, then take their average; the result is a pretty good estimate for $\mathbb{E}[Y]$.  The larger the value of $n$, the more accurate your estimate will be.

With more mathematical precision: let $y_1,\dots,y_n$ be the result of sampling $n$ times from the distribution of $Y$.  This means that they come from i.i.d. r.v.'s with the same distribution as $Y$.  Now let $\hat{y} = (y_1+\dots + y_n)/n$ be the average of these values.  Then it follows that $\hat{y}$ is a good estimate for $\mathbb{E}[Y]$ (with high probability).  In particular, $\mathbb{E}[\hat{y}] = (\mathbb{E}[y_1]+\dots + \mathbb{E}[y_n])/n = (\mathbb{E}[Y]+\dots + \mathbb{E}[Y])/n = \mathbb{E}[Y]$, so $\hat{y}$ is an unbiased estimator for $\mathbb{E}[Y]$.  Also, by a similar calculation, $\text{Var}[\hat{y}] = \text{Var}[Y]/n$; the interpretation of this is that the error in your estimate of $\mathbb{E}[Y]$ will typically be roughly on the order of $\sigma/\sqrt{n}$, where $\sigma = \sqrt{\text{Var}[Y]}$ is the standard deviation of $Y$.  Thus, if $Y$ has variance that is not too large, then this approach gives a reasonably accurate estimate of $\mathbb{E}[Y]$.

In your case, this shows how to answer your second question: if you can sample from $Y$, this gives you one candidate way to estimate $\mathbb{E}[Y]$.  There are other ways to get an estimate, but this is a simple method that applies whenever you know how to sample from the underlying distribution.
How to sample from a sum of random length. The next question is, how to sample from $Y$?  The challenge you seem to be struggling with is how to deal with the fact that the definition of $Y$ is as a sum containing $N$ terms, but where here $N$ is a random variable.

It turns out there is a simple way to deal with this.  In particular, you can sample from $N$ by using the following process:

Sample from $N$, i.e., pick a random value for $N$ by sampling from a geometric distribution (since that's the distribution of $N$).
Now you have a fixed, constant value for $N$, so it becomes easy to sample from $Y$.  In particular, for this fixed value of $N$, sample a random value for $F_1,F_2,\dots,F_{N+1}$ (according to the distribution of these random variables).  Then, plug those values into the definition of $Y$; the result will be a random value for $Y$, picked according to the correct definition for $Y$.

In general, if you have a random variable that is defined by some stochastic process, then you can sample from it by simulating the process, sampling from random values whenever the process does.

So, let me spell out the implications for you.  This means that if you can figure out how to sample from the distribution of $F_i$, then you can use the above two techniques to sample from the distribution of $Y$ and thereby estimate the value of $\mathbb{E}[Y]$.  This reduces your problem to a smaller/simpler one: figuring out how to sample random values, distributed according to the distribution of $F_i$.


Is there any strategy to brute force search?

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.


print the nodes of an immutable single-linked list in reverse order

No, there is no such algorithm. This is proved in Theorem 2 of "Almost Optimal Hash Sequence Traversal" by Coppersmith and Jakobsson.


Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass?

Unfortunately I don't have a copy of TAPL with me, so I can't figure out exactly what the author intends. But there is a point we should make, that types are something which classifies terms or values, even if there are other pieces that are related to the type.

As such, classes and interfaces are not literally types themselves in Java or C++. Rather, each instance of a class/interface defines a few things simultaneously:

At runtime, we associate with each such defined class, a table of details. This can include where to find code for overrideable methods, but also information like which methods exist, what fields and the like, for reflection.
Both at compile time, and runtime, it defines a type with the same name, which denotes those objects whose runtime class is a subclass of said class.
So here we have a distinction we can make: Each object has exactly one class, but belongs to potentially many different types (the transitive reflexive closure of the subtyping relation).

This is different from the situation in something like OCaml, or likely, those simple objects in TAPL. If there is no means of distinguishing which class created an object, we likely do not want to associate it with a type (as we cannot do anything different with it). In particular, classes in OCaml define a means of constructing an object, so they are a value (just as in the function x -> x + 2).

Following this reasoning, we can think about what metaclasses imply for Python. When we define a metaclass, it creates a particular object, much the same as any other Python object. This portion is a value. Now, later code may reference that value for construction of classes. As stated, we haven't quite made them relate to types yet.

And from here, the answer really comes down to what we decide the types are. It is reasonable to say that objects have a type based on their class (Note again, this is distinct from the denotation given by the type function in Python, which returns a value related to our type). In this situation, yes, metaclasses can be considered to define a kind, as to each class-type, we have an associated metaclass. But we'd be just as reasonable to not consider anything here to be types, and to work only with values and functions.

To really talk about this, we might want to say that Python has a reflection principle: for every class value, we have an associated class type, and vice versa. Extending this we can talk about metaclasses as kinds, (but that will begin requiring subkinding, which may be undesirably complex).

So the key point of distinction we come down to is this: types are classifications, and values are concrete data structures. There can certainly be relations in languages which have run-time type information, but they are not literally identical, and there may be multiple sorts of things defined simultaneously.


Why computer take long time to open huge text files?

The difference would be between loading the complete file into memory and reading the file part-by-part as you need each part.

If I open a file in some applications I am asking for it to be fully loaded into memory all in one go.

If I play a movie file or DVD in most player applications the applications will be structured to just fetch data as it needs it, not all at once.

There are different ways to open files and devices in operating systems and they are not all the same.


Algorithm for generation of Canonical represented integers

The simplest algorithm to do this is to divide repeatedly by the prime, until the division no longer yields an integer.


Definitely possible for a computer, since three-input logic gates exist.   Possible for humans too, at least as far as conscious operations are concerned.  If you show me a partition of 13 into no more than 4 parts (e.g. 5+3+4+1), I can recognize it without any intermediate calculation simply from long experience playing bridge.


Hint: Compute recursively the number of independent sets (a) containing the root, (b) not containing the root.


Constructing a data structure for a computer algebra system

From the comments OP wrote, I understand he wants to start small. However, we need to think more generally so that the to-be developped CAS can be of real use. Otherwise it is nothing but another calculator. Please see Definition of Computer Algebra System.

My suggestion:

Numbers, elements, sets, operations, etc. are fundermental in algebra. The data structures will have to be about them. In particular, you can start with elementary set theory. Determine what will be an element, a set, etc. The elements should be generic(they can be anything). Abstraction is the key. Then, what are the operations associated with them? Constructing a set, membership test, union, intersection, etc. Once we have them in place, plug in the number manipulation packages to the system is a matter of instantiation.


Shouldn't the application rule be written:
$(\lambda x : \tau . e \space e : \tau)$ ?

No, there are at least three problems with this formulation:

First, it is important that the first time can be a variable. For example, we want to allow the term
$$
x \; y
$$
Why do we want to allow this? Well we want to be able to apply a function to an argument. For example, the following lambda term is a function which applies $x$ to $y$:
$$
\lambda x: \tau_1 \to \tau_2. \lambda y: \tau_1. (x \; y)
$$

Second you are assuming the first term has already been reduced. This is not generally true. Although once reduced, the term $e_1$ in $(e_1 \; e_2)$ should usually be a lambda expression (or a variable), this may not hold before it has been evaluated.

The third problem is really a misunderstanding, not a concrete issue with your formulation: in STLC, we allow terms that are not well-typed. For example, if there are base types including numbers and Booleans, then we can write nonsense like
$$
\text{true} \; 3
$$
and this is a valid lambda term, just not a well-typed one. So your question seems to want to make sure that the application rules is well-typed, but that will be part of the typing rules, not part of the definition of a lambda term itself.

The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression.

That is correct, and this is going to be the motivation for the typing rules. In fact, the typing rule will say this exactly: the term $e_1 \; e_2$ will be well-typed only if $e_1$ is a function $\tau_1 \to \tau_2$ and $e_2$ is a value of type $\tau_1$. But for the reasons above, it is important that these restrictions be on the typing level, not baked into the syntax.

$(x \space e)$ makes no sense.

It does make sense: but only in a context where $x$ is a variable of a function type. Think of a variable that may be assigned to a value; if it is assigned to a value which is a function, then this makes sense.

$(c \space e)$ again, you can't apply to a value.

It's true that this makes no sense, but we allow it anyway; we just don't say that it is well-typed.

$((e \space e) \space e)$

As you said this case may resolve to one of the other cases, but we are defining the syntax here, not the semantics. So it doesn't imply that we should rule it out just because resolves to the other cases; it is still a valid lambda term, just one that is not fully reduced.


Clarification of Theorem 1.11 in the book Computational Complexity by Arora/Barak

Since neither HALT nor UC is computable, the machine $M_{UC}$ actually does not exist. The proof by contradiction assumes that HALT is computable and then constructs a machine $M_{UC}$, which contradicts the preceding theorem. This machine is hypothetical, and the proof of Theorem 1.10 indeed shows that it doesn't exist. That's why HALT cannot be computable.


The rationale is that the number of neurones you need to use for approximating any given contiguous function decreases as you add subsequent layers.
See Colah's Deep Learning, NLP, and Representations for a more in-depth explanation.


For every 4 ‘c’ in the input push a ‘c’ in the stack (Push down automata)

You can recognise the language $L = \{c^{4n}|n\geq 0\}$ with a normal DFA. Use this automata as a base and just use one designated state, that pushes a C onto your stack, for which I would choose the first one. For every transition one c is consumed from the word.

$\{(q_1, c, S, CS, q_2) ,
(q_2, c, S, S, q_3),
(q_3, c, S,S,q_4),
(q_4, c, S,S,q_1),
(q_1, d, C, \varepsilon, q_d)\} \subset \Delta $
with $S \in \Gamma$


Knapsack does not have any known quasipolynomial time algorithm (one which runs in
$n^{poly(\log n)}$ time, with $n$ being the inputs length).

What it does have is a pseudo-polynomial time algorithm, i.e. an algorithm which requires polynomial time in the numeric value of the input, but exponential in the length of its description. The dynamic programming algorithm for knapsack runs in time $O(nW)$, however the input $W$ when given in binary representation requires $\log W$ bits, so the algorithm is actually exponential (and not quasipolynomial).


How powerful are CFGs that allow an infinite number of rules?

Suppose we take the metagrammar $G'$ and factor it by two-symbol prefixes. In other words, for each $A \in N$ construct  $G'_A$, the left-derivative of $G'$ over the string $A \to$. That will produce a (finite) set of (finite) metagrammars, each one producing all the (possibly infinite) productions for some $A \in N$.

Now, construct the grammar $G''$, whose rules are the union of all the rules in the $G'_A$ grammars (with non-terminals renamed to avoid collisions), along with $A \to S_{G'_A}$ for each $G'_A$, where $S_{G'_A}$ is the start non-terminal for $G'_A$. The non-terminals for $G''$ include $N$ and all the non-terminals for each $G'_A$; the start non-terminal is the start non-terminal of $G$, and the terminals for $G''$ are precisely the terminals for $G$. I assert (without proof) that $G''$ is a finite grammar for the same language, since the derivation process isn't affected by the origin of the rules; it is just a string substitution over an alphabet.

If the above proof outline is valid, $CF$ and $irCF$ are the same.

As I alluded in a comment, there are more interesting examples of two-level grammars, including Van Wijngaarden grammars and the various attempts which have been made to create more manageable formalisms without losing all of the additional power.


Are there any theorems/formulas that apply to the height of comparison trees?

Basically, we just need to look at the worst case comparison number, a worst case comparison number is when we  compare 1 with 2...N, then 2 with 3...N, etc. that will take (N^2 - N)/2 steps (arithmetic progression ((N-1)*(N-1+1))/2). So that's the height of that tree.

So for N = 3 we get (3^3 - 3)/2 = (9 - 3)/2 = 3. For N = 4 we have (4^2 - 4)/2 = 6.


How do I find an upper bound on this recurrence

For definiteness, let's assume that the recurrence is
$$
f(n) = \begin{cases}
f(\lfloor n-\sqrt{n} \rfloor) + 1 & n > 0 \\
0 & n = 0.
\end{cases}
$$
(We assume that the domain is the non-negative integers.)

Since $\lfloor n-\sqrt{n} \rfloor > n-\sqrt{n}-1$, we see that
$$
f(n) \geq \frac{n}{\sqrt{n}+1} = \Omega(\sqrt{n}).
$$
In the other direction, let us note that $f(n)$ is monotone and that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \frac{\lceil n/2 \rceil}{\sqrt{\lceil n/2 \rceil}}.
$$
This is because until the parameter gets down to $\lfloor n/2 \rfloor$ (or smaller), the decrease at every step is at least $\sqrt{\lceil n/2 \rceil}$. This shows that
$$
f(n) \leq f(\lfloor n/2 \rfloor) + \sqrt{\lceil n/2 \rceil} \leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1.
$$
Iterating this $\log_2 n+1$ times, we get
$$
\begin{align*}
f(n) &\leq f(\lfloor n/2 \rfloor) + \sqrt{n/2} + 1 \\ &\leq
f(\lfloor n/4 \rfloor) + \sqrt{n/2} + \sqrt{n/4} + 2 \\ &\leq \cdots \\ &\leq
f(0) + \sqrt{n/2} + \sqrt{n/4} + \cdots + \sqrt{n/2^{\log_2 n + 1}} + \log_2n + 1 \\ &\leq
\sqrt{n} \sum_{t=1}^\infty \frac{1}{\sqrt{2}^t} + O(\log n) \\ &= O(\sqrt{n}).
\end{align*}
$$
We conclude that $f(n) = \Theta(\sqrt{n})$.


If you choose $\frac{n}{2}$ as the pivot to do the partition, you just need then to continue the search in the half containing strictly more than $\frac{n}{2}$ elements.
That way you don't have to check both halves.


People crossing a bridge (a proof for a greedy algorithm)

The reason you can't prove that the greedy algorithm is correct is because it isn't.

Suppose the people cross the bridge in times 1, 2, 5 and 10 minutes.  The greedy solution involves the one-minute person walking backwards and forwards every time and takes 10+1+5+1+2=19 minutes.  The optimal solution is 17 minutes (spoiler, since it's a famous puzzle that people might want to try on their own).

   1 and 2 cross, 2 returns with the flashlight, then 5 and 10 cross and 1 returns with the flashlight to collect 2: total time 2+2+10+1+2=17 minutes.


In my mind when you start using a "DB" I'm assuming that you mean a relational/SQL database, and then the design of how the information is stored might change entirely.

It seems like you're using this Excel file to track a master production schedule for some kind of parts manufacturing, so it's how many parts you need, and when you need them by.

I'm not sure it makes sense to have multiple time scales in the same table for that purpose. So my reflex would be to say, we should create a table that stores information about, the date, how many parts need to be produced on that date, and which part needs to be produced.

CREATE TABLE production_schedule (
    prod_date date,
    part_no   int,
    part_qty  int
);

Then if you need to build reporting or gather the information about how much in a week, a month, six months, or a year. You could do that with queries when you need that information or you could create views that are based on such queries.

For example, a query like the following would return the total amount of parts to be created in January 2018.

SELECT SUM(part_qty) FROM production_schedule WHERE prod_date BETWEEN '01/01/2018' AND '31/01/2018';

Hopefully, this helps you understand the way you should think about creating a database to solve your problems, and perhaps a verbatim transfer of the information isn't the best solution.

It can help when getting started to think of databases as spreadsheets because they store information in a way that can be thought of as "column and row". The fact that you can store information in them and also ask sometimes simple and sometimes complicated questions of them can throw off people who are new to working with databases.


Is finding a set cover of size $k$ NP-complete?

Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$.

For example, for $k = n / 3$, 3-dimensional matching can be directly reduced to your problem.


The following answer works for a previous variant of the question, in which the goal is to determine which of $x,y,z$ are in $A$. It might be possible to adapt it to the current version, in which the goal is to determine whether or not all of $x,y,z$ are in $A$. One difficulty is that the number of trees of depth $h$ is now $\Theta(2^hh^3)$, so following the same steps would only give a lower bound of $3\log_2 n - \Theta(\log \log n)$.

Suppose that the array $A$ is $1,\ldots,n$. Let $x = i + 1/2$, $y = j + 1/2$, $z = k + 1/2$, where $1 \leq i < j < k < n$ are integers. Let us denote the resulting leaf of the algorithm by $\ell(i,j,k)$.

I claim that if $(i,j,k) \neq (i',j',k')$ then $\ell(i,j,k) \neq \ell(i',j',k')$. Indeed, suppose that $\ell(i,j,k) = \ell(i',j',k')$ although $(i,j,k) \neq (i',j',k')$. Suppose that $i < i'$ (the other cases are similar). Since $i + 1/2 < A_{i+1} < i' + 1/2$, we conclude that in this computation path, the algorithm never compares $x$ to $A_{i+1}$. Suppose that we change $A_{i+1}$ to $A'_{i+1} = i + 1/2$. The new array $A'$ is still sorted, and when running the algorithm on $A',i+1/2,j+1/2,k+1/2$, it still reaches the leaf $\ell(i,j,k)$ (since the only comparison whose answer is different is $A'_{i+1}$ and $x$). We have reached a contradiction, since $x \in A'$, and so we should have reached a different leaf.

Concluding, we have shown that the algorithm tree must have at least $\binom{n-1}{3}$ different leaves (this is the number of possible triples $(i,j,k)$). Since we are only considering runs of the algorithm in which the answers to all comparison queries are either $<$ or $>$, we can ignore all edges labeled $=$, and so we are left with a binary tree, whose depth must therefore be at least $\log_2 \binom{n-1}{3}$. This is a lower bound on the number of comparisons in the worst case.

When $n \geq 4$, we have
$$
\binom{n-1}{3} = \frac{(n-1)(n-2)(n-3)}{6} \geq \frac{(n-3)^6}{6} \geq \frac{(n/4)^3}{6} = \frac{n^3}{384},
$$
since $n-3 \geq n/4$. Therefore for $n \geq 4$ the number of comparisons must be at least
$$
\log_2 \frac{n^3}{384} = 3\log_2 n - \log_2 384.
$$
When $1 \leq n \leq 3$, we must still make (say) at least one comparison, and this allows us to obtain a lower bound of $3\log_2 n - c$ valid for all $n \geq 1$ (details left to the reader).


Find the $k$-th lexicographically smallest hamiltonian circuit

Counting the number of Hamiltonian circuits in a graph is $\mathsf{\#P}$-hard (see for example this answer). Your problem is even harder, since we can use your problem together with binary search to count the number of Hamiltonian circuits in a given graph.

As an aside, let me mention that listing things in lexicographical order might be harder than listing them in any order. A case in point is the complexity of finding a [maximal independent set], which is an independent set which cannot be enlarged (but not necessarily one which has maximum size). A maximal independent set can easily be found by going over the vertices in some arbitrary order, putting the problem in the complexity class $\mathsf{P}$. This algorithm can be improved, and in fact a maximal independent set can be found in $\mathsf{NC^2}$. In contrast, finding the lexicographically first maximal independent set (that is, deciding whether a given vertex belongs to this set) is $\mathsf{P}$-complete.


Big-O with nested loops and "variables" in the T(n)

One common way to arrive at a tight big-$O$ upper bound of the complexity of an algorithm is to estimate one. Then prove that estimate works.

Let me take your computation by nested loops as an example.

In this post $\log(x)$ means $\log_2(x)$. The first loop runs $\lceil\log(n)\rceil$ iterations. For each iteration in the first loop, the second loop runs $\lfloor\log(n)\rfloor+1$ iterations. For each iteration in the second loop, the third loop runs $\lfloor(n - j+1)/2\rfloor$ iterations, where $j>0$ is the loop variable of the second loop. Ignoring the floor function, the addition by the constant 1, the subtraction by $j$, the division by the constant 2 and the constant number of operations executed by each iteration in the third loop, I will estimate the upper bound of the number of total operations as $O(\log(n)\log(n)\,n)$.

Is that $O(n\log^2n)$ a tight upper bound of the the number of total operations $T(n)$? Yes, it is indeed.

Firstly, let us show it is an upper bound. We can assume $n>2$. Let $c_3$ be the number of operations executed by each iteration of the third loop.
$$ T(n) \le (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor+1)(n/2)c_3\\
\le (2\log(n))(2\log(n))(n/2)c_3\\
\le (2c_3)n\log^2n
$$

Now let us show it is tight. Let us do not count the first iteration of the the second loop. That is, let us only consider the operation done by the second loop starting from $j=\lfloor n/2\rfloor$. Then for each iteration in the second loop, the third loop runs $⌊(n−j+1)/2⌋ \ge n/2-1$ iterations. Then for $n\ge6$,
$$ T(n) \ge (\lceil\log(n)\rceil) (\lfloor\log(n)\rfloor)(n/2-1)c_3\\
\ge (\log(n))(\log(n)/2)(n/3)c_3\\
\ge (c_3/6)n\log^2n\\
$$

So we have proved from the ground up.

The above proof, although rigorous and clear, is not the usual way to reason about the big-$O$ because it is so exact as to require too much thinking. That is almost the kind of computation needed to get the exact asymptotic approximation. Here is a simpler version assuming you are familiar with the big-$\Theta$ notations.

The first loop run $\Theta(\log(n)$ iterations. For each iteration in the first loop, the second loop runs $\Theta(\log(n)$ iterations. For all but the first iteration in the second loop, the third loop runs between $n/2$ to $n$ iterations, which is $\Theta(n)$ iterations. In the first iteration of the second loop, the third loop runs no iteration. So $$T(n)=\Theta(\log(n)(\Theta(\log(n)-1)\Theta(n)=\Theta(\log(n))\Theta(\log(n))\Theta(n)=\Theta(n\log^2(n))$$
which implies $O(n\log^2n)$ is the tight upper bound.

By the way, in all computations above we are not counting the operations to maintains the indice $i,j,k$. That is ignored by convention, because they will not change our approximation in big $O$-notations unless in extraordinary situations. Or because in many situations we are only interested in the number of the "real" operations.

The reasoning about the big-$O$ notations can be an art or a precise process. On the one hand, you can be very "sloppy" when you are trying to get an estimate and even when you are reasoning. That is because you can hide or absorb constant factors into the notations. That way you can arrive at a possible answer very quickly. With practice and experience, you can be certain immediately most of the times once you got an estimate. On the other hand, you can also verify every part of the "sloppy" process by rigorous mathematical deduction or by applying a set of valid shortcut rules. In the end, we will arrive at a precise conclusion using the big-$O$ notations.


Can you share some pointers to get better at working alone in projects?

ML is an extremely broad subject but generally it can be understood broadly as follows

you formalize the problem
you identify the domain of the problem
you identify candidate models to solve the problem
you evaluate the candidate models with data subsets
you select a model and try to fit your data
you deploy the model

You can think of it as a(n iterative deepening ) search of a tree of choices.  To improve your odds of success (find a choice that solves the problem) you need the tree narrow down as quickly as possible e.g. pruning bad choices.  This is only acquired through experience but having a broad understanding of models helps e.g by taking introductory courses.

Once you've narrowed down the types of models you want to apply.  You want to know if you have the expertise to apply them.  Given that this is a broad subject, you acquire expertise only in a limited set of models.  If the model that best fits your problem is not in your domain of expertise you either refer it someone with that expertise or reject that you can solve the problem in a limited amount of time e.g. due to the complexity of the tree of choices for a non-expert.

Within your model expertise you'd have acquired a set of techniques to determine that even when you have the right model, if you do not have sufficient data, or data with sufficient quality, or the necessary computation resources you may not be able to deploy your model.


How to use DFA/NFA to prove the language {$0^n 1^$ | x ∈ Σ*, n ≥ 1} is regular?

Your language consists of all words starting with $0$ and ending with $1$.


Context free grammar for $L=\{a^n b c^n | n \ge0\}$

$$\begin{align}X&\to aXc\\
               X&\to b\end{align}$$


Suppose that the points are $(x_1,y_1),\ldots,(x_n,y_n)$. You are looking for the smallest (in some sense) bounding box $[X_m,X_M] \times [Y_m,Y_M]$ containing all your points. For every $i$, we must have $X_m \leq x_i \leq X_M$ and $Y_m \leq y_i \leq Y_M$. In particular,
$$
\begin{align*}
X_m \leq \min_i x_i =: x_{\min}, \\
X_M \geq \max_i x_i =: x_{\max}, \\
Y_m \leq \min_i y_i =: y_{\min}, \\
Y_M \geq \max_i y_i =: y_{\max}.
\end{align*}
$$
Summarizing, this shows that every bounding box must satisfy
$$
X_m \leq x_{\min} \leq x_{\max} \leq X_M, \\
Y_m \leq y_{\min} \leq y_{\max} \leq Y_M,
$$
that is, it must contain $B := [x_{\min},x_{\max}] \times [y_{\min},y_{\max}]$. Conversely, $B$ is itself a bounding box, since $x_{\min} \leq x_i \leq x_{\max}$ and $y_{\min} \leq y_i \leq y_{\max}$ for all $i$. We conclude the following fact:

  $B$ is the intersection of all bounding boxes.


Determining if a langage defined by a given context-free grammar is finite using the pumping lemma

Here is the corresponding result for regular languages:

  Given a DFA with $n$ states, its corresponding language is infinite iff it contains a word whose length is between $n$ and $2n-1$.

This implies an inefficient algorithm for determining whether the language is infinite.

The proof uses the pumping lemma in its following formulation:

  If a regular language $L$ is accepted by a DFA with $n$ states, then any word $w \in L$ of length at least $n$ can be decomposed as $w = xyz$, where $|xy| \leq n$ and $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$.

In one direction, if the DFA accepts some word $w$ of length at least $n$, then the pumping lemma shows that there is some decomposition $w = xyz$ with $y \neq \epsilon$ such that the infinitely many words $xy^iz$ belong to the language.

In the other direction, if the language is infinite then it contains some word whose length is at least $n$. Let $w$ such a word of minimal length. The pumping lemma show that there exists a decomposition $w = xyz$, with $0 < |y| \leq n$, such that $xz$ is in the language. Since $|xz| < |xyz|$, it follows that $|xz| < n$, and so $|w| = |xyz| < 2n$.

If you use the pumping lemma for context-free languages in a formulation in which the pumping constant is related to the size of a context-free grammar for the language, then you can use similar reasoning to come up with an algorithm that determines whether the language generated by a context-free grammar is infinite.


Find offset and page number given paged virtual memory address

assume address printed out to be a "byte address"
guess whether the offset to find is addressable unit in page or byte in page

if addressable unit in page, figure out its size
with nothing more than 64-bit to go on a first assumption is 8 bytes

guess the representation wanted for virtual page number & offset

(Base conversions in the process depend on practice with the representations involved. For a result in hex, too, some would prefer to just double (word offset) or halve ("byte page#") "in hex". A coder might have a program print both parts before even considering if coding the task was least effort.)


In general, the answer is no. If we put XOR-like restrictions on the out-going edges of a vertex, we can prove that finding a min-cut-max-flow is NP-Hard. The technique is to reduce 3-SAT to it.

Let's assume there are $n$ variables $x_1, x_2, ..., x_n$ in the 3-SAT and $m$ clauses $c_1, c_2, ..., c_m$. We create a graph $G(V,E)$ encoding the instance of the 3-SAT problem. For each variable $x_i$, we create a vertex $v_i$ connected to the source $s$ with an edge of $\infty$ capacity. Two more vertices $u_i, w_i$, which are connected to $v_i$, are created to represent $x_i$ taking the value 0 or 1 also with edges of capacity $\infty$.

For each of the clauses $c_i$, we create a vertex $o_i \in G$ corresponding to it and $o_i$ is connected to the variables or their negations in the clause with edges of capacity $1$. For example, if $c_i = (x_3 \lor x_4 \lor \neg x_5)$, we connect it to $u_3, u_4, w_5$ with edges of capacity. All $o_i$ are connected to the sink with edges of capacity 1.

Since $x_i$ and $\neg x_i$ cannot take the same value, we put the XOR restriction on edges $(v_i, u_i)$, $(v_i, w_i)$, $\forall i = 1,2,3,...,n$. It can be proved that there is a maximum flow of size $m$ if and only if the 3-SAT instance is satisfiable. Since the problem is trivially in $NP$ and the reduction is polynomial, we conclude the decision version of XOR restriction network flow is NP-Complete.


Should one learn proofs for the correctness of algorithms? Why?

That's up to you. Reading correctness proofs for algorithms is useful since:

The proofs explain why the algorithms work. If you need to modify these algorithms, you'd better know how they work. Such an understanding is very useful even just for coding algorithms, and certainly for debugging them.
The proofs are good examples of mathematical proofs. The mathematical notion of proof is one of the most important contributions of mathematics to the world, and is a way of knowing which you could find useful in life, even without using it yourself.
If you continue in academia, say get a graduate degree, you might have to write such proofs in the future.

However, it is my understanding that most programmers don't come up with new algorithms, or even code classical ones. If this is your case, you can probably skip the proofs, indeed the entire course, if it were not made compulsory by your university (if any).


What is the difference between maximal flow and maximum flow?

As saadtaame mentions, maximum usually means global maximum, whereas maximal means local maximum. For example, a maximal independent set in a graph is one to which no vertex can be added (making it a dominating set), while a maximum independent set is one with largest cardinality among all independent set.

My guess is that a maximal flow is one in which every source-to-sink path has a saturated edge (i.e., the flow equals the capacity). Such a flow cannot be improved by pushing more flow through some source-to-sink path.

It so happens that such a flow is also maximum. To see this, consider the residual network, formed by the unsaturated edges. Let $C$ be the connected component containing the source. Since the flow is maximal, $C$ does not contain the sink, and so it forms a source-sink cut in the graph. The value of every flow in the graph is bounded by the capacity of edges crossing the cut. Yet by definition, this is also the value of the flow under consideration, completing the proof.


That looks like an error in your notes.  {r2,r3,r4} are compatible.


Number of nodes of a parse tree when the Grammar is in CNF?

Both of the answers are wrong. To find the correct answer, let us consider the grammar
$$ S \to SA \mid a \\ A \to a $$

You can check that the tree corresponding to $S \to a$ has 2 nodes, the one corresponding to $S \to SA \to aA \to aa$ has 5 nodes, and the one corresponding to $S \to SA \to SAA \to aAA \to aaA \to aaa$ has 8 nodes. This corresponds to the formula $3n-1$ (rather than $3^n-1$, the formula you quoted).

Let us now prove that this formula is correct. The proof is by induction, where we allow varying the starting nonterminal. When $n = 1$, the derivation must be of the form $A \to \sigma$, which includes 2 nodes. When $n > 1$, the first step must be $A \to BC$, where $B$ gives rise to a word of length $k$, and $C$ gives rise to a word of length $n-k$. The entire tree is formed from the trees corresponding to $B,C$ by adding the root, and so the total number of nodes is $$1 + (3k-1) + (3(n-k)-1) = 3n-1.$$


Artificial intelligence and undecidibility

No.  The Post correspondence problem is undecidable.  That means that no computer program can solve it (in all cases).  "Artificial intelligence" is just a computer program. Actually, "artificial intelligence" is a name for something that we're not even sure how to do with a computer program; but even if we knew how to achieve it, it would still be a computer program.  Artificial intelligence isn't magic -- anything that can be done is still constrained by the laws of physics and mathematics.


If there is any research on Goal Based Programming (GBP)?

Yes.  The research area is known as program synthesis.  You can find hundreds or thousands of papers on the subject.  (You might also be interested in declarative programming.)

What you're describing is way beyond the state of the art.  It'd be really cool if we could do something like that -- but we're a long long way away from knowing how to build that.


Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

If you take any tour and remove any edge, then you get a spanning tree. Hence the weight of a minimum spanning tree is at most the weight of every tour.

I should add that one of the tricks behind this algorithm is that while we can't find a minimum tour efficiently, we can find a minimum spanning tree. Minimum spanning tree is an efficiently computable relaxation of minimum Hamiltonian path.


Coming up with a loop invariant for the partition section Quicksort?

You're sort of on the right track in that you're trying to relate the position of array elements to their value, but your statement makes a serious error in directly comparing the value of an index, $j$, to the value of arbitrary data, $a[L]$ and $a[R-1]$.
I think you meant to say $L\leq j\leq R$ is a loop invariant. Observe that $L\leq i\leq j$ is as well, but neither are very interesting statements.
Remember, the motivation for identifying loop invariants is so that we can use them to verify that our code does what it's supposed to. Here, implementing the partition stage of Quicksort, our goal is to rearrange the elements of $a$ such that all the data to the left of the pivot will be less than or equal to the pivot, and all the data to the right of the pivot will be greater than or equal to the pivot.
One important loop invariant is $$\text{For all indices }k \text{ with } L\leq k<i, \text{ we have } a[k]\leq\text{pivot}=a[R]$$
We can see this in your code:
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];
    //a[k]<=pivot for all k with L<=k<L=i (true since there are no such k)

     for (int j = L; j < R; j++) {
         //a[k]<=pivot for all k with L<=k<i (inductive hypothesis)

         if (a[j] <= pivot) {
             swap(a[i], a[j]);
             //we have now ensured a[i]<=pivot
             //it is an invariant that i<=j
             //so the elements a[L],...,a[i-1] are unchanged
             //thus a[k]<=pivot for all k with L<=k<i+1

             i++;
             //now a[k]<=pivot for all k with L<=k<i
         }
      }
    swap(a[i], a[R]);
    }

Another important loop invariant is $$\text{For all k such that } i\leq k< j, \text{we have } a[k]\geq\text{pivot}=a[R]$$
Again we can see this looking at your code:
    void partition(int a[], int L, int R) {
    int i = L;
    int pivot = a[R];

    //a[k]>=pivot for all k with i=L<=k<L=j (true since there are no such k)
     for (int j = L; j < R; j++) {
         //a[k]>=pivot for all k with i<=k<j (inductive hypothesis)

         if (a[j] <= pivot) {
             //it is an invariant that i<=j. now either i<j or i=j
             //if i=j, then there are no k such that i<=k<j, so assume i<j
             //then i<=i<j, and consequently a[i]>=pivot

             swap(a[i], a[j]);
             //now a[j]>=pivot and a[i]<=pivot
             //the other elements are unchanged
             //so now a[k]>=pivot for k with i+1<=k<=j

             i++;
             //now a[k]>=pivot for k with i<=k<=j

         }
      }//after incrementing j by 1, now a[k]>=pivot for k with i<=k<j

    swap(a[i], a[R]);
    }


Analysis of the following integer program

A simple greedy approach works here: choose the $k$ elements having maximal $v_i L_i$.


Recognizable vs co-recognizable languages

A language is recognizable if there is a Turing machine that enumerates all words in the language. It is co-recognizable if there is a Turing machine that enumerates all words not in the language.

Every language has a one-to-one correspondence to the natural numbers, simply because the number of possible words is countable.

To see the difference between recognizable and co-recognizable, let's take the prototypical example of a recognizable language: it is the language of Turing machines which halt on the empty input. It is easy to enumerate this language: run in parallel all Turing machines on the empty input, and whenever one of them halts, print its index. There is provably no similar way to enumerate the complement of this language.

If a language is both recognizable and co-recognizable, then it is decidable, meaning that there is a Turing machine that always halts and tells you whether the input belongs to the language or not. Indeed, if $L$ is recognizable and co-recognizable, then there is a Turing machine $T_1$ which enumerates all words in $L$, and other Turing machine $T_0$ which enumerates all words not in $L$. Using these, we construct a decider $T$: on input $w$, run $T_1$ and $T_0$ in parallel, until one of them prints $w$. If it were $T_1$, answer "Yes", and if it were $T_0$, answer "No".


Do determinacy of one-step evaluation and uniqueness of normal forms apply to all (or most) languages in TAPL?

Uniqueness of normal forms definitely applies. This is still a theorem you have to prove, but if it doesn't hold, what you have isn't really a normal form. The whole point of normal forms is that there's a unique form for each value, that's what makes it "normal".
For determinancy, I think it holds for most languages in the book. Usually when you're defining a small step semantics, you try to do it in such a way that it's deterministic. However, there are notable exceptions to this. First, if you have a general rewrite system, like the untyped lambda calculus, then it's totally valid to have non deterministic reductions. This is what lets us talk about Church Rosser and the diamond property. Secondly, if you have a language with any sort of concurrency, then you probably want to have non deterministic rules, to model the different possible orders of evaluation, so that you can show your language is well behaved regardless of which interleaving is taken.

That said, I want to be clear that these things do not come for free. They hold for the Languages in the book because Pierce has been very careful to ensure they hold. It is easy to accidentally definite a language where these do not hold.


Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?

According to the Wikipedia article, at each step the length of the integers is reduced from $N$ to (roughly) $\sqrt{N}$, and there are (roughly) $\sqrt{N}$ of them, and so the additions only cost $O(N)$. There is a detailed analysis of the running time in the final paragraph of the linked section, copied here in case it changes:

In the recursive step, the observation is used that:

Each element of the input vectors has at most $N/2^k$ bits;
The product of any two input vector elements has at most $2N/2^k$ bits;
Each element of the convolution is the sum of at most $2^k$ such products, and so cannot exceed $2N/2^k + k$ bits.

Here $N$ is current input length and $k = \Theta(\sqrt{N})$. Arithmetic is done modulo $2^n+1$, where $n$ is some multiple of $2^k$ which is larger than $2N/2^k + k$; note that $n = \Theta(\sqrt{N})$.


Amortized analysis of binary counter with increment and resetting operations

First, 9th line of increment sets $\max[A]$ to -1 if $i \le \max[A]$ does not make much sense.

It does not make sense because it is wrong. This part of code has been wrongly aligned. It should be

5. if i < length [A]
6.   then A[i] = 1
7.       if i > max[A]
8.         then max[A] = i
9.   else max[A] = -1 // the array A overflows; A is effectively reset to 0. So max[A] = -1.

  Why do we need to put yet another coin?

As explained in the article, the amortized costs of INC and RESET are $\$$4 and $\$$1, respectively.

$\$$4 for INC is composed of

pay $\$$1 to set 0 to 1;
place another $\$$1 on the same bit as credit. The credit on each 1 bit will pay to reset the bit during INC (not by RESET);
pay $\$$1 to update max[A]
place an additional $\$$1 of credit on the new high-order 1 (If max[A] does not increase we just waste that one dollar). The credit will pay to reset the bit during RESET.

$\$$1 for RESET is

pay $\$$1 to reset max[A]. Note that the resetting of bits From i = 0 to max[A] is paid for by the credit stored on the bits (each bit reset here has a credit on it due to the last $\$$1 for INC).

Added: For your specific question on "another $\$$1 on bit 1", note that the first $\$$1 credit on each bit 1 put by INC is consumed by the "resetting" part in INC itself (just as in the binary counter without the RESET operation). That is why you need another $\$$1 on each, to pay for the RESET operation (i.e., the code From i = 0 to max[A] A[i] = 0). The charged $\$$1 for RESET operation is only for the update of max[A].


Using integer programming to find a solution without optimizing it

There is at most a pseudo-logarithmic gap between the complexity of optimization and simply finding a feasible solution.
We can turn any optimization problem into a feasibility problem by simply adding the optimality expression to the inequalities with some value $C$, and using binary search to find the optimal $C$.


Which one of these two sequences is random, and which one is not?

The second sequence is not random.  Let $\alpha_1,\alpha_2,\alpha_3,\alpha_4$ be random, iid Bernoulli $1/2$ random variables.  Let $\beta = B_4(\alpha_1 \alpha_2 \alpha_3 \alpha_4)$.

What is the distribution of the random variable $\beta$?  Answer: $\beta=1$ if at least two of the $\alpha$'s are $1$, so $\Pr[\beta=1] = 11/16$.

In other words, $\beta$ is biased towards $1$.  It follows that the second sequence is not algorithmically random: it is a set of independent Bernoulli random variables with $p=11/16$, i.e., the outcome of an infinite sequence of tosses of a biased coin.


Multi-threading : N cores = N times one core?

If I understood your question correctly, you are essentially asking:

  Given a piece of sequential code, if we run N instances of it in parallel on N cores (on real, modern, typical, and not-particularly-high-end CPU models), should we expect any slowdown versus running only a single instance of that program on a single core?

As usual, the answer is: it depends. However, the answer will often be yes indeed, you should expect a slowdown. It will often take more than "one minute" per instance.

How and why? Intuitively, since you've got shared (and limited) resources, your threads will naturally compete for them.

For instance, main memory will be shared. Thus, if your program is bandwidth-bound (which is very common across many applications), few threads can easily fully saturate your limited memory bandwidth (essentially, they can request data from memory at a faster pace than your hardware can support) and you may notice degradation in performance (given your "one minute" measure) beyond that limit. You may want to look up the bandwidth-wall problem.

For another similar instance, many modern CPU models will have a shared last-level cache per chip/socket. These (typically L3) caches will often provide significantly higher bandwidth and lower latency for any thread (on the chip) accessing any cached data, in comparison to directly accessing main memory. Once threads start competing for this shared resource, the total working set size of all thread may exceed the cache capacity -- even though a single thread was running within cache. They effectively thrash the cache for each other.

You may want to contrast these cases to the case where the program is compute-bound and CPU-intensive yet can work with high locality in the smaller, private (i.e., not shared) caches. There are probably non-memory-hierarchy reasons as well (unlike the two above), although the reasons above are perhaps among the most obvious and most significant (or, at least, that is what I would expect).


Recovering species from a phylogenetic tree

I present an algorithm for the tree case. The algorithm solves the problem in two 'passes' through the tree: first from leaves to root, then from the root to the leaves.

Algorithm:
First, we augment our tree $T$ with the additional field $v.subcolors$ for each vertex $v$. This field should contain the set of all colors present in the subtree rooted at $v$ (with $v$ included).

We traverse the tree 'layer by layer' from leaves to the root: Our first layer consists of all leaves. The next layer is constructed by taking the set of parents from all vertices in the current layer, which we repeat until we reach the root.

Then, we fill in the field $v.subcolors$ for all vertices $v$ in our layer. This is easy to do, as we know that $w.subcolors$ is already set for all children of $v$, as those belong to the previous layer we've already visited.

Observe that some vertex $v$ must be of color $c$ if and only if it separates two vertices of color $c$, i.e. it lies on the (unique!) path between two vertices of color $c$. We can determine whether $v$ separates some vertices easily if we know what colors lie in the components formed by removing $v$ from the tree: if the color $c$ lies in two distinct such components, $v$ must separate some vertices in those components.

We can efficiently find the colors in the subtree of the children of $v$, as that is given by $v.subcolors$. The parent of $v$ is a bit more tricky. However, if the parent has already been colored with color $c$, $v$ can be a separator of some vertex the component of the parent only if that vertex has color $c$! Otherwise, if there were some other color $c'$, the parent of $v$ would also separate those vertices. But the parent has color $c$, which means that the coloring of the parent of $v$ is incorrect. This contradicts our assumption that we know the correct color of the parent (note that we have assumed a valid coloring exists!)

So, we can now color the vertices by traversing the tree from root to leaves, again layer by layer: we check at each vertex $v$ whether it separates vertices of some color (as a valid coloring exists, this is at most once color) and fill in that color. If it separates no vertices of the same color, we simply give it an unused color from $[1,n]$.

Efficiency: Coloring the sub-tree requires traversing the tree from bottom to top. As we need to compute with the field $v.subcolors$ at most once for every edge in the tree, this part takes $O(|E|) = O(|V|) = O(n)$ time.

For the down-traversal, we must perform a comparison again for each edge. We can check for each color and vertex adjacent to $v$ whether it occurs and see if it is a separator if it occurs twice. This takes $O(\mathrm{degree}(v)\cdot |C|)$ time if we store the color sets in a hash-table, where $|C|=n$, the number of colors. As the average degree of a tree is constant, performing this operation on all vertices takes $O(n^2)$ time.

So, in total, the algorithm runs in $O(n^2)$ time. This turned out to be fast enough for the testcases given in the contest.

This time could maybe be improved by using an efficient union algorithm to check the separator more efficiently. (Union-find doesn't seem to do the trick, as the sets aren't disjoint)


Difference between consensus number n and consensus number infinite

The consensus number of an object is the maximum number of concurrent processes that you can synchronize with one such object in a wait-free manner (I won't go into what wait-free means here). For example, a register with only read and write operations doesn't help with wait-free synchronization at all, so it has consensus number 1. A register with a test-and-set operation can be used to synchronize two processes in a wait-free manner, but not three or more, so the consensus number of test-and-set is 2.

$n$-register assignment, where a process can atomically write to multiple registers, allows up to $2n-2$ processes to synchronize wait-free if there are $n$ registers. More processes require more registers. Therefore the consensus number of an objet consisting of $n$ registers that can be assigned atomically is $2n-2$.

A single register with a compare-and-swap operation is sufficient to synchronize any number of processes wait-free. Therefore the consensus number of compare-and-swap is infinite.

Lemma 40 states that a mem-and-swap object allows the wait-free synchronization of all the processes in a system of $n$ concurrent processes, for any number $n$. This means that for any number $n$, the consensus number of mem-and-swap is at least $n$. (Stating that the consensus number is $n$ in a system of $n$ processes is a bit of a misnomer since the definition of the consensus number doesn't actually depend on the total number of processes.) Since consensus number of mem-and-swap is at least $n$ for any $n$, it's infinite.

If you prefer another source than Raynal's book, you can read the original paper by Maurice Herlihy.


What will be the pictorial diagram of this transition table?

You just create a super simple Graphviz document encoding the information:

$ cat foo.gv
digraph {
  q0 -> q0 [label = "input: a\noutput: 0"];
  q0 -> q2 [label = "input: b\noutput: 0"];
  q1 -> q1 [label = "input: a\noutput: 1"];
  q1 -> q0 [label = "input: b\noutput: 1"];
  q2 -> q2 [label = "input: a\noutput: 1"];
  q2 -> q1 [label = "input: b\noutput: 1"];
}
$ _

Process it:

$ dot foo.gv -T png -o foo.png
$ echo $?
0
$ _

Profit!


How are graph representations containing only (i, j) instead of both (i, j) and (j, i) named?

Your second kind of representation is simply called the adjacency list representation.  It's a standard representation for graph data structures.

To my knowledge, there is no standard name for your first kind of representation; it's a weird and non-standard kind of representation.  That's probably because it's not sufficient for most algorithms on undirected graphs (most algorithms require more), whereas the adjacency list representation is sufficient for most algorithms on undirected graphs.  So, it would be rare to find situations where your first kind of representation is sufficient and useful.

You say that your first kind of representation is sufficient for Kruskal's algorithm, but this might be a bit misleading.  In fact, Kruskal's algorithm is fine with something even more minimal: merely having a list of all edges is sufficient for Kruskal's algorithm.  In other words, Kruskal's algorithm does not require the edge (i,j) to be associated with either i or j (it's OK if it's not associated with either, as long as you have a list of all edges).

In general, your first kind of representation does not seem like a natural choice for any graph algorithm that I can think of right now, so it's not surprising if it doesn't have a standard name.


You asked for a hint.  OK, here goes:

Obviously, we don't know $D$ (otherwise the problem is too easy).  But suppose we do know an upper bound $U$ on $D$.  In other words, suppose we know an integer $U$ and are promised that $D \le U$.  Then it is possible to build a solution whose running time is a low-order polynomial of $U$.  In fact, it is possible to build a solution whose running time is $O(U^2)$.  Take a close look at your professor's algorithm (the one labelled "the given algorithm"), and think for a bit, and maybe you'll see how to accomplish this.

But what about the fact that we don't know the value of $U$?  Well, you might ponder the sequence $1,2,4,8,16,32,\dots$.  I'm being deliberately terse here since you asked for a hint, but if you ponder on this, I think you'll be able to find an algorithm that it meets all your criteria.


How many snakes there can be in the "snakes and ladders" game?

If we assume any given square can be the head or tail (but not both) of at most one snake then clearly an upper limit on the number of snakes on a $n \times n$ board is $\frac {n^2} 2$. For a $m \times n$ board we can generalise this to $\frac {mn} 2$. And we can reach this upper limit if either $m$ or $n$ is even. What happens if $m$ and $n$ are both odd ?


Hardness of finding a true or a false assignment into a generic boolean formula?

You can always convert your formula or circuit to an equivalent CNF formula of polynomial size.

The result you mention is only for 3CNF formulas. In general for kCNF-SAT the assumed threshold phenomenon happens on a point depending on $k$, the values you mention are only for 3CNF-SAT.

Also remember what these result say is w.h.p. in a particular distribution of k-CNF formulas. It doesn't mean that this will hold for all formulas. In fact it is quite easy to come up with formulas that have values mentioned in the range but are easy and also formulas that are outside this range but are hard (think about padding formulas to obtain your desired ration). So given a particular 3CNF formula with some clause ration, you can't say anything about its difficulty (or the time it will take a particular SAT solver to solve it).


How to get the calculate the binary logarithm of a fixed-point number with 18 decimals?

I figured it out, eventually, by making the following observations:

$\log_2{(x)} = -log_2{(\frac{1}{x})}$
To accurately calculate $\frac{1}{x}$, multiply $1e18$ by itself then divide by $x$.

My implementation looks something like this (written in Solidity):
pragma solidity ^0.8.0;

function log2(uint256 x) internal pure returns (int256 result) {
    require(x > 0);
    unchecked {
        // This works because log2(x) = -log2(1/x).
        int256 sign;
        if (x >= 1e18) {
            sign = 1;
        } else {
            sign = -1;
            unchecked {
                x = 1e36 / x;
            }
        }

        // Calculate the integer part of the logarithm and add it to the result and finally calculate y = x * 2^(-n).
        uint256 n = mostSignificantBit(uint256(x / 1e18));

        // The integer part of the logarithm as a signed 59.18-decimal fixed-point number. The operation can't overflow
        // beacuse n is maximum 255, SCALE is 1e18 and sign is either 1 or -1.
        result = int256(n) * 1e18;

        // This is y = x * 2^(-n).
        int256 y = int256(x) >> n;

        // If y = 1, the fractional part is zero.
        if (y == 1e18) {
            return result * sign;
        }

        // Calculate the fractional part via the iterative approximation.
        // The "delta >>= 1" part is equivalent to "delta /= 2", but shifting bits is faster.
        for (int256 delta = 5e17; delta > 0; delta >>= 1) {
            y = (y * y) / 1e18;

            // Is y^2 > 2 and so in the range [2,4)?
            if (y >= 2 * 1e18) {
                // Add the 2^(-m) factor to the logarithm.
                result += delta;

                // Corresponds to z/2 on Wikipedia.
                y >>= 1;
            }
        }
        result *= sign;
    }
}

Where mostSignificantBit is a function that calculates the most significant bit of a number that can go as high as $2^{256} -1 $.


How can the VC-dimension of Turing machine be finite?

First, let me correct your definition of VC dimension: it is the largest size of a set which can be shattered.

If the VC dimension is $d$, then this means that for every set $C$ of size larger than $d$ there exists a function $f\colon C \to \{0,1\}$ which is not compatible with any function computed by an $n$-state Turing machine.

You are attempting to refute the claim that the VC dimension is $\Theta(n\log n)$ by showing that for any set $C$ of size $n^2$ there exists a single function $f\colon C \to \{0,1\}$ which is compatible with some function computed by an $n$-state Turing machine. However, what you need to do in order to refute the claim is to give a single set $C$ of size $n^2$ (say) such that all functions $f\colon C \to \{0,1\}$ are compatible with some function computed by an $n$-state Turing machine. Note the different quantifiers: you considered all $C$ and one $f$, but in fact you should consider a single $C$ but all $f$.

Finally, suppose that $M$ is a universal Turing machine having $n$ states. This doesn't mean that $M$ can compute arbitrary functions – in fact, $M$ computes a single function. What it does mean is that for any Turing machine $T$, $M(\langle T \rangle, x) = T(x)$. That is, if $M$ is given as input the pair $(\langle T \rangle, x)$ (where $\langle T \rangle$ is the encoding of $T$), then $M$ evaluates $T$ on $x$. This is different than what you claim, since the Turing machine being simulated is part of the input, that is, part of the set $C$.

In fact, in order to show that the collection of $n$-state Turing machines shatter a set $C$, you need to exhibit $2^{|C|}$ different Turing machines. Considering just a single universal Turing machine cannot possibly work.

Since there are only $O(n)^{O(n)}$ many different Turing machines having $n$ states (assuming the alphabet is fixed), this implies that the class of $n$-state Turing machines cannot shatter any set of size larger than $\log[O(n)^{O(n)}] = O(n\log n)$. This is how you get the upper bound on the VC dimension. The lower bound looks more challenging.


If $G$ is a tree, it has a unique MST whatever its weights are.  The weights could be unique, all the same, anything.


Algorithm Design Patterns vs. Algorithm Strategies vs. Algorithm Design Techniques vs. Algorithm Design Paradigms

Yes, they all refer to a categorization in terms of design paradigms (such as greedy, divide and conquer, dynamic programming, et cetera).


What is a good reference for NP hardness in the machine learning/optimization/operations research context?

In modern papers, and unless stated otherwise, NP-hardness is one of the following:

A decision problem is NP-hard if it is NP-hard with respect to many-one reductions.
An optimization problem is NP-hard if its decision version is NP-hard.

Sometimes, more informal notions are used. The most common one is probably hardness of approximation. When a theorem states that maximization problem X is NP-hard to approximate within a factor of $\alpha < 1$, it usually means that there is a many-one reduction from SAT (or some other NP-complete problem) an instance of X and a parameter $k$ such that

If the original SAT instance is satisfiable, then the value of the X-instance is at least $k$.
If the original SAT instance is unsatisfiable, then the value of the X-instance is at most $\alpha k$.

However, to be sure, you need to look at the exact statement being proved.
Your case is similar. The complete version of your paper proves the main theorem in Section 5. Theorem 5.2 on page 21 states exactly what holds in the Yes case and what holds in the No case (Theorem 5.1 shows that it is NP-hard to distinguish the two cases). You should be able to relate this to the informal statement appearing in Theorem 1.1.


prove(disprove) asymptotic exact bound (theta)


Enumerating all n-tuples over a finite domain

Use recursion.  Something like this:

def f(l, k):
    if l==0:
        yield []
    else:
        for i in range(k):
            for L in f(l-1, k):
                yield [i]+L

Here f(l, k) produces all lists of length l all of whose entries are in the range 0..k-1.  The idea is that if you have all lists of length l-1 (the output of f(l-1, k)) you can use that to generate all lists of length l, by using a for-loop.

If you're not familiar with that Python syntax, try this variant:

def f(l, k):
    if l==0:
        return [[]]
    t = []
    for i in range(k):
        for L in f(l-1, k):
            t.append([i]+L)
    return t

Note that [i] is a list containing a single element, i, and + is the list concatenation operator, so [i] + L is a list obtained by prepending the element i to the front of list L.


how many boolean functions exist that satisfy the condition

If we did not have this constraint, there would initially be $2^{2^n}$ possible boolean functions on $n$ boolean variables. We have $2^n$ unique inputs that we can either map to a 1 or 0 for any of them.

Now for this problem, we need to map a subset of those $2^n$ inputs because the rest will be implicitly mapped. For instance if we map $f(x_1, \neg x_2, \neg x_3) = 0$, this will implicitly map $f(\neg x_1, x_2, x_3) = 1$. This means only a subset of the $2^n$ inputs can be uniquely mapped, the rest will be implicitly mapped as described. For this, we need to determine how many pairs of inputs exist such that we have: $$(\{\ell_1, \ell_2, \ldots \ell_n\}, \{\neg \ell_1, \neg \ell_2, \ldots, \neg \ell_n\})$$ where $\ell_i$ is a literal (positive or negative) containing variable $x_i$. Intuitively, we should know that each pair contains 2 sets of $n$ variables so there should be $2^n / 2 = 2^{n-1}$ pairs possible. Another way to think about it would be to hold one variable constant positive, let's say $x_1$. We then define a new function: $$f_{x_1}(x_2, x_3, \ldots, x_n) = \ldots$$
In this function we "hold" $x_1$ to be positive so that we're only ever setting one of the sets in these pairs that we have described, thus we only have $2^{2^{n-1}}$ possible functions $f_{x_1}$. With this, we can now define $f$ pretty easily:

$$f(x_1, \ell_2, \ell_3, \ldots \ell_n) = f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

$$f(\neg x_1, \neg \ell_2, \neg \ell_3, \ldots \neg \ell_n) = \neg f_{x_1}(\ell_1, \ell_2, \ldots, \ell_n)$$

We basically use $x_1$ to say "we're looking at the positive instance of this input" vs "we're looking at the negative instance of this input". Then this configuration of $f_{x_1}$ will ensure they are opposite. Consider the following example on 3 variables:

$$\begin{array}{|c|c|c|c|}
\hline x_1 & x_2 & x_3 & f_{x_1}(x_2, x_3) & f_{x_1}(\neg x_2, \neg x_3) & f(x_1, x_2, x_3) \\
\hline 0 & 0 & 0 & 1 & 0 & 1\\
\hline 0 & 0 & 1 & 1 & 1 & 0\\
\hline 0 & 1 & 0 & 1 & 1 & 0\\
\hline 0 & 1 & 1 & 0 & 1 & 0\\
\hline 1 & 0 & 0 & 1 & 0 & 1\\
\hline 1 & 0 & 1 & 1 & 1 & 1\\
\hline 1 & 1 & 0 & 1 & 1 & 1\\
\hline 1 & 1 & 1 & 0 & 1 & 0\\
\hline
\end{array}$$

With this we can see $f_{x_1}$ is clearly a function over $n-1$ variables and thus there are $2^{2^{n-1}}$ possible functions that satisfy this.


Partial answer only.

For me, the paper is behind a paywall. So I can base this only on its abstract and your question.

I believe you have a point with your complexity doubts. I can see how to write an FO[LFP] self-interpreter, provided there is a way to handle large arities. In particular, the self-interpreter has a single, fixed, maximum arity and number of variables while the interpreted formulae should be unbounded with respect to arity and number of variables. I can see a few ways to go about that:

There is in fact not a single self-interpreter, but a family of such, indexed by maximum arity.
The structure that encodes the input (the formula plus the original structure) has in its domain not only (subformulae of the formula and) elements of the original structure, but also tuples of the original structure up to the required arity. Then, converting the original input into its encoding structure already imposes an exponential blowup.
For infinite structures, tuples can be encoded as single elements using a pairing function. On well-ordered structures, FO[LFP] can define (ordinal) arithmetic and hence such a pairing function. Possibly, the statement in the paper does not address finite structures at all?

For the Datalog self-interpreter, I suggest you start with a Datalog interpreter written in FO[LFP] and then convert that formula into a Datalog query.


Suppose that DFA for $A$ and $B$ are $D_A$ and $D_B$ respectively.
We will construct a PushDown Automata (PDA) for the given language $A \cdot B$ by combining $D_A$ and $D_B$ in a particular manner.
Modify the transitions of $D_A$ such that on reading any letter it pushes a symbol $X$ on the stack. Join all the final states of $D_A$ to the initial state of $D_B$ with epsilon transitions. Modify all the transitions of $D_B$ to Pop $X$ from the stack. Accepting condition will be that on reading a word we should reach one of the final state of $D_B$ and the stack should be empty.
It will be quite easy for you to convince yourself that this will accept the language $A \cdot B$ as required. Now, we can apply the standard method to convert the PDA to grammar to get the required grammar.


Recursive algorithm to find maximum value in 2D array

You can solve this using dynamic programming. For each $i$ and $\ell \leq k$, find the best solution for the first $i$ columns, when you are allowed to pick at most $\ell$ values.


A* isn't finished until all nodes with $f(n) < f(goal)$ are expanded.

So even though you have added $D$ to the open set you still need to expand $B$ because $f(B) = 11 < f(D) = 17$ after which $f(D)$ will become $12$


What's the difference between a "dead" and "empty" state?

That ∅ in the figure is just the name of that particular state in that machine.You could name it "cpx" if you want.

The figure is an example showing conversion from NFA to DFA. The conversion algorithm builds the DFA states from subsets of NFA states.The state named ∅ indicates that this state represents a particular subset of the states of the NFA, namely the empty set.

So, the symbol is just for the viewer to understand the significance of that particular state in the machine.


Measuring the length of a "loop" in a linked list in $O(n)$ Time?

There is a surprisingly simpler solution! Are you familiar with the tortoise and hare algorithm?
Start thinking from there: Understand this algorithm and why it works, and then you might get an idea or two for the problem


Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable

Your proof is wrong. Note if $M$ accepts $w$, it must halt on $w$, so $L_1\cap L_2$ is the empty set, which is of course decidable.

To disprove the statement, you can set $L_2$ to be $\Sigma^*$, i.e. the language containing all strings. Since $\emptyset$ is Turing recognizable, $L_2$ is co-Turing recognizable. However, $L_1\cap L_2=L_1$ is undecidable.


How to calculate the number of states in designing a Turing machine?

I think that given a decidable language $L$, you can always build a 2-states TM that recognizes it.

Indeed there exists a 2 state Universal Turing Machine $UTM_{2U}$ (with alphabet $|\Sigma| \geq 18$).

If $TM_i$ decides $L$ then $UTM_{2U}(i,x)$ decides $L$; so you can build a 2-states $TM_{2L}$ hard encoding $i$ in $UTM_{2U}$ but keeping only two states; the idea is:

add $2*|i|*|\Sigma|^{|i|}*|\Sigma|$ symbols to the alphabet that will represent the possible combinations of (state, head position, tape content, first symbol $\alpha$ of $x = \alpha x'$ on the tape)  of $UTM_{2U}$ on input $(i,\alpha x')$
adjust the transition table of $TM_{2L}$ in order to simulate the behaviour of $UTM_{2U}$ on the first $|i|+1$ characters of the tape using only the first cell of the tape (that initially will contain $\alpha$).

EDIT (alternate take :)

Given a generic $TM_L$ that recognizes $L$ there is an easier way to build an equivalent 2-states $TM_{2L}$.
I'll try to sketch its construction (anybody wants to check if it is correct? :)

Idea: simulate $TM_L$ using the tape to store at the same time the alphabet symbol of the original tape, plus the current state and head position of $TM_L$.
A single cell of the tape is a 5-tuple:

[(direction)(symbol)(current_state)(state_to_copy)]

that represents:

direction: 0 = we are scanning the tape from left to right
           1 = we are scanning the tape from right to left
symbol:    symbol from the alphabet of TM_L
current_state: if > 0 then the head position of TM_L is here and
               the state is current_state
state_to-copy: if > 0 then we are copying the next state to
               the left or right according to direction

Using the direction flag we can move from left to right and "execute" the
$TM_L$ transitions that moves the head to the right (i.e. we can copy the next head/state
to the right), then we can go back and "execute" the $TM_L$ transitions that moves
the head to the left (i.e. we can copy the next head/state to the left).
The transition table with two states is built in the following way:

STATE0

...from LEFT to RIGHT

// scan left to right until we found the cell with the head
Read(0, X, 0, 0)  -> Write(1, X, 0, 0)    stay in STATE0 and move R

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then add the
// following transition  which will start the copy of Qj on the right cell
Read(0, A, Qi, 0) -> Write(0, B, 0, Qj-1) enter STATE1 and move R

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then
// add the following transition (we will process it later):
Read(0, A, Qi, 0) -> Write(1, A, Qi, 0)   stay in STATE0 and move R

// if we are copying a state to the right continue:
Read(0, X, 0, Qj) -> Write(0, X, 0, Qj-1) enter STATE1 and move R

// when we reach a blank symbol, start moving from right to left
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move L

... from RIGHT to LEFT

// scan right to left until we found the cell with the head
Read(1, X, 0,  0) -> Write(0, X, 0, 0)    stay in STATE0 and move L

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then add the
// following transition which will start the copy of Qj on the left cell
Read(1, A, Qi, 0) -> Write(1, B, 0, Qj-1) enter STATE1 and move L

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then
// add the following transition (we will process it later):
Read(1, A, Qi, ) -> Write(0, A, Qi, 0)    stay in STATE0 and move R

// if we are copying a state to the left continue:
Read(1, X, 0, Qj) -> Write(1, X, 0, Qj-1) enter STATE1 and move L

// when we reach a blank symbol, start moving from left to right
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move R

STATE1

// we are copying the head/state to the right
Read(0, Y, Qk, 0) -> Write(0, Y, Qk+1, 0) enter STATE0 and move L

// we are copying the head/state to the left
Read(1, Y, Qk, 0) -> Write(1, Y, Qk+1, 0) enter STATE0 and move R

The 5-tuple (direction)(symbol)(current_state)(state_to_copy) must be encoded using a single symbol of $TM_{2L}$, so its alphabet size is:

$|\Sigma_{2L}| = 2 \times |\Sigma_L| \times |Q_L| \times |Q_L|$

P.S. with the same technique (if it is correct) a generic UTM can be converted to a 2-states UTM ... unfortunately we are not in 1956 :-)))


How is the following ML Curry expression evaluated

It seems that what you are confused about is the common practice of Curryfication: the function
$$ (\alpha\times \alpha\rightarrow \beta)\rightarrow \alpha\rightarrow \alpha\rightarrow \mathrm{bool} $$

Is parenthesized as:

$$ (\alpha\times \alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow (\alpha\rightarrow \mathrm{bool})) $$

and is equivalent to a different function:
$$ (\alpha\times \alpha\rightarrow \beta)\times \alpha\times \alpha\rightarrow \mathrm{bool} $$

The reason for this is the following. Take a function:

$$f:A \rightarrow (B\rightarrow C)$$
This is a function that takes an element $a:A$ and returns a function
$$ f\ a: B\rightarrow C$$
Apply this to an element $b:B$ and you have
$$f\ a\ b:C$$

It is clear that this is equivalent to a function $f':A\times B\rightarrow C$ that takes a pair $(a,b):A\times B$ and returns an element of $C$. The equivalence can be explicitely written:

curry : ('a * 'b -> 'c) -> ('a -> 'b -> 'c)
curry f' = function x -> function y -> f' (x,y)

or more simply

curry f' x y = f' (x,y)

The other direction goes:

uncurry : ('a -> 'b -> 'c) -> ('a * 'b -> 'c)
uncurry f = function p -> let (x,y) = p in f x y

or simply

uncurry f (x,y) = f x y


Impossibility for Byzantine Generals Problem where $n \leq 3m$

In the synchronous model of communication, there are $n$ agents which share a clock. In each round of communication, each agent sends an arbitrary message to each other agent, and then receives the message sent her by every other agent.

A protocol for byzantine agreement on $n$ agents supporting $m$ byzantine agents is a communication protocol for the agents satisfying the following properties:

Each agent receives an input bit.
The agents all start talking at time 0.
There are at most $m$ byzantine agents, whose behavior is arbitrary.
The other agents follow the protocol.
The protocol always terminates (this means that the non-byzantine agents always reach a special "terminate" state of the protocol, and then stop talking forever), with a return value which is also a bit.
The return values must all agree (note that this only applies to the non-byzantine agents).
If all input bits are the same, then the return values have to be the same bit.

The impossibility result states that such a protocol exists if and only if $n > 3m$.

There is a different model in which an agent can sign a message, and this signature cannot be tampered with. In this model (which I will not specify formally) the problem can be solved for any $n,m$.

One of the difficulties in the area of distributed systems is the complicated nature of the computation model. If you want to understand the meaning of impossibility results, you have to familiarize yourself with these models in full detail (even more detail than the rather informal treatment in this answer).


A reduction from A to B shows that A is "no harder" than B in some sense. We call it a reduction because it reduces the problem of solving A to the problem of solving B. This is a usage of the word "reduce" that is more mathematical and less about "size"; you can think of it as meaning that we've reduced the amount of work the world has to do, because even though we haven't solved A or B with the reduction we've made it so that a solution to B will automatically also be a solution to A.

Where A was a problem we didn't have any efficient solutions for, and where we already have an efficient solution for B, this does result in A getting "smaller" in a sense. For example, say we'd already come up with an exponential solution to A, and B is an NP-complete problem. Previously, the best we knew was that A was an exponential problem. After someone comes up with the A -> B reduction, now we know it's actually an NP problem.

Yes, you can use a reduction argument to show that an already-known-to-be-easy problem is "no harder" than a hard problem. You can in fact use a polynomial-time reduction from ANY problem in P to ANY other problem whatsoever (that has at least one "yes" instance and at least one "no" instance),  because you can "solve" the P problem in the reduction but simply encode the answer as an instance of another problem. Yes, this is pointless. But it's not "wrong" or inconsistent.

The problem you're having is purely in the analogy you're using, namely that a reduction is a "way of making a problem smaller". That is a reasonable metaphor for one of the usual aims of reduction proofs, which is to show that a problem is "easier" than previously suspected by finding a way to reduce it to another problem already known to be "easier".

But that doesn't help you with the other extremely common use of reduction arguments, which is to show that a problem C is impossible to solve, by finding a reduction from another problem D which is already known to be impossible. Here the reduction argument isn't "making D smaller", it's showing that C is "big".

Try to think of a reduction argument from A -> B as a way of showing that A is "no harder" than B.  When you think of it that way, it's not at all surprising that you can often reduce easy problems to hard ones; we already knew that they were easier! This account also easily explains the incomputability proofs by reduction; if the Halting Problem is no harder than X, then X can't be solvable.


Finding a reduction for two-Subset sum problem

There is a trivial reduction from Partition to your problem: given an instance $S$ of partition, construct the instance $(S,\frac{1}{2} \sum_{i \in S} i)$ of your problem. This shows that if you take any reduction from Subset-Sum to Partition, you immediately get a reduction from Subset-Sum to your problem. You can find the reduction from Subset-Sum to Partition in many places, or come up with it on your own.


What is the complexity of recurrence $T(n) = T(n-1) + 1/n$

By unfolding $$T(n) = T(n-1) + \frac{1}{n} = T(n-2) + \frac{1}{n} + \frac{1}{n-1} = \dots=T(0) + \sum_{k=1}^{n} \frac{1}{k}$$
Now we can easily approximate the sum on the RHS using that
$$\sum_{k=1}^{n}\frac{1}{k} \le 1 + \int_{1}^{n}\frac{1}{x} dx = 1+ \log{n} - \log{1} = 1+ \log{n}$$
Therefore $T(n) \equiv O(\log{n})$


Can all packing/covering problems be rephrased as set packing/covering problems?

If we restrict ourselves to problems in NP, then yes. There are NP-complete problems of either category, so (many-one poly-time) reductions exist; we can view these as "rephrasing".

Since integer programming is also NP-complete, these same is true for that one.

Problems outside of NP do not reduce to integer programming, but I am sure that any (meaningful) complexity class contains examples of both covering and packing problems.

It's not the "type" of a problem that determines its hardness. There are satisfiability problems all the way from linear complexity to undecidability, to name just one example.