Are coevolutionary "Free Lunches" really free lunches?

Coevolutionary algorithms can't magically accelerate progress on any arbitrary problem class. So in that sense, the conclusion at the end of the question is correct. However, it doesn't follow that all coevolutionary free lunches are trivial, as the conclusion of the question suggests.

I can't offer an exhaustive account of all the kinds of coevolutionary free lunches, but I can offer two examples, the first of which is trivial, and the second of which I would argue is nontrivial. The second is nontrivial because it helps explain why the no free lunch theorem really must hold.

The important difference between the two examples is this: in the first, the competing algorithms are competing to achieve the same overarching goal, while in the second, the competing algorithms are trying to achieve different goals. In the second case, the mismatch between the two algorithms' goals allows interesting things to happen. I'll begin with the trivial example.

Opponents seeking the same goal

Imagine a very simple optimization problem in which the search landscape is a 7x7 grid of cells. The primary goal is to find the cell with the maximum value. 48 of the cells have a value of 0, and one randomly chosen cell on the grid has a value of 1.

Our secondary goal is to discover a search strategy that finds the maximum value more quickly. But it follows from the initial problem that no strategy could possibly beat random search here, because nothing can be learned from one cell about another. Nonetheless, the coevolutionary free lunch theorem holds! Here's why:

Suppose you have two optimization algorithms, A and B, both searching the grid. It doesn't really matter what strategy they use, but for concreteness, we'll stipulate that they both use a random search strategy. The only difference between them is that B pays attention to A's moves, and when it sees that A has found the maximum value, it jumps to that cell too. In some sense, when that happens, B has still "lost" the contest. But if you run a lot of competitions, and then compare the average performance of A to the average performance of B, you'll see that B finds the maximum value faster on average.

The explanation is simple. The average time to first discovery -- whether by A or B -- stays the same. But whenever A beats B to the win, B doesn't bother looking anywhere else. It skips ahead to the best cell. When B beats A to the win, on the other hand, A just continues searching, plodding along until it finds the maximum value on its own.

This looks like a win if you're only counting the number of moves B makes. If you look at the total number of moves that A and B make together, they actually do worse together than either would on its own, on average. That's because of A's obliviousness. If we change A to behave the same way as B, then they do about as well together as either would on its own -- but no better.

So here, modeling both algorithms together returns us directly to the no free lunch zone, just as the question argues. In effect, A and B are just performing random search algorithms in parallel. The final number of search operations remains the same.

Opponents seeking different goals

Now imagine a very different scenario. Suppose we have a classification problem: recognizing sheep. Here, A's job is to look at a stream of pictures and say whether there are sheep in them. Simple enough.

But B's job is very different. B has the power to inject pictures of its own into the stream! Its goal is not to identify sheep; it just wants to slow A down.

How can B do this? There's a great blog post and associated Twitter thread about a closely related question by Janelle Shane. The Twitter thread begins:

  Does anyone have a picture of sheep in a really unusual place? It's for pranking a neural net.

And here's one of the first replies:

  How about an orange sheep?

Here's the orange sheep:

Turns out, this was perfect for pranking:

  You totally got it. Orange sheep are not a thing it was expecting.
  "a brown cow laying on top of a lush green field"

Here are a couple of other examples from Shane's blog post:

So what does this have to do with our problem? We can connect them by being more precise. Suppose A's goal is to reach greater than 99% accuracy, and B has the power to inject one picture into A's stream for every nine "natural" pictures. B looks for patterns in A's behavior and uses them to find pictures that mess with its model. This will keep A's accuracy below 99% for much longer than if A saw only "natural" pictures.

Two things follow from this. First, B will do much better if it pays attention to what A does. If B just picks images on the basis of some randomly chosen general principle like "sheep in odd places," then there's a good chance that A will be prepared for them already. If not, it will quickly learn to handle them correctly, and B will then have to adopt a new strategy. On the other hand, if B watches A's behavior, it can pick out the specific things that A is worst at, and focus on those. As soon as A improves at one of them, B can have another one ready to go. As long as B can find patterns in A's behavior, B will always present the most challenging images for A.

Second, A will do much better if it pays attention to which images B picks. After all, B is looking for patterns in A's behavior. If it finds patterns, then it will use those patterns to send fake or troublesome pictures to A. In turn, that means that there will be noticeable patterns driving B's choices. Here again, if A is paying attention to the patterns in B's behavior, it will more quickly be able to identify which pictures B is injecting.

What's important is that in this scenario, both A and B are relying on data that is guaranteed to have patterns. It is guaranteed to have patterns because if A is doing its best, A is doing something other than random search. And if B is doing its best, then B is doing something other than random search.

So initially, this looks like a really compelling free lunch situation. But what have we actually shown? We've shown this:

  As long as A is doing something other than random search, B can always find out-of-band samples that A's methods cannot handle.

That's the no free lunch theorem in a nutshell!

The only way A can prevent B from finding out-of-band images is by behaving in ways that look random to B. But if A's behavior isn't really random, then in the very long run, B will always be able to find the pattern -- even if B itself is only doing random search.

The very same argument works in the other direction. The only way B can prevent A from noticing patterns in its images is by behaving in random-seeming ways. But if B's behavior isn't really random, A will eventually find the pattern, even if it's only doing random search.

In this scenario, both algorithms will try to fool each other by adopting more and more complex, random-seeming behaviors. So in the very, very long run, they will slowly converge to a truly random search -- which is the best any algorithm can do on average across all problem domains.

An infinite pool of randomness

It might be that these coevolutionary learning strategies do still have this advantage over others: they may encourage both algorithms to explore the space of relevant non-random behaviors more quickly or extensively. I am not even sure of that. Either way, the no free lunch theorem holds in general, because the space of possible non-random behaviors is far, far smaller than the space of possible random behaviors.

How do we know? It would be off topic to go into a detailed proof, but consider the related question of how many long strings can be compressed into shorter strings. Regardless of the compression method, the majority of all strings cannot be compressed at all. This is easy to prove with a bin-counting argument. Suppose we consider binary strings, and start with the empty string. Assuming there can be no negative-length strings, that's incompressible. Now consider length-1 strings. There are two, but there's only one length-0 string, so only one of them can be compressed. Now we have two incompressible strings, and a third string that can be compressed by one bit. Moving on to length-2 strings: there are four, but there are only two length-1 strings, and the one length-0 string is already taken, so we can only compress two of the length-2 strings. The other two are incompressible. That's three compressible strings and four incompressible strings... and so on.

As the numbers get higher, one of the things you notice is that even among the compressible strings, half of them are only compressible by one bit, because they compress to strings that are themselves incompressible. A quarter are only compressible by two bits; an eighth are only compressible by three bits. No matter how you slice it, the number of substantially compressible strings is always much lower than the number of strings that are incompressible or barely compressible.

The line of reasoning for random behavior is similar. You could also connect these ideas to the proof that there are vastly more real numbers than integers. In the global scheme of things, the no free lunch theorem is true because the scope of randomness is unimaginably vast.


Genetic Algorithm Getting Stuck on Certain Values

As @Ray mentioned, the solution was to change how I encode the values. I encoded the positions and radius as floating point values initially. I switch from 32-bit IEEE-754 encoding to a 16.16 fixed point representation, since I didn't need more precision than that. I then converted from the fixed point representation to a 32-bit Gray code to store the genes. That allowed the simulations to converge on a solution much more quickly. It also seemed to help the mutations and crossover produce higher quality variations.


What is the time complexity of MergeSort without its penultimate merge?

It will still take $O(n \log n)$.

There are four steps in mergesort.

Divide the list in half.
Mergesort the left half.
Mergesort the right half.
Merge the two together.

If I understand right, you're asking about removing the fourth step, in the final stage only (that is, not in any of the recursive calls).

In this case, you'll still have to do step 1 in $O(1)$, step 2 in $O(\frac{n}{2} \log \frac{n}{2})$, and step 3 in $O(\frac{n}{2} \log \frac{n}{2})$ (since steps 2 and 3 still call conventional mergesort, which is $O(n \log n)$).

So your total time complexity will be $O(1 + \frac{n}{2} \log \frac{n}{2} + \frac{n}{2} \log \frac{n}{2}) = O(n \log \frac{n}{2}) = O(n \log n)$.

The final merging only takes $O(n)$ time; it's the recursive part that's the real cost.


Absorbing Markov Chains: An efficient algorithmic approach

There are several possible techniques.

Let $P^t$ denote the matrix $P$ raised to the $t$th power.  Then $(P^t)_{i,j}$ (the $i,j$-th entry of that matrix) represents the probability that if you start in state $i$, you'll end in state $j$ after $t$ steps.  If $t$ is sufficiently large, this is a good approximation to the limiting value as $t \to \infty$.

So, one possible technique is to choose a sufficiently large value of $t$, compute $P^t$, and then evaluate $(P^t)_{i,j}$.  Notice that you can compute $P^t$ using $O(\lg t)$ matrix multiplications using the square-and-multiply algorithm, so it is possible to choose a very large value of $t$.  Unfortunately, if $P$ is a $n\times n$ matrix, this will be slow: it will take $O(n^3 \log t)$ time, which is significant if $n$ is very large.

Another option is to use the power iteration method as used in the PageRank algorithm.  Basically, you set the vector $x^0$ to be a vector that $1$ in its $i$th element and all zeros elsewhere.  Then, you iteratively compute

$$x^{k+1} = P \cdot x^k.$$

After $t$ steps, you have computed $x^t$; now you read off the $j$th element in that, i.e., $(x^t)_j$, and that is the probability after $t$ steps.  If $P$ is dense, each iteration takes $O(n^2)$ time, for a total of $O(n^2 t)$ time.  That might be better than the previous method, but still not too encouraging if $n$ is very large.  However, in many real applications, $P$ is sparse, and thus each iteration can be computed in $O(n)$ time; in this case, the method takes $O(nt)$ time, which can be quite efficient.

How large does $t$ need to be?  In practice, often $t$ doesn't need to be very large.  You can analyze how large $t$ needs to be, as a function of the gap between the first largest and second largest eigenvalue of $P$.  In particular, if $\lambda_1$ denotes its first largest eigenvalue and $\lambda_2$ its second largest eigenvalue, for a Markov process we have $\lambda_1 = 1$ and $\lambda_2 \le 1$.  Now effectively we need $t$ to be large enough that $\lambda_2^t$ is much smaller than $1$ (negligible compared to $1$).  If $\lambda_2$ is not too close to $1$, then $t$ won't need to be very large.  In particular, $t = O(\log(1/(1-\lambda_2)))$ iterations suffices.

As a result, the power iteration method can often be very effective and very efficient.


When choosing a specific model, to which you will try to fit your data into, you must know something about the problem. There is no way around it, machine learning cant do this magic for us, we have to know something.

First, convince yourself why complicated models can cause overfitting. Suppose I'm trying to learn some real valued function $f$, and I'm given $n$ samples of the form $S=(x_1,y_1),...,(x_n,y_n)$. If i choose to model my data by some polynomial (of arbitrary degree) then for any set of samples $S$, i can find a function in my model with zero training error, although it is likely to have high generalization error (a degree $n$ polynomial passing through all points in $S$ can always be found, regardless of any structure of the points in $S$). Perhaps using polynomials of degree$ \le 3$ will be good enough to model my data (it doesn't suffer from the previous problem). Why 3? I don't know, this depends on the specific types of functions I'm trying to learn.

A more concrete example, suppose you want to learn what is the appropriate dosage of some medicine, and you are given samples of the form $(x_1,y_1),...,(x_n,y_n)$ where $x_i\in\mathbb{R}$ denotes the dosage, and $y_i\in\left\{\text{'good'},\text{'bad'}\right\}$ tells you whether the dosage $x_i$ worked (it can be too high or too low). Allowing your algorithm to choose some arbitrary function can result in strange outputs. For example if you received the samples $(1,\text{'bad'}),(2,\text{'good'}),(3,\text{'good'})$ then a function $f:\mathbb{R}\rightarrow\left\{-1,1\right\}$ which satisfies $f(1)=-1,f(2)=f(3)=1$, but is random everywhere else, is consistent with the samples. Such $f$ will probably have no indication on the true effect of the medicine. Now, I'm no doctor, but perhaps it is worth considering functions of the form:

$I_{a,b}=\begin{cases}
+1, & x\in [a,b] \\
-1, & \text{otherwise}
\end{cases}$.

When choosing to model my data using such functions (segments), i use my knowledge on how medicines work (there is some appropriate dosage interval, while large deviations to any side could be dangerous).


Is there a unit of measurement that can express code execution speed in absolute terms?

I think the comparison is a bit clouded actually. Some unspoken concerns are that you can't claim python will compile to precisely 72+8n bytes by reading the high-level code.  There's a virtual machine with untold optimization and overhead heavily dependent on memory layouts, CPUs, your OS, even your version of Python. Memory blocks might be allocated in fixed increments: 1KB page even if all you need is 100 bytes.  Then within your fancy hyperthreaded CPU it might decide to pack bytes together, or rip them apart to run someone else's code along side yours.  So how many physical bytes you use in the program can be far more than you expect you need.  I think those issues seem to hit at the same ambiguity you considered with time.

In the literature on complexity these concerns are usually given with footnotes.  That is we accept that asymptotics are necessary for modeling time and space because we cannot quantify the really fine details, and if we could, the results would be unusable.

So I think the answer to your question is no, there is no such unit, but that there isn't one for space either.  It is important to remember that the role of modeling an algorithm is to know its behavior in broad strokes.  If you model it so precisely that you can predict it to the fine detail chances are your model is as complex to evaluate as the thing it is modeling.  We need models that simplify so we can get at identifying the big bottlenecks and not get stuck in the weeds.  (Probably that is a theorem whose proof is basically the same as the proof that there exist Kolmogorov random sequences -- but I only speculate on that point.)

As a side remark, there are time-space complexities which measure the two together and these can come closer to modeling resource use in real life.  These can be quantified with units of "power" (Watts) or in economic models as "cost" ($$ spent to run).


Rational agent question from Russell and Norvig

This question is obvious as you told and its purpose is to ensure that the reader has understood a part of the chapter.
You are right that the actions that the agent does will differ in the time period T. They will also differ after this period, because the agent's actions will have no value.

One example may be for a car agent that has to cover as much distance as possible and has limited fuel. If only the distance reached during the first hour counts, the car could take it in full throttle(exhausting the fuel very fast). However if there was no time limit the car agent should choose the optimal speed that maximizes the distance covered per fuel unit spent.


A greedy algorithm for the bottle filling problem

Here is the "greedy" idea.

Suppose you need to choose one bottle to fill completely with minimal amount of water. Which bottle will you choose?

Once you have chosen one bottle and fill it completely with water, the situation you are in now is just as before but one bottle less. You can apply the "greedy" choice again. And so on.


Are most metaheuristic algorithms different metaphors for the same method?

Comparing ideas

If you want to compare the ideas involved on the various metaheuristics, a good starting point for the comparison is to think of them as Population based vs Trajectory based. Population based metaheuristics works with the concept of create a solution that mix components of good solutions. Trajectory based metaheuristics works with the concept of creating a solution and iteratively do improving modifications(moves) on it. With the image below, you can visualize this dichotomy and other possibles parameters for comparison.

Comparing performance

To compare performance, a common approach is to use time to target. Given a known solution and its objective value, how fast my metaheuristic achieve this value? This site provides a tool that helps in this task.


Let $x$ be the real number you wish to convert. We will assume without loss of generality that $0 \le x < 1$. Form the Dedekind-completeness of the order on $\mathbb{R}$, it follows that $x$ can be (almost) uniquely written as

$$
x = \sum_{h=1}^{\infty} 2^{-h} \alpha_h
$$

where $a_h \in \{ 0, 1\}$ for all $h$. Now observe that:

$$
2x = \sum_{h=1}^{\infty} 2^{-h+1} \alpha_h = \alpha_1 +\sum_{h=1}^{\infty} 2^{-h} \alpha_{h+1}
$$

where the rightmost sum is nonnegative and less than $1$. Multiplying by $2$, therefore, allowed us to discover a single binary digit of $x$, namely $\alpha_1$. The same procedure can be iterated to yield as many digits as you wish.


Finding negative cycle using Bellman Ford

Choosing a arbitrary vertex as source may not reach the negative cycle in the graph.

Assuming the graph is directed. The cycle may not be visited if there are vertices that the source node cannot reach, such as: (assuming $V_0$ is the source)

Graph containing different components or

There are vertices behind the source vertex.

So, the solution is to:

Set Dist[v]=0 for all v that has 0 in-degree (or alternatively, add an additional vertex as source, which connects to all other vertices with 0-weighted edges. (similar to Johnson's algorithm))
Run Bellman-Ford for V-1 iterations
Perform an additional iteration for marking negative paths (by ancestor backtracking)
Maintaining the minimum cycle while perform a BFS starting from the 0-in-degree vertices.


Is the reverse of a closed under operation maintainable?

No, if $L_1\cup L_2$ is decidable $L_1$ and $L_2$ are not necessarily decidable.

Here's an example.

$$\begin{align}
L_1 &= \text{any language that is not decidable.}\\
L_2 &= \Sigma^*\setminus L_1.
\end{align}$$
$L_1\cup L_2$ is $\Sigma^*$, which is decidable. However, $L_1$ is not decidable. In fact, $L_2$ is not decidable, either.

The proof given in the preformatted block of the question is a proof for the original proposition, "if $L_1$ and $L_2$ are decidable,  then $L_1\cup L_2$ is decidable". It is not a proof for its converse proposition.

To prove its converse proposition, all you can assume is a Turing machines that decides $L_1\cup L_2$. There is no way that you can construct a Turing machine that can decide $L_1$ from that machine.

Intuitively, one condition cannot imply two other conditions. That is, "$L_1 \cup L_2$ is decidable" cannot imply both "$L_1$ is decidable" and "$L_2$ is decidable"

Here are a few related exercises.

Exercise 1. Does $L_1 \cup L_2$ is regular imply $L_1$ is regular and $L_2$ is regular?

Exercise 2. Does $L_1 \cup L_2$ is context-free imply $L_1$ is context-free and $L_2$ is context-free?

Exercise 3. Does $L_1 \cup L_2$ is recursively enumerable imply $L_1$ is recursively enumerable and $L_2$ is recursively enumerable?

Exercise 4. Raise a question similar to the above question.

Exercise 5. If you know that $L_1\cup L_2$ and $L_1$ are both decidable, does that imply $L_2$ is decidable?

The case with intersection is the same. Please check question if $L_1$ and $L_2$ are languages over the same alphabet and $L_1\cup L_2$ is context free, at least one of them must be context free, its answer and its exercises.


Do the following two CFGs describe the same language

No. The word "abab" is described by (1) but not (2). You can test and visualize this here.
Trying to think about it inductively: (1) can only prepend "a" or "b" to a string while (2) can only prepend "a" and only append "b".
Switching the order of a production does not necessarily change the language the grammar represents, but it is in this case. As to the second part of your question, there is no generalizable or efficient way to determine whether two CFGs describe the same language.


If $M$ recognizes an infinite language, then $M$ has a cycle

Whithout a cycle, each string can only traverse a state once. If it is at a state $q$, there exists no string $x$ that can return the machine to state $q$. So if a string can only traverse each state once, then we can bound the lenght of the string to k, the number of states. Thus you can only represent a finite number of strings if they are bounded in length ($\sum_{n=0}^{k-1} |\Sigma|^n$). Thus to recognize an infinite language, there must be a cycle.


Why is an Artificial Neural Network with high accuracy score giving poor results?

You're testing your neural net with data from the training set, of course it will get you great results. But you're neural net is now trained for a specific data and is unable to make generalization. This is known as Overfitting.

You should either split your data into test/train or use another technique to estimate your NN performance. A good technique is K-fold Cross validation.

Also check Overfitting wiki page and Cross validation on sklearn if you want more details.


A general picture of formal verification in software

A formally proven program is a formally proven program regardless of which language it's in. Just because a program is written in Coq and perhaps extracted to OCaml or Haskell, rather than written in a more “enterprisy” language such as C++ or Java, doesn't make it any less of a program.
Proving programs written in general-purpose programming languages, even “tame” ones like Haskell, is hard because these languages typically include a lot of convenience features, dark corners for performance and to interface with the operating system, and rich and complex libraries. To prove a property of a program, you first need to state this property, and the statement embeds the semantics of the language that the program is written in. When you try to formalize languages that were initially designed without a formal semantics (which is almost all of them), you very quickly hit dark corners which the English description leaves unspecified, or where it's ambiguous, or where it's outright self-contradictory, or where the reference implementation doesn't do what the description says and that's considered a bug in the English rather than in the implementation. The state of the art of proving properties of programs written in a preexisting language is to restrict the programs to a subset of the language.
What goes into that subset is highly variable. Syntactic sugar is not too difficult: the semantics just needs to translate it into simpler constructs. Reflection properties aren't particularly difficult to model, but may make the model a lot more difficult to reason about (for example, it invalidates properties such as “this snippet of code doesn't have any way to reference this variable, therefore it cannot change its value”), so many frameworks rule this out. Interactions with the operating system (typically via libraries) are problematic because they require modeling the operating system, which get be extremely complex. Floating point operations are hard because keeping track of the approximations across successive operations causes a huge blow up.
For C, one of the main large subsets with a formal model is CompCert C, the language of CompCert. CompCert is a formally verified compiler (written in Coq), so if you prove a property of the C program, you can additionally get a proof of the generated machine code. CompCert C is a very large subset of C99, but the formalization excludes most of the standard library and some quirks of the language.
To prove a program that is written in a (suitable subset of a) real-world programming language, the program needs to be structured in such a way as to make the proof tractable. In practice, this means having written and proved the program first in a higher-level language (which has no implementation on real hardware), and using this higher-level language as a specification of the final program. Often there are several levels of successive refinements between the executable program and the specification.
It's fairly common that the final program is not written manually, but extracted mechanically from a higher-level language. For example, writing Coq which is extracted to OCaml, or writing F* which is extracted to C. But the opposite approach is possible as well, for example writing (“tame”) C, annotating it with properties of functions and other code subdivisions, and using Frama-C to prove those properties (and the implied property that the C program has no undefined behavior).
When you have a formal semantics of a programming language and a way to express properties of programs, proving these properties is a mathematical theorem. Typically these theorems don't involve any complex mathematics such as calculus (unless brought in by the application domain, such as tracking the movement of a physical object), but they're difficult to prove because involve very large formulae, and contain arithmetic statements ($x^n+y^n=z^n$ is not a complex equation, but solving it is not elementary!). It's theoretically impossible to write a program that can prove a non-trivial semantic property of all programs, and practically impossible to write a program that can prove many interesting properties of typical programs. Formal verification involves a combination of breaking the problem down into sufficiently small steps (writing small functions and stating enough precise properties of those functions), having a tool automatically prove some of those properties (such as a SAT solver for propositional logic), and having humans write proofs where the computer can't do it (but the computer will check the human's proof). Proof assistants such as Coq and Isabelle come in for this last step.
Formally proving a real-world program is a huge effort, requiring a much larger amount of time and expertise than the typical software project. It's rarely done outside of high-assurance environments, mostly environments with high safety requriements such as transportation (planes, trains, not so much cars), sometimes environments with high costs such as space or (very rarely) with high security requirements such as smart cards.

if we just check say a sorting algorithm on lists of length <n with entries between 1 and n for some fixed n, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general.

That would not be a formal proof unless the program had a limit of n items for its input. I don't know this book, but I suspect either you misread something. Formally checking a sorting program would involve proving its correctness for all n.


How is the (local) clustering coefficient defined for vertices with degree 1

Yes, it is reasonable and common to have $C_i = 0$ when $k_i < 2$. This is sometimes a matter of taste, and some software libraries like igraph lets the user define how to handle the small-degree cases (i.e., whether to return 0 or NaN).


boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$

Since you are allowed an $n^{O(k)}$ size circuit, you could go over all possible $k$-length paths originating at $u$. The first level will contain $n^{O(k)}$ AND gates, one for every possible sequence of vertices $v_1=u,v_2,...,v_l=v$, for $l\le k$, and in the second level you input the results of the previous level to an OR gate.


The decision version of this problem is NP-hard (and so NP-complete), by reduction from Hitting Set.

Let $S_1,\ldots,S_m$ be an instance of hitting set. We will have the following vertices and edges:

Vertices $A_i$ for $1 \leq i \leq m$ and $A_{i,j}$ for $1 \leq i \neq j \leq m$.
Vertices $B_u$ for every $u$ in the universe of the hitting set instance, and $B_{i,j}$ for $1 \leq i \neq j \leq m$.
Vertices $C_i$ for $1 \leq i \leq m$ and $C_{i,j}$ for $1 \leq i \neq j \leq m$.
For every $u \in S_i$, edges $A_i \to B_u \to C_i$.
For every $1 \leq i \neq j \leq m$, edges $A_{i,j} \to B_{i,j} \to C_{i,j}$.
For every $1 \leq i \neq j \leq m$, edges $A_i \to B_{i,j} \to C_j$.

Every feasible solution to this instance of your problem has to contain each $B_{i,j}$, since this is the only way to connect $A_{i,j}$ and $C_{i,j}$. Hence every $A_i$ is automatically connected to every $C_j$ for $j \neq i$. In order to connect $A_i$ to $C_i$, we need to have $B_u$ for some $u \in S_i$. Hence the minimal solution contains $m(m-1) + k$ vertices iff the hitting set instance has a minimal solution with $k$ elements.


How do I find depth and height of all nodes in a bounded semilattice?

If you do a topological sort and then traverse the nodes in reverse topologically sorted order, you can annotate each node with its height in linear time.  Similarly, you can annotate each node with its depth in linear time by traversing in topologically sorted order.  This achieves linear running  time, which is significantly faster than the quadratic time approach you mention.


TCP Connection Termination - FIN, FIN ACK, ACK

A TCP implementation might send a standalone FIN in the first closing segment. However, it can also send a FIN ACK, instead.

The latter is strictly better:  the implementation can bundle a "free" ACK with the FIN segment without making it longer. This is because, if you don't ACK, there is still room in the segment for the ACK number, which will be ignored, and waste bandwidth. Hence the last-sent ACK is simply re-sent, just in case the receiver missed it.

This is true for all TCP segments. Hence, except for the very first SYN segment, where the sender has no information about the ACK number, all the other segments will usually have the ACK flag on.


Hint: Given $T(n)$, any $k \leq n$, and an input $x$, it is enough to run $M_k$ for $T(n)$ steps in order to decide whether it halts on $x$.


Algorithm for computing volume of union or intersection of n-dimensional convex polytopes given their facets?

A standard approach is to decompose it into a bunch of triangles (well, the n-dimensional generalization of triangles), then compute the volume of each triangle and sum them up.  Have a look at https://mathoverflow.net/q/979 or https://scicomp.stackexchange.com/q/2881.  Be warned that this could take exponential time.

There are also algorithms for approximating the volume of such a polytope, if that is useful to you.


Worst known case for log rank conjecture

The function is described in a footnote in Nisan and Wigderson's paper On rank vs. communication complexity. It is

$$
E(z_1 \dots z_6) = \sum_i z_i - \sum_{ij} z_{i}z_{j} + \\z_1z_3z_4 + z_1z_2z_5 + z_1z_4z_5 + z_2z_3z_4 + z_2z_3z_5 + \\ z_1z_2z_6 + z_1z_3z_6 + z_2z_4z_6 + z_3z_5z_6 + z_4z_5z_6.
$$


How does Hassin's algorithm for the Restricted Shortest Path work?

I have one theory now, which is that the final application of the exact algorithm on the scaled costs has complexity $\mathcal{O}\left(|E| OPT\frac{(n-1)}{LB\epsilon}\right) \subseteq \mathcal{O}(|E| 2LB\frac{(n-1)}{LB\epsilon})=\mathcal{O}(|E| 2\frac{(n-1)}{\epsilon})=\mathcal{O}\left(|E|\frac{n-1}{\epsilon}\right)$ which is then polynomial in $n \le \sqrt{|E|}$ and $\epsilon$. Can anybody confirm this?


How to compute amoritized cost for a dynamic array?

I think your particular structure does not have amortized $O(1)$ cost, and you identified the problem.

Your general approach is salvageable, but you either need to grow less aggressively or shrink less aggressively. The standard solution is to grow from capacity & size $n$ to capacity $2n$ and to shrink from capacity $n$ and size $n/4$ to capacity $n/2$.


Why are hash map look-ups assumed to be $O(1)$ on average

Because we generally use the RAM model of computation with uniform cost model when computing the running time of operations on a hash table, and the RAM model with uniform cost states that the time to do a single operation on an entire machine word is $O(1)$.  Also, we generally assume that the hash value fits within a single machine word.

Thus, the running time of computing a hash value is not $O(l)$, but rather $O(1)$ [assuming both the value being hashed and the hash value fit within one word, or a constant number of words].

Moreover, when you choose the hash function and size of the hashtable appropriately, the expected value of $k$ is $O(1)$.  In particular, the number of buckets is not fixed, but increases as the number of items in the hashtable grows.  The number of buckets it is usually chosen to be some function of $n$; say $m = 4n$, or something like that.  In any case, we usually choose $m$ so that $n/m = O(1)$.  Therefore, the (expected) running time to find an item within the bucket is $O(1)$.

Therefore, the total (expected) running time is $O(1)+O(1) = O(1)$.

So why do we use the RAM model with uniform cost model?  Because it's often a better match to reality than other alternatives.


The average complexity of the search from the back to the front is equal to
$$
  \sum_{i=1}^n  \frac{2i}{n(n+1)}(n-i+1) = \frac{2}{n(n+1)}\sum_{i=1}^n i(n-i+1) = \frac{2}{n(n+1)} \frac{1}{6}n (n+1) (n+2) = \frac{1}{3}(n+2)
$$
which is indeed linear.


Inference of a measure for a decreasing chain

Yes.  This is possible.  $t=1$ suffices.  Take

$$\begin{align*}
f(m,n-1) &= Cm + D\\
f(m,n-2) &= f(m+v_{n-2},n-1) + 1 = Cm + C v_{n-2} + D + 1\\
f(m,n-3) &= f(m+v_{n-3},n-2) + 1 = Cm + C v_{n-3} + C v_{n-2} + D + 2\\
&\ldots\\
f(m,i) &= Cm + C v_{i} + \dots + C v_{n-2} + D + n-1-i
\end{align*}$$

where we take the constant $C>0$ to be at least $n$; we choose a constant $D>0$ that's large enough that the output of $f$ is always positive; we take $t=1$; and we use the standard order on $\mathbb{N}$.  Then you can verify that this satisfies all the conditions.

How do you find this?  As always, start with small cases.  Start with $n=2$ and see what has to hold of $f$, and try to construct a $f$ that meets the conditions.  (One way to ensure that $x>_t y$ is to set $x=y+1$; in the construction above, I used that to construct $f$ that satisfies the condition by definition.)  Then try $n=3$.  Then generalize.  The above definition follows as a straightforward consequence of your requirements; if you choose elements of $f$ in the right order, it becomes routine to fill out the truth table of $f$ so all the requirements are met.


What's the difference between Row Polymorphism and Structural Typing?

Structural type systems don't necessarily have anything to do with records. For instance, you could have a system where:
data Bool = False | True
data Two = Zero | One

are actually the same type, because they are both types with two nullary constructors. It also doesn't necessarily tell you much about records, because even though types are determined by their structure, the two records:
{s : S ; t : T}
{s : S ; t : T ; u : U}

are not the same structure, so you could have structural typing without there being anything convenient about these two types.
Similarly, row polymorphism in isolation doesn't tell you much---just that you can quantify over rows, and probably use them with e.g. a record type parameterized by a row. But there are all sorts of variations on what you can do with rows that really specify the capabilities of the system.
Usually with structural records people at least want subtyping. That allows you to say that my second record type above is a subtype of the first, so that you can pass the latter to anything expecting the former. A typical way to do this with row polymorphism is to instead quantify over the extra fields that may be present, and use some kind of row concatenation.
So perhaps a more targeted question is what is the difference between subtyping and quantifiers. The answer to that is generally that subtyping cannot express quantified types unless the quantified variable only occurs exclusively covariantly or contravariantly. So we could say:
(forall a. a -> T) ~= Top -> T
(forall a. T -> a) ~= T -> Bot

But for a type like forall a. a -> a, there is no one type to pick for a without losing information.
This extends to systems with just record subtyping vs. (appropriate) row polymorphism. However, if you have a system with subtyping and quantifiers, and subtyping can apply to quantified types, then the differences might be a lot more subtle. Having both quantifiers and subtyping can get quite tricky, though (not that row polymorphism is easy to get right, either).


Can a Turing machine or Push Down Automaton construct languages of type 3?

The set of languages of type $3$ is a proper subset of the of languages of type $2$. In other words, a language of type $3$ is also a language of type $2$.
If some automaton can recognize languages of type $2$, then it can also recognize languages of type $3$.


Can Non-Linear Grammars generate Regular Language?

You are confused a bit I believe by using the terms grammar and language somewhat interchangeably.

A grammar is a set of production rules. A language is a set of words. A language is described, or generated by a grammar.

They are not the same and you should be careful at all times to see which is which.

There are a lot of terms such as "context-free", "linear", "regular", etc, that are direct properties of grammars. That is their original definition.

These terms when applied to a language, has a different, indirect meaning. When I say that a language L is X for those above properties, I mean that there exists a grammar with property X that generates L.

Now this can get confusing. Let's take your original grammar. It itself is not linear or regular, but the language it generates is both. Why? Because I can construct another grammar for it which generates the same language, which has those properties:

$$S \to A$$
$$A \to aaA \mid B$$
$$B \to bB \mid \epsilon$$

If you want to be even stricter I could make it a strictly right-linear grammar without epsilon productions (other than the whole language being nullable):

$$S \to aA_2 \mid bB \mid \epsilon$$
$$A_1 \to a A_2$$
$$A_2 \to aA_1 \mid aB \mid a$$
$$B \to bB \mid b$$

Finally, we have that for language classification we have (among others):

$$\text{Left-linear} = \text{Right-linear}   =\text{Regular} \in \text{Linear} \in \text{Context-Free}$$

  Can I then say that above language is an example of non-linear, regular language?

That is indeed wrong, because the language above is linear. You are confused because you are looking at the grammar, which isn't linear. Just because a certain grammar for a language isn't property X doesn't mean that there doesn't exist another grammar that generates the same language that has property X.

That's why it's generally hard to prove that a language doesn't have some property X. You need to show that every possible grammar you can construct for that language doesn't have that property, because a single one is enough to give that property to the language.


Adding the requirement of linear time on infinitely many inputs into the class $P$

[EDIT 2]

No, and in particular $M_2$ does not exist in general.

Consider only TM's (and languages) that do not distinguish between the letters $0$ and $1$. Let's call them monochrome. Thus, membership of a word $w$ in a monochrome language depends only on $|w|$. Now let $L$ be a non-regular monochrome language in P. For example, $L$ can be the set of all words whose length is a square number.

Next, we exploit the fact that we use Turing machines (and not RAMs or whatever) and that the time bound is exactly $n$ (and not $O(n)$). In that time bound, all the TM $M_2$ can do on the witness word $w$ (by which I mean the special input of a given length $n$ for which $M_2$ runs in time $n$) is to read the input once from left to right. If at any step it does not go right, it cannot discern the length of $w$. As $L$ is by nature neither finite nor co-finite, $M_2$ must measure the length exactly.

So, at least on the witness words, $M_2$ acts like a DFA. Then, construct an NFA $A_1$ which simulates $M_2$ as long as $M_2$ only goes right. The NFA $A_2$ is obtained from $A_1$ by replacing all edge labels by $\{0,1\}$. Then $A_2$ recognizes $L$: For any input, $A_2$ behaves just like $A_1$ does for the respective witness word, including acceptance or rejection.

Thus, $L$ is regular, contradicting the choice of $L$.


Balanced Binary Search Tree Two-Sum with Constraints

I don't know how to do this is in $O(n)$ time and $O(1)$ space, but I can show you how to do it in $O(n)$ time and $O(\lg \lg n)$ space.  In particular, given any tree of depth $O(\lg n)$, I'll show how to do an in-order traversal in $O(n)$ time and $O(\lg \lg n)$ space.  That will be enough to solve this problem.

Warmup

Let me first establish some notation.  At any point in the traversal, we'll currently be at some leaf node $x_1$.  Let $x_1,x_2,x_3,\dots,x_d$ be the nodes on the path from $x_1$ to the root (so $x_1$ is the leaf and $x_d$ is the root of the tree), where $d$ denotes the depth of the tree.  Note that since the tree has depth $O(\lg n)$, it follows that this sequence has length $O(\lg n)$.

For convenience, I'll assume that the tree is a complete binary tree, i.e., all leaves are at the same depth.  This simplifies explanation of the main ideas.  All of the techniques here generalize to an arbitrary binary tree, as long as its maximum depth is $O(\lg n)$.

An easy way to do a traversal would be to keep track of the entire sequence $x_1,x_2,x_3,\dots,x_d$.  When you want to find the successor, you update the entire sequence.  For instance, if $x_1$ is the left child of $x_2$, this involves updating just $x_1$ to its right sibling.  If $x_1$ is the right child of $x_2$ and $x_2$ is the left child of $x_3$, this involves updating $x_1$ and $x_2$.  And so on.  Notice that as we repeatedly compute the successor, the first parts of the sequence get updated more often: $x_1$ changes every time, $x_2$ changes half of the time, $x_3$ changes $1/4$ of the time, and so on.  This gives an $O(n)$ time traversal (since $1 + 1/2 + 1/4 + \cdots = O(1)$), but it requires $O(\lg n)$ space.

The main attraction

Our improvement will be to store only part of that sequence: we'll store $x_1,x_2,x_4,x_8,\dots,x_k$ (where $k=2^{\lfloor \lg d \rfloor}$).  In other words, we're only storing the power-of-two-indexed elements of the path from the current leaf to the root.  Since $d=O(\lg n)$, we're only storing $O(\lg \lg n)$ elements of the sequence.

When we want to find the successor, we might need to update one or more of these elements.  As we repeatedly iterate compute successors, the early parts change more often: $x_1$ always changes, $x_2$ changes $1/2$ of the time, $x_4$ changes $1/2^3$ of the time, $x_8$ changes $1/2^7$ of the time, $x_{16}$ changes $1/2^{15}$ of the time, and so on.  How do we do the updates?  To see if $x_2$ needs to change, we go down from $x_2$ to $x_1$ to find the successor to $x_1$.  If $x_2$ doesn't need to change, we're done.  Otherwise, we go down from $x_4$ to $x_2$ to find the successor to $x_2$ (at the same height as $x_2$).  And so on. When $x_{2^i}$ changes, we go down from $x_{2^{i+1}}$ to $x_{2^i}$ to compute the successor to $x_{2^i}$ at the same height, and this takes $2^i$ steps of computation since we have to traverse $2^i$ levels of the tree; this happens for a $1/2^{2^i-1}$ fraction of the successor operations.  Taking all of that into account, the amortized amount of work we do per successor operation is

$$1 + {2 \over 2} + {4 \over 2^3} + {8 \over 2^7} + {16 \over 2^{15}} + \cdots
= O(1).$$

This yields an in-order traversal that takes $O(n)$ time and $O(\lg \lg n)$ space.

Bonus answer

As an extra bonus, I'll show how to do an in-order traversal in $O(n \lg^* n)$ time and $O(\lg^* n)$ space.  $O(\lg^* n)$ "might as well be constant" for all practical purposes, so maybe this is of interest.

The construction is a small modification of the scheme I gave above.  Define $a_1,a_2,a_3,\dots$ by $a_1 = 1$ and $a_{i+1} = 2^{a_i}$.  Now, instead of storing the whole sequence $x_1,\dots,x_d$, we'll store just the elements $x_{a_1},x_{a_2},x_{a_3},\dots,x_{a_\ell}$, where $\ell= \lg^* d = \lg^* (\lg n)$.  Notice that $x_{a_i}$ changes for a $1/2^{a_i-1}$ fraction of the successor operations, and when it does change, we do $a_{i+1} - a_i$ work.  Therefore, the amortized time per successor operation is

$$T = \sum_{i=1}^\ell {a_{i+1} - a_i \over 2^{a_i-1}}.$$

With a bit of manipulation we can show

$$T \le \sum_{i=1}^\ell {a_{i+1} \over 2^{a_i-1}} = \sum_{i=1}^\ell {1 \over 2} = \ell/2 = O(\lg^* (\lg n)) = O(\lg^* n).$$

Therefore, a traversal of the entire tree can be done $O(n \lg^* n)$ time, using $O(\lg^* n)$ time.


How does one end up with a non-integer exponent in time complexity? (e.g., $O(n^{2.81})$)

The running time complexity of Strassen's algorithm is given by the recurrence
$$
T(n) = 7T(n/2) + O(n^2).
$$
(With a suitable base case.) The solution of this recurrence is $T(n) = O(n^{\log_2 7})$.

Strassen's algorithm multiplies two $n \times n$ matrices $A,B$ by decomposing them into four $(n/2)\times(n/2)$ matrices each, computing seven linear combinations of the smaller matrices each, say $(A_i,B_i)_{i=1,\dots,7}$, recursively computing $C_i = A_i B_i$, and computing the four $(n/2)\times(n/2)$ matrices of the result by taking linear combinations of the matrices $C_i$. That's how this running time came to be. If you want to learn more, there is a lot of information out there on Strassen's algorithm. There are, by the way, asymptotically faster algorithms for matrix multiplication, the current champion being Le Gall.


Language Features Not Translatable into Lambda Calculus

That's not what "pure" means. Pure means, generally, that there is no mutable state, and no way to interact with the outside world (i.e. IO).

Haskell is not "directly translatable" (what translation between language features really means needs to be defined fist, but let's ignore that for now) into either the untyped or simply-typed lambda calculus. There are many features that prevent it from being so, but a good example is polymorphism: there is no polymorphic identity function in the simply-typed lambda calculus.

Instead, Haskell and SML are actually derived from the Hindley-Milner type system, which is an extension of the simply-typed lambda calculus with polymorphism and type-constructors (aka higher-kinded types). Hindley-Milner has the nice property that type inference is decidable without any type annotations.


If the duplicate element is the maximum element, the answer is the same as when all numbers are distinct. Let's say the duplicate element is $a_1, a_2$. Even though they are the same, we can treat it as $a_1 > a_2$, and then remove the duplicate heaps where the only difference is the exchange of $a_1, a_2$, but that is not possible because $a_1$ is always at the root. So no duplicates found.

If the duplicate element is the minimum element, the problem gets more interesting. Let $S(n)$ be the number of max heaps such that the minimum element is duplicated, and $T(n)$ be the number of max heaps such that there are no duplicates. We already know that

$$T(n) = {{n-1}\choose {l}} \times T(l) \times T(r)$$

with base case $T(1) = 1$.

For the duplicate case, we have 3 cases. We can put them both into the left subtree, both into the right subtree, or one in each subtree. Hence, the recursion is

$$S(n) = {{n-3}\choose {l-2}} S(l) T(r) + {{n-3}\choose {r-2}} T(l) S(r) + {{n-3}\choose {l-1}} T(l) T(r)$$

with base case $S(1) = 0, S(2) = 1, S(3) = 1$.


How does casting really work for primitive data types?

Casting of primitive datatypes works in a very simple way:

  Under the hood, values don't have types. Casting does absolutely nothing.

As a simple example, let us consider casting 65 to an ASCII character, thus obtaining the symbol A. What happens under the hood? Absolutely nothing. The only thing that changes is how the program treats the value. When it thinks of it as an integer, it sees 65; when it thinks of it as an ASCII character it sees A.

The CPU does accommodate different datatypes when performing various operations. For example, it has separate instructions for signed and unsigned integer arithmetic, and for floating point arithmetic. Moreover, there are different instruction for different lengths (i.e. 16-bit vs. 32-bit vs. 64-bit for integers). But it is up to the programmer to instruct the CPU which instruction to use. The CPU doesn't keep track of datatypes, which are a higher-level concept.

Modern CPUs do keep a distinction between code and data to some extent, for security purposes. But otherwise the semantics of data is up to the programmer.

Sometimes casting does have an actual effect, and this is during promotion. When casting an integer to a floating point number, or a 32-bit integer to a 64-bit integer, the program calls some instruction which effects this conversion (in the second case, the exact instruction depends on whether the integer is signed or unsigned).

When casting a signed integer to an unsigned integer of the same length (or vice versa), probably nothing happens. This is exactly your case.


Why is the orthogonal line segment intersection algorithm $O(n\log n+R)$ instead of $O(n\log n + Rn)$?

It's a bit hard to get through your text since a lot of information is missing. However I assume that you have the following misunderstanding.

Let me ignore the constants in the big-O for this argument since this is irrelevant. For every horizontal segment $h$ you perform an action that takes $O\log n + R_h$ time, where $R_h$ are the intersections you output. Then the overall running time is
$$\sum_h \log n + R_h =  n\log n +R.$$

Simply speaking, you only output every crossing once. So the overall time for the output is $O(R)$.


Isn't NP problems always also co-NP problems?

The definition you give in the quesition is very imprecise so it's understandable that you've misunderstood it.  The formal definitions are given at our reference question on NP.

A decision problem is in NP if there's some polynomial $p$ and an ordinary, deterministic polynomial-time Turing machine $M$ such that:

For every "yes" instance $x$, there is some $y$ with $|y|\leq p(|x|)$ such that $M$ accepts the string $x,y$;
For every "no" instance $x$, $M$ rejects all strings $x,y$.

So, for example, 3-COLOURABILITY is in NP: the string $y$ is just a description of a $3$-colouring and $M$ accepts $x,y$ if $y$ is a valid $3$-colouring of the graph $x$ and rejects otherwise.  The point is not that you can "verify 'yes' instances" but, rather, that every "yes" instance has a certificate $y$ that you can use to easily prove that it really is a "yes" instance.

But there's a significant asymmetry in the definition.  If you give $M$ a "yes" input and a certificate $y$, then $M$ will say "I agree – that's a 'yes' instance." However, there's no input you can give it that will cause it to say "I agree – that's a 'no' instance." For any certificate you try, it will just say "That doesn't convince me it's a 'yes'." You could, of course, try all possible certificates. That would certainly prove that you had a "no" instance but there's a problem: there are exponentially many possible certificates to try, so trying all of them doesn't give you a polynomial-time algorithm.


For which values of $m$ is $m$-partition hard?

The $1$-partition problem is trivial, since there is only one possible partition.

The $2$-partition problem is the same as MAX-CUT, which is known to be NP-complete.

For $m > 2$, the $m$-partition problem is NP-complete by reduction from $m$-coloring, which is NP-complete for that range of $m$.


Big Theta Proof: May I chose any constant?

Yes, as long as the constant conforms to the definition of $\Theta$, that is it

is positive and
independent of $n$.

This follows directly from the definition of $\Theta$, which requires only the existence of some $c_1, c_2>0$ (in typical formulations).

You may find our reference questions helpful; in particular, there are more convenient ways to prove such claims besides checking the definition explicitly.


Help comparing relative error for different parenthesizations of addition

With nothing but an upper bound for the relative error: Consider that the final sums are almost the same, so bounds for relative error will be almost the same. What’s significantly different is the absolute error of the first addition, and that will be smallest if the first sum has the smallest possible absolute value.

In the first case 0 < x+y < y+z, so the first function has the smaller error.

In the second case it depends whether x+y or y+z is closer to zero, which we don’t know. And exactly the same in the third case.


You are asked to prove: There is a language X which is in P, such that the language π(X) is NP complete. Because in this case, since P is closed under the operation π, π(X) is also in P, which means P = NP. The idea is: Define a language X, which consists of strings that are YES-instances of an NP-complete problem, followed by an oracle that proves the instance is a YES-instance. The details are a bit tricky.

Define an encoding of instances of the travelling salesman problem: The encoding starts with the number n of cities in decimal notation, a comma, the number K which is the maximum length of a tour, an opening bracket, n * (n-1) / 2 distances in decimal notation, separated by commas if there is more than one distance, and a closing bracket. It is easy to determine that a string is such an encoding of a TSP instance.

We define the language L as follows: Each string in L consists of the encoding of a TSP instance with answer "YES", followed by hyphen characters "-" to exactly double the length of the string so far, followed by a permutation of the numbers 1 to n in decimal notation, separated by commas, such that starting at town 1, then visiting towns in the given order, produces a cyclic tour with length at most K.

The language L is clearly in P. The language π(L) consists of strings that are the encoding of a YES-instance of TSP, followed by some number of hyphens, and if there are enough hyphens, part or whole of an oracle. Because the oracle is much shorter than the encoded instance, π(L) contains some strings that are just encoded TSP instances, followed by hyphens. But for these strings, deciding that they are in π(L) is hard, as hard as deciding that an ordinary instance of TSP is a YES-instance. So π(L) is NP-complete.

And if π(L) is also in P as assumed, then P = NP.


Showing that a language is not recursive

In order to prove $L \in coRE$ you could prove that $\overline{L} = \{\langle M,w \rangle | M \text{ is a TM and } w \neq CH\left( \langle M \rangle \right) \}$ is r.e.

Given input $\langle M,w \rangle$

reject if input is not well-formed including $\epsilon$
if $w \neq \epsilon$. Then $w$ must be a history. If it is not a legal history, just accept since $CH(\langle M \rangle) \neq w$. Otherwise inspect the history, and assume it runs for $k$ steps. Then simulate $M$ for $k$ steps and compare its history with $w$. If they are NOT equal then accept, otherwise reject/loop forever.
if $w = \epsilon$. Then run $M$ until it halts. If it halts then accept since $CH(M)$ must be a legal history different from $\epsilon$ which means $CH(\langle M \rangle) \neq w = \epsilon$. Otherwise, i.e. $M$ does not halt. But our TM which simulates $M$ also runs forever which means that $CH(M) = \epsilon = w$, but it will never halt and so never accept.


what does it mean by problem of size $0$?

We're talking about algorithms to sort a list.  Therefore, in this context, a problem of size 0 is a list of size 0, i.e., the empty list.

Quicksort splits a list of size $n$ into two sublists of size $m$ and $n-m-1$.  They sum to $n-1$ (not $n$), because quicksort removes the pivot element: the pivot element is not included in either sublist.  Therefore, the text you have quoted is correct.  If one sublist has size $n-1$, then the other will have size 0 (not size 1).


Finding the $k$-smallest elements in a min-heap

If you mean the usual binary heap represented in an array, this is answered in "An Optimal Algorithm for Selection in a Min-Heap", by  Frederickson. It is pretty complex.

Other priority queues have easier algorithms. For instance, if you use a threaded AVL tree as priority queue, you can just follow right neighbor pointers from the minimum value.


How to avoid loops/cycles in iterative deepening with linear space?

The main point of Iterative Deepening is to completely search a potentially infinite (or just really huge) tree with depth first search with storage linear in the maximum you search. To detect cycles, the information that a node has been visited before must be stored somewhere. This requires exponential storage, so there is no non-exponential ID algorithm that prevents searching in cycles.

However, this may not be too bad in practice if the graph is already stored somewhere. The easiest method to do this then is simply to label the 'depth' of every node as encountered by the search, so you can detect when a cycle has been found. (This is essentially the same as depth limited breadth first search, apart from the order.)

But in general, cycle detection requires more storage, or a different algorithm that uses a bit more time. In fact, you can see a very clear time-space trade-off in many cycle detection algorithms.


Decision problems vs "real" problems that aren't yes-or-no

As you said, there is no decision to make, so new complexity classes and new types of reductions are needed to arrive at a suitable definition of NP-hardness for optimization-problems.

One way of doing this is to have two new classes NPO and PO that contain optimizations problems and they mimic of course the classes NP and P for decision problems. New reductions are needed as well. Then we can recreate a version of NP-hardness for optimization problems along the lines that was successful for decision problems. But first we have to agree what an optimization-problem is.

Definition: Let $O=(X,L,f,opt)$ be an optimization-problem. $X$ is the set of inputs or instances suitable encoded as strings. $L$ is a function that maps each instance $x\in X$ onto a set of strings, the feasible solutions of instance $x$. It is a set because there are many solutions to an optimization-problem. Thus we haven an objective function $f$ that tells us for every pair $(x, y)$ $y\in L(x)$ of instance and solution its cost or value. $opt$ tells us whether we are maximizing or minimizing.

This allows us to define what an optimal solution is: Let $y_{opt}\in L(x)$ be the optimal solution of an instance $x\in X$ of an optimization-problem $O=(X,L,f,opt)$ with $$f(x,y_{opt})=opt\{f(x,y')\mid y'\in L(x)\}.$$ The optimal solution is often denoted by $y^*$.

Now we can define the class NPO: Let $NPO$ be the set of all optimization-problems $O=(X,L,f,opt)$ with:

$X\in P$
There is a polynomial $p$ with $|y|\le p(|x|)$ for all instances $x\in X$ and all feasible solutions $y\in L(x)$. Furthermore there is an deterministic algorithm that decides in polynomial time whether $y\in L(x)$.
$f$ can be evaluated in polynomial time.

The intuition behind it is:

We can verify efficiently if $x$ is actually a valid instance of our optimization problem.
The size of the feasible solutions is bounded polynomially in the size of the inputs, And we can verify efficiently if $y\in L(x)$ is a fesible solution of the instance $x$.
The value of a solution $y\in L(x)$ can be determined efficiently.

This mirrors how $NP$ is defined, now for PO: Let $PO$ be the set of all problems from $NPO$ that can be solved by an deterministic algorithm in polynomial time.

Now we are able to define what we want to call an approximation-algorithm: An approximation-algorithm of an optimization-problem $O=(X,L,f,opt)$ is an algorithm that computes a feasible solution $y\in L(x)$ for an instance $x\in X$.

Note: That we don’t ask for an optimal solution we only what to have a feasible one.

Now we have two types of errors: The absolute error of a feasible solution $y\in L(x)$ of an instance $x\in X$ of the optimization-problem $O=(X,L,f,opt)$ is $|f(x,y)-f(x,y^*)|$.

We call the absolute error of an approximation-algorithm $A$ for the optimization-problem $O$ bounded by $k$ if the algorithm $A$ computes for every instance $x\in X$ a feasible solution with an absolute error bounded by $k$.

Example: According to the Theorem of Vizing the chromatic index of a graph (the number of colours in the edge coloring with the fewest number of colors used) is either $\Delta$ or $\Delta+1$, where $\Delta$ is the maximal node degree. From the proof of the theorem an approximation-algorithm can be devised that computes an edge coloring with $\Delta+1$ colours. Accordingly we have an approximation-algorithm for the $\mathsf{Minimum-EdgeColoring}$-Problem where the absolute error is bounded by $1$.

This example is an exception, small absolute errors are rare, thus we define the relative error $\epsilon_A(x)$ of the approximation-algorithm $A$ on instance $x$ of the optimization-problem $O=(X,L,f,opt)$ with $f(x,y)>0$ for all $x\in X$ and $y\in L(x)$ to be

$$\epsilon_A(x):=\begin{cases}0&f(x,A(x))=f(x,y^*)\\\frac{|f(x,A(x))-f(x,y^*)|}{\max\{f(x,A(x)),f(x,y^*)\}}&f(x,A(x))\ne f(x,y^*)\end{cases}$$

where $A(x)=y\in L(x)$ is the feasible solution computed by the approximation-algorithm $A$.

We can now define approximation-algorithm $A$ for the optimization-problem $O=(X,L,f,opt)$ to be a $\delta$-approximation-algorithm for $O$ if the relative error $\epsilon_A(x)$ is bounded by $\delta\ge 0$ for every instance $x\in X$, thus
$$\epsilon_A(x)\le \delta\qquad \forall x\in X.$$

The choice of $\max\{f(x,A(x)),f(x,y^*)\}$ in the denominator of the definition of the relative error was selected to make the definition symmetric for maximizing and minimizing. The value of the relative error $\epsilon_A(x)\in[0,1]$. In case of a maximizing problem the value of the solution is never less than $(1-\epsilon_A(x))\cdot f(x,y^*)$ and never larger than $1/(1-\epsilon_A(x))\cdot f(x,y^*)$ for a minimizing problem.

Now we can call an optimization-problem $\delta$-approximable if there is a $\delta$-approximation-algorithm $A$ for $O$ that runs in polynomial time.

We do not want to look at the error for every instance $x$, we look only at the worst-case. Thus we define $\epsilon_A(n)$, the maximal relativ error of the approximation-algorithm $A$ for the optimization-problem $O$ to be
$$\epsilon_A(n)=\sup\{\epsilon_A(x)\mid |x|\le n\}.$$

Where $|x|$ should be the size of the instance.

Example: A maximal matching in a graph can be transformed in to a minimal node cover $C$ by adding all incident nodes from the matching to the vertex cover. Thus $1/2\cdot |C|$ edges are covered. As each vertex cover including the optimal one must have one of the nodes of each covered edge, otherwise it could be improved, we have $1/2\cdot |C|\cdot f(x,y^*)$. It follows that $$\frac{|C|-f(x,y^*)}{|C|}\le\frac{1}{2}$$
Thus the greedy algorithm for a maximal matching is a $1/2$-approximatio-algorithm for $\mathsf{Minimal-VertexCover}$. Hence $\mathsf{Minimal-VertexCover}$ is $1/2$-approximable.

Unfortunately the relative error is not always the best notion of quality for an approximation as the following example demonstrates:

Example: A simple greedy-algorithm can approximate $\mathsf{Minimum-SetCover}$. An analysis shows that $$\frac{|C|}{|C^*|}\le H_n\le 1+\ln(n)$$ and thus $\mathsf{Minimum-SetCover}$ would be $\frac{\ln(n)}{1+\ln(n)}$-approximable.

If the relative error is close to $1$ the following definition is advantageous.

Let $O=(X,L,f,opt)$ be an optimization-problem with $f(x, y)>0$ for all $x\in X$ and $y\in L(x)$ and $A$ an approximation-algorithm for $O$. The approximation-ratio $r_A(x)$ of feasible solution $A(x)=y\in L(x)$ of the instance $x\in X$ is
$$r_A(x)=\begin{cases}1&f(x,A(x))=f(x,y^*)\\\max\left\{
\frac{f(x,A(x))}{f(x, y^*)},\frac{f(x, y^*)}{f(x, A(x))}\right\}&f(x,A(x))\ne f(x,y^*)\end{cases}$$

As before we call an approximation-algorithm $A$ an $r$-approximation-algorithm for the optimization-problem $O$ if the approximation-ratio $r_A(x)$ is bounded by $r\ge1$ for every input $x\in X$.
$$r_A(x)\le r$$
And yet again if we have an $r$-approximation-algorithm $A$ for the optimization-problem $O$ then $O$ is called $r$-approximable. Again we only care about to the worst-case and define the maximal approximation-ratio $r_A(n)$ to be
$$r_A(n)=\sup\{r_A(x)\mid |x|\le n\}.$$
Accordingly the approximation-ratio is larger than $1$ for suboptimal solutions. Thus better solutions have smaller ratios. For $\mathsf{Minimum-SetCover}$ we can now write that it is $(1+\ln(n))$-approximable. And in case of $\mathsf{Minimum-VertexCover}$ we know from the previous example that it is $2$-approximable. Between relative error and approximation-ratio we have simple relations:
$$r_A(x)=\frac{1}{1-\epsilon_A(x)}\qquad \epsilon_A(x)=1-\frac{1}{r_A(x)}.$$

For small deviations from the optimum $\epsilon<1/2$ and $r<2$ the relative error is advantageous over the approximation-ratio, that shows its strengths for large deviations $\epsilon\ge 1/2$ and $r\ge 2$.

The two versions of $\alpha$-approximable don’t overlap as one version has always $\alpha\le 1$ and the other $\alpha\ge 1$. The case $\alpha=1$ is not problematic as this is only reached by algorithms that produce an exact solution and consequentially need not be treated as approximation-algorithms.

Another class appears often APX. It is define as the set of all optimization-problems $O$ from $NPO$ that haven an $r$-approximation-algorithm with $r\ge1$ that runs in polynomial time.

We are almost through. We would like to copy the successful ideas of reductions and completness from complexity theory. The observation is that many NP-hard decision variants of optimization-problems are reducible to each other while their optimization variants have different properties regarding their approximability. This is due to the polynomialtime-Karp-reduction used in NP-completness reductions, which does not preserve the objective function. And even if the objective functions is preserved the polynomialtime-Karp-reduction may change the quality of the solution.

What we need is a stronger version of the reduction, which not only maps instances from optimization-problem $O_1$ to instances of $O_2$, but also good solutions from $O_2$ back to good solutions from $O_1$.

Hence we define the approximation-preserving-reduction for two optimization-problems $O_1=(X_1,L_1,f_1,opt_1)$ and $O_2=(X_2,L_2,f_2,opt_2)$ from $NPO$. We call $O_1$ $AP$-reducible to $O_2$, written as $O_1\le_{AP} O_2$, if there are two functions $g$ and $h$ and a constant $c$ with:

$g(x_1, r)\in X_2$ for all $x_1\in X_1$ and rational $r>1$
$L_2(g(x, r_1))\ne\emptyset$ if $L_1(x_1)\ne\emptyset$ for all $x_1\in X_1$ and rational $r>1$
$h(x_1, y_2, r)\in L_1(x_1)$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$
For fixed $r$ both functions $g$ and $h$ can be computed by two algorithms in polynomial time in the length of their inputs.
We have $$f_2(g(x_1,r),y_2)\le r \Rightarrow f_1(x_1,h(x_1,y_2,r))\le 1+c\cdot(r-1) $$ for all $x_1\in X_1$ and rational $r>1$ and for all $y_2\in L_2(g(x_1,r))$

In this definition $g$ and $h$ depend on the quality of the solution $r$. Thus for different qualities the functions can differ. This generality is not always needed and we just work with $g(x_1)$ and $h(x_1, y_2)$.

Now that we have a notion of a reduction for optimization-problems we finally can transfer many things we know from complexity theory. For example if we know that $O_2\in APX$ and we show that $O_1\le_{AP} O_2$ it follows that $O_1\in APX$ too.

Finally we can define what we mean by $\mathcal{C}$-hard and $\mathcal{C}$-complete for optimization-problems:

Let $O$ be an optimization-problem from $NPO$ and $\mathcal{C}$ a class of optimization-problems from $NPO$ then $O$ is called $\mathcal{C}$-hard with respect to $\le_{AP}$ if for all $O'\in\mathcal{C}$ $O'\le_{AP} O$ holds.

Thus once more we have a notion of a hardest problem in the class. Not surprising a $\mathcal{C}$-hard problem is called $\mathcal{C}$-complete with respect to $\le_{AP}$ if it is an element of $\mathcal{C}$.

Thus we can now talk about $NPO$-completness and $APX$-completness etc. And of course we are now asked to exhibit a first $NPO$-complete problem that takes over the role of $\mathsf{SAT}$. It comes almost naturally, that $\mathsf{Weighted-Satisfiability}$ can be shown to be $NPO$-complete. With the help of the PCP-Theorem one can even show that $\mathsf{Maximum-3SAT}$ is $APX$-complete.


Can a computational complexity class be redefined by using any complete (decision) problem?

If $X$ is any NP-complete decision problem, then NP consists of all decision problems which are polytime many-one reducible to $X$.
We cannot replace polytime many-one reductions with polytime Turing reductions, however (unless NP=coNP), since coSAT is polytime Turing reducible to SAT.


Show Recognizing two Regular Expressions as equal is in PSPACE

Hint: One obvious algorithm for this problems goes as follows. Given two regular expressions $R,S$, convert them to NFAs $N_R,N_S$ and then to DFAs $D_R,D_S$. Using the product construction, construct a DFA for $D_R \Delta D_S$ (here $A \Delta B$ is the symmetric difference), and check whether the language it accepts is empty.

While this algorithm doesn't quite use polynomial space (why?), you can follow the same general plan to solve your problem. It might be helpful to use NPSPACE=PSPACE or perhaps coNPSPACE=PSPACE.

Here is a complete answer. Let $R,S$ be two regular expressions. The idea is that if $L(R) \neq L(S)$ then there is a word in $L(R) \Delta L(S)$ whose length is at most exponential in $|R| + |S|$ (where $|R|$ is the length of $R$). This puts your problem in coNPSPACE=PSPACE, since you can guess and verify such a word.

Indeed, once you convert $R$ and $S$ to (polynomial size) NFAs, you can keep track of the set of possible states in both NFAs, and so verify that a word is accepted by one or not the other. You also need your machine to terminate if it guessed wrong, so you need to limit the length of the word to exponential in $|R| + |S|$. Fortunately, counting up to $\exp(|R|+|S|)$ takes only a polynomial size counter.

It remains to show that if $L(R) \neq L(S)$ then there is an exponential size witness. Indeed, the DFA for $L(R) \Delta L(S)$ has exponential size: the DFAs for $L(R)$ and $L(S)$, constructed from the corresponding NFAs, have exponential size, and the product construction maintains this property for $L(R) \Delta L(S)$. Finally, it is known that if a DFA with $n$ steps accepts some word, then it accepts some word of length less than $n$.


Sorted unsigned integer intervals tree structure

Interval trees seem like a natural candidate. The Wikipedia page has links to implementations in various languages.
You can overwrite an existing interval by querying its endpoints, then removing the resulting intervals on the left and right, and then adding back the truncated intervals together with the new one.


What I was looking for is a selection algorithm that will select the k-th element.
As mentioned in comment, running then a simple partition algorithm if needed will then provide the expected result.
The reference seems to be the quick select algorithm while the reference implementation points to introselect as implemented in Numpy's partition function or C++ nth_element function.


Solving SAT correctly on all but $poly(m)$ formulas

I'll provide a sketch.

Given any formula $\varphi$ of size $m$, we can rewrite it in an equisatisfiable way as $\varphi \land p$ where $p$ is a fresh propositional variable. In this way, we can generate an infinite amount of equisatisfiable formulas.

Now, exploiting this, it is easy to find a way to generate, in PTIME, $2 poly(m')+1$ formulas $\varphi'$ equisatisfiable wrt $\varphi$, where each such $\varphi'$ is of size $m'$. We can then decide SAT on $\varphi$ by taking what is the result of the majority of $\varphi'$ instances ($poly(m')+1$ instances), and return that. Indeed, among the $2poly(m')+1$ test, at most $poly(m')$ can have a wrong result, so the result of the majority must be the correct one.

This runs a PTIME algorithm a polynomial number of times ($2 poly(m')+1$, where $m'$ is polynomial wrt $m$), so we indeed solve SAT in PTIME.

To generate all the needed $\varphi'$, we note that the "longest" variable name in $\varphi$ can't more than $m$ bit long for obvious size reasons. Hence if we take $p$ to be any variable whose name has size $m+1$ bits it is surely fresh, and this makes $\varphi'$ to have size $m' = m+(m+1)+O(1)$. Further, we have $2^{m+1}$ choices of such $p$, which is (asymptotically) a large enough space to choose $2 poly(m')+1$.


Here is a lower bound and an asymptotically matching construction, at least for some ranges of the parameters. Denote by $m$ the number of columns, and suppose for simplicity that $p \leq n/2$.

We start with a lower bound on $m$. Let $X$ be the encoding of symbol chosen uniformly at random. Let $X_1,\ldots,X_m$ be the individual coordinates, and let $w_i \leq p$ be the weight of the $i$th column. Then
$$
\log n = H(X) \leq \sum_{i=1}^m H(X_i) = \sum_{i=1}^m h(w_i/n) \leq m h(p/n).
$$
Therefore
$$
m \geq \frac{\log n}{h(p/n)}.
$$
Here $H$ is the entropy of a random variable $H(X) = -\sum_x \Pr[X=x] \log \Pr[X=x]$ and $h$ is the entropy function $h(x) = -x\log x-(1-x)\log(1-x)$. (You can use whatever base for the logarithm you want.)

The asymptotically matching construction, that should work for $p = \Omega(n)$, chooses $m$ a bit larger than this lower bound, and chooses a random encoding scheme, each bit being set to $1$ with some probability $q/n$ which is a bit smaller than $p/n$. Choosing the parameters correctly, we should get that this results in a legal encoding (all codewords are different and all column weights are at most $p$) with positive probability.


Algorithm for a list of best solutions to the Assignment problem

Here's one technique to enumerate the best $n$ assignments, for any instance of the assignment problem.  I suspect my approach isn't optimal, but it does run in polynomial time: it uses $O(nm)$ invocations of the Hungarian algorithm, where $m$ denotes the number of agents in the problem instance.  In your example, $m=26$, so my approach requires $O(n)$ invocations of the Hungarian algorithm.

Let $A_1,A_2,A_3,\dots$ denote the assignments, from best to worse.  $A_1$ is the best assignment; $A_2$ is the next-best; and so on.  Our goal want to enumerate $A_1,\dots,A_n$.

You can find $A_1$ by solving the original assignment problem, e.g., with the Hungarian algorithm.

How can we find $A_2$, the second-best assignment?  The idea is to use a case analysis.  Let $v_1,\dots,v_m$ denote the $m$ agents in the problem instance, and let $A(v)$ denote the task assigned to agent $v$ by assignment $A$.  We'll break down the space $\mathcal{S}$ of possible candidates for $A_2$ (i.e., the space of all assignments other than $A_1$) into the disjoint union $\mathcal{S} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_m$, where $\mathcal{S}_i$ is the space of assignments that agree with $A_1$ for $v_1,\dots,v_{i-1}$ but disagree with $A_1$ on $v_i$.  (In other words, we look at the first agent that receives a different assignment in $A_1$ vs $A_2$.  Then there are $m$ possibilities for that agent; we let $i$ denote its index, i.e., the index of the first agent whose assignment in $A_1$ is different from its assignment in $A_2$.  This breaks down the space $\mathcal{S}$ into subspaces $\mathcal{S}_1,\dots, \mathcal{S}_m$, as listed before.)

Now the approach will be to find the best assignment in each $\mathcal{S}_i$, separately.

$\mathcal{S}_1$: We find the best assignment $A$ such that $A(v_1) \ne A_1(v_1)$ using one invocation of the Hungarian algorithm, by changing the cost of the edge $(v_1,A_1(v_1))$ to $\infty$ (or some very large positive number) and then re-running the Hungarian algorithm.  This finds the best assignment out of all assignments that assign $v_1$ to something different than $A_1$ did.
$\mathcal{S}_2$: We find the best assignment $A$ such that $A(v_1) = A_1(v_1)$ and $A(v_2) \ne A_1(v_2)$ using one invocation of the Hungarian algorithm: change the cost of the edge $(v_1,A_1(v_1))$ to $0$, and change the cost of the edge $(v_2,A_1(v_2))$ to $\infty$.
$\mathcal{S}_i$:  Similarly, for each $i$, we can find the best assignment $A$ such that $A(v_j) = A_1(v_j)$ for all $j=1,2,\dots,i-1$ and such that $A(v_i) \ne A_1(v_i)$, using one invocation of the Hungarian algorithm.

This gives us $m$ assignments, i.e., $m$ candidates for $A_2$.  By construction, each one of these assignments is different from $A_1$.  Also, by construction, this covers all the space of all assignments that are different from $A_1$.  Therefore, $A_2$ will be the best of these $m$ candidates, so we can just compare these $m$ candidates and call it $A_2$.

That find the second-best assignment.  How can we find $A_3$, the third-best assignment?  Well, the same ideas apply: we'll use a case split, but now the case-split will be a little more involved.  Suppose that $v_i$ is the first agent where $A_1$ and $A_2$ disagree (i.e., $A_1$ and $A_2$ agree on $v_1,\dots,v_{i-1}$ but disagree on $v_i$, so that $A_2 \in \mathcal{S}_i$).  Then we can break down the space of possibilities for $A_3$ by looking at the first agent that receives a different assignment from $A_2$, or from $A_1$.

In particular, let $\mathcal{T}$ denote the space of possible candidates for $A_3$ (i.e., the space of all assignments other than $A_1$ or $A_2$).  We can partition it into the disjoint union

$$\mathcal{T} = \mathcal{S}_1 \cup \dots \cup \mathcal{S}_{i-1} \cup (\mathcal{T}_1 \cup \dots \cup \mathcal{T}_m) \cup \mathcal{S}_{i+1} \cup \dots \cup \mathcal{S}_m.$$

In other words, since $A_2 \in S_i$ and we now want to exclude $A_2$ from the space of allowable assignments, we partition $S_i$ into $S_i = \{A_2\} \cup \mathcal{T}_1 \cup \dots \cup \mathcal{T}_m$ and remove $A_2$.  Here $\mathcal{T}_j$ denotes the set of assignments that agree with $A_2$ on $v_1,\dots,v_{j-1}$ but disagrees with $A_2$ on $v_j$ (and, if $j=i$, disagrees with $A_1$ on $v_j$ as well).

Now, we use the Hungarian algorithm to find the best assignment in each of $\mathcal{S}_1, \dots, \mathcal{S}_{i-1}, \mathcal{T}_1, \dots, \mathcal{T}_m, \mathcal{S}_{i+1}, \dots, \mathcal{S}_m$.  This is doable using the techniques shown above, using one invocation of the Hungarian algorithm per subspace.  Finally, we let $A_3$ be best of all the solutions found.

We can continue in this way, at each step identifying the next-best by decomposing the space of remaining assignments into multiple subspaces and invoking the Hungarian algorithm on each subspace.  At each step, we introduce at most $m$ new subspaces, and we can reuse the previously-obtained results for the other subspaces.  Therefore, on each step we make at most $m$ invocations of the Hungarian algorithm, so the total number of invocations of the Hungarian algorithm is $O(nm)$.

There's probably a better way to do it, but if you can't find any other algorithm, this is one you could use.  Note that this is a general technique for problem of enumerating the $n$ best assignments to any instance of the assignment problem.  It's not specific to your substitution-cipher example.


Constrain traveling salesman: visit a given city within a given distance from start

You can easily impose the constraint that a given city should be visited before a given location in the sequence. I.e., that city 5 should be one of the three first visited:

node_order[5 - 1] <= 3

Or that city 7 should be visited as the third, fourth, or fifth:

node_order[7 - 1] <= 5,
node_order[7 - 1] >= 3

This does not exactly impose the constraint on cumulative distance, though.


Finding a minimal subset of strings whose bitwise OR is the all ones string

This is the set cover problem, a well-known NP-complete problem, in disguise.


How many cookies in the cookie box? -- Tiling stars

Let me answer your question partially for the hexagram case.

You can make the following tiling

$\hskip1.2in$

By this you will cover 12/14=6/7 of the plane (count the triangles in the dashed quadrilateral).

Is this optimal? I would think so. Although I am not giving a proof I will provide some arguments. One can ask, how good we can fill the space (triangle) in between the pointy spikes. In the above tiling we fill half of it. Can we do better?

$\hskip20mm$

It is possible that two hexagram will intersect this space, but then they cover very little of its area (without proof). If there is only one hexagram intersecting I assume that its tip touches the concave corner of the other hexagram as depicted in the picture. If this would not be the case we can improve by moving the intersecting hexagram to this corner (again no proof here). Under these assumptions it is not hard to see that the case where there is side-to-side contact maximizes the intersection. If you do the math, then you will find out that the area of the intersection equals
$$\frac{\sec ^2(x)}{2 \sqrt{3} \tan (x)+2}.$$

The plot of this function looks like this and shows that our intuition was right.

$\hskip30mm$


Hamiltonian Path in a DAG is easy to solve: You can find the longest path in $O(|V|+|E|)$ time using the critical path algorithm: https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths.  For unweighted DAGs, this sounds like essentially the same thing as your topological sort.

Hamiltonian Path is NP-hard on digraphs with cycles, and on undirected graphs.


I don't understand how the reduction from FACT to 3-SAT works. Are there any simple articles in which I can read about it?

Most of the reading material assumes several steps of knowledge.

First, you should read about how logic circuits (logic gates) work.
Optionally learn or use a simple multiplication algorithm. You might want to start with the long-multiplication algorithm that everyone learns in school.
Then research and understand a multiplication circuit, and/or learn how to convert the chosen algorithm to a circuit.
You should now know how to make a simple multiplication circuit (MULT). Next learn to extend it for $n$-bit numbers.
Once you have a circuit, you can force the outputs of the circuit to the $N$ value you want to factor. You do this by taking the $n$ outputs, and point-wise xoring them together with your $N$ value. Set the final output to be true iff $N$ and the MULT output cancel each-other out. You can do this by first oring all the xor results; if they are all $0$, then the output matched $N$ (in this case, set the final output to be $1$, else $0$).
Now you have $\text{Circuit-SAT}$. Learn about $\text{Circuit-SAT}$.
$\text{Circuit-SAT}$ asks if there is an input that can satisfy the output. $\text{Circuit-SAT}$ is an NP-complete problem, that is almost directly convertible to $3\text{-SAT}$ (when you get to this step, you will understand this pretty easily)
There is a straightforward reduction from $\text{Circuit-SAT}$ to $3\text{-SAT}$ available here: Convert Circuit SAT to 3-SAT

You can't get it all in one scoop without talking to someone in-person. Rather you should follow the steps, without skipping. Each of these has "simple" material to learn from; but you'll not find one that teaches you everything in one sitting from the very basics.

Also see Computer Organization - Module II, section 2.5.1 Array Multiplier, which implements a carry-save-array-multiplication circuit:

Looks a lot like grade-school multiplication, doesn't it ...

Each box is (FA means "Full adder", which is also on that page in section 2.2 Serial & Parallel Adder):


Deterministic algorithm to find number of collisions

You could hash all of the elements of $D$, sort them, and then count duplicates.  Sorting brings all duplicates next to each other, so a linear scan lets you count the number of duplicates.  The running time will be $O(|D| \log |D|)$.

If you don't insist on a deterministic algorithm, you could place elements of $D$ into a hashtable, using $h$ as your hash, and then count the size of each hash bucket.  If the hash function is any good, then there is a sense in which the expected running time is $O(|D|)$ (e.g., if the elements of $D$ are random and the hash function is sufficiently good) -- but the worst case is $O(|D|^2)$.


How to prove the correctness of the MinDistance algorithm?

Define an order of pairs of indices $(i,j)$ according to the order in which they are accessed in your code. At the end of the $(i,j)$th iteration, $dmin$ holds the minimum of $|A(k)-A(\ell)|$ among all pairs $(k,\ell) \preceq (i,j)$ such that $k \neq \ell$. This loop invariant is easy to prove, and implies the correctness of the entire algorithm.


I found this: Sung Eun Bae, Sequential and Parallel Algorithms for the Generalized Maximum Subarray Problem. Read pages 18-30, where it says that there are just cubic $O(nm^2)$ and sub-cubic algorithms for this problem (in general case), for example Tadao Takaoka's $O\left(n^3 \sqrt{\frac{\log\log n }{\log n }}\right)$ algorithm.

I've also found a forum comment saying that this problem can be solved in $O(N^2\log N )$ for matrices with N non-zero elements using "funny" segment tree (you can ask commentator about details).


Need help optimizing the loading of passengers on small airplanes

This is an optimization problem.

The first step is to work out more precisely what your objective function is.  In other words, given a candidate assignment of pilots, you need a well-specified way to compute a single "goodness value" for that assignment.  That's your objective function: an objective function maps a candidate solution to a number indicating how good the candidate solution is.  Once you have defined an objective function, you then have a well-defined optimization problem.

Right now, it sounds like you haven't yet settled on a specific objective function.  You mention some possible factors, but the question isn't completely precise about how exactly those factors should be measured or how to weight the individual factors and combine them to get a single number.  Generally you can't solve the optimization problem until you formulate an objective function that gives you a single number (otherwise the notion of a "best" solution isn't well-defined).

Once you can do that, you could look at expressing this as an integer linear programming problem.  See, e.g., integer-programming.

The kind of problem you mention generally falls into the field known as "operations research".

Alternatively, with only 15-20 kids, you might even be able to write a program that exhaustively enumerates all candidate solutions and scores each one.  There will be exponentially many candidate solutions but if the number of kids is small enough it might be feasible to enumerate them all.  15-20 kids is probably on the edge of what could be computed in a reasonable amount of time, so this might fail badly, and you might need to resort to combinatorial optimization methods, such as integer linear programming.


The point of the halting program IMO is not to show that you can't check whether an arbitrary program can halt--that's not a very interesting fact on its own. The point of the halting program, is to use "reduction", to go on and prove that a (very large number of) procedures you might like to have a tool do are also impossible in general:

Deciding whether two programs are the same (including, whether a program always outputs "true"). This is true even for even many simple definitions of "program".
Deciding whether a mathematical fact is true or false
Determining the longest time a program could run
Checking whether a particular line of code like an error condition, is possible to reach

Of course, much like NP-complete problems, it may still be worthwhile to work on heuristic versions or special cases. But knowing that it's impossible in general, saves us a lot of time trying to come up with a perfect version--after all, we usually want a perfect version if we can get one. And knowing that a problem is impossible in general, is a good hint that it may be hard in specific cases you're likely to run into (checking if two programs are identical for example, is actually really hard in practice).
I think it's fairly reasonable to assume that for any program a human would write, the answer is "yes, it halts"--otherwise it's a bug! So the class of "programs a human would write on purpose" is not really that interesting to look at.
A more interesting question is, "what sorts of things in real programming, lead to problems analyzing whether the program halts?". For example:

Almost all opcodes (ex. addition) complete
Bounded loops complete (if the inner loop completes)
Function calls with no recursion complete (if the body of each function does)
Arbitrary while loops are hard to analyze
Global variables may be hard to analyze
Recursive function calls are hard to analyze

It's quite possible to invent a language (Charity, Epigram, and LOOP are academic/niche langauges, but you can also just imagine making a list of all these features and banning them from Java) where all programs halt. The challenge then becomes, can you express what you want to do in this language?
Edit: For an example of a practical program that is hard to analyze, here is bubble sort in python:
swapped = True
while swapped:
    swapped = False
    for i in range(0, len(list)-1):
        if list[i] > list[i+i]:
            list[i], list[i+i] = list[i+1], list[i]
            swapped = True

As a human, we can tell that this program halts for all inputs. It's much harder to get a computer to realize the same thing.


Acceptance conditions when translating LTL to Büchi automaton?

I will start with the last question and then come to the question at the top of your post.

The construction assumes that the LTL formula is given in negation normal form, so that no temporal operator occurs in negated form (as you wrote).
So $\neg (p_1 U (p_2 U p_3))$ gets translated to $\neg p_1 R (\neg p_2 R \neg p_3)$, and because in the latter formula, there is no Until subformula, we have 0 acceptance pairs in the Generalized Buchi automaton.
Now, a generalized Buchi automaton accepts all words for which there exists an infinite run on which all acceptance sets are visited infinitely often. If there are none, then this condition is vacuously true on any infinite run, which still has to exist. For example the word $(\{p_1,p_2\}^\omega)$ does not satisfy the LTL formula, and the corresponding generalized Buchi automaton has not infinite run for the word. If you model check with this automaton, every reachable cycle represents a case in which the LTL property holds. If you translate the generalized Buchi automaton to a Buchi automaton, then the standard construction makes every state in the latter accepting.
As far as the subformulas are concerned, you have to take the definition quite literally. For every Until-subformula in the NNF LTL property, you have an acceptance set. For instance, for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$, you will have acceptance sets for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$ and $(a\,\mathcal{U}\,b)$. For the All states in the generalized Buchi automaton containing $b$ or not containing $(a\,\mathcal{U}\,b)$ as a disjunct are accepting for  the latter acceptance set. All states containing $c$ as a disjunct or not containing $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$ as a disjunct are labeled as contained in the acceptance set for $(a\,\mathcal{U}\,b)\,\mathcal{U}\,c$.
The example $((\neg A)R(\neg B))\vee(\top U C)$ that you mentioned is actually not problematic. Depending on how you write down the algorithm, either (1) no state will ever be labeled by $((\neg A)R(\neg B))\vee(\top U C)$, but only by $((\neg A)R(\neg B))$ or $(\top U C)$ (and you will have two initial states), or (2) all states labeled by $((\neg A)R(\neg B))\vee(\top U C)$ need to also be labeled by either $((\neg A)R(\neg B))$ or $(\top U C)$, and for determining in which acceptance set a state is, you only look at the whole subformulas, so a state labeled by $((\neg A)R(\neg B))$ would be accepting for all acceptance sets, while one also labeled by $(\top U C)$ would not be labeled by the acceptance set for $(\top U C)$ (unless it is also labeled by $C$).


Show a sequence of distinct Primes number is O(log n)

Since each of the prime numbers is at least 2, we have
$$n \geq \prod_{i=1}^{r(n)} p_i \geq \prod_{i=1}^{r(n)} 2 = 2^{r(n)}, $$
from which it follows that $r(n) \leq \log_2 n$.

In fact, since the prime numbers are generally larger than 2, we can obtain a better bound, namely $$ r(n) \lesssim \frac{\log n}{\log \log n}. $$
See for example MathWorld, which states the number of distinct prime factors in a primorial.


Why on board graphics is unfit for gaming/rendering?

The difference between dedicated and integrated device is in resources and power. Dedicated have own resources integrated share them with various tasks. Integrated is less parallel but has (commonly) higher frequency. Integrated card uses CPU and RAM while dedicated has own RAM and own cores (far more than dedicated one).

This makes integrated cards unfit for real graphics, besides rendering part there are also tasks like controlling the game, running AI, keeping buffers of done tasks etc.


The Peterson Algorithm uses only memory read and memory write operations, which are atomic in almost every computer ever built.  (All the bits in a word are read or written on the same cycle, and the memory bus of the computer is built in such a way that only one of the processors has access on any specific cycle.)
That said, the atomicity of the write operations is not necessary.  Leslie Lamport is quite clear about this in his commentary on his web page about his classic "Bakery Algorithm" for mutual exclusion (http://lamport.azurewebsites.net/pubs/pubs.html#bakery):

Several books have included emasculated versions of the algorithm in which reading and writing are atomic operations, and called those versions "the bakery algorithm".  I find that deplorable.  There's nothing wrong with publishing a simplified version, as long as it's called a simplified version.
What is significant about the bakery algorithm is that it implements mutual exclusion without relying on any lower-level mutual exclusion.  Assuming that reads and writes of a memory location are atomic actions, as previous mutual exclusion algorithms had done, is tantamount to assuming mutually exclusive access to the location.  So a mutual exclusion algorithm that assumes atomic reads and writes is assuming lower-level mutual exclusion.  Such an algorithm cannot really be said to solve the mutual exclusion problem.  Before the bakery algorithm, people believed that the mutual exclusion problem was unsolvable--that you could implement mutual exclusion only by using lower-level mutual exclusion.  Brinch Hansen said exactly this in a 1972 paper.  Many people apparently still believe it.

(emphasis added)
For more details about this aspect of the problem see Lamport's 1991 paper, "The Mutual Exclusion Problem Has Been Solved," http://lamport.azurewebsites.net/pubs/pubs.html#lamport-mutual-solved.