The well-known classifiers that can be trained/tested in linear time

You might want to read my blog post Comparing Classifiers, especially the MNIST summary.

Time Complexity of Training

By Training Samples

Let $n$ be the number of training samples.

The following classifiers can perform at least on training / fitting step in $\mathcal{O}(n)$:

Neural Networks: You can take a fixed batch size. Then increasing $n$ is simply having more mini-batches to train on.
$k$-nearest-neighbors: All "training steps"

The following classifiers cannot perform at least one training / fitting step in $\mathcal{O}(n)$:

???

I am unsure about the following:

SVMs
Decision Trees: I'm relatively sure it is linear, but I would need to go through one of the training algorithms

By classes

If $n$ is the number of classes, then the training of $k$-NN is in $\mathcal{O}(1)$. If you keep the number of samples and k constant, then it doesn't matter if you have 2 classes or $10^{100}$.

I'm unsure about:

Neural Networks: The size of the last layer grows. My intuition is that this is in $\mathcal{O}(n)$, but I need to put more thought into it. I am, however, not sure if the Big-O Time Complexity makes a lot of sense for this classifier. If you look at the tables in Appendix D, you see that in real problems the FLOPs are dominant in the beginning. Given a problem, you usually you can't influence the number of classes. And the wall-clock time complexity of training for two classes is vastly different for different classifiers. So much, that up to a reasonable amount of classes you will likely not see the asymptotic behavior.
Decision trees might even be in $\mathcal{O}(1)$. I have to give impurity measures a closer thought.


How to prove for that a given non-regular language its given super-set is also non-regular?

Since you already know that $L_1$ is nonregular, here is a simple proof.
Suppose that $L$ is regular. Then since $a^*ba^*$ is regular, the language $L \cap a^*ba^*$ should be regular. But $L \cap a^*ba^* = L_1$, which is not regular. Hence $L$ is nonregular.


The time complexity is $O(n^2)$ because $O(n\cdot(n-1)) = O(n^2)$

The big-O notation is showing the worst-case performance of one algorithm, it is not showing the exact number of steps the algorithm will make, but only its overall complexity

For example $$O(2n) = O(n)\\O(3n) = O(n)\\O(\frac{n}{2}) = O(n)\\O(2n^2) = O(n^2)$$


Algorithm to output all instances of stable matching

Dan Gusfield gave such an algorithm in his paper Three Fast Algorithms for Four Problems in Stable Marriage. The algorithm uses $O(n^2)$ space, and takes time $O(n^2 + nS)$, where $S$ is the number of stable matchings.


Monogenic semigroups.
Consider the case of a [monogenic semigroup](monogenic semigroup), that is, a semigroup $S$ generated by a single element $s$. If $S$ is finite, then it can be totally ordered if and only if it is aperiodic, that is, if there exists a positive integer n such that $s^n = s^{n + 1}$. In this case, the order could be $s \leqslant s^2 \leqslant \dotsm \leqslant s^n$.
If $S$ is not aperiodic, then it contains a finite subgroup, and the only compatible order on a finite group is the equality, as you observed.

If $S$ is infinite, it can also be ordered by $s \leqslant s^2 \leqslant s^3 \leqslant\dotsm $.

Arbitrary semigroups. An interesting example is the free monoid $A^*$ equipped with some shortlex order. Shortlex orders are total and are compatible with the concatenation product.

Second question. I am not sure what you mean by a "finitely generated finite semigroup" since every finite semigroup is finitely generated. Thus I suppose that the question is whether the order of a finite ordered semigroup can be a total order. There are some examples which are not monogenic, for instance the ordered semigroup $(S, \leqslant)$ with $S = \{a,b\}$, $a \leqslant b$,  $aa = ba = a$ and $ab = bb = b$.

Third question. See my comment.


Splitting the array in the median-of-median solution for $k$th smallest element problem

Along with the explanation given on wikipedia, I'll try to give more visual examples. The main point is that subarrays of length $ \frac{n}{3}$ make it a non-linear algorithm.

We can actually check out the 3 scenarios you discuss. I'm going to be referring to area diagrams similar to the one depicted on wikipedia. These area diagrams are a useful abstraction to see how large of a subproblem we might have to recurse on in the worst case. The area diagrams will look something like this:

Where $M$ is median of medians, $(< M)$ and $(> M)$ represent the area (amount of values in the array) that are potentially less than $M$ and greater than $M$ respectively, in the worst/best case. Note that in the area diagrams I present I say the area is roughly (~) some value. This is because it may be off by one or two and I am largely ignoring these small constants because they will be insignificant to the analysis. If you are bothered by this, you can assume $n$ is of a useful form such that the values are exact.

For $\frac{n}{3}$ size subarrays we will end up with an area diagram like this:

It is clear that in the worst case we will have to recurse on roughly $\frac{4 n}{6}$ elements in the array. This will give us a recurrence relation:
  $$\begin{align}
T(n) & = T\left(\frac{n}{3}\right) + T\left(\frac{4n}{6}\right) + cn\\
& = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + cn
\end{align}$$
  This actually turns out to be on the order of $O(n \log n)$. I won't go through an explicit proof of this recurrence because I'm sure it's been done before. If you wish to prove it to yourself, you can use a similar approach to this, or use the recursion tree method, or use the Akra-Bazzi method. So this subarray size won't work because we now have non-linear time complexity.

For $\frac{n}{5}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + cn$$

This is linear $O(n)$! You can use this method directly to prove it is linear.

For $\frac{n}{7}$ size subarrays we will end up with an area diagram like this:

We similarly get a worst-case recurrence of the following:

$$T(n) = T\left(\frac{n}{7}\right) + T\left(\frac{10n}{14}\right) + cn$$

This is also linear! Again, you can use the method I described above to prove this.

So in conclusion

Diving the subarrays into length $\frac{n}{3}$ will not be good because it is non-linear! Diving the subarrays into length $\frac{n}{5}$ or $\frac{n}{7}$ will be very good because it is linear! You can actually go on to use $\frac{n}{9}, \frac{n}{11}, \ldots$ and still get linear time!


Validity of □(P→ Q) → (◊P → ◊Q) in linear temporal logic

Think about what the formula means. The first part says that it's always true that $P$ implies $Q$; the second part says that, if $P$ is true somewhere, then $Q$ must be true somewhere, too. Well, if $P$ implies $Q$ then, if $P$ is true somewhere, then $Q$ had better be true in that place, too!


Is it possible to solve this problem in less than n^2 time without using additional space?

Let’s use $a_i$ for the array. You are interested in
$$
\begin{align*}
\max_{i,j} a_i + a_j + |i-j| &= \max_{i,j} a_i + a_j + \max(i-j,j-i) \\ &=
\max_{i,j} \max((a_i+i)+(a_j-j), (a_j+j)+(a_i-i)) \\ &=
\max \left[ \max_{i,j} (a_i+i) + (a_j-j), \max_{i,j} (a_j+j) + (a_i-i) \right] \\ &\stackrel{(*)}=
\max_{i,j} (a_i+i) + (a_j-j) \\ &=
\max_i (a_i + i) + \max_j (a_j - j).
\end{align*}
$$
The tricky step is $(*)$. The final expression can be computed in linear time and constant space.


Is the set of context free grammars that generate all words in co-RE?

For $A = \{\langle G \rangle \mid L(G) \neq \Sigma^\ast\}$ this procedure, returns "yes" iff there is a word $w \notin L(G)$ for a given grammar  encoding $\langle G \rangle$ and never halts otherwise:

Assume the input encodes a context-free grammar $G$. Otherwise, accept the input if it is not an encoding of a context-free grammar. (Note, however,  that we can always assume that every string encodes some dummy grammar, e.g. $(\{S\}, \{a\}, \{S \to \varepsilon\}, S)$).
Convert $G$ in Chomsky normal form $G'$.
For each $w \in \Sigma^\ast$:
Check whether there exists a derivation in $G'$. Note that for a grammar in Chomsky normal form a derivation of a word $w$ has length $ \leq 2 |w|$, so you only have to check finitely many for each word. If such an derivation does not exists, return "yes", otherwise continue with next word.

Thus, $A$ is recursively enumerable and $A^C = \{\langle G \rangle \mid L(G) = \Sigma^\ast\}$ is co-RE.


How does virtual memory work when it need to save data in physical memory into disk?

There are a few options:

if a page is in memory then it cannot be on disk as well, As such there is no duplication and the issue doesn't exist.

there is more than just the MMU's pagetable to hold paging information. This mean that the kernel has an auxiliary data structure that says where the page is on disk and the MMU page table only tracks what is in memory. This solution allows memory mapping of files whether they are on disk or over the network.


Deterministic Communication Complexity of Equality if inputs differ by at most 1

Hint: Compare the parities of the inputs. (Can you generalize this idea to at most $k$ differences?)


Can the maximum single sell profit by divide and conquer be O(n)?

Answering my own question, yes! The trick is to do the work to compute the max and min of the sublists in the divide-and-conquer recursion rather than when merging the results.
To do this, you need an inner function that returns not just the best trade in a subproblem, but also it's min and max. The combine step is then $O(1)$ rather than $O(n)$.
Here's what that looks like:
def best_trade(prices: List[int]) -> int:
    """
    Divide-and-conquer in O(n).
    """
    def f(start: int, end: int) -> Tuple[int, int, int]:
        if start == end:
            return 0, prices[start], prices[start]
        else:
            best_left, min_left, max_left = f(
                start,
                start + (end - start) // 2,
            )
            best_right, min_right, max_right = f(
                start + (end - start) // 2 + 1,
                end,
            )
            return (
                max(best_left, best_right, max_right - min_left),
                min(min_left, min_right),
                max(max_left, max_right),
            )

    # `else 0` for the corner case where prices = []
    return f(0, len(prices) - 1)[0] if prices else 0

Note that the inner function passes the start and end index of the subproblem down the stack, rather than taking slices, because taking slices is $O(k)$, where $k$ is the length of the slice. By passing pointers we keep the work done outside the recursion to $O(1)$.
With this implementation, $T(n) = 2 T(n/2) + O(1)$ which implies this divide-and-conquer algorithm is $O(n)$.
The general pattern here is to do more work (or return more information) than is strictly necessary in the recursion to reduce the work outside the recursion. In this case, the "extra" work done inside the recursion is trivial, so the running time is significantly reduced, at the cost of a slightly less legible bit of code.
One final point: of course the single scan solution is also $O(n)$ and significantly simpler than either divide-and-conquer solution:
def best_trade(prices: List[int]) -> int:
    """
    Single scan in O(n).
    """
    if not prices:
        return 0
    lowest = prices[0]
    best = 0
    for p in prices:
        lowest = min(p, lowest)
        best = max(best, p - lowest)
    return best


You are asking two questions. The answer to your first question, for models stronger than Turing computation, is the field of hypercomputation. The answer to your second question, asking for evidence for the Church-Turing thesis, has been answered on cstheory.


Algorithm for converting (coordinates + reach radius) data to directed graph

If all pairs of points are within each other's reach, you can not optimize the construction below $O(N^2)$. However, you can optimize for sparser graphs by ordering pairs of points by distance from smallest distance to largest. Once you find a pair $(A, B)$ where $d(A, B) > R_{max}$, you are done. A technique you can use for this can be found here. This technique makes use of divide and conquer.

This is more a heuristic. I do not think there is a way (with or without use of divide and conquer) to reduce the worst case complexity.


Are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

Suppose it's not the case, it means that there is a node $v$ that is either isolated (contradicts $n \geq 2$) or has an arrow that is incident to it. Let this arrow be from $v$ to $v'$, with no loss of generality. Since we have supposed that $v$ is not part of a cycle, it's impossible to go from $v'$ to $v$, which contradicts strong connectivity.


Generate random labeled tree with constrained edge lengths

I'm not entirely sure of what you're asking for, but I think it might be one of these three:

Permutations that preserve topological structure
The tree you listed in parenthetical notation is (5 (2 (1 4) ) (3) (5 (6 (7 (8) ) ) ). Are you looking for permutations of this tree structure, because you can simply calculate all n! permutations of nodes and put them in the same tree structure:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (5) (4 (3 (1 (2) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (2 (3) ) ) )
(9 (8 (7 6) ) (5) (4 (1 (3 (2) ) ) )
...
(This would yield 362,880 distinct trees).

Note, this class of trees would preserve the sequences of lengths of the current tree. Now, if you have an array of these, simply use a good PRNG.

Permutations that calculate topological isomorphisms
It also would preserve topological properties, so if you want to generate other isomorphic topologies, then you can take the structure of the tree and do permutations on the sequences at the same level. Hence:

(9 (8 (7 6) ) (5) (4 (3 (2 (1) ) ) )
(9 (8 (7 6) ) (4 (3 (2 (1) ) ) (5) )
(9 (5) (8 (7 6) ) (4 (3 (2 (1) ) ) )
(9 (5) (4 (3 (2 (1) ) ) (8 (7 6) ) )
...
(This will be a variable number of permutations, in this case (3!(1!)(2!)(1!)) or 12 trees.)

Permutations that calculate equivalent lengths

Let your tree be [1 2[1 4] 3 4 *5[2 3 6] 6[7] 7[8] 8] where * represents root, and nodes inside of brackets are pointers. Notice it's possible to calculate lengths by taking the absolute value of the difference between nodes (2[4]->2[[2]] The node two which points to [node four] is a node that has an [[edge length 2]]). Then use [1 2[[1 2]] 3 4 *5[[3 2 1]] 6[[1]] 7[[1]] 8 9] -> {1, 1, 1, 1, 2, 3}. Now we can simply replicate this by traversing the original tree and constructing isomorphisms of length. Hence:

Determine root
Rnd(1-9)->3 -> [1 2 *3 4 5 6 7 8]
Permute first level by taking three lengths and finding candidates
[1 2 *3[[3 2 1]] 4 5 6 7 8 9]->  (note three lengths)
[3]±[[3]]->{0,6} (0 is invalid so don't push on the stack)
[3]±[[2]]->{1,5}
[3]±[[1]]->{2,4}
Note we need to select P(2,1) on all three sets iteratively.
So, randomly, one permutation is {6,1,4} :[1[] 2 *3[1 4 6] 4[] 5 6[] 7 8].
Call this recursively on [1], [4], [6] over the set {with [[1], [[1]], and [[1 2]] with the base case being any tree that satisfies {1, 1, 1, 1, 2, 3}.

Now, I think that preserving the lengths as a function of order of the sequence might yield a very small set, because certain trees, might only have a single isomorphism. Consider:

(1 (2 (3 (4 (5 (6 (7 (8)))))))) ~ (8 (7 (6 (5 (4 (3 (2 (1))))))))
{1 1 1 1 1 1 1} = {1 1 1 1 1 1 1}

There's only one isomophism because of the way a tree when considering edges whose lengths are caculated from sequences partitions. In fact, every tree done in this manner might have at most 1, but I'd have to think about how to prove that after implementing code.

Let me know what you think; if you can clarify what you're seeking, I might be able to help.


Solving recurrence relation $T(n)=\sqrt{n} \cdot T(\sqrt{n}) + n$ using method of guessing and confirm?

The book answer skips over some things. Here's a more detailed explanation.

You want to show $T(n)=O(n\log n)$, in other words there exists a $c>0$ such that $T(n)\le c\cdot n\log n$. [Actually, you need also to show that this inequality holds for all $n$ greater than some constant $N$, but we'll put this off temporarily.]

We'll use strong induction here; our induction hypothesis is that

  $T(k)\le c\cdot k\log k$, for all $k<n$.

Now we'll expand the book's answer.
$$\begin{align}
T(n) &= \sqrt{n}\;T(\sqrt{n}) + n &\text{by definition} \\
     &\le\sqrt{n}\;[c\cdot\sqrt{n}\log{\sqrt{n}}]+n &\text{by induction hypothesis, since $\sqrt{n}<n$}\\
     &= cn(\log\sqrt{n})+n
\end{align}$$
which answers your question about the step from $(1)\rightarrow(2)$. To get $(4) \rightarrow(5)$ the text wants to end up with $T(n)\le c\cdot n\log n$, so to conclude this they need
$$
n\cdot c\cdot\frac{1}{2}\log n+n\le c\cdot n\log n
$$
Dividing both sides of the desired equality by $n$ yields the needed condition:
$$
\frac{c}{2}\log n+1\le c\log n
$$
and this will be true when $1\le \frac{c}{2}\log n$. [The book actually doesn't need an unspecified $c$: in fact, $c=2$ will work perfectly here, since as long as $n\ge 2$ we'll have $1\le\log n$, satisfying our needed condition.]

In sum, we've shown by induction that the recurrence $T(n)= \sqrt{n}\log\sqrt{n}+n$ is satisfied by any function $T(n)=c\cdot n\log n$, as long as we pick a suitable $c$, which is exactly what was required.

It's worth pointing out that $O(n\log n)$ is an upper bound, but it's not the tightest upper bound possible. As gnasher729 pointed out, a better bound is $O(n\log\log n)$. It's a good exercise to do the same argument (with $c=1$) to show that $T(n)=n\log\log n$ is a solution to $T(n)=\sqrt{n}\;T(\sqrt{n})+n$.


Complexity class of integer factorization

Integer factorization (or rather, an appropriate decision version) is not known to be NP-complete. In fact, it is conjectured not to be NP-complete. However, any reasonable decision version of integer factorization is in NP, and so reducible to any NP-complete problem (by definition). There are specialized algorithms for integer factorization which are better than, say, reducing integer factorization to SAT and then using a SAT solver.


Cover k edges to minimize the length of the longest uncovered path in a tree

(This answer expands on Albert Hendriks' approach from the comments.)

First idea: let us turn the problem around.
As stated, we fix the number of covered edges, $k$, and minimize the maximum length of an uncovered path $d(k)$.
Instead, let us fix the maximum length of an uncovered path, $d$, and minimize the number of covered edges $k(d)$.

Suppose now we can calculate $k(d)$ in $O(n)$.
Then the original problem can be solved in $O(n \log n)$.
Indeed, note that both $d(k)$ and $k(d)$ are non-increasing functions.
To answer the question "what is $d(k_0)$?", we can find the minimum $d_0$ such that $k(d_0) \le k_0$.
And that can be done in $log (n)$ calculations of $k(d)$ by doing a binary search for the right $d$ with the obvious bounds of $[0, n-1]$.

What's left is to, given a fixed value $d$, calculate $k(d)$ in $O(n)$.

Second idea: we can select an arbitrary vertex as the root, run a depth-first search from the root, and make decisions about covering edges in depth-first search order.

Let us visit a vertex $v$ in our depth-first search.
We recursively visit all its children in any order.
After visiting child $u$, we assume that we have dealt with all uncovered paths longer than $d$ in $u$'s subtree.
We also know the length $\mathrm{dfs}(u) \le d$ of the longest uncovered path from $u$ to the vertices of its subtree.
The longest uncovered path from $v$ to the vertices of $u$'s subtree has an extra edge $v - u$, so its length is $r = \mathrm{dfs}(u) + 1$.

(I) Obviously, if $r > d$ (it can only be $d + 1$), we have to cover some edge on the long path we found.
Since the whole subtree of $u$ is already dealt with, it makes sense to cover an edge which is the closest to the complement of the subtree of $u$ in the whole tree, which is the edge $v - u$.

(II) But there's more to consider.
A path can go from the subtree of one of our children, via our vertex $v$, to the subtree of another child.
And if such path has length greater than $d$, we have to cover an edge on it.

To find such paths, for our vertex $v$, we store the maximum length of an uncovered path into a child's subtree we have so far.
Let this stored length be $s$, initially zero.
After each child $u$ we visit, check whether $r + s > d$.
If so, let us cover the edge to the longest of $r$ and $s$, so the new maximum length of an uncovered path becomes $s_{\textit{new}} = \min (s_{\textit{old}}, r)$.
If $r + s \le d$, we don't yet have to cover anything, and the new maximum length is $s_{\textit{new}} = \max (s_{\textit{old}}, r)$.

Note now that, with such implementation, case (I) is covered by case (II).
In particular, if we don't yet store a path in a child's subtree, the stored value just adds a length of $0$.

When we finish visiting all children of $v$, the stored value $s$ is the length of the longest remaining uncovered path from $v$ to the vertices of its subtree.
In particular, if $v$ is a leaf, the value $s$ remained zero.
We can now return this value as $\mathrm{dfs}(v)$.

The remaining question is, if we don't cover an edge using the algorithm above, could it have helped us later if we had in fact covered it?
The answer is no: such a cover could safely be moved at least one step closer to the root of the tree, without altering other covers.

In pseudocode, with a bit more low-level details than the explanation above.
Assume the vertices are numbered 0, 1, ..., n-1.
We select vertex 0 as the root (recall that the root can be arbitrary), and just call dfs (0, -1).

dfs (v, p):                            // v is current vertex, p is its parent
    {s, w} := {0, -1}                  // maximum path of length s into child w's subtree
    for u in adjacent[v]:              // all neighbors of v...
        if u != p:                     // ...except its parent, if it has one
            r := dfs (u, v) + 1
            if r + s > d:              // we have to cover the longest...
                if r > s:
                    cover (v, u)
                else:
                    cover (v, w)
                    {s, w} := {r, u}   // ...and possibly update to shortest
            else:
                if r > s:
                    {s, w} := {r, u}   // here, update to longest
    return s                           // length of the longest remaining path

As we can see, dfs (v, p) returns the length of the longest uncovered path from $v$ to the vertices of its subtree.

So, we set the value d (to the pseudocode, it acts as a global variable), run dfs, and track the number of covered edges as the total number of calls to the cover function.
The cover function may actually record the covered edges if need be, but at the very least, it increases the counter k by 1.
If the edges themselves are not needed, we can drop the variable w too, and leave only s from the tuple {s, w}.

For the original problem, do the above in a binary search over the possible values of d to get the full solution.


Pumping lemma for simple finite regular languages

You are right - we cannot allow "pumping" words of a finite $L$. The thing you are missing is that the lemma says there exists a number $p$, but does not tell us the number.

All words longer than $p$ can be pumped, by the lemma. For a finite $L$, it happens so that $p$ is larger than the length of the longest word in $L$. Thus, the lemma only holds vacuously, and cannot be applied to any word in $L$, i.e., any word in $L$ does not satisfy the condition of "having length at least $p$" as the lemma requires.

A corollary: if $L$ has pumping length $p$, and there exists some word $w\in L$ of length at least $p$, then $L$ is infinite.


Calculate Complexity, loop incremented by log(k)

Let's ignore the outer loop, and concentrate only on the inner one. Since $\log m \approx \log (2m)$ for $m \geq 2$, we see that the number of times it takes $k$ to double is proportional to $k/\log k$. Therefore the number of iteration it takes to get from $2$ to $n$ (assuming for simplicity that $n$ is a power of $2$) is roughly
$$
\frac{2}{\log 2} + \frac{4}{\log 4} + \frac{8}{\log 8} + \cdots + \frac{n}{\log n} \approx \frac{n}{\log n},
$$
since the numbers increase exponentially. Therefore the inner loop runs in time $O(n/\log n)$.

You can make this reasoning rigorous with enough effort.


(DROP) Data Reduction Algorithm - How it works?

Algorithm 1 takes non-annotated data as input, so it is agnostic to the labels (shapes). In line 1, algorithm 1 computes clusters on the non-annotated data. The cluster assignments do not necessarily correspond exactly to the labels. The output of algorithm 1 will be a set of edges between data in different clusters, but the data need not have different labels. So the reason edges 6 and 7 can connect between triangles is because the triangles have been assigned to different clusters.


Can Quantum Computing solve Problems not even a Turing Machine can solve?

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine.

The main advantage of quantum Turing machines is that they appear to solve some problems much faster than classical Turing machines. As Sasho comments, at the moment we can't quite prove this, yet this advantage is believed to hold by most researchers.

For more, check out this talk by Ashley Montanaro.


Turing Machine 'marking' specific portion of encoding

A quick answer: if the tape alphabet is large enough ($\geq 18$ symbols), then $L = \{\langle M,w\rangle \mid $ M on w  visits at least two unique states different than the starting state $\}$ is undecidable; indeed for every $M$ with $n$ states there is an equivalent $M'$ with only 2 states such that  for all $x$ $M(x)$ halts if and only if $M'(x)$ halts. To prove that L is undecidable, you can use the following reduction from the halting problem: given $\langle M\rangle$ build the equivalent two states machine $M'$ (the starting state plus another one), and add an additional final and accepting third state that can be reached only if $M'$ halts when run on the empty tape. Clearly $\langle M',w\rangle  \in L$ (i.e. visit the second and the third accepting state) if and only if $M$ halts ($w$ is irrelevant), so if $L$ is decidable you can solve the halting problem which is a contradiction.

Reducing the number of symbols, doesn't help too much, indeed you can encounter Turing machines that behaves like the Collatz function (e.g enter the third state only when the sequence reaches 1) ... and it is an open problem if for all $n$ the Collatz function reaches 1.

For a proof that you can build an Universal Turing machine (using 2-tag simulation) with only 2-states and 18 symbols see:

Y. Rogozhin. Small universal Turing machines. Theoretical Computer Science,
168(2):215–240, Nov. 1996.

Finally, as an exercise, you should be able to easily prove that the following language is undecidable:

$L' = \{ \langle M,w,k \rangle \mid$ when run on w the Turing machine M visits at least $k$ different states $\}$


How do I use the pumping lemma for a^n b^m a^(n+m) ? How can I choose the pumping length?

It seems that you are trying to force the string length to be $p$, which is not necessary. What is required is that $|xy| \leq p$. The length of $w$ can be greater than $p$. Also, $n$ or $m$ can be $p$ or some multiple of $p$, whatever  makes the reasoning for the impossibilty of partition of $w$ to satisfy the lemma. With that, I think you can follow through and complete your proof.
Just remember, the aim is not to look for a partition of $w$ that does not work. Rather show that no partition works.
Cheers.


I find the simplest way to think about this problem is to consider a machine that has two Register Alias Tables (RAT).  These tables simply store the physical register identifier associated with each architectural register.

The two tables sit in the retirement stage (the Retirement Register Alias Table or RRAT), and the renaming stage. Retirement and renaming both happen in-order, no matter how the execution stages work.  The Retirement-RAT represents the architectural/non-speculative state of the machine.  The renaming RAT represents the speculative state of the machine (the state the machine will have if all of the speculative decisions made before the current instruction were to be found to have been correctly predicted).

Think about the state of the Retirement Register Alias Table just before the retirement of an instruction that writes to (architectural) register $R$.  At this point the Retirement Register Alias Table contains a mapping from $R$ to $P_0$, the previous physical register that was assigned to architectural register $R$, and the next instruction to retire will have a different assignment from $R$ to $P_1$.  Since retirement happens in-order, we know that all instructions that could have referenced physical register $P_0$ have already retired, and thus physical register $P_0$ can be returned to the free list.

Many (most) actual out-of-order designs do something more complicated than what I've described here (instead of Register Alias Tables mapping from architectural to physical registers, there are CAMs mapping from physical to architectural registers which allows quicker recovery from mis-speculations), but the reasoning techniques are the same: renaming and retirement both happen in-order, and you can use that fact to reason about which registers can be returned to the free list.


How does the token method of amortized analysis work in this example?

Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median).

After partitioning (they assume Quicksort-style partitioning), you can just delete the last $\lceil |S| / 2 \rceil$ elements in the array.

  Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more.

That is a useful intuition, but I feel a little bit besides the point.

Mainly, amortized analysis is about investigating the compound cost of sequences of operations. By dividing the sum by the number of operations we get what we call amortized cost for each operation.

I don't see a specification of such sequences in your problem statement so it may be ill-posed, unless the analysis goes through for all sequences.

So let us check. What is the worst that could happen? Well, probably a sequence of only DELETE-LARGER-HALF operations; consider $n$ elements and a sequence of $m = \lfloor \log_2 n \rfloor$ DELETE-LARGER-HALF operations (after this many, the set is almost empty). Since each operation has linear cost in the number of elements, the total cost then is $\Theta\bigl( \sum_{i=1}^{\log_2 m} 2^i \bigr) = \Theta(m)$ -- fits!

If we wanted to make this sequence more expensive by making individual summands larger, we would need to add INSERT operations. Say we wanted to increase one summand $2^i$ to $2^{i+1}$. We would have to add $2^i$ elements at cost $O(1)$ each, so the compound cost would increase by $2^{i+1}$ -- but $m$ would increase by $2^{i}$! Therefore, the amortized cost would only increase by a constant.

The core observation is this: if an element is to partake in making a DELETE-LARGER-HALF operation expensive (by being there), it has to be INSERTed first. Since DELETE-LARGER-HALF has linear cost, we can not add more than constant cost per element. In combination, this means we will get constant amortized time.

The tokens are a way to formalize this into a proof (which the part you quote does not quite manage to do). The way the tokens are set up and passed around, we see that the cost of any sequence of operations is in $\Theta$ of the total number of tokens we see. We can not possibly see more than $2m$ different tokens so we get an $O(m)$ bound on the compound cost or an $O(1)$ bound on the amortized cost.


scale-free networks and adjacency matrix

The most popular generative model for scale-free networks is the preferential attachment model of Barabási and Albert. A graph is sampled using an iterative procedure. This is a different sampling procedure than you suggest, since the goal is not only to generate a certain degree sequence, but also to mimic other properties of real-life networks.

If all you're after is a certain degree sequence, you can use MCMC methods; see for example Stanton and Pinar. Such algorithms don't conform to your type of algorithm, however. If you want to use your type of model, you have to decide in advance which vertices will have high degree and which will have low degree, since otherwise you will get a degree distribution which is either roughly Gaussian or roughly Poisson, but definitely no power law.

If all you're after is a certain degree sequence and you really want to use your own generative model, here is one possibility. Use the preferential attachment model, the algorithm of Stanton and Pinar, or any other randomized algorithm to generate a graph $G$. Now your model is: given two vertices $x,y$, if $(x,y) \in G$ then connect $x$ and $y$ with probability $1$, otherwise connect them with probability $0$.


Prove that a language is not regular with process of elimination

A simple technique is using the pumping lemma:

For any regular language $L$ there exists an integer $n$ such that for all $x \in L$, with $|x| \geq n$ there exists $u,v,w \in \Sigma^*$, such that,

$x = uvw$
$|uv| \leq n$
$|v| \geq 1$
for all $i \geq 0: uv^iw \in L$

Assumption: Suppose your language is regular.

Consider $s = a^nb^n$. Clearly $s \in L$ and $|s| \geq n$. We get that $uvw = a^nb^n$ and we know that $|uv| \leq n$, i.e $v$ can only contain $a$'s and since $|v| \geq 1$ it must contain at least one $a$. According to the last condition of the pumping lemma, $uv^0w \in L$ but this is clearly not the case. We now have a contradiction as we assumed the language to be regular:

The assumption must be wrong implying non-regularity of the language


What is the difference between a module in a monolithic kernel and a server in a microkernel?

Basically, a module runs at the same memory space than the kernel and a server runs in a different one.

Although a module can surely be added/removed on-the-fly (linux kernel does that), any misbehavior caused by it may affect the entire system, whether in the micro-kernel architecture, only the server gets compromised.


Finding an interval in a binary search tree that contains a point

You can't find a better algorithm for your problem using comparisons, because a lower bound of $\Omega(\log n)$ can be proven for these setings (proof below).

What you can do is some minor optimizations; if each node in your tree saves the end of the rightmost segment and the beginning of the leftmost segment, by adding $2$ comparisons to each query, you can immediately decide $x$ is outside any segments when it becomes out of bounds. These comparisons do not increase your overall complexity, but they also don't improve it.

Let us consider the data as $n$ disjoint line segments. Or to be formal, $I = \{(i_1,j_1),\dots (i_n,j_n) \} $

Suppose given a query $x$ we wish to determine in which interval $(i_t,j_t)$ our query $x$ is located at, or whether no $ 0 \leq k \leq n$ exists s.t $x \in (i_k,j_k)$.

Since your algorithm performs comparisons, it can be represented as a decision tree; a node represents a comparison $x : q$; the left child are the comparisons you would make if $x < q$ and the right child the same for $x>q$.

Note that since in your case, your values $q$ are medians, if $x=q$ you can finish your algorithm (and $x$ belongs to that segment).

Let's denote the decision tree $T$.

Some observations about $T$:

$\bullet$ $T$ MUST have at least $n+1$ unique leaves; one for each segment $(i_t, j_t)$ and one that represents the decision that $x$ belongs to no segment.

$\bullet$ Each inner node $v$ of $T$ has three children ($=, <, >)$

$\bullet$ A trenary tree of height $h$ has at most $3^h$ leaves;
$3^h \geq n+1 \rightarrow h \geq \log_3{(n+1)} \geq \log_3{n}$

Since $\log_3{n} = \Omega(\log n)$, we proved a lower bound for comparison based search, and thus any search as described by your algorithm must perform at least $\log n$ queries.


Are the regular languages closed against injecting single letters?

This language is regular. Let $M$ be a DFA accepting $L$ and assume it has a single initial and final state. We can construct a NFA accepting $L_2$. We create two copies of $M$: $M_1$ and $M_2$. Let us denote the states of $M_1$ as $q_1, \dots, q_n$ and the states of $M_2$ as $p_1, \dots, p_n$. Note that these two DFA are isomorphic where $q_i$ corresponds to $p_i$. The initial state of the new automaton will be $q_1$, and its accepting state will be the accepting state of $M_2$ (so the accept state of $M_1$ is no longer an accept state, and the initial state of $M_2$ is no longer an initial state; in the new NFA, these are just normal states).  Add new transitions $\delta(q_i, a) = p_i$ for each pair $(q_i,p_i)$. The resulting NFA accepts $L_2$.  You can think over it to prove it accepts $L_2$; effectively, $M_1$ is reading the $u$ part of the input and $M_2$ is reading the $v$ part.


Prove that  is not a element of NOT-SELF

Assume (i) $L(Z) \subseteq \text{NOT-SELF}$ and assume towards contradiction that (ii)
$\langle Z \rangle \notin \text{NOT-SELF}$.

Because of (ii) and (i) we get that $\langle Z \rangle \notin L(Z)$.

(if it was in $L(Z)$ and $L(Z)$ is a subset of $ \text{NOT-SELF}$, it must also be in $\text{NOT-SELF})$.

Thus, $Z$ does not accepts its own encoding.
Thus, by the definition of $ \text{NOT-SELF}$ it should be that $\langle Z \rangle \in \text{NOT-SELF}$, which is a contradiction.

Also see the related question:
Can I construct a Turing machine that accepts only its own encoding?


Tight approximation for the chromatic number of an arbitrary graph in polynomial space and time

The result of Zuckermann tells you that the chromatic number of an $n$-vertex graph cannot be approximated in polynomial time to within $n^{1-\epsilon}$, for any $\epsilon > 0$ unless P = NP. In other words, the problem is extremely hard to approximate, so you won't find good theoretical algorithms for the problem.
However, if you care about a practical solution as you claim, i.e., you just want a solution that is computed in a short amount of time and the result is good, there are many things you can try. First, quite a bit depends on the actual instances you want to compute the chromatic number for - what do you know about their structure? For instance, are they sparse or dense?
There a many approaches to try out here. For starters, I would take some sample - representative as possible - of your instances, and see how far their chromatic number is from their clique number (i.e., the size of a maximum clique). Especially if your graphs are sparse, there are very good heuristics and exact solvers available for computing the clique number that can work even on billion-scale graphs. So that will give you a lower bound. If you want a decent algorithm for testing whether that is optimal, you can try a SAT solver. It's simple to map the graph coloring problem to an instance of SAT, and the solvers are highly practical.
Of course, you can also consider a metaheuristic for the problem, say a genetic algorithm or ant colony optimization. For any of these, you can also exploit the lower bound information given via the clique number or upper bound information given by e.g., the maximum degree.


Words that have the same right- and left-associative product

$(\ast)$ If $L$ is a regular language, then $L^R$, the language consisting of the reverse of all words in $L$, is also regular. Take this as an exercise.

How does this help us solve the problem? Let $L_a,L_b,L_c$ be the languages consisting of all strings that evaluate to $a,b,c$ when evaluating from left to right. The language you're interested in is
$$ (L_a \cap L_a^R) \cup (L_b \cap L_b^R) \cup (L_c \cap L_c^R). $$
This shows that if you know how to prove $(\ast)$, then you can construct an NFA for the language in question.

In fact, if you use the idea of the proof of $(\ast)$, then you can probably just go ahead and construct the automaton. So let's consider this. In particular, let's try to construct an NFA for $L_a^R$, the language of all strings that evaluate to $a$ when evaluated from right to left.

The idea is this. Suppose that the first letter you see is $b$. Then the rest of the string must evaluate to $b$ (since $bx = a$ implies $x = b$). Similar reasoning applies when the first letter is $c$. When the first letter is $a$, however, the rest can evaluate to either $a$ or $b$, or be null. With an NFA, we can guess (and later verify our guess).

This hint should give you enough to think about, and hopefully solve the problem.


Local type argument synthesis when type variable does not appear in arguments

As a prelude, there is some terminological confusion in your question.  The issue is about a type variable occurring in a result type of a function.  This is fairly minor.  A more serious one is when you say "my implementation happily infers the types of the above two functions to be ...".  What functions?  Functions are terms like (in this case) $\tt fun(x:T)e$ but the rule you quote is actually about function application, i.e. it applies to terms like $\tt f(e)$.  Either way, the two things you present are types not terms.  What you seem to want to say is: given a function $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ seems to have the inferred type $\tt X$.

$\tt \sigma \in \bigwedge \overline{C} \Downarrow R$ implies that $\sigma$ is a map for all the variables in $\tt R$ or else it wouldn't even make sense.  Maybe it doesn't make sense, but we see that in the rule you listed the constraint generation step produces a $\mathtt{\bar X}/V$ constraint and the substitution algorithm will thus produce a $\mathtt{\bar X}/V$ substitution which, by definition, has a mapping for each type variable in $\tt \bar X$.  I assume your confusion is that you look at the minimal substitution generating algorithm $\sigma_{C\tt R}$ at the bottom of page 11, note that in your second case, for example, the constraint generation step produces an empty set of constraints and thus the "for each constraint" iterates over an empty set producing a substitution with no mappings which presumably would act as the identity.  However, this would violate the definition of an $\mathtt{\bar X}/V$ substitution.  The detail here is the definition of the empty constraint set.  At the beginning of section 3.3 on page 9 it states:

  The empty $\mathtt{\bar X}/V$ constraint set, written $\emptyset$,
  contains the trivial constraint $\tt Bot <: X_\mathit{i} <: Top$ for
  each variable $\mathtt{X}_i$.

Since the result type is covariant (in a top-level context), we'll get $\tt Bot$ in those cases.  In particular, given that $\mathtt{f}\in\tt All(X)()\to X$, the expression $\tt f()$ will have the inferred type $\tt Bot$.  The produced substitution $\sigma_{\emptyset\tt R}$ will map $\tt X$ to $\tt Bot$.


In order to prove that 4-SAT is NP-complete, you need to prove that it is in NP and that it is NP-hard.

Prove 4-SAT $\in$ NP

Given an instance of 4-SAT and an answer that evaluates to TRUE, it's pretty quick to verify.

4-SAT is NP-hard

Like the comments suggested, reduce 3-SAT, which is a known NP-complete problem, to 4-SAT:

Assume that you are given an instance of 3-SAT. The goal is to convert it in polynomial time into an instance of 4-SAT in such a way that the answer is preserved.

Take each clause $(x \lor y \lor z)$ and turn it into $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$, where $a$ is arbitrarily set.

If any $(x \lor y \lor z)$ clause is satisfied, then $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ will also be satisfied. If the instance of 3-SAT is satisfiable, then the new instance of 4-SAT is satisfiable.
If $(x \lor y \lor z \lor a) \land (x \lor y \lor z \lor \neg a)$ is satisfied, then $(x \lor y \lor z)$ must also be true because $a$ is opposite of $\neg a$. If the new instance of 4-SAT is satisfiable, then the instance of 3-SAT is satisfiable.


What is the $4k$ kernelization algorithm for Planar Independent Set?

The formal problem is:

Input: A planar graph $G = (V, E)$ and an integer $k$ (the parameter)
Question: Does $G$ have an independent set of size at least $k$?

A kernelization algorithm for Planar IS with $4k$ vertices.

Recall that we can obtain a four-coloring of $G$ in polynomial time.  That is, we get a partitioning of your vertex set $V$ into $V_1, V_2, V_3, V_4$ such that each class is an independent set.

We now distinguish between two cases:

One class $V_i$ has size at least $k$.  This is a witness and hence $G,k$ is a yes instance, so we may output a trivial yes instance.
Otherwise, every class has size less than $k$, so $V$ has at most $4k-4$ vertices.

Thus in polynomial time, we may output a graph $G'$ with at most $4k$ vertices such that $G,k$ is a yes instance if and only if $G', k$ is a yes instance.

Notice that this only holds for planar graphs.  Independent Set is W[1]-hard on general graphs.


What algorithm to use for training combinations

Your current setup might not be the best one for this.  You need to think about the structure of the model, and the set of features you use.

Model

I would suggest a different approach: see if you can construct a model that captures how well a set of 5 colors match.  In particular, perhaps you can fit a model $f$, where $f(c_1,\dots,c_5)$ describes how well the five colors $c_1,\dots,c_5$ match each other (larger values of $f$ correspond to a better match).  For instance, one plausible model for $f$ is

$$f(c_1,\dots,c_5) = \prod_{i<j} g(c_i,c_j)$$

where $g$ is some function (that you try to fit to the data).  Then, given a training set that describes many different combinations of five colors and how well they match, you could try to fit a model to that (e.g., find $g$ such that $f$ matches the training set as closely as possible).  You can then consider some architecture for $g$, e.g., a small neural network with a few hidden layers, and use gradient descent to train the model.

Features

Constructing a model based solely on the RGB values might be a lot to ask.  I suspect you can do a lot better by choosing some features that are likely to be relevant to color matching.

Often it helps to have some domain knowledge.  Do you know anything about color matching?  Are there any properties of colors that are relevant or informative or affect whether they match?

I would suggest that you pick multiple plausible features, then let the model training process work out which ones are most relevant.  Here are some ideas for you to consider:

Consider adding other color space as additional features.  I would suggest you consider adding the CMYK, HSV, and CIELAB.
It appears that primary colors are best matched with primary colors, and secondary colors best matched with secondary colors, etc.  Therefore, when determining how well two colors $c_i,c_j$ match, perhaps the difference between their hues (modulo 360 degrees) might be relevant.  You could add this as an additional feature that is input to $g$.

Maybe your study of the art of what colors match will suggest other features you can try as well.


Language where every prefix has almost equal a's and b's

Hint: as you read each letter of the input, imagine trying to keep track of the difference between the number of $a$'s and the number of $b$'s.  What is the set of possible values that this could possibly take on, if the input is in $L$?  What's the largest this difference could be?  What's the smallest it could be?


Prove that { ⟨M⟩ ∣ ⟨M⟩ ∉ L(M) } is undecidable

You do not need to reduce $ATM$ to $L$. As it hints, Let $L$ is recognized by a TM $M_L$, and note that $L = L(M_L)$ ($L(M_L)$ denotes the language recognized by $M_L$). Then you have the following contradictions
$$\langle M_L \rangle \in L \implies \langle M_L \rangle \notin L(M_L) \implies \langle M_L \rangle \notin L$$
and
$$\langle M_L \rangle \notin L \implies \langle M_L \rangle \in L(M_L) \implies \langle M_L \rangle \in L$$
This completes the proof.


differences between theoretical research and applied research

Rule of thumb:

Theoretical research concerns itself with models: defining models, determining their properties and theorems that hold given a set of models.
Applied research concerns itself with the real world: solving problems given a real context governed by physical (or social) laws.

Obviously, the two are intertwined and not always clearly separated. For instance, TCSists sometimes call a piece of work "applied" if the model of choice somewhat resembles reality, in contrast to being completely academic.


I don't know which proof you're referring to, but i'd expect it's because the input is assumed to be binary. I.E. a binary string of length 1 can have two values, 0 or 1. A binary string of length 2 can have 4 values, 00,01,10,11, and a binary string of length 3 can have 8 values, and so on.


It is not actually the diameter. It is the longest chain in the partial order $P$ of the input graph $G = (V,E)$. The poset $P$ is constructed as follows. Given an input graph $G = (V,E)$ such that each vertex has a unique identifier. Build an oriented graph $G' = (V,E')$ such that an edge $(u,v) \in E'$ if $(u,v) \in E$ and $u \succ v$. Then build a partial order $P$ of $G'$ by taking the transitive closure of $G'$. Let $l$ be the length the longest chain of $P$, then the time complexity of your algorithm is exactly $l$  (assuming here that the time complexity is measured by the number of communication rounds and in each round a node can send/receive a message to/from all its neighbors). Note that $l$ is $\in O(n)$ and in $\Omega(1)$.

What about average complexity ?
Let's $G(n,p)$ be a random graph of $n$ vertices and an edge between any pair of nodes exist with probability $p \in [0,1]$. Then, if you build a partial order $P$ of this graph (called random graph order), you will find that the longest chain $l$ is in $\Theta(n)$. This result is proven in [1].

[1]: Albert, Michael H., and Alan M. Frieze. "Random graph orders." Order 6.1 (1989): 19-30.

(This is for additional knowledge)
It is possible that assigning identifiers on the input graph such that the complexity of this MIS algorithm is minimized (that is, minimize $l$).  The problem is NP-Hard as it is reducible to minimum coloring. This NP-Hard problem was given in: [2] and [3].

[2]: Deming, R. W. "Acyclic orientations of a graph and chromatic and independence numbers." Journal of Combinatorial Theory, Series B 26.1 (1979): 101-110.

[3]: Chvátal, Vašek, and Carsten Thomassen. "Distances in orientations of
graphs." Journal of Combinatorial Theory, Series B 24.1 (1978): 61-75.

(Ok this is just for fun, and you can skip it)
Now assume that you want to measure time with a different metric. And let's add a restriction to the definition of communication rounds (found in [4]). And let's say that a node 1) can send a message to only neighbor in a communication round, and 2) can receive a messages (more than one) from all its neighbors In such case, the order that a node follow to send a message to its neighbors will affect the time complexity. Let's consider three strategies that a node $v$ follows to visit its neighbors (with smaller identifiers) which are $\{u _1, ..., u _k\}$ such that $u _i \succ u _j$ if $i > j$. Then:

Strategy 1: $v$ sends messages in an order from $u _k$, to $u _{k-1}$ ..., $u _1$ etc .. . This strategy leads to $\Theta(n)$ time complexity.
Strategy 2: $v$ sends messages in an order from $u _1$, to $u _{2}$ ..., $u _k$ etc .. . This strategy leads to $\Theta(n^2)$ time complexity.
Strategy 3: $v$ sends messages to its neighbors in a uniformly random order. This strategy will also lead to $\Theta(n^2)$ in expectation.

(Why I am interested in all that ?) - because it was found in some practical wireless networks (Bluetooth networks), that this slow MIS algorithm is the fastest although not being the theoretically fastest one. It was found that this type of networks follow the modified communication model I defined above.

[4]: Peleg, David. Distributed computing: a locality-sensitive approach. Vol. 5. Society for Industrial Mathematics, 1987.


the problems that could exist if halting problem is solved

"Exists" is a weird word to use here; I assume you're asking about what problems would be solvable if we were suddenly able to solve the halting problem.

Phrasing things in terms of sets of natural numbers for simplicity (as is the general approach here) you're asking for a characterization of the sets which are Turing reducible to $0'$. It turns out that this is a very robust notion. For example, the following three properties of a set $X$ are equivalent:

$X\le_T0'$.
$X$ is limit computable: there is a computable total function $f(x,s)$ such that for each $n\in\mathbb{N}$ we have $\lim_{s\rightarrow\infty}f(n,s)$ exists and is $1$ iff $n\in X$ and is $0$ otherwise.
$X$ is $\Delta^0_2$-definable: there are formulas $\varphi_1(z)\equiv\forall x\exists y\theta_1(x,y,z)$ and $\varphi_2(z)\equiv\forall x\exists y\theta_2(x,y,z)$ where $\theta_1,\theta_2$ use only bounded quantifiers such that $$X=\{n:\varphi_1(n)\}=\{n:\neg\varphi_2(n)\}.$$

Meanwhile, some problems which are not Turing reducible to the halting problem include:

Does a given Turing machine halt on all inputs?
Do two Turing machines accept the same language?
Is a given c.e. set actually computable?

The first two have Turing degree $0''$, while the third has degree $0'''$. It's worth noting that while there are sets which are not "iterations of the halting problem," and in particular there are always lots of degrees between ${\bf d}$ and ${\bf d'}$, there is strong evidence that no "natural" examples of such sets. (There's also a lot of stuff "off to the side" - for example, the set of problems which are Turing-incomparable with $0'$ has full measure and is comeager.)


How does a regular language satisfies the second condition of the pumping lemma

The pumping lemma states that if a language $L$ is regular then there exists $p$ such that every word $w \in L$ that is long enough ($\lvert w \rvert \ge p$) can be split as $w = xyz$ such that

$|y| \geq 1$.
$|xy| \leq p$.
For all $i \geq 0$, $xy^iz \in L$.

You give an example of a language $L$ and a string $s \in L$ which can be split as $s = xyz$ such that

$|y| \geq 1$.
$|xy| = 2$.
For all $i \geq 0$, $xy^iz \in L$.

This is a property which is similar to the one guaranteed by the pumping lemma, but perhaps different. The property expressed by the pumping lemma need not be the only property satisfied by a regular language. All the pumping lemma states is that if a language is regular then it satisfies the pumping property. It does not state that if a language is regular then the only property it satisfies is the pumping property.

To give an analog, consider the following statement: if $x$ is a multiple of $4$ then it is a multiple of $2$. Here is a "counterexample": $12$ is a multiple of $4$, but it is a multiple of $3$ (rather than $2$). Your counterexample is similar.

Another issue is the pumping length $p$. If you look at the proof, then $p$ is the size of a DFA accepting $L$. In particular, $p$ doesn't depend on $w$. In your case, it's not clear why you assume that $p=1$; in fact, when applying the pumping lemma, you cannot assume anything about $p$. You're just guaranteed that some $p$ exists. In fact, for your language $p \geq 5$, since the minimal DFA has $5$ states.

The condition $|xy| \leq p$ is supposed to help you apply the pumping lemma. For example, if you look at the language with strings $0^n1^n2^m$ for $m, n \ge 0$, without this condition you wouldn't be able to prove that the language is not regular, since the pumped part could always be in the $2^m$ area. The condition $|xy| \leq p$ allows you to locate the pumped part.

This condition isn't always general enough, for example it doesn't work for showing that $2^m0^n1^n$ is not regular. There is a more general version of the pumping lemma which can handle this called Ogden's lemma.


How can I restructure matrices to have non-zero elements close to the diagonal?


The mechanics of shift-reduce parsing is pretty simple -- the hard part is understanding why it works or how to construct the tables.  But since you already have the table, that is not relevent.

To do shift/reduce parsing, you need an action table and a goto table (which you have) and a stack of states.  You start with just state 0 on the stack.  At each step you look up in the action table with the top state on the stack and the next token of input and perform the corrsponding action.

for a SHIFT action you consume the token of input and push the state on the stack
for a REDUCE action, you find the SIZE of the right-hand-side of the rule to be reduced (number of symbols -- ε is zero size) and the SYMBOL on the left-hand-size.  You pop SIZE states from the stack and then use the state now on top of the stack and the SYMBOL to lookup in the GOTO table and push the corresponding state.

That's it.  You repeat the above until you either reach an ACCEPT action (the string matches) or a REJECT action (any blank in the action table -- the string is not matched).  The reduce action is a bit complicated as it chains immediately to a goto action, so you can think of the reduce+goto as a single action or as two distinct actions as you prefer.

If you want your parser to construct the parse tree while you're at it, its a bit more complicated.  You need to have your stack hold state × subtree pairs -- when you shift a token you include that token (as a single node subtree) along with the state, and when you reduce, you create a new subtree from the subtrees popped (as children to the LHS symbol) which you push along with the GOTO state.  When you get to the ACCEPT state you do a 'reduce 1' action to build the complete parse tree.


When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis

It's a tradeoff between accuracy vs running time.  CSA often provides more accurate (more precise) results than CIA; but it takes longer.  There's no hard-and-fast rule about when you must use one or the other; rather, you can use either, and you choose where you want to live on that tradeoff.


Your manipulation where you went from $Q_1 = (b \cup ab)Q_2 \cup aaQ_1$ to $Q_1 = (aa)^*(b \cup ab)Q_2$ was not valid.  Instead, in this case I suggest that you first start by finding a nice form for $Q_2$, before trying to manipulate $Q_1$.

A good way to handle $Q_2$ is to note that $Q_2 = a Q_2 \cup b Q_2 \cup \epsilon$ implies $Q_2 = (a \cup b) Q_2 \cup \epsilon$ (by the distribute law); when then apply Arden's rule to conclude that $Q_2 = (a \cup b)^* \epsilon = (a \cup b)^*$.

Now plug in this expression for $Q_2$ into your equations for $Q_0$ and $Q_2$.  You obtain

$$\begin{align*}
Q_0 &= b (a \cup b)^* \cup a Q_1\\
Q_1 &= b (a \cup b)^* \cup a Q_0
\end{align*}$$

Next, take the expression for $Q_1$ and plug it into the first equation.  We see that

$$Q_0 = b (a \cup b)^* \cup a b (a \cup b)^* \cup a a Q_0.$$

Now applying Arden's rule tells us that

$$Q_0 = (aa)^* (b \cup ab) (a \cup b)^*.$$

That's the regular expression that you ultimately wanted.


A variant of the vertex cover problem on trees

Define $f(v,r,s)$ to be the minimum size of a multiset $S$ that covers the entire tree rooted at $v$, such that $S$ contains exactly $r$ copies of $v$'s parent and exactly $s$ copies of $v$.

Then you can express $f(v,r,s)$ in terms of the values $f(w_i,s,t_i)$, where the $w_i$'s are the children of $v$.  If the tree is a binary tree, there are only $9=O(1)$ cases you need to consider and at most $2\times 3=O(1)$ terms in the recursive expression for $f(v,r,s)$.  The case analysis gets a bit ugly, but it's all $O(1)$.

Therefore, you get a $O(n)$ time algorithm for this problem, if the tree is guaranteed to be a binary tree.  I don't know what happens for general trees of unlimited degree.


How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$

Let's take the alphabets as a and b in-order to avoid confusion.

Suppose that A1 is a regular language. Let p be the “pumping length”
of the Pumping Lemma. Consider the string $s = a^pba^pba^pb$. Note that $s ∈ A1$
since $s = (a^pb)^3$, and $|s| = 3(p + 1) ≥ p$, so the Pumping Lemma will hold.

Thus, we can split the string $s$ into 3 parts $s = xyz$ satisfying the conditions.

i. $xy^iz ∈ A1$ for each $i ≥ 0$

ii. $|y| > 0$,

iii.$ |xy| ≤ p.$

Since the first $p$ symbols of $s$ are all $a’s$, the third condition implies that $x$ and $y$ consist only of $a’s$. So $z$ will be the rest of the first set of $a’s$, followed by $ba^pba^pb$.

The second condition states that $|y| > 0$, so $y$ has at least one $a$. More precisely, we can then say that

$x = a^j$ for some $j ≥ 0$,

$y = a^k$ for some $k ≥ 1$,

$z = a^mba^pba^pb$ for some $m ≥ 0$.

Since $a^pba^pba^pb = s = xyz = a^ja^ka^mba^pba^pb = a^{j+k+m} ba^pba^pb$, we must have that $j + k + m = p$. The first condition implies that $xy^2z ∈ A1$, but

$xy^2z = a^ja^ka^ka^mba^pba^pb$

$ = a^{p+k}ba^pba^pb$

since $j + k + m = p$. Hence, $xy^2z$ not an element of $A1$ because $k ≥ 1$, and we get a contradiction. Therefore, $A1$ is a nonregular language.


P Vs NP can never be proven one way or the other!

And I found out that proving P Vs NP is an NP problem.

I think the two different meanings of the word "problem" are mixed here.
When we discuss P and NP, they are the class of decision problems, which are essentially maps from the set of bits sequence to boolean values.
On the other hand, "NP =/= P" is a long standing mathematical problem (general meaning,) but "NP =/= P" itself is a single proposition, and usually it's not considered as decision problem.

If you convert "NP =/= P" to a decision problem as the map from single point to true/false (this is completely valid formalization), its complexity is constant time (algorithm can simply return true or false, though we don't know which one is correct,) so it's in P and NP.

  if somebody proves that, then won't they be contradicting the result itself

Proving "NP =/= P" means we know the correct return value in the algorithm above, and that doesn't contradict with anything. The result simply claims there is a NP problem that is not P. The decision problem "NP =/= P" is just an instance within class P. Both facts can hold simultaneously.


Kolmogorov complexity of strings in a given language

You haven't explained what is meant by the canonical $n$th word, but I assume that there is an algorithm generating all words in $L$, and the canonical $n$th word is just the $n$th word in this list. One such algorithm could go over all possible words in size-lexicographic order, and check for each word whether it belongs to $L$, outputting the words that are in $L$ in size-lexicographic order.

Given such an algorithm, you can construct a new algorithm which gets $n$ and outputs $x_n$. Using the new algorithm, you can generate $x_n$ by running the new algorithm on the input $n$. Since the new algorithm is fixed, it has some size $C$. A prefix-free encoding of $n$ takes $2\log n$ (in fact, you can do almost twice as good), leading to a description length of $C + 2\log n$. (Depending on your definition of Kolmogorov complexity, you might be able to do away with prefix-freedom, and then you can replace $2\log n$ with $\log n$.)

Note that we have only used the fact that the canonical $n$th word is generated by some algorithm which gets $n$ as input. The particular form of $L$ wasn't important.


$L_S$ is undecidable if $S = \mathbb{N}_{odd}$:
The problem of whether a given TM accepts $\epsilon$ is undecidable. There is a simple reduction from this problem to the problem of membership in $L_S$ when $S = \mathbb{N}_{odd}$.  Given a TM $M$, we create a new TM $M'$ which on any input simulates $M$ on the same input, but for each step of $M$, it takes one (or any finite odd number of) extra redundant step(s). This basically makes sure that the number of steps taken by $M'$ on any input is always even.
Now, since $T_{M'} \notin S$, hence, $M'$ is in $L_S$ if and only if $M'$ doesn't halts on $\epsilon$, which in turn implies that $M$ doesn't halt on $\epsilon$. Hence, this language is undecidable.
A similar proof can be also given for $\mathbb{N}_{even}$.
[Undecidable $S$ with Oracle Machines]
$L_S$ is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.
Assuming that the set $S$ need not be decidable itself, and we are going to use it as an oracle and check for decidability using oracle machines.
We construct the set $S$ as follows: for each Turing Machine $M$, let it's binary encoding be $\langle M \rangle$, and let the length of the string $\langle M \rangle$ be $n$. If $M$ doesn't halt on $\epsilon$, then we add the number $10^{n}\langle M \rangle$ to our set $S$. By construction, this set doesn't contain infinite numbers.
Now, the decider will work as follows: On an input $M$, it will check whether the number $10^{n}\langle M \rangle$ is in $S$. It will accept $M$ if the number if found, else we can be sure that the machine $M$ will halt, and hence we simulate $M$ on $\epsilon$ until it halts while keeping the count of the number of steps taken by $M$. We finally accept or reject $M$ on the basis of whether this count is in $S$ or not.
Hence, this language is decidable for a set $S$ for which $\mathbb{N} \setminus S$ is not finite.
[Decidable S]
When the set $S$ is decidable, it will be interesting to know whether the hypothesis that "$\mathbb{N} \setminus S$ is finite" holds. I suspect that the answer would be affirmative.
Let $S' = \mathbb{N} \setminus S$ be infinite set. If $S'$ has "simple" subsequence in it (say, an Arithmetic Progression), then we can prove that $L_S$ would be undecidable by a proof similar to the one in the case of $S = \mathbb{N}_{odd}$. The idea is simply to run a construct a TM $M'$ which simulates $M$, and if $M$ halts, then jump to the next hole in $S$. $M'$ will be in $L_S$ iff $M$ halts.
This idea doesn't seem to work when $S'$ is a difficult set; by which I mean that checking the membership is hard in terms of time complexity.


If you have a variable $x$ that can represent any number from $0$ to $n-1$ (or any value from a set of of $n$ possible values, really), such an the index of an array of $A[0 \dots n-1]$ of $n$ elements, then $x$ needs to use at least $\lceil \log_2 n \rceil = \Omega(\log n)$ bits.
This is because there are $2^b$ combinations for the values of $b$ bits. Then, to represent $n$ values you need to have $2^b \ge n$, i.e., $b \ge \log_2 n$. You can add the ceiling since $b$ must be an integer.
When you say "an array of $n$ elements uses $O(n)$ space" you are probably  thinking of a word-RAM model. Here the memory is split into addressable words, i.e., groups of $w$ bits. Each entry in the array occupies one (or a constant number of) words of memory (this also means that the elements in the array can't represent more than $2^{\Theta(w)}$ values each).
Usually the word size $w$ is chosen to be $\Theta(\log n)$, where $n$ is some natural parameter of the input problem (e.g., the size of the instance). In this case an index of an array of $n$ elements can be stored into a single memory word, i.e., in $O(1)$ space.
However this is not contradicting the above lower bound of $\lceil \log_2 n \rceil$ bits, it's just that these bits are all packed into a single (or into a constant number of) memory word(s).


Note that $x=i!$. Now it's easy to see $y=(i+1)!$ and $z=(2i)!$. So $c=\frac{(2i)!}{i!(i+1)!}$, which is the $i$th Catalan number.

P.S. Your formula is wrong. The condition of the inner loop is $j=i+m\le2i$, so $m$ is from $1$ to $i$ instead of $2i-1$ or something.


Converting indirect recursion to direct one

$S\to A$

$A\to aA'|EP$

$B\to CDB'$

$B'\to AB'|EP$

$C\to bC|EP$

$D\to aD'|bC'DB'bD'$

$D'\to B'bD'|EP$

There is a standard algorithm to remove indirect left recursion check here https://en.wikipedia.org/wiki/Left_recursion#Indirect_left_recursion


Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example,

HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ eventually halts when started on input $x$,

and, similarly

MP is a collection of pairs $M, x$ as above and an instance of MP is in the set MP if the machine described by $M$ eventually halts in an accept state when started on input $x$.

In simple terms, HP is about programs and inputs and answers "Does this program halt on this input?" and MP answers "Does this program accept this input?"

The octothorpe (the # symbol) is just a separator so we know where $M$ ends and $x$ starts.


why & how are BFS nodes goal tested when they are generated?

The question makes sense as is and it, indeed, stands for a very important difference in how search algorithms are implemented.

Before moving further, let us refer to basic concepts that were certainly defined in your course material:

Definition 1 [Generation of a node] A node $n$ is generated when a data structure representing its contents is created, i.e., when it is allocated in main memory.

Definition 2 [Expansion of a node] A node $n$ is expanded when all its children are generated.

In general, all brute-force search algorithms (or uninformed as they are usually termed in modern literature) "goal test" nodes when they are generated. There is no reason to modify this decision as it suffices for preserving the main properties of search algorithms. Since you mention Breadth-First Search (BFS), let us review its main properties:

Lemma 1 [Completeness of BFS] Breadth-First Search is complete, i.e., it is guaranteed to find a solution, provided that any exists.

The proof is very simple. It just suffices to observe that by storing nodes in a queue, nodes at depth $d$ are expanded only if all nodes at depth $(d-1)$ have been expanded. Conversely, nodes at depth $d$ will surely be expanded, immediately after all nodes at depth $(d-1)$ have been expanded. Hence, it does not matter where the solution node hides, it will be certainly found even if the graph is infinite (but not locally infinite, i.e., solutions might not be found if there are nodes with an infinite number of descendants).

Lemma 2 [Admissibility of BFS] Breadth-First Search is admissible, i.e., it is guaranteed to find optimal solutions provided that any exist.

This is true if edge costs are neglected. Thus, cost of a solution path equals its depth. Since BFS only expands nodes at depth $d$ after expanding all nodes at the preceding depths, once a solution is found, it can be guaranteed to be optimal since we already tested all paths of shorter lengths (or, equivalently, costs).

There's the trick! If edge costs are neglected, then there is a correspondence between path cost and path length.

Now, what about searching in graphs with arbitrary costs? Best-First Search algorithms (termed also as BFS, but I will not to avoid confusion with the preceding algorithm) are devised to handle this case specifically. Dijkstra is one among many algorithms in the family of Best-First Search algorithms.

In this case (i.e., with arbitrary costs), there is not a correspondence anymore between path length and path cost. Hence, an algorithm can not stop once a goal has been generated if admissibility if desired (i.e., the property that guarantees that solutions found are also optimal). Instead, we keep on generating nodes and inserting them in ascending order of cost. This way, once a goal is about to be expanded (and only when it is about to be expanded!) we can certainly ensure that it is an optimal solution, because: (1) all the other nodes in open have a cost which is larger or equal; (2) path cost is assumed to grow monotonically (i.e., negative edge costs are not allowed).

As I said at the beginning, the stopping condition (whether to stop when the goal is generated, or when it is about to be expanded) is critical for the good behaviour of search algorithms. Indeed, many people believe that A$^*$ (which is also a Best-First Search algorithm) with a null heuristic ($h(n)=0, \forall n$) is equivalent to Breadth-First Search. This is not true as there is a critical difference in the stopping condition.

For more details about this, I would recommend you to look at Robert C. Holte. Common Misconceptions Concerning Heuristic Search. Proceedings  of  the Third Annual Symposium on Combinatorial Search (SoCS-2010), pp. 46-51 and, specifically, to page 49.

Hope this helps,


Borrowing the definition from Gaurang Tandon's question:

An array $A[1...n]$ is said to be k-ordered if
$$A[i - k] \leq A[i] \leq A[i + k]$$
for all $i$ such that $k < i \leq n - k$.
For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.

I must also say that I've never seen a similar definition before (and I find it to be quite un-useful, but maybe it is important somewhere).
Another definition I have seen, extends the ordering to $k$-dimensional objects. For instance, with two dimensions:

Given vectors $v=(v_1,v_2)$ and $u=(u_1,u_2)$,  we say that $v>u$ in a 2-ordering if
$$v_1 > u_1$$
or if
$$ v_1=u_1 \text{ and } v_2>u_2$$

Then, an array of vectors $v[1...n]$ is $2$-ordered if for every $i$, $v[i]<v[i+1]$ via the above 2-ordering.


What is the difference between quantum TM and nondetermistic TM?

As a general preamble, QTMs, TMs and NTMs are all different things (taking huge liberties with a bunch of unspoken assumptions).

I'll assume you know what a Turing Machine is.

 A NTM is a TM where, at any state, with any symbol, the transition function is allowed to have a number of choices of action that is not precisely $1$, i.e. $0$ or more than $1$ (a deterministic TM must have exactly one action for each symbol at each state, though the $0$ case is easy to deal with). When faced with a situation where there are several choices of transition a NTM will make the choice that will ultimately take it to an accepting state, if such an option exists.

In contrast a QTM is a model of quantum computation, as detailed in the thread you linked. It is not nondeterministic, not all. Probably the key high level differences between a QTM and a TM is that a QTM has as its state a linear combination of the basis states (again, it's all in that other thread) and that it's probabilistic, that is, the accuracy of its ouput is bounded by some probability less than $1$ (broadly speaking).
Just to be really really clear on a point that catches many people, nondeterminism is not randomness, it's not parallelism, it's a theoretical construct that has nothing to do with either of those.

 The full answer to this depends on some complexity theoretic assumptions. Taking a particular standpoint (that $QMA \supset BQP$ and $NP \supset P$), the answer is yes. $NP$-complete problems can be solved by a NTM in polynomial time, and it also seems that $NP\text{-complete} \cap BQP = \emptyset$, so they can't be solved by a QTM in polynomial time.
Again, this is all dependent on which way the cards fall with a variety of complexity classes. If it turns out that $QMA = BQP$ then the answer is no, for example.

 The first thing to say here is to be careful about confusing TMs (of any kind) and computers. A TM is not a computer, a QTM is not a quantum computer. TMs (of any kind) model computation. What a given computer can do is governed by this, but this is quite different to saying that the thing I'm typing this on is a TM.
Having said that, if we speak loosely and lazily identify QTMs with quantum computers and TMs with standard computers, then (again under certain complexity assumptions) it seems that quantum computers can quickly do certain tasks that seem hard for standard computers (factoring, discrete logs, a really particular type of searching, and a couple of others). However these problems aren't known to be hard in the $NP$-complete sense either, it seems quantum computers offer capabilities that extend a standard computer, but in a different direction to what would be needed to solve $NP$-complete problems quickly.

Again just to be really clear, I've glossed over a lot of computational complexity here, if you really want to understand how everything fits together, you'll need start digging in to the literature.


What is the advantage of Greibach Normal Form over Chomsky Normal Form?

There are actually several variants for these normal forms, so it might be useful to first recall the definitions. A context-free grammar is in Chomsky normal form if all of its production rules are of the form:

  $X \to YZ$
  $X \to a$
  $S \to 1$

where $X, Y$ and $Z$ are nonterminal symbols, $S$ is the start symbol, $a$ is a letter and $1$ is the empty word. A grammar is in Chomsky reduced form if its productions are of the form 1 or 2, but with $X$ and $Y$ being possibly equal to the start symbol.
The Chomsky Normal Form has been used to give a polynomial-time parsing algorithm (the CYK algorithm).

A grammar is in Greibach normal form if its productions are of the form

  $X \to aX_1 \dotsm X_k$
  $X \to b$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$ are letters. It is in Greibach quadratic normal form if $k \leqslant 2$ in all rules. It is in Greibach two sided normal form if its productions are of the form

  $X \to aX_1 \dotsm X_kb$
  $X \to c$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$, $c$ are letters. It is in Greibach quadratic two sided normal form (or Hotz normal form) if $k \leqslant 2$ in all rules. These normal forms have important applications in formal language theory. See for instance the article Towards an algebraic theory of context-free languages.


Having trouble in understanding the definition of a clique

Recalling that a clique is a subset $C$ of vertices of an undirected graph such that the subgraph induced by $C$ is fully connected. That is, every two distinct  vertices in $C$ are connected by a distinct edge of the graph. This means different edges, not the same.
So, on a clique $C$ containing $k$ vertices $v_1, v_2,..,v_k$, there are $\frac{k(k-1)}2$ edges connecting them, that is the number of possible unordered pairs on $k$ elements.
Example

As you can see in the previous picture, this is a clique on four vertices $\{{1,2,3,4}\}$, so there is a different edge connecting every edge (i.e. $(1,2)$,$(1,3)$,$(1,4)$,$(2,3)$,$(2,4)$,$(3,4)$).
You can count them and see that there are exactly $6 = \frac{4\times 3}{2}$ edges.


Complexity classes closed under finite union and intersection, why not infinite union and intersection?

Consider the "singleton" languages: $L=\{w\}$ for some fixed word $w$.  (e.g., the language $L=\{00010100\}$ would be a singleton language)  Most "nice" complexity classes include the singleton languages.

Every language can be written as an infinite union of singleton languages. So, if all singleton languages are in the class, and if the class is closed under infinite union, then all languages are in the class.

Thus, if there is any language at all that isn't in such a complexity class yet it does contain all the singleton languages, then the class cannot be closed under infinite union.


Distinct elements count of huge multiset

Let me simplify your third step: count the number of elements in your multiset which are not in the map, and add to it the number of elements in the map.

Suppose that your elements are $x_1,\ldots,x_n$. For a given hash $h$, let $x_{i_1},\ldots,x_{i_\ell}$ be the elements hashing to $h$ (in order). If $\ell = 1$, then the elements won't be added to the map in the first or second step. Otherwise, elements $x_{i_2},\ldots,x_{i_\ell}$ will be added to the map in the first step, and elements $x_{i_{\ell-1}},\ldots,x_{i_1}$ will be added to the map in the second step.

In total, this shows that after the first two steps, the map will contain all elements whose hash appears more than once.

After the third step, cnt will contain the number of elements whose hash appears exactly once. All of these elements are distinct, and also distinct from the elements in the map. You then add to cnt the number of elements present in the map, and so obtain the number of distinct elements.


Must the champion of an entire tournament beat the champion of a possible tournament among other players?

Here is a proof by induction. The base case, $n = 2$, is clear.

Now consider a tournament in which $p_1$ wins. Suppose first that the first competition doesn't involve $p_1$. Let the new set of players be $p_1,P$. By induction, we know that $p_1$ must beat one of the possible winners of the tournament in $P$, say $p_i$. Since the first competition didn't involve $p_1$, $p_i$ can also win the tournament on $p_2,\ldots,p_n$, completing the proof in this case.

Suppose next that the first competition has $p_1$ beating $p_2$. Applying the induction hypothesis, we know that $p_1$ must beat one of the possible winners of the tournament in $p_3,\ldots,p_n$, say $p_i$. If $p_i$ beats $p_2$, then $p_i$ can also win the tournament on $p_2,\ldots,p_n$, and we're done. If $p_2$ beat $p_i$, then $p_2$ can win the tournament on $p_2,\ldots,p_n$, and so we're again done (since in the first competition, $p_1$ beat $p_2$).


Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

Your problem is NP-complete, so you should not expect to find any efficient algorithm for it.

If we could solve your problem efficiently, we could solve the $k$-clique problem, too.  Let $G$ be an unweighted, undirected graph; we are curious whether it has a $k$-clique.  Translate it into an instance of your problem by making each edge have weight 2, and then for each pair of vertices $u,v$ that are not connected by an edge, add a new edge of weight 1.  Now ask for the solution to your problem.  Notice that there exists a way to select $k$ vertices such that the corresponding spanning tree has cost $2k$, if and only if $G$ has a $k$-clique (if $G$ does not have a $k$-clique, no matter how you select $k$ vertices, the cost of the spanning tree will always be $\le 2k-1$).

Since the $k$-clique problem is NP-complete, your problem is NP-complete, too.  Therefore, we cannot expect an efficient solution for your problem, when $k$ is arbitrary.


How is the Varshamov-Tenegolts code decoded?

Right, the code $VT_0(4)$ has Levenshtein distance (edit distance) of 4: to get from one codeword to another you must do 2 deletions and 2 insertions. Therefore, the code can correct one deletion.
Indeed, if 101 was received, the only possible way to get this message assuming one deletion, is if 1001 was sent.

Decoding can be done in several ways:

The naive approach: since the edit-distance is large, if only a single deletion occurred there is only a single codeword that could have been sent. To decode we can just go over all the codewords until we find the one that leads to the received word. More efficiently, we can start with the received word and try to insert 0 or 1 in all the possible position until we get a codeword. We are guaranteed that we will get only one code word. However, this still may take a lot of time/computation.

The more efficient approach is an observation that appeared in Levenshtein's original paper[1] and then also re-explained in Sloan's manuscript on single-deletion correction codes[2]. I'll repeat the essence of it, but you can find it there as well.

Assume each of the codewords $x=x_1\ldots x_n$ satisfies
$$ \sum_{i=1}^n ix_i = a  \mod n+1$$
If there was only a single deletion we will get the word $y=y_1\ldots y_{n-1}$. we can compute the value
$$a' = \sum_{i=1}^{n-1} i y_i$$
The key observation is the following. Let's assume the index $j$ was deleted. That is $y_1=x_1, \ldots, y_{j-1}=x_{j-1}$ and $y_j=x_{j+1}, \ldots y_{n-1}=x_n$. Denote with $R_0$ the $\{x_i\}_{i<j}$ that are a $0$, and with $R_1$ the ones that are a $1$. similarly, let $L_0=|\{ x_i =0 \mid i>j\}|$ and $L_0=|\{ x_i =1 \mid i>j \}|$.
Now let's look at $a'-a \mod n+1$. (below all computations are $\text{mod } n+1$.)

3.1. Let $w=L_1+R_1$ the weight of $y$ (the number of $1$'s).

3.2. If $x_j=0$, then
$$\begin{align*}
a'-a &= \sum_{i=j}^n  i(y_i-x_i) = \sum_{i=j}^n  i(x_{i+1}-x_i) \\
     &= ix_{j+1} + (i+1)(x_{j+2}-x_{j+1}) + \dotsb + (n-1)(x_n - x_{n-1}) - nx_n\\
     &=-x_{j+1} - x_{j+2} - \dotsb - x_n = -R_1
  \end{align*}$$
(note that $R_1<n$ so the mod $n+1$ is good enough; I also virtually set $y_n=x_{n+1}=0$ so it adds nothing to the sum but make them well defined)

3.3. But if $x_j=1$, then
$$\begin{align*}
a'-a &= \sum_{i=j}^n  i(y_i-x_i) = \sum_{i=j}^n  i(x_{i+1}-x_i) \\
     &= i(x_{j+1}-1) + (i+1)(x_{j+2}-x_{j+1}) + \dotsb + (n-1)(x_n - x_{n-1}) - nx_n\\
     &= -R_1 -i = -R_1 - L_0 -L_1 -1 = -w -L_0 -1
  \end{align*}$$

3.4. Forget about the minus sign (that is, look at $a-a'$ instead). If we get something which is $<w$ then we must be in the first case (since $R_1<w$), and we learn two things: (1) that a zero was deleted, and (2) we learn $R_0$, which means that we know where to put the zero back: before this deleted zero there are exactly $R_1$ ones!
if what we get from $a-a'$ is $>w$ we know we are in the second case. Now we learn that: (1) a one was deleted from the codeword, and (2) we learn $w+1+L_0$ but we know $w$ so we get $L_0$, and we can restore the deleted 1: to the left of this deleted one there are exactly $L_0$ zeroes.

See also

[1]: V.I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, 1966.
[2]: N.J.A Sloan, On Single-Deletion-Correcting Codes, 2002.


Expressing the condition as a set of linear constraints

Let us instead translate $x=0 \leftrightarrow y=0$ into disjunctive normal form. We would get

$$ (x=0 \wedge y=0 ) \vee (x>0 \wedge y=1) \vee (x<0 \wedge y=1) $$

Each conjunction is a linear constraint.

In your solution you assumed that the constraint $y=1 \vee x=0$ is always true. In fact $y=1 \vee y=0$ is always true, since this is the domain of $y$.

If you kept this constraint, you would have eliminated solutions where $y=0$ and $x \not= 0$.

Another issue is with your interpretation of the constraints. The pair
$$
\begin{array}{c}
-M < x < 0\\
y=0
\end{array}
$$
is a set of two constraints not a single constraint, therefore it is satisfied by the following 19 pairs
$(-5,0),...,(8,0),(-5,1),...,(-1,1)$. The first 14 pairs clearly violate the condition $x=0 \leftrightarrow y=0$.


The first point seems like a mistake. Find a different solution.

For the second point, $o(f(n))$ often refers to a function whose absolute value is $o(f(n))$. So $-o(f(n))$ and $o(f(n))$ are really the same thing. For example, you can write $n - 1 = n + o(n)$.

For the third point, here is a simpler example: $n + o(n) = \Theta(n)$. You can check that if $|f(n)|/n \to 0$ then $(n + f(n))/n \to 1$, and in particular $n + f(n) = \Theta(n)$.


Fenwick Tree/ Binary Index Tree Interval location

You can perform binary search on a Fenwick Tree.
The idea is Binary Lifting.

I'm assuming that we use a one-based indexing in the Fenwick tree, and that we have exactly $2^k$ elements in the array $A$. And to formalize the problem: we want to find the biggest $i$, such that $A[1] + A[2] + ... + A[i] < x$ for a given $x$. This means that the prefix sum of the first $i$ element is still too small, but the prefix sum of the first $i + 1$ elements is exactly $x$ or already too big.

The exist multiple different implementations of the Fenwick tree. As I said here I use one-based indexing, since the algorithm is a lot more beautiful this way.
For refreshment, one-based indexing in a Fenwick tree means the following (explained using an example): The sum of the first $13 = 1101_2$ numbers can be computed as $bit[1000_2] + bit[1100_2] + bit[1101_2]$, where $bit$ is the array of the nodes of the Fenwick tree. The first summand $bit[1000_2]$ covers the first $1000_2 = 8$ elements (last set bit), the second summand $bit[1100_2]$ covers the next $100_2 = 4$ elements (last set bit), and $bit[1101_2]$ covers the last $1_2 = 1$ elements (last set bit).

This indexing allows a very cool trick:
We can iterate over the bits, from the highest to the lowest one, and check in $O(1)$ time if we should set it or not.

function find_biggest_smaller_index(x):
    // returns biggest i such that A[1] + A[2] + ... + A[i] < x
    i = 0
    for b = log(n)...0:
        set bit b in i
        if bit[i] < x:
            // yay, gives a better lower bound
            // this handes the last 2^b elements, therefore subtract them
            x -= bit[i]
        else:
            // damn, too big already
            unset bit b in i
    return i

edit: now that I think about it. It should also work if the size of the array $A$ is not a power of 2.


Compression for set of integers preserving their sequence

Given that all the numbers form 0 to N-1 are to be stored, and their order, there will be N! permutations.  The minimum number of bits needed to store any combination and its order from an randomly selected order will be

$$\lceil \frac{\log(n!)}{\log(2)}\rceil$$

For example give a range of {0..99} (N=100) the Number of bits to store the permutations is $\lceil \frac{\log(100!)}{\log(2)}\rceil = 525\text{bits}$.

This can be encoded using a Mixed-Radix Calculation, or can be done using Arithmetic Coding (with a slight extra few bits).

In short using a LIST of the numbers to choose from. Each time one of the numbers is eliminated, to take the last number in the list, move it to fill in the eliminated number, adjust the "stats" for Arithmetic coding. Since All the symbols are equally, the same percent applies to all the symbols, and makes easy and Linear time to encode.

Each elimination increase percent chance of the next symbol (IE Number) occurring in the remaining of the list using list of the 0..(N-1) and using the move the last item to the empty position, and shorten the list.

A hash table can be used to make finding the number to replace be done in $\mathcal O(1)$ expected time, for the $\mathcal O(N)$ sequence.


Can a language be context free and not have a BNF grammar?

No. If a language is context-free, it has a BNF grammar, by definition. A context-free language is a language with a context-free grammar, and a context-free grammar is a grammar written in BNF with only one symbol on the left-hand side of each production. That's what "context-free" means.
It might not be convenient to write the grammar. For example, consider the language of words containing characters from some alphabet where no word contains two of the same character. The language is context-free, but the size of the shortest BNF grammar which describes it is exponential in the size of the alphabet. If you chose the set of 95 printable ASCII characters, the grammar would have so many productions that you would need a computer the size of the galaxy to store them.
Even if the language is not so pathological, you might feel that writing down its grammar in BNF is too time-consuming and mundane to make it a worthy use of your superior intellect.
But if the language is context-free, the grammar exists, at least in the mathematical sense of the word "exists".


Why are these states equivalent on this translation table

The two states F and G on similar inputs leads to a final state.
     w(F)+0*1 = w(final-state);
     w(G)+0*1 = w(final-state);
Here, w(X) is the string that leads to the state X, and
      + is concatenation operator.

Due to the above proposition, it is clear that the two states behave in the same manner and the system's functionality will be unaffected because of merging of these states.


Scheduling optimization problem in theta(n)

Since there are no dependencies between tasks, you might try a greedy algorithm: at each step, take the task that has the smallest start time (of all remaining tasks), then move on to the next time step.  This does end up requiring you to sort.

If the start and end times are all bounded above by some constant times $n$, you might want to read up on non-comparison based sorting routines, such as counting sort.  These sorting algorithms can achieve $O(n)$ time (under those conditions), yielding a $O(n)$ time solution to your problem (under the condition that the start and end times are all bounded above by some constant times $n$).

If you have no guarantees on the range of possible start and end times, then as David Richerby explains in his comment, there is no hope of achieving $O(n)$ time: there is a reduction from sorting, as he explains, so $O(n \lg n)$ is about the best you can hope for if we have no guarantees about the start and end times.  That still might be plenty efficient in practice; for realistic values of $n$, $\lg n$ will be quite small, and standard sorting algorithms are extremely efficient.


small size and small depth circuit for set intersections

You are asking many different questions. The usual rule is one question per post. To help you get started, here is how to compute $S_1 \cap S_{\min S_1}$ (defined as $\emptyset$ if $S_1 = \emptyset$).

The input to the circuit is the $n^2$ variables $x_{i,j}$, indicating $i \in S_j$ (this means that they are TRUE if the condition holds, and FALSE if it doesn't hold). The output to the circuit are $n$ variables $y_i$, indicating whether $i \in S_1 \cap S_{\min A}$.

Let $f_a$ indicate $\min S_1 = a$. Then
$$
f_a = \lnot x_{1,1} \land \cdots \land \lnot x_{a-1,1} \land x_a.
$$
Given these, we can calculate
$$
y_i = x_{i,1} \land \bigvee_{a=1}^n (f_a \land x_{i,a}).
$$
We can implement each $f_a$ as a depth 2 circuit with unbounded fan in of size $O(a)$, and each $y_i$ as a depth 2 circuit (with inputs $f_a$ and $x_{i,j}$) with unbounded fan in of size $O(n)$. The circuits for $f_a$ take $O(n^2)$ in total and the circuits for $y_i$ take $O(n^2)$ in total, so altogether we get a depth 4 circuit of size $O(n^2)$.

This circuit is equivalent to a depth $O(\log n)$ circuit of size $O(n^2)$ with bounded fan-in, by replacing each large fan-in gate by a balanced binary tree.


Creation of skip list: Las Vegas or Monte Carlo?

The difference between a Las Vegas algorithm and a Monte Carlo algorithm is that a Las Vegas algorithm is always correct but its running time may be large with small probability, whereas a Monte Carlo algorithm always has the same time complexity but may give wrong results with small probability.
These definitions are more appropriate for decision problems and optimization problems, and less for data structures. That said, they still make sense for data structures. Here are two examples:

Skip-lists correctly implement the list abstract data type. They are efficient with high probability. This is like a Las Vegas algorithm.
Bloom filters are always efficient (in this case we care about space complexity), but may give wrong results to queries. This is like a Monte Carlo algorithm.

Most data structures are designed with the Las Vegas objective in mind.


There is a pretty reasonable discussion in this essay from the SLK parser generator.

Basically, you just need to extend $FIRST$ and $FOLLOW$ to be $FIRST_k$ and $FOLLOW_k$, meaning the first / following $k$ symbols. The basic principle is the same, but when $k > 1$ there is a complication, leading to the distinction between "strong" and regular grammars.

The naming is a bit counterintuitive; the parsing table for a strong grammar can be generated by an easier but less powerful algorithm, so the strong grammars are in a sense weaker; they make a stronger guarantee about predictability.


Why are greedy algorithms used to find upper/lower bounds? (when they doesn't guarantee an optimal solution)

There are lots of NP-complete problem where no algorithm will find an optimal solution - during your lifetime. Given the choice between a greedy algorithm that finds a solution quickly which is often good, and an algorithm that will find a guaranteed optimal solution, but not while you are waiting for it, what are you going to use?