Expected value of the distance between nodes in a binary tree

Let's name the nodes $\mathit{node0}$ through $\mathit{node15}$. (with the implication that that's the order of the nodes)

I would approach this problem first by saying "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?" Then I'd ask the question "what if $a$ is $\mathit{node1}$?", etc. Presumably along the way there would be patterns and symmetries I could make use of so I wouldn't need to do a long calculation 16 times.

So let's take that first question: "if $a$ is $\mathit{node0}$, then what's the expected value of the distance between $a$ and $b$?"

First off, the distance between $\mathit{node0}$ and $\mathit{node0}$ is $0$.
To $\mathit{node1}$, the distance is $2$.
To nodes $\mathit{node2}$ or $\mathit{node3}$, the distance is $4$. To the four nodes $\mathit{node4}$ through $\mathit{node7}$, the distance is $6$. To the remaining eight nodes the distance is $8$.

So the expected distance when $a$ is $\mathit{node0}$ is $(0 + 2 + 2*4 + 4*6 + 8*8)/16 = 6.125$.

Now figure out the expected distance when $a$ is $\mathit{node1}$, and then other nodes. (there is an obvious pattern - prove it)

Then average over those results to find the answer.

Often, you will find a shorter or more elegant solution to a problem as you are working on it. This is normal, and should not be taken as a sign that your initial approach was wrong or that you should have seen the more elegant approach without trying your initial approach first, any more than a writer should expect to write an essay without first writing some notes or a rough draft.

Unfortunately, though writers are often trained in the idea of rough drafts and revisions, solutions to math or computer science problems are usually only presented in their final form without much indication of the bumbling around and blind corners that really went into discovering the elegant explanation.


Would the P vs. NP problem become trivial as a result of the development of universal quantum computers?

No, there will be absolutely no implication, for several reasons:

The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial time.
Universal quantum computers, in a theoretical sense, are (to the best of my knowledge) already known to exist. These are just the quantum analogs of universal Turing machines: they can execute any given quantum "program".
Both quantum computation and the P vs. NP problem are theoretical notions. What someone can construct in the physical world has absolutely no bearing on anything having to do with them.

Lieuwe Vinkhuijzen gave a different interpretation of your question:

  Will quantum computers be able to solve NP-complete problems efficiently?

The expected answer is: no. So even in this sense, physical quantum computers won't enable us to solve NP-complete problems at will.


Isn't the given characterisation of recursively enumerable subsets of the class of all recursively enumerable languages?

No, it is not contradictory. Both conditions are positive in the sense that they "put things in $S$", so they cannot be at odds with each other.

There is an equivalent formulation of $S$: there is an r.e. set $B$ of finite languages such that
$$S = \{L \mid \text{$L$ is r.e. and $\exists L_0 \in B \,.\, L_0 \subseteq L$}\}.$$
In words: $S$ is generated by an r.e. set of finite language $B$ in the following way: $S$ contains precisely all r.e. languages which contain an element of $B$.


Why is the language of even-length non-palindromes context-free?

The language of even-length non-palindromes is given by the following context-free grammar:

$$S \rightarrow 0S0 \mid 1S1 \mid D$$
$$D \rightarrow 1A0 \mid 0A1$$
$$A \rightarrow \lambda \mid 00A \mid  01A \mid  10A \mid  11A$$


Estimating the bit operations using big O notation

There are several problems. First, the time complexity of multiplying two k-bit numbers is much less than O(k^2). More like O(k log k). Since this is an important open research problem, you usually assume it is O(M(k)) for some function M and use that further.
Second, you are not multiplying two k bit numbers. You are multiplying one k-bit number by 3, which is done easily in O(k). This would get you a total of O(n^2).
Third, that’s not a clever method to calculate $3^n$. Much better is repeated squaring/multiplying. For example to calculate $3^{100}$: Start with 3, square, multiply by 3, square, square, square, multiply by 3, square, square. Since the number of bits starts small and doubles every time, this works in O(M(n)).


When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative.

You can convince yourself that almost every algorithm can be adapted to have a best-case complexity of $O(n)$, where $n$ is the size of the input, by simply running a preliminary check that verifies if the input instance belongs to some class of instances for which the solution is trivial.

Just to give a concrete example: the best case for every sorting algorithm can be made $O(n)$ if you just check whether the input sequence of numbers is already sorted.

The focus is often on the worst-case complexity. Once you decide that you want to compare algorithms with respect to their  worst-case complexity, it also makes sense to ask how quickly a problem can be solved.

It is usually impossible to give a sharp bound to the time needed to solve a problem, therefore one seeks upper and lower bound.

An upper bound of $O(f(n))$ tells you that there is some algorithm that solves the problem in $O(f(n))$ worst-case time.

A lower bound of $\Omega(g(n))$ tells you that no conceivable algorithm can take  $o(g(n))$ time to solve the problem.

Just to be clear: a lower bound on the time needed to solve a problem is expressed as a function of the input size $n$ and is the smallest amount of work that is necessary to solve all instances of size $n$. Intuitively (not a formal definition) you can think of it as $\min_{A \in \mathcal{A}} \max_{I \in \mathcal{I}_n} T(A,I)$ where $\mathcal{A}$ is the set of all possible algorithms that solve your problem, $\mathcal{I}_n$ is the set of all instances of size $n$, and $T(A,I)$ is the time needed by $A \in \mathcal{A}$ to solve instance $I \in \mathcal{I}_n$.

What you seem to have in mind instead is $\min_{A \in \mathcal{A}} \min_{I \in \mathcal{I}_n} T(A,I)$.

A lower bound for a problem is useful to establish how "hard" that problem is to solve (problems that require more time to solve are harder, this would make little sense if we looked at the easiest instances instead), and to measure how far an algorithm is from being optimal.
For example Merge Sort solves the sorting problem in the optimal amount of time because its running time (asymptotically) matches the $\Omega(n \log n)$ lower bound for the sorting problem (in the comparison-based model).


What kind of growth is $O(0.24\cdot K\cdot 2^w)$

If $K$ is constant and $w$ is variable then $0.24\times K\times 2^w$ and the function is exponential in $w$, therefore it is $O(2^w)$.

If $K$ is variable and $w$ is constant then $0.24\times K\times 2^w$ is $O(K)$ - linear in $K$.

If both $K$  and $w$ are variables then $0.24\times K\times 2^w$ is $O(K2^w)$.

If both $K$  and $w$ are constant then $0.24\times K\times 2^w$ is $O(1)$.

The constant $0.24$ is ignored since it becomes irrelevant when we compare the rate of growth of a function. For more details please see Big-O notation.

We also use $O^*(f(n))$ notation, in particular in analysis of parametrized algorithms, which means that the algorithm runs in
$O(f(n)p(k))$ for some polynomial $p(k)$. So you could also write it is $O^*(2^w)$ in case $w$ is variable.


What are the state-of-the-art algorithms for pathfinding on a continuous map of the Earth?

The deterministic requirement isn't all that constraining. That just implies your vehicle is certain of the state it's in. That being said, you'll probably want to plan paths in a way that allows you to avoid obstacles. The best way I've seen this done is with sampling-based planners. Steven LaValle wrote the central academic resource on this topic: Planning Algorithms.

The RRT* algorithm is among the planners he describes. This algorithm generates the state space tree with random samples and a few heuristics to ensure feasibility (e.g. obstacle avoidance) and optimality. Details on RRT* can be found in LaValle's book, or at Sertac Karaman's website. The asymptotic time and memory characteristics are described as O(nlogn) to process, and O(n) for queries. The algorithm is linear, O(n), in space complexity too.


Does NP-completeness require to find the solution?

You are right that NP-completeness applies only to decision problems. What they mean by "Problem 2.1 is NP-complete" can be either

  The decision problem corresponding to Problem 2.1 is NP-complete

or

  The decision problem corresponding to Problem 2.1 is NP-complete, and the search problem is in FNP

Here the search problem is finding a clique of size $k$ if one exists. We think of the search problem as a two-place predicate $f(\langle G,k \rangle,K)$ which is true if $G$ is a graph and $K$ is a $k$-clique of $G$. This search problem is in FNP if the predicate $f$ is in P. (Usually FNP is defined for functions, i.e. for relations which are functions, but you can also define it for general relations.)


What exactly is the reason for rule P1?

The paper says:

  We use the customary asynchronous, non-Byzantine model...

In other words, it assumes that everything can take an arbitrarily long time to happen, but no messages are corrupted in transit and all agents obey the protocol.

What this means is that it would be perfectly fine to write the timeout-based rule as you describe, but it would be harder to describe and analyse and yet it would not satisfy any different properties from a protocol that has no timeouts: the asynchronous model already allows for arbitrary delays and message-reordering, so adding any further delays and message-reordering doesn't gain anything.

  What does "P1a subsumes P1" mean?

It means it replaces P1. The sentence after P1 starts ...

  But this requirement raises a problem.

... which means that P1 isn't the correct requirement. The correct requirement is in fact P1a.


Why do I have to make it as an NFA instead of making an DFA...

You don't have to, but making an NFA allows you to use $\epsilon$ transitions, which are convenient for making your procedure.

Can i kill the state q3...

Sure, but it wouldn't be useful for your proof.  Dead states don't hurt anything, and it would be harder to write this step into your procedure.

Why the first state of the NFA transitions with ϵ?

Because the FMS you are working from may have had multiple final states, so you need a way to encode multiple potential starting points.  Using $\epsilon$ transitions gives you a choice of multiple states.

What you're trying to do is make a procedural proof.  In essence, you're trying to show that for every FSM $A$, you can follow some formula to construct a FSM that also accepts $A^R$.  If you can always construct a Finite State Machine for $A^R$, then $A^R$ must be Regular.

The machine that results from your process doesn't have to be the most efficient machine or contain the minimum possible number of states.  This isn't a work of art, it's a proof of concept: if you can always make an appropriate reversal machine, then your reversal must always be regular. All it must do is work every time to accomplish your proof.


Easy instances of the coloring problem on graphs with degree at most 4

You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".

But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.


How to prove that $\{\$x\$\}$ is a regular language if $x$ is derived from $L=\{w\}$ by substituting substrings?

Unfortunately, your argument breaks down at step 2). For example, let $L=\{01\}$. Then
$G =\{\$\$\$\$\}.$
$H=\{\$01\$\}$.
$h^{-1}(H)=\emptyset$ since every word in the range of $h$ contains neither 0 or 1.
$h^{-1}(H)\cap \$(\Sigma^*\$\$\Sigma^*)^+\$=\emptyset.$
However, $G$ is not empty.

  If I managed to think of a regular expression to describe G then would this alone have proved that G is regular?

Of course. However, it looks like it is not immediate to figure out a regular expression for $G$ even if we have been given the regular expression for $L$ and DFA for $L$.

Here is a way to show $G$ is regular by DFA.

Let the DFA for $L$ be $(\Sigma,Q, q_0,\delta_L, F)$.

Define (an incomplete) DFA $D$ with alphabet $\{0,1,2,\$\}$, states $Q\times \{s_0, s_1, o\}$, initial state $(q_0, s_0)$, accepting state $F\times\{s_0, o\}$, transition function $\delta_D$ such that
$\delta_D((q, s_0), 0)= (\delta_L(q, 0), o) $
$\delta_D((q, s_0), 1)= (\delta_L(q, 1), s_0) $
$\delta_D((q, s_0), 2)= (\delta_L(q, 2), s_0) $
$\delta_D((q, s_0), \$)= (\delta_L(q, 0), s_1) $

$\delta_D((q, s_1), \$)= (\delta_L(q, 1), s_0) $

$\delta_d((q, o), 0)= \delta_L(q, 0), o) $
$\delta_d((q, o), 2)= \delta_L(q, 2), s_0) $
$\delta_d((q, o), \$)= \delta_L(q, 1), s_1) $

Here is how we can understand the states

state $(q,o)$ corresponds to the states that are reached by words that end with $0$.
state $(q,s_1)$ corresponds to the states that are reached by words that end with odd number of $\$$'s.
state $(q,s_0)$ corresponds to the states that are reached by words that end with $1$ or $2$ or even number of $\$$'s.

We can check that $G=\$L(D)\$$.

Exercise. Prove that if $L$ is regular over $\Sigma=\{0,1\}$ then the following language over $\{0,1,2\}$ is also regular.
$$
G=\{x\mid \exists w\in L: x\text{ is derived from }w\text{ by substituting } 00 \text{ and } 11 \text{ with } 2 \text{ from left to right} \}$$
For example, if $w=1000111110$, then $x=1202210$.


Which combinations of pre-, post- and in-order sequentialisation are unique?

First, I'll assume that all elements are distinct. No amount of sequentialisations is going to tell you the shape of a tree with elements [3,3,3,3,3]. It is possible to reconstruct some trees with duplicate elements, of course; I don't know what nice sufficient conditions exist.

Continuing on the negative results, you can't fully rebuild a binary tree from its pre-order and post-order sequentializations alone. [1,2] preorder, [2,1] post-order has to have 1 at the root, but 2 can be either the left child or the right child. If you don't care about this ambiguity, you can reconstruct the tree with the following algorithm:

Let $[x_1,\dots,x_n]$ be the pre-order traversal and $[y_n,\ldots,y_1]$ be the post-order traversal. We must have $x_1=y_1$, and this is the root of the tree.
$x_2$ is the leftmost child of the root, and $y_2$ is the rightmost child. If $x_2 = y_2$, the root node is unary; recurse over $[x_2,\ldots,x_n]$ and $[y_n,\ldots,y_2]$ to build the single subtree.
Otherwise, let $i$ and $j$ be the indices such that $x_2 = y_i$ and $y_2 = x_j$. $[x_2,\ldots,x_{j-1}]$ is the pre-order traversal of the left subtree, $[x_j,\ldots,x_n]$ that of the right subtree, and similarly for the post-order traversals. The left subtree has $j-2=n-i+1$ elements, and the right subtree has $i-2=n-j+1$ elements. Recurse once for each subtree.
By the way, this method generalizes to trees with arbitrary branching. With arbitrary branching, find out the extent of the left subtree and cut off its $j-2$ elements from both lists, then repeat to cut off the second subtree from the left, and so on.

As stated, the running time is $O(n^2)$ with $\Theta(n^2)$ worst case (in the case with two children, we search each list lineraly). You can turn that into $O(n\,\mathrm{lg}(n))$ if you preprocess the lists to build an $n\,\mathrm{lg}(n)$ finite map structure from element values to positions in the input lists. Also use an array or finite map to go from indices to values; stick to global indices, so that recursive calls will receive the whole maps and take a range as argument to know what to act on.

With the pre-order traversal $[x_1,\ldots,x_n]$ and the in-order traversal $[z_1,\ldots,z_n]$, you can rebuild the tree as follows:

The root is the head of the pre-order traversal $x_1$.
Let $k$ be the index such that $z_k = x_1$. Then $[z_1,\ldots,z_{k-1}]$ is the in-order traversal of the left child and $[z_{k+1},\ldots,z_n]$ is the in-order traversal of the right child. Going by the number of elements, $[x_2,\ldots,x_k]$ is the pre-order traversal of the left child and $[x_{k+1},\ldots,x_n]$ that of the right child. Recurse to build the left and right subtrees.

Again, this algorithm is $O(n^2)$ as stated, and can be performed in $O(n\,\mathrm{lg}(n))$ if the list is preprocessed into a finite map from values to positions.

Post-order plus in-order is of course symmetric.


Examples of specialized instructions of assembly language not available in compilers?

Counting bits set, Brian Kernighan's way

unsigned int v; // count bits set (1)
unsigned int c; // result
for (c = 0; v; ++c)
{
  v &= v - 1;
}

This code becomes popcnt


How can I show that a problem is not $NP$

The only result that I am aware of (assuming your problem is computable) is the time hierarchy theorem, which implies that $NP\neq NEXPTIME$. If you have a problem that is $NEXPTIME$-hard and show that that problem reduces to your problem, you've shown your problem isn't in $NP$. Since $NEXPTIME\subseteq EXPSPACE$, an $EXPSPACE$-hard problem would work as well.

Your problem is in $NP$, however.


Alright, I think I've figured it out. It can be seen in working with the transition function Δ : Q × Σ → P(Q), where Q is the set of states and Σ is the alphabet.

First, lets define some unary functions (P is powerset, of course):

∪ : P(S) -> S, ∪(X) = X1 ∪ X2 ∪ ... Xk where k = |X| (classic NFA)
∩ : P(S) -> S, ∩(X) = X1 ∩ X2 ∩ ... Xk where k = |X|
⊕ : P(S) -> S, ⊕(X) = X1 ⊕ X2 ⊕ ... Xk where k = |X| (symmetric difference NFA)

So basically, take a set of sets, and either and, or, or xor them all together.

Now, we extend the domain of our transition function to Δ : Q × Σ* → P(Q), where Σ* is a string of Σ, via the following recursive definition:

Δ(s, e) = s, where e is the empty string
Δ(s, xa) = ⋆({ s' ∈ Δ(s, x) | Δ(s', a) })

Where ⋆ can be any one of the three unary operators we defined above (and as specified in the second link in the original question, can be any associative and commutative operator on sets, converted into a combining unary function like above). The ⋆-NFA is the generalized NFA, so ⋆ is basically a wild card.

This is most intuitively understood in how an NFA is converted to a DFA by the subset construct. With a ∪-NFA, when you're creating your DFA states, you are taking the union of each result of the transition function from all the previous NFA states. With the other operators, its the intersection or symmetric difference of those states, respectively. If you take another look at that first link that I put in the original question, with this information in mind, it makes a pretty good example that should be relatively easy to understand. It seems this was the original intent of the slides, but without accompanying lecture it was a bit difficult to follow. I guess that about covers it.


Notations around the polynomial hierarchy

$\newcommand{\P}{\mathsf{P}}\newcommand{\PH}{\mathsf{PH}}$
$\newcommand{\SUM}[1]{\Sigma_{#1}^{\P}}\newcommand{\PROD}[1]{\Pi_{#1}^{\P}}$
$\newcommand{\DELTA}[1]{\Delta_{#1}^{\P}}$
$\newcommand{\NP}{\mathsf{NP}}\newcommand{\coNP}{\mathsf{coNP}}$
From the comments:

  Why is $\SUM{1} = \NP$?

Recall the definition of $\NP$ using certificates/proofs:

  A language $L$ is in $\NP$ if there exists a poly-time TM $M$ and a polynomial $q$ such that $$x \in L \iff \exists u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$

This is also exactly the definition for $\SUM{1}$. In the case of $\NP$ it is a single existential ($\exists$) quantifier. Now, the negation of existential quantifier is the universal quantifier ($\forall$). If we swap out the quantifiers in the certificate definition of $\NP$ we have $$x \in L \iff \forall u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$ which is exactly $\coNP$ (and denoted in the hierarchy as $\PROD{1}$)! We see that $\PH$ is just a generalization of this, by allowing more (alternating) quantifiers.

For the first bullet:

  $\bigcup_{i}(\SUM{i} \cup \PROD{i} \cup \DELTA{i}) = \bigcup_{i}\SUM{i} = \bigcup_{i}\PROD{i} = \bigcup_{i}\DELTA{i}$

Sketch: It is straightforward to show that $\SUM{i} \subseteq \PROD{i+1} \subseteq \SUM{i+2}$. The reasoning is that you can simply "ignore" the leading quantifiers in the verifying TM. Likewise, we see $\SUM{i} \subseteq \DELTA{i+1} \subseteq \SUM{i+1}$. Again, this can be explained due to the fact that both $\DELTA{i+1}$ and $\SUM{i+1}$ have oracle access to $\SUM{i}$ with the difference being that $\SUM{i+1}$ is an $\NP$-based machine whereas $\DELTA{i+1}$ is a $\P$-based machine.

With the subset relation in-hand, we see that a union over all integers will cover all cases.

Now for your second bullet:

  $\forall k \in \mathbb{N}\ \  \SUM{k} = \PROD{k} \Rightarrow \PH = \SUM{k}$

Proof: This can be shown by induction on $k$. For our base case let $k = 1$ and observe that if $\SUM{1} = \PROD{1}$ then a collapse occurs. To see this, let $Q_1, \cdots, Q_i$ be the alternating quantifiers for some level $i$ in the hierarchy. Since $\SUM{1} = \PROD{1}$, we can replace each universal quantifier in the sequence with an existential quantifier resulting in $\exists u_1, \cdots, \exists u_i$. But by definition of the quantifiers, we can reduce this to a single $\exists \langle u_1, \cdots, u_i \rangle$ which is exactly $\SUM{1}$.

Now assume this holds for all values less than $k$. Given level $\SUM{k}$ we can decompose its quantifiers into two parts, the initial $\exists u_1$ and the following alternating sequence $\forall u_2, \cdots, Q_{k} u_{k}$, where $Q_{k}$ is either $\exists$ or $\forall$ depending on whether $k$ is odd or even. Observe this sequence is exactly $\PROD{k-1}$ which by our hypothesis is equal to $\SUM{k-1}$. By substituting and combining the initial term we have $$\exists \langle u_1, u_2 \rangle, \cdots, Q_{k} u_{k}$$ which is really only $k-1$ terms! Therefore a collapse occurs.


The difference between dynamic logic and temporal logic

OK, dynamic logic adds assertions that specify what modal situation should exist following an action, however way this action is specified. In temporal logic the modal aspect is not emphasized. For example, if we consider dynamic alethic logic, the alethic bit would be missing from temporal logic. I hope this helps.


Why does Locality Sensitive Hashing use multiple sets of hash tables? How does it guarantee similarity?

LSH indexing first concatenates $k$ simple hash functions $h$ to produce a function $g$. Note that $g$ is a regular LSH function, only with slightly different parameters. In particular, probabilities of collision decrease for both near and far objects. The new probabilities are $p'=p^k$.

Then they take $L$ such functions $g$ and produce $L$ hash tables. Then we search through all the hash tables, one by one. This effectively increases the probability of collision. The new probabilities are $p''=1-(1-p^k)^L$. Note that this function has a sigmoid shape.

It may seem weird to first reduce $p$ and then increase it. However, the parameters $k, L$ are useful knobs for controlling the behavior of the algorithm. You could certainly run with $k=L=1$, but larger values may perform better.


Difference between page table and inverted page table

An inverted page table is just a hash map.  An inverted page table always fits in DRAM because it is proportional in size to the DRAM.

A DRAM total space is divided into $N$ page frames. If the size of a page frame is 4096 bytes, then the DRAM is of size 4096 $N$ bytes.
Assuming that an inverted page table entry is 16 bytes, and considering that there is an entry for each physical memory frame, then the page table is of size 16 $N$. This corresponds to 16/4096 = 1/256 $\approx$ 0.4% of the memory.

Your picture of the inverted page table is not correct.  Here is the picture from the original paper about inverted page tables (Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993. doi:10.1145/165123.165128.)

It's a hash table.  Each entry of the hash table needs to store both a virtual address and a physical address.  The virtual address is there to check for hash conflicts.

The reason you can guarantee the total number of entries for the HPT (hash page table) plus the collision resolution table is just $N$ (the number of physical pages), is that there can be only one entry in the tables for each physical page.


Turing Machine that triples a unary format number?

Copy the number once (as you have done already). Mark the spot between the original and the copy with a new letter. Now run again the copy, but stop copying once you see the letter $\land$.
That is, copy $\land 111\land$ into $\land 111 \#  111 \land $. Now copy again, while thinking of $\#$ as the new beginning of the tape. You will get $\land 111 \# 111 \# 111 \land$. After that, replace all $\#$ with $\land$ to get: $\land 111\land 111\land 111\land$
Notice that this process can be done any number of times, meaning that you can clone the input any number of times you would like!

Also, as a general "trick" for such problems, try introducing either a new letter to the alphabet (it usually helps create edge cases that you need to solve), or to meddle with an existing machine's states (such as adding an index into their states, etc')


Intersections of some context-free languages

Notice that $L_3 = \Sigma^*$, since you can always choose $y=\epsilon$ (the empty string is a substring of any string) and then choose $x$ from $\Sigma^*$. $L_1$ is also $\Sigma^*$, since $L$ is always a subset of $L^*$ and we're basically saying $L_1 = (\Sigma^*)^*$. These observations imply the following: the answers to #2, #3 and #4 are "yes" (indeed, there's a DFA with one state accepting each of these, which are all $\Sigma^*$)... and the intersection in #1 is simply $L_2$, so the question is really "is $L_2$ context-free?"

Please also note that we have other questions on the site about proving and disproving that languages are context-free.

To clarify:

$L_2 \cap L_3 = L_2 \cap \Sigma^* = L_2$
$L_2 \cup L_3 = L_2 \cup \Sigma^* = \Sigma^*$
$L_1 \cap L_3 = \Sigma^* \cap \Sigma^* = \Sigma^*$
$L_1 \cup L_2 = \Sigma^* \cup L_2 = \Sigma^*$

As for $L_2$:

First note that I'm assuming $(\Sigma + \Sigma)^*$ is a funny way of writing $\Sigma^*$. Plus usually stands in for union when dealing with regular expressions, and I'm guessing that's the intention here as well, though it would be well to confirm this.

Assume $L_2$ were context free. By the pumping lemma for context-free languages, we could write any word $w \in L_2$ of length at least $p$ as $uvxyz$ where $|vxy| \leq p$, $|vy| > 0$ such that $uv^kxy^kz \in L$ for all $k \geq 0$. Consider the word $(0^p1^p)(1^p0^p)(0^p1^p)(1^p0^p)\in L_2$ (parentheses added for clarity). We consider cases for the assignment of $vxy$:

$vxy$ consists entirely of $0$s from the first (parenthesized) part of the string. Pumping will change the number of $0$s without changing the number of $1$s in the first part, leading to a string that can't possibly be in the language.
$vxy$ consists of a mix of $0$s and $1$s from the first (parenthesized) part of the string. Pumping will change the numbers of $0$s and $1$s in the first part without affecting the other parts, leading to a string that cannot be in the language.
$vxy$ consists of a $1$s from the first (parenthesized) part only. See argument in point 1 above.
$vxy$ consists of $1$s from the first part and $0$s from the second. See arguments above.

etc. There are 15 cases in total, but the arguments are all basically the same: you always get some parts out of sync (the $p$s won't match). This means that the language is not context-free.


Are there other interpretations of |G| than |V|, that is |V(G)|?

I don't have the book, so I looked through the pages available on Google Scholar. It seems that they use $|G|$ to denote the size of a graph description that is $|V(G)| + |E(G)|$.

For example on page 24 they say that Vertex Cover is solvable in $2^k|G|$ time using bounded search tree method. In fact this method gives $2^kk|V|$ time for graphs with at most $k(|V| - 1)$ edges (it's easy to show that otherwise graph doesn't have Vertex Cover of size $k$). According to this "reverse engineering" $|G|$ corresponds to $k|V|$ that is essentially $|V| + |E|$.


Why does this graph show the tightness of MST heuristic's 2-approximation bound?

There is a lot of freedom in the algorithm: several minimum spanning trees, and several corresponding Eulerian tours. Try to find the worst choice and show that it produces an inferior tour. What you are showing is that the algorithm could make this choice, and so could produce an inferior approximation.

If you don't like this idea of choice, you can sometimes guarantee that the algorithm makes the choices you want by slightly tweaking the weights.


Define $f(s)=h(g(s))$, where $g(\cdot)$ is the conversion to octal and then interpreting the result as a decimal string, and $h(\cdot)$ is the conversion to hexidecimal and then interpreting the result as a decimal string (if possible).  For instance, $g(245)=365$, and $h(365)=163$.

Asymptotically, it is easy to see that $g(x) \sim x^\alpha$, where $\alpha = \log_8 10 = 1.1073\dots$.  In other words, once $x$ is large enough, $g(x)$ is asymptotically proportional to $x^{\alpha}$.  (Why?   Consider $x=8^k$, or $x=a \cdot 8^k$ where $a \in \{1,2,\dots,7\}$.  Once $x$ is large enough, the lower-order terms in the base-8 representation of $x$ become negligible, asymptotically.)  Similarly, asymptotically we have $h(y) \sim y^\beta$, where $\beta = \log_{16} 10 = 0.83048\dots$.

It follows that asymptotically

$$f(s) \sim s^{\alpha \beta}.$$

Notice that $\alpha \beta = 0.9196\dots$, and in particular $\alpha \beta < 1$.  Therefore, asymptotically, $f(s)$ grows more slowly than $s$.

It follows that there is a constant $c$ such that, for all $s>c$, we have $f(s)<s$.  From this it is easy to see that we only need to check finitely many  possible values of $s$: the values $s=1,2,\dots,c$.

All that remains is to determine the constant $c$ explicitly.  This can be done with a bit of algebra; it gets a bit messy, and I don't know of any elegant way to derive it.  But hopefully the above is a relatively clean way to show why your approach has to work, and isolates the messy part to a well-contained calculation.  To me, this is much nicer, because it provides some pretty simple intuition about why there can be only finitely many fixed points.

In other words, this all follows as a consequence of the fact that

$$(\log_8 10) \times (\log_{16} 10) < 1.$$


What is Pumping length for Union of Regular languages?

A pumping length is a positive integer $p$ such that any string of $L$ of length at least $p$ can be decomposed in the form $xyz$ with $|xy|\leq p$, $|y|>0$ and for all $n\geq0$ the words $xy^nz$ are in $L$.
Assume that $p<12$. Then the word $b^{10+12}$ should be able to be decomposed as above. We cannot take $y$ with $1\leq|y|\leq p <12$. Otherwise $xz=xy^0z$ wouldn't be in $L$.
We can take $p=12$ or larger.
If $10+12k=|b^{10+12k}|\geq p\geq 12$ then $k\geq1$ and we can decompose $b^{10+12k}$ as $xyz$, with $x=\epsilon$, $y=b^{12}$ and $z=b^{10+12(k-1)}$. Then $|xy|=12\leq p$ and for all $n\geq0$ we have $xy^nz=b^0b^{12n}b^{10+12(k-1)}=b^{10+12(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$
If $2+3k=|a^{2+3k}|\geq p\geq 12$, then $k\geq4$. We can decompose $a^{2+3k}$ as $xyz$ with $x=\epsilon$, $y=a^3$ and $z=a^{2+3(k-1)}$. We have that $|xy|=3\leq p=12$, $|y|=3\geq1$ and for all $n\geq0$ we have $xy^nz=a^0a^{3n}a^{2+3(k-1)}=a^{2+3(n+k-1)}$ in $L$, since $n+k-1\geq k-1\geq0$.
So, the minimum pumping length of $L$ seems to be $12$. Any larger value would also work in this case.


Using a combination of spatial and non-spatial inputs for convolutional neural networks

Yes.  One way is to start with several convolutional layers, and then end with one or two fully connected layers.  You can add the other features as inputs to the first of those fully connected layers.  This is basically serial composition of convolutional layers then fully connected layers.

There are other options for network architectures, but that'd be a reasonable one to try first.  The choice of architecture is an art and depends partly on how you think one might learn from the features, and how the value of one feature might affect the kinds of things you'd like for in other features.  The architecture I suggest above would be good if we pretty much want to look for the same kinds of information about the pixel input, regardless of the value of health, ammo, etc.  If you think the health, ammo, etc. would dramatically influence what kinds of information we'd want the network to extract from the pixel input, one might consider other network architectures.


NP-complete and polynomial time reduction

If there is no resource bound for the reduction and you want to reduce problem A to problem B then there is a trivial "reduction" algorithm for any computable A - simply compute the answer for problem A.


How would you prove a family of functions is universal?

A good approach is to simultaneously try to prove it, and try to disprove it.

To try to prove it: look at what the definition says, plug in the definition of the hash function, and see what number-theoretic fact needs to be true.  Can you find any proof for this number-theoretic fact?

To try to disprove it: look for a counterexample.  When looking for a counterexample, I suggest starting with the smallest parameters you can, to make manual calculations tractable.  In this case, you might start with prime $p=3$ and number $n=2$; I think that is the smallest possible parameter setting that meets your requirement.  Now, calculate the probabilities explicitly and see if it meets the definition.  (The numbers are so small you should be able to calculate that explicitly by just enumerating all cases.)  What do you get?

If you try this, I think you'll be able to answer your own question.  If you're still stuck, edit the question to show what you tried along each of these two directions and where you got stuck.


Understanding Bellman-Ford and Floyd-Warshall Algorithms as Dynamic Programming Algorithms

Floyd–Warshall algorithm

You can prove inductively that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that passes through the vertices $1,\ldots,k$. How does it do that? When $k = 0$, you can read this off the adjacency matrix. For larger $k$, there are two possibilities:

The shortest path from $i$ to $j$ through $1,\ldots,k$ doesn't use $k$. In this case it equals the shortest path from $i$ to $j$ through $1,\ldots,k-1$.
The shortest path does use $k$. In this case you can break it up to two parts: a part from $i$ to $k$, and a part from $k$ to $j$. In both parts, the path only goes through $1,\ldots,k-1$.

You can therefore compute the shortest past from $i$ to $j$ through $1,\ldots,k$ using shortest paths that go through $1,\ldots,k-1$. Taking $k = n$, we obtain the unrestricted shortest paths.

Bellman–Ford algorithm

Let us consider first a parallel version of the Bellman–Ford algorithm which updates all weights simultaneously. In this case, you can show that on the $k$th iteration, the algorithm computes, for each pair of vertices $i,j$, the shortest path between $i$ and $j$ that is of length at most $k$. When $k = 1$, this is easy. For larger $k$, there are two possibilities:

The shortest path of length at most $k$ actually has length at most $k-1$.
The shortest path of length at most $k$ has length exactly $k$. Let $v$ be the penultimate vertex in one such path. Then the length of shortest path from $i$ to $j$ of length at most $k$ is the length of the shortest path from $i$ to $v$ of length at most $k-1$, plus the length of the edge from $v$ to $j$.

Once again, this can be computed by induction on $k$. Taking $k = n-1$, we obtain the unrestricted shortest paths (assuming no negative cycles).

The usual algorithm, which is sequential, is a bit different, but you can show that it is at least as good as the parallel algorithm.


Can I say ≤ O(f(x)) rather than = O(f(x)) if the bound is not tight?

Technically in my paper I should say “runtime $=O(n^2)$”, but it’s somewhat misleading because people think I mean it's a tight bound

No, technically you should write "runtime $\in O(n^2)$".

  I am considering saying “runtime $≤ O(n^2)$”, even though it's technically redundant

I don't think "redundant" is the right word. In a way, it makes even less sense than "$= O(\_)$"

While you can not control your readers' misconceptions, you can try not to feed them. Why not make explicit what you mean?

  The running time is bounded by $O(n^2)$ but we suspect this bound can be improved to match the lower bound $\Omega(n \log n)$.

Or:

  We have thus shown that the running time is in $\Omega(n \log n) \cap O(n^2)$.

In formulae, my advice is to always use "$\in$" unless you can give more precise results. For instance,

$\qquad C(n) = 2n\log n - n \pm O(\log n)$

would be okay.


You are asking two different questions. First, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free grammar? Second, is $\{a^nb^nc^n : n \geq 1 \}$ a context-free language?

The answer to the first question is No, since $\{a^nb^nc^n : n \geq 1 \}$ is not a grammar, let alone a context-free grammar; it is a language. What you probably meant to ask was: "Does $\{a^nb^nc^n : n \geq 1 \}$ have a context-free grammar?", which is the same as the second question.

The answer to the second question is also No. In fact, it is one of the standard examples of non-context-free languages, and as such most textbooks will have proofs to that effect.


Difference between Normative annexes and Informative annexes in ADA 95

"Normative" means something that has to be followed, part of the standard. "Informative" is explanations meant to be understood by mere human beings, and that might be ambiguous or inaccurate. It is not to be relied on. Read it to understand, refer to the normative parts where it matters.


How to generate uniformly random binary trees?

There is a article available here and survey available here

But desipte that its very easy to generate such tree, it all depends on random generator, it must be uniform.

There are two simple approaches:

Generate full tree up to some height and randomly cut edges
Start from root and make decision about each child on lower level

Both of them are guarantee to end, fist one is obvious, second one needs some induction proof which is quite simple to do.

Taking into account Juho's hint take a look at Boltzmann sampling, it is indeed a powerfull tool which you can use. And here's a working example.


when can i detect the position of error in hamming code

You can never detect the positions of errors with certainty.

You can make the assumption that there is at most a single bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in only one bit position; if there is exactly one such data then you know where the error is (under your assumption).

You can make the assumption that there is at most a double bit error. Under that assumption, if your code is not a valid code, you can find all different data where the hamming code differs from your code in at most two bit positions; if there is exactly one such data then you know where the error or errors are (under your assumption).


Randomized quicksort expected running time analysis

Let us denote by $p(n,i,j)$ the probability that $X_{ij} = 1$ given that there are $n$ elements.

Let $k$ be the first chosen pivot. If $k \in \{i,j\}$ then $X_{ij} = 1$. If $i < k < j$, then $X_{ij} = 0$. Otherwise, if $k < i$ then $X_{ij} = 1$ with probability $p(n-k, i-k, j-k)$, and if $k > j$ then $X_{ij} = 1$ with probability $p(k-1, i, j)$. Altogether, we get
$$
p(n,i,j) = \frac{2}{n} + \frac{1}{n} \sum_{k=1}^{i-1} p(n-k, i-k, j-k) + \frac{1}{n} \sum_{k=j+1}^n p(k-1,i,j).
$$
We can now prove that $p(n,i,j) = 2/(j-i+1)$ by induction, by noticing that
$$
\frac{2}{n} + \frac{2}{n} \cdot \frac{i-1}{j-i+1} + \frac{2}{n} \cdot \frac{n-j}{j-i+1} = \\
\frac{2}{n} + \frac{2}{n} \cdot \frac{n-(j-i+1)}{j-i+1} = \\
\frac{2}{n} + \frac{2}{j-i+1} - \frac{2}{n} = \\
\frac{2}{j-i+1}.
$$
Another way to get this result is to follow the algorithm until the first time when a pivot (at any level of recursion) in $\{i,\ldots,j\}$ gets selected. Elements $i$ and $j$ are compared if and only if this pivot happens to be $i$ or $j$, which happens with probability $2/(j-i+1)$.


Here a simple answer is;

Arrays

allow fast random access in $\mathcal{O}(1)$ to their elements since and they are sequential in memory.
$\mathcal{O}(1)$ time write or update an element
if not created in heap memory size is very limited.
The size is fixed.

Vectors

Access and write is similar to array
The size not fixed. When capacity is full, extended.


How are image processing and computer vision related to artificial intelligence.?

The answer is simple.

Assume you are making a robot for interacting with other people. The first thing that it needs is to recognize people who it sees.

Another application is in self-driving cars. If the car is not able to see the road and read the signs or break when it sees a dangerous obstacle ahead, how could it drive in a safe way?

There are a lot of smart agents who need to see an recognize a scene or a person and many other applications; this is where computer vision and image processing come handy. One of the best techniques that is used in Computer Vision is machine learning which is one of the cutting-edge methods in AI.


How to prove that the complement of a regular language is always regular?

If a language is indeed regular that means there is an FA that accepts it. The complement of L is just the language of all words that are not in L.

Thanks to Rick Decker for mentioning in the comments that this only works for FAs that are deterministic and to D.W for correcting the answer.

Now, a trick we can perform to test that the complement of L, namely L', is actually regular is to take the FA that accepts L and reverse all final states to non-final states and all non-final states to final states. Note that start states in the old FA become start and final states in the new FA.

This new FA will then accept all words present in L' which are words not in L.

In conclusion, take the FA accepting L and then form a new FA by:

Changing all final states to non-final states
Changing all non-final states to final states

The new FA accepts all words not in L, which is the language L'.


Is every edge of a graph included in some spanning tree?

Note that the initial graph $G$ needs to be connected or it has no spanning trees at all.  (Though the same argument applied to each component would show that any graph has a spanning forest containing any chosen edge.)

Let $G=(V,E)$ be a connected graph, let $T$ be any spanning subtree and let $e$ be any edgein $E$. We claim that there is a spanning tree that includes $e$. If $e\in T$, we are done. Otherwise, $T+e$ contains a cycle. That cycle necessarily contains at least one edge $e'\neq e$ (actually, it contains at least two). $T+e-e'$ is a spanning tree that contains $e$.

You should prove to yourself that $T+e-e'$ really is a spanning tree.


Binary Equivalent vs. Computer code(Ascii or UTF)

I am not an expert in the field, but I can try to give an approximately correct answer.

Reading from memory itself, you can not diferentiate between lets say ints and characters.
The compiled program is compiled with locations of where to find the operator that is needed, in this case print for ints and for chars. You must specify how to represent that data in your print command.

Example in c:

printf("ASCII value = %d, Character = %c\n", ch , ch );

This code will first represent data at location ch as a number and than as a char.

Let me give another example:
Let us say that your language can "add" strings, in form of concatenating one onto another. How can computer know which "add" to use, if you cannot learn of data type from memory? The compiler compiled the program with address to the appropriate "add" command, according to data type you specified your operands to be.

Moral of the story: you cannot learn of data type from memory.
Hopefully this clears it out.


Radix sorts are often, in practice, the fastest and most useful sorts on parallel machines.

Zagha and Blelloch: Radix sort for vector multiprocessors. Supercomputing, 1991: 712-721.
Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha: A Comparison of Sorting Algorithms for the Connection Machine CM-2. Symp Parallel Algorithms and Arch (SPAA-3):3-16, 1991.
Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson: High-performance sorting on networks of workstations. Conf on Mgt of Data, (SIGMOD-1997):243-254.
Arpaci-Dusseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson. Searching for the sorting record: experiences in tuning NOW-Sort. ACM Sigmetrics Symp Parallel and Distributed Tools, (SPDT-2):124-133, 1998.

On each node of the multiprocessor you probably do something like a quicksort, but radix sort allows multiple nodes to work together with less synchronization than the various recursive sorts.

There are other situations too.  If you need a stable sort (a sort where whenever two keys are equal they stay in the same order rather than getting rearranged) then I'm not aware of any version of quicksort that will be of use.  Mergesort is also stable (if implemented correctly).  Your link is the first time I've ever heard anyone say that mergesort could be made to have better cache behavior than radix sort.


Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference

Mathematics and computer science doesn't have anything to say about whether simpler hypotheses are more likely.  That's a question about reality, not about math / computer science.

What computer science can provide is the notion of Kolmogorov complexity.  Kolmogorov complexity is one reasonable notion of simplicity: bit-strings with lower Kolmogorov complexity are "simpler" in some sense.

Now we could start with a model of reality, which says that nature randomly picks a process for generating data; the process is obtained by picking a Turing machine at random, with smaller (simpler) Turing machines more likely to be chosen than complex ones; and then nature runs the Turing machine and the data you observe is the output of that Turing machine.  That's a sketch of a possible model of reality; basically, it's an assumption about how nature works.

That assumption then implies (if we fill in some details) a particular prior on hypotheses.  A hypothesis amounts to a Turing machine.  There will be multiple Turing machines that are all consistent with the observations (that could have produced those observations), and Bayes theorem + the prior will let you infer the posterior distribution on which of those hypotheses are most likely.

This is a possible way to obtain a prior, and it seems reasonable to me.  Computer science can't tell you whether that model (that assumption) is a good model of reality. But it can help you work out the consequences of making that assumption.

Finally, you seem to be asking why simpler explanations are more often correct.  Basically, why is Occam's razor useful?  I don't know if there is any completely convincing answer to that.

One possible answer is the empirical answer: it seems to work well in practice.  In other words, we often find in nature that very simple processes/models suffice to explain a wide range of natural observations.  See, e.g., the unreasonable effectiveness of mathematics.

There's lots more that one can say about Occam's razor.  See, e.g., https://en.wikipedia.org/wiki/Occam%27s_razor#Justifications and https://philosophy.stackexchange.com/questions/tagged/occams-razor?sort=votes.  I think that gets beyond the scope of this site.


The type of unordered pairs in a type $A$ is defined to be $$\sum_{(X:\mathcal{U})}\sum_{(H:\|X\simeq \mathsf{bool}\|)}A^X.$$ In other words, an undordered pair in $A$ is simply a map $X\to A$ from a type $X$ that merely has two elements.

Note that in general, this is not a set, because the type of 2-element types is not a set but a 1-type. The way to think about this is that unordered pairs have some symmetries (swapping the order of the elements in the unordered pairs) that should be taken into account in homotopy type theory.

Note that the type of unordered pairs can also be used to define the type of fully coherent commutative binary operations on a type $A$. This type is simply $$\Big(\sum_{(X:\mathcal{U})}\sum_{(H:\|X\simeq\mathsf{bool}\|)}A^X\Big)\to A.$$
In other words, a fully coherent commutative binary operation on $A$ is an operation on the unordered pairs of $A$.


Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

We don't have to merge two sorted arrays, if we can simply compute the median information and store it in an auxilliary array; by definition, a median of an array $A[l...r]$ is the element in $A[(l+r)/2]$ when $A$ is in sorted order. Given this definition, we can simply use mergesort-style divide and conquer, while keeping track of another array $A'$ with medians of subarrays of $A$; in the end, $A'$ will be the sorted version of $A$:
Procedure Median-Merge-Sort($A,l,r,A'$) {

If $r-l<2$ then manually update $A'[l...r]$ and return; $\leftarrow$ Basecase.
Let $m:=$Median($A,l,r$); $\leftarrow$ Compute a median in $O(\sqrt{n})$-time using the oracle.
Let $A'[(l+r)/2]:=m$;
Median-Merge-Sort($A,l,(l+r)/2,A'$);
Median-Merge-Sort($A,(l+r)/2+1,r,A'$);

}
The overall running time is $T(n)=2T(n/2)+O(\sqrt{n})$, which solves to $O(n)$ using master's theorem. This also tells us we cannot have a median-finder working in $O(\sqrt{n})$ on the comparison model, otherwise we can sort in linear time, which violates the sorting lower bound on the comparison model.


Difference between dynamic loading and dynamic linking in the OS

Let me explain these terms in the simplest way possible. Now since both the terms have the word dynamic in them, both occur during execution.

Dynamic Loading : Suppose our program that is to be executed consist of various modules. Of course its not wise to load all the modules into main memory together at once(in some cases it might not be even possible because of limited main memory). So basically what we do here is we load the main module first and then during execution we load some other module only when its required and the execution cannot proceed further without loading it.

Dynamic Linking : Suppose our program has some functions whose definition is present in some system library. We do know the header file only consists of declarations of functions and not definitions. So during execution when the function gets called we load that system library into main memory and link the function call inside our program with the function definition inside system library.


Are there any known implementations of a functional Heap's Algorithm?

I'm really not very familiar with clojure. I think this is probably the longest clojure program I've written so far. But I guess it provides some sort of answer.

On the whole, functional enumerations of permutations are going to suffer from the O(n) cost of creating a new permutation vector on each iteration. Pretty well all of the common imperative solutions make some attempt to avoid this cost, and many of them can produce amortised O(1) complexity (for a single permutation). Heap's algorithm is interesting in an imperative environment largely because it guarantees to perform a single swap on each iteration, which is clearly a minimal total number of mutations. That's particularly useful if the goal is to perform some sort of aggregate computation over the permutation which can be incrementally computed from the previous value and the modifications.

Heap's algorithm is not the only algorithm which performs just a single swap to produce the next permutation. The possibly even more famous bell-ringers' algorithm (often called the Steiner-Johnson-Trotter algorithm) produces sequences in which consecutive permutations differ only by a swap of two adjacent elements. This could be even more valuable for updating of aggregate computations, but it is more complicated to figure out which two adjacent elements to swap at each iteration. (Indeed, although tables of plain changes for up to seven bells were produced several centuries ago, the precise algorithm used to produce these table has not, as far as I know been recorded. However, the results line up with the algorithm proposed independently in the 1960s by the three mathematicians after whom it is named.)

The plain changes algorithm was motivated in part by the desire to keep the various bell ringers' attention on the changes; if a bell stays in the same position in the change for too long, its ringer may become bored and lose their place in the sequence. (In fact, current change ringing sequences try even harder to avoid leaving a bell in the same position for too long, so they no longer use the STJ algorithm.)

For many combinatorial problems, though, the opposite criterion is desired. For example, it may be useful to generate the permutations in lexicographic order, which means that the first item retains its value for (n-1)! iterations. Lexicographic ordering can still be performed in amortised O(1), and it involves O(1) mutations at each iteration, but the number of mutations may be as great as n-1 (or n, if the permutation sequence is circular, since the last permutation in lexicographical order is the reverse of the first one).

If the vector to be permuted may have repeated elements, and only unique permutations are desired, then lexicographic order is far and away the easiest solution. Furthermore, it is very easy to describe the next-permutation algorithm for lexicographic ordering:

Start with the vector sorted from left to right.
At each iteration:

Find the shortest suffix which is not monotonically non-increasing. (In other words, find the last element for which some subsequent element is greater.) If the entire vector is monotonically non-increasing, then it is the last permutation and the process is done.
Sort that suffix by shifting its first element to the right, and then reverse it. (This can be done by a modified reversal algorithm with k/2 swaps where k is the length of the suffix, but doing it in two steps is conceptually simpler.)

I think that algorithm would be quite simple to implement in functional style.

But let's get back to Heap's algorithm. Heap developed his algorithm in 1963, about the same time as Trotter and Johnson independently published the change ringing algorithm. (Steinhaus had published his version of the algorithm in 1958, but since he was writing in Polish it was relatively unknown until it was translated into English in 1963.) Heap's paper was a simple description of his algorithm, without formal proof, and it probably would have remained in the dusty archives of computer science had it not been rediscovered by Robert Sedgewick a decade later. In 1977, Sedgewick wrote a long survey on permutation algorithms, in which he devoted quite a bit of attention to Heap's algorithm, including producing an optimised implementation in a kind of virtual machine code. He concluded that for typical hardware architectures (in 1977), "Heap's method will run faster than any other known method."

A couple of years later, he presented a public lecture on permutation algorithms, during which he repeated this claim, and Heap's algorithm became the permutation algorithm of choice for programmers with a performance fetish. Unfortunately, the presentation slides (which are rather more easily found online than any of the other sources for Heap's algorithm) had a minor error in the algorithm pseudocode (not present in the 1977 paper, which presents a number of variant implementations, all impeccable). And because the presentation slides are rather more accessible than any of the academic references, that particular error has plagued implementations of Heap's algorithm ever since. Ironically, the error causes the algorithm to both run more slowly and to generate an incorrect sequence in which consecutive permutations sometimes do not differ by a single swap.

I have a certain affinity to Heap's algorithm because a few years ago, a question appeared on StackOverflow asking for help with that algorithm; the poster had carefully implemented the algorithm based on pseudocode in Wikipedia, and discovered that their code did not work as expected. In the course of reviewing the code, I soon realised that the poster's code was an entirely accurate implementation of the Wikipedia write-up, and in the course of trying to validate Wikipedia, I tracked down the history of the error which I summarised in the preceding paragraph. A Wikipedian noticed the answer and fixed the Wikipedia page. (Constant vigilance is necessary, however; every couple of months some aspiring computer science expert compares the  pseudocode on Wikipedia either with Sedgewick's buggy slide or with one of the many buggy implementations floating about the internet, and "corrects" the Wikipedia page.)

The beauty of Heap's algorithm is the simplicity of enumerating the swaps. The algorithm is similar to a lexicographic algorithm, in reverse, in that it always does a complete permutation cycle of a prefix of the elements before changing the next element. So the higher index of the swapped elements follows a kind of factorial variant on the ruler function, in which element i appears every i! iterations (except for the iterations which are multiples of a larger factorial). The lower index follows an only slightly more complex pattern: for prefixes with an odd number of elements, the lower index is always 0; for prefixes with an even number of elements, the lower index starts at 0 and is sequentially incremented. So, for example, in the case of a four element permutation sequence, the swaps are:

0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0
1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1 3 1 2 1 2 1

(Note that the element with index 3 appears as the larger index every 3! == 6 iterations, and the element with index 2 appears as the larger index every 2! == 2 iterations, except the ones which have already been taken by index 3.)

This sequence of pairs of indices is very easy to produce recursively, but one really wants it as a sequence. There is a non-recursive algorithm which effectively involves maintaining an explicit stack, but since the published algorithms tend to mutate this stack, I chose to use the recursive algorithm. In many Scheme's, one would use some kind of continuation to turn the recursive algorithm into a sequence, but since clojure doesn't have continuations (as far as I could see), I did it with nested calls to mapcat, the same approach as is taken by clojure's tree-seq standard library function.

Once you have the list of pairs of indices to swap, they can be repetitively (and lazily) applied to permutations by using reductions, which generates the result of successively applying a sequence of values to a seed value, using an arbitrary binary function. You can see that in the last line, where reductions is applied to the sequence generated by swaps using the swap-v function to turn each successive permutation into the next one.

I hope that's enough narrative to explain the (possibly non-idiomatic) clojure program which I came up with:

(letfn [(even-swaps [n]
            (if (= n 2) [[0 1]]
              (drop 1 (mapcat (fn [i] (cons [(- i 1) (- n 1)]
                                            (odd-swaps (- n 1))))
                              (range n)))))
          (odd-swaps [n]
            (drop 1 (mapcat (fn [i] (cons [0 (- n 1)]
                                          (even-swaps (- n 1))))
                            (range n))))
          (swaps [n]
            (cond
              (< n 2) '()
              (even? n) (even-swaps n)
              :else (odd-swaps n)))
          (swap-v [v [i j]] (assoc v i (v j) j (v i)))]
  (defn heap [sq]
    (let [v (vec sq)]
      (reductions swap-v v (swaps (count v))))))

Sample output:

user => (run! prn (heap '(a b c d)))

[a b c d]
[b a c d]
[c a b d]
[a c b d]
[b c a d]
[c b a d]
[d b a c]
[b d a c]
[a d b c]
[d a b c]
[b a d c]
[a b d c]
[a c d b]
[c a d b]
[d a c b]
[a d c b]
[c d a b]
[d c a b]
[d c b a]
[c d b a]
[b d c a]
[d b c a]
[c b d a]
[b c d a]


This is a nice question.

In the comparison model or, what is more general, the algebraic decision-tree model, the problem of element distinctness has a lower bound of $\Theta(n\log n)$ time-complexity in the worst case as said in this Wikipedia article. So there is no algorithm to count distinct elements in linear time in the worst case, even without counting the duplicities.

However, it is not clear whether it can be done in another computational model.  It seems unlikely in any reasonable deterministic computational model.


What NP decision problems are not self-reducible?

The paper indeed shows that planar graph four coloring is not self-reducible in the sense of Schnorr. There are several other senses, under some of which every problem in P is self-reducible. See the follow-up paper of Große, Rothe and Wechsung. I am not aware of any other result of this kind. Going over all papers citing the paper you mention (this can be done using Google Scholar, for example), none give any such problems.


Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?

You can reduce SAT to this version. Connect the source to nodes $x_1,\ldots,x_n$, one per variable, with infinite capacity. Connect each $x_i$ to two exclusive nodes $x_i^T,x_i^F$, with infinite capacity. Create one node per clause, and connect a literal to a clause (with infinite capacity) if the clause contains the literal. Finally, connect each clause to the sink with unit capacity. The maximum flow is the number of clauses iff the formula is satisfiable.


Is this grammar really LL(1) while not being LR(1)?

I've just consulted a parsing book, and it indeed requires that $S \Rightarrow^+ S$ be impossible, if $S$ is the starting symbol, before a grammar is considered $LR(k)$. As you said yourself, this is not required for a grammar to be $LL(k)$.

Usually, it is implicitly assumed grammars 'behave' when we make statements about them, such as $LL(k) \subset LR(k)$. For instance, $S \Rightarrow^+ S$, absence of symbols not derivable from $S$, and absence of symbols not deriving terminal strings are all properties of 'well behaved' context free grammars.

If we assume these things, we are spared some weird oddities of context-free grammars: for example, if we have some grammar with starting symbol $S$, by adding a nonterminal $T$ and productions $T \to \epsilon$, $S \to T S$, we can force the grammar to have infinitely many parse trees for every string in the language it represents. In contrast, if we do assume 'well behaved' grammars, we are guaranteed only finitely many parse trees exist for any input.


Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages

Just keep going. You've written what it means for $x$ to be in $A\cup B$. Now write out what it means for a string $y$ to be in $(A\cup B)\circ C$.  Do the same kind of thing on the right-hand side and relate the two statements you get.


Recognize end of Input in a Turing Machine

There are many possible input conventions for Turing machines. The one I know has the tape initialized by the input word (in case of a single input) surrounded by blanks, where a blank is a symbol of the tape alphabet that isn't in the input alphabet. The Turing machine treats all tape symbols in the same way, so you can do with them whatever you want.

Other conventions are also possible. For example, we might want to forbid writing blank for some reason. Only you know which convention is used in your class. The various input conventions are mostly equivalent, so in practice it usually doesn't matter which one is used.


n>1 means that minimum n value is 2.

(bb)^n means bb repeated n times, i.e. if n=2, then it's bbbb.

With n=2, it's "ba bbbbbb a" (I added spaces only for clarity).

With n=3, it's "ba bbbbbbbb aa" - as you see, teacher used n to regulate size of the first and the second repetition in sync.


A path of length $n$ consists of $n$ line segments in the plane.  You want to find all intersections between these line segments.  This is a standard problem that has been studied in depth in the computer graphics literature.

A simple algorithm is the following: for each pair of line segments, check whether they intersect (using a standard geometric algorithm).  The running time of this algorithm is $O(n^2)$.  In terms of worst-case complexity, this is the best we can hope for, as in the worst case, there can be $\Theta(n^2)$ intersections, so obviously it'll take at least $\Theta(n^2)$ time to output them all.

However, in many cases, we have an arrangement of line segments where there are only a few intersections, say at most $O(n)$ intersections.  In this case, there are algorithms whose running time is $O(n \lg n)$.  See, e.g., the sweep line technique; there are others as well.  In general, if there are $k$ intersections, the total running time for the sweep line algorithm to find all $k$ intersections is $O((n+k) \lg n)$ time.


What complexity class is the TSP problem?

It has been proven that TSP is $FP^{NP}$-complete but it remains an open question whether TSP is a function problem in $FNP$ (it probably is not). The reason is that, in the case of TSP, the optimal solution is not an adequate certificate, as we do not know how to verify in polynomial time that it is optimal.

You can see a proof that TSP is $FP^{NP}$-complete here, starting on page 418.

Note: I don't know if it's allowed to put the link to that PDF although it's from a university. You can buy the full book searching for Computational Complexity by Christos H. Papadimitriou.


In programming languages, generally we do not distinguish relations and functions. Is there a better way to deal with these two concepts?

Let $A$ be any set. Then, its powerset $\mathcal{P}(A)$ is isomorphic to the function space $A\to \mathbb{B}$ where $\mathbb{B}=\{\sf true, false\}$.

Indeed, the isomorphism is given by mapping each subset to its own characteristic function.

$$
\begin{array}{lcl}
\mathcal P A & \leftrightarrow & (A \to \mathbb B) \\
X & \mapsto & \lambda a. {\sf if}\ a\in X\ {\sf then\ true\ else\ false} \\
\{a|g(a)={\sf true}\} & \leftarrow\!\shortmid & g
\end{array}
$$

Since relations are sets of pairs, relations too can be seen as binary functions whose codomain is $\mathbb B$.

In most programming languages, as you realized, we don't really find propositions, sets, or relations, but we instead find their isomorphic counterparts: booleans, unary boolean functions, binary (or more) boolean functions.

This choice is mostly suggested by the fact that everything we compute ultimately is represented by a few bits. It is therefore very efficient for a computer to represent the truth values associated to propositions. Further, it is convenient to be able to write e.g. b = b or (y < 5) without using a conditional. (Actually, using a conditional for that usually reveals that the programmer does not understand that boolean expressions are indeed expressions, and not special syntax that is relegated to conditional or loop guards. This phenomenon also shows up in the infamous if b==true ... where the programmer often thought that we have to use at least one boolean operator in the guard, since we usually need that.)

In programming languages, there are some theoretical contexts where we do separate propositions from booleans, though. For instance, in the calculus of inductive constructions, as implemented in Coq, we find a Prop type for propositions, and a bool type for booleans. Very roughly, this allows the programmer to deal with propositions that can not be automatically checked by the computer, e.g. $\forall a,b,c\in\mathbb N.\ (a+b)\cdot c = a\cdot c + b\cdot c$
is a Prop. Even if the computer can not check them, we can still mathematically prove them. Note that we can not turn a Prop into its bool truth value since we have no way to check $\forall n$ or $\exists n$. (Actually, there's no such a thing as its "truth value" since the logic is constructive, but I'll be silent about this.) By comparison, we get two forms of n < 4 comparisons: one which is a Prop and can be used in logic, and another one which is a bool and can be used in programs.


Testing graph property on enumerated graphs

If you need to generate graphs, you can look at nauty: this is useful if you want to check whether a claim holds for all $n$-vertex graphs up to some small $n$. If you fancy planar graphs, you can have a look at plantri. I would not be surprised if you don't find tutorials, since this type of software is usually intended for professional researchers (but generally speaking, you should have little trouble in compiling and running if you are familiar with the typical Unix-like software).

To answer question 2, you can find online (via the nauty homepage, for instance) collections of small graphs with certain properties. House of Graphs is also pretty nice, but not exhaustive. If the properties you care about are exotic enough, you will have to come up with your own generator and/or just discard the graphs that don't satisfy your property from some collection of all small graphs.

To answer question 1, again, if you need efficiency, it will hard to beat something like nauty and its many utility programs. These are quite well-optimized and thoroughly used pieces of software. If you insist on more user friendliness at the expense of efficiency, I can recommend Mathematica. More generally, it is often the case you will have to write your own programs to strike the right balance between usability and efficiency.

There are also automated systems for suggesting conjectures, particularly in graph theory. One system I have successfully used is GraPHedron [1], but note that the system is currently unavailable. There are similar systems out there, and you should find pointers from [1] and the later papers that cite it.

[1] Mélot, Hadrien. "Facet defining inequalities among graph invariants: the system GraPHedron." Discrete Applied Mathematics 156.10 (2008): 1875-1891.


How to create DFA from regular expression without using NFA?

Since you want "to convert regex to DFA in less than 30 minutes", I suppose you are working by hand on relatively small examples.

In this case you can use Brzozowski's algorithm $[1]$, which computes directly the Nerode automaton of a language (which is known to be equal to its minimal deterministic automaton). It is based on a direct computation of the derivatives and it also works for extended regular expressions allowing intersection and complementation. The drawback of this algorithm is that it requires to check the equivalence of the expressions computed along the way, an expensive process. But in practice, and for small examples, it is very efficient.

Left quotients. Let $L$ be a language of $A^*$ and let $u$ be a word. Then
$$
u^{-1}L = \{v \in A^* \mid uv \in L \}
$$
The language $u^{-1}L$ is called a left quotient (or left derivative) of $L$.

Nerode automaton. The Nerode automaton of $L$ is the deterministic automaton $\mathcal{A}(L) = (Q, A, \cdot, L, F)$ where $Q = \{u^{-1}L \mid u \in A^*\}$, $F = \{u^{-1}L \mid u \in L\}$ and the transition function is defined, for each $a \in A$, by the formula
$$
  (u^{-1}L)\cdot a = a^{-1}(u^{-1}L)=(ua)^{-1}L
$$
Beware of this rather abstract definition. Each state of $\mathcal{A}$ is a left quotient of $L$ by a word, and hence is a language of $A^*$. The initial state is the language $L$, and the set of final states is the set of all left quotients of $L$ by a word of $L$.

Brzozowski's algorithm. Let $a, b$ be letters. One can compute the left quotients using the following formulas:
\begin{align*}
a^{-1}1 &= 0  & a^{-1}b &= \begin{cases}
 1 &\text{if $a = b$}\\
    0 &\text{if $a \not= b$}\\
\end{cases}\\
a^{-1}(L_1 \cup L_2)       &= a^{-1}L_1 \cup u^{-1}L_2,&
a^{-1}(L_1 \setminus  L_2) &= a^{-1}L_1 \setminus  u^{-1}L_2,\\
a^{-1}(L_1 \cap L_2)       &= a^{-1}L_1 \cap u^{-1}L_2,  &
a^{-1}L^* &= (a^{-1}L)L^*
\end{align*}
\begin{align*}
a^{-1}(L_1L_2)             &=
\begin{cases}
  (a^{-1}L_1)L_2                 &\text{si $1 \notin L_1$,}\\
    (a^{-1}L_1)L_2 \cup a^{-1}L_2  &\text{si $1 \in L_1$}\\
\end{cases}\\
%\\v^{-1}(u^{-1}L) &= (uv)^{-1}L.
\end{align*}

Example.
For $L = (a(ab)^*)^* \cup (ba)^*$, we get successively:
\begin{align*}
1^{-1}L &= L=L_1\\
a^{-1}L_1 &=(ab)^*(a(ab)^*)^*=L_2\\
b^{-1}L_1 &= a(ba)^*=L_3\\
a^{-1}L_2 &= b(ab)^*(a(ab)^*)^* \cup (ab)^*(a(ab)^*)^*=bL_2 \cup L_2=L_4\\
b^{-1}L_2 &=\emptyset \\
a^{-1}L_3 &=(ba)^*=L_5\\
b^{-1}L_3 &=\emptyset \\
a^{-1}L_4 &= a^{-1}(bL_2 \cup L_2)=a^{-1}L_2=L_4 \\
b^{-1}L_4 &= b^{-1}(bL_2 \cup L_2)= L_2\cup b^{-1}L_2 = L_2 \\
a^{-1}L_5 &= \emptyset\\
b^{-1}L_5 &=a(ba)^*=L_3
\end{align*}
which gives the following minimal automaton.

$[1]$ J. Brzozowski, Derivatives of Regular Expressions, J.ACM 11(4), 481–494, 1964.

Edit. (April 5, 2015) I just discovered that a similar question: What algorithms exist for construction a DFA that recognizes the language described by a given regex? was asked on cstheory. The answer partly addresses complexity issues.


Complexity of enumeration vs complexity of counting

Yes. An enumeration algorithm executes at least 1 step (an instruction, line of code, or whatever else your metric is) for every instance it finds, so there's at least as many steps as there are instances to count.
Just remember that if you use an asymptotic time complexity like $O(N)$, it doesn't tell you enough for an exact bound on the count. For example, it takes $O(N)$ time to enumerate $1,\dots,2N$.


How are problems classified in Complexity Theory?

That's what you get when you distill a whole bunch of theory to a wider audience.

In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.

The "scheme" Sipser is talking about are reductions. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$\le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us relative, not absolute notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).


How can I get all representations of an n-ary tree that completely "cover" the tree?

Let $T$ be a tree with root $r$, and let the children of $r$ be $r_1,\ldots,r_d$. Then every minimal cover of $T$ either consists of $r$, or is a union of minimal covers of $r_1,\ldots,r_d$; if $r$ is a leaf then the second option doesn't exist. You can easily convert this to a recursive algorithm that lists all minimal covers.


Gap between the average length of a Huffman code and its entropy

Shannon's source coding theorem shows that you cannot compress data more than its entropy, even if you encode chunks at a time. For the specific case of prefix-free codes (even uniquely-decodable codes), this follows from Kraft's inequality, which for a uniquely-decodable code with codeword lengths $\ell_i$ states that
$$ \sum_i 2^{-\ell_i} \leq 1, $$
and furthermore every code can be "improved" (by only decreasing its codeword lengths) so that equality holds.
Suppose that the probability of the $i$th symbol is $p_i$. The average codeword length is $E = \sum_i p_i \ell_i$.
We want to minimize $E$ given the constraint $\sum_i 2^{-\ell_i} = 1$, and furthermore $\ell_i \geq 0$ are integers. Relaxing integrality, we can find the optimum using Lagrange multipliers: it satisfies $p_i = \lambda 2^{-\ell_i} \log_e 2$ for some $\lambda$. Kraft's inequality forces the solution $2^{-\ell_i} = p_i$, and so
$$ E \geq \sum_i p_i (-\log_2 p_i). $$
The right-hand side is simply the entropy of the distribution.

This argument immediately gives a criterion for when Huffman's code reaches the entropy: this happens if $-\log_2 p_i$ is always an integer, that is, all probabilities are of the form $1/2^k$ (for integer $k$).


Why exactly are Regular Languages decidable?

I will try to explain it without a formal proof,

Imagine a turing machine where you have input written over a tape you can only but read only the input and not modify it. In addition you can only visit the length of the tape where the input is written. This gives you a finite number of configurations to traverse. Thus after a finite number of moves you can $Decide$ whether or not the word word belongs to the input language ; making regular languages decidable.


How to find max flow in a graph after decrementing an edge capacity?

If the capacity of edge $c(e') \ge f(e') + 1$ i.e. the max flow remains the same, there is no chance max flow increase, as it would increased without decreasing $c(e')$.

Suppose that $c(e') = f(e')$ (this edge is saturated) and we decrease the capacity in $1$ unit. You need to remove one unit of flow from $s$ to $t$ that goes through edge $e'$. Let say that $e'= (u,v)$.

Removing flow: Just run two BFS, one starting from $s$ to $u$ going through edges that has flow greater that $0$, the other from $v$ to $t$ equally from edges that has flow greater than $0$. (It is guaranteed you will reach your goal in both cases since there is a unit of flow traversing this edge). Select a path from $s$ to $u$ and remove $1$ unit of flow from each edge and do the same with a path from $v$ to $t$. Complexity: $O(|V| + |E|)$

Recover max flow: Now we have a valid flow network but not necessarily the network with max flow. So now you just need to run one iteration of augmenting path with the capacity of edge $e'$ reduced. (Just like running one iteration of Ford-Fulkerson algorithm) Running just one iteration has the complexity of a single DFS which is $O(|V| + |E|)$.

Overall complexity of this approach would be $O(|V| + |E|)$ which is linear in the amount of nodes and edges.


Designing a sorting algorithm based on the Fibonacci Heap is the same as the Heap Sort; Build the Fibonacci-Heap, Extract Minimum.

From the Wikipedia;

  Although the total running time of a sequence of operations starting with an empty structure is bounded by the bounds given above, some (very few) operations in the sequence can take very long to complete (in particular delete and delete minimum have linear running time in the worst case). For this reason Fibonacci heaps and other amortized data structures may not be appropriate for real-time systems.

The data size should be very long to achieve better than the heap sort, but this time you may turn into external sort.

And, remember, for comparison based sorting algorithm, we have $\Omega(n \log n)$ as lower bound.


Constructing a tree from disjoint graphs

The reverse direction is relatively straight forward, as we start with disjoint vertices, and at each step only add edges to a new vertex, we cannot introduce a cycle, furthermore at each step we connect the "graph so far", so we finish with a connected graph.

For the forward direction, we just need to consider how we could construct a tree in such a manner. The key observation being that a subtree is also a tree. Thus we can recursively break down a tree (the construction is then a series of applications of adding a new node and some edges) by picking a vertex in the tree, and taking each of its subtrees as the sets $X_{1},X_{2},\ldots$. Each of these is a tree (and hence "valid"), so we can construct them in the same manner. Eventually we reach a set of leaves (individual vertices) which are by definition "valid".

The diagram gives a little sketch of this, with the "valid" components $X_{1}$, $X_{2}$ and $X_{3}$ all representing trees, with a new vertex added, and a single edge from each component to this new vertex.


Ok, I managed to prove it:

We note that the total size of the tables = $$n^2 + \sum_i n_i^4$$
where $n^2$ is the first table and $n_i$ is the size of the $i$th index of table with collisions.
Therefore we get:

$$n^2 + \sum_i n_i^4 = n^2 +\sum_i (n_i^2)^2 \le n^2 + \sum_i (4\binom{n_i}{2})^2 \le n^2 + 16(\sum_i \binom{n_i}{2}) = n^2 +16(\text{number of collisions})^2 = n^2 + 16n^2 = O(n^2)$$


How to understand the CRC Algorithm from the CAN specification?

CRC(x) is remainder of polynomial division of x by some fixed polynomial. Here bits of x, as well as bits of result, represents polynomial with binary coefficients, f.e. 0b101 may represent polynomial 1*x^2 + 0*x + 1.

So, the algorithm you have cited, is the most straightforward one - if q(x) = p(x) mod f(x), then p(x)*x mod f(x) is either just q(x)*x (if it doesn't contain x^N where N is order of f(x) polynomial), or q(x)*x - x^N + (x^N mod f(x)). As you may note, the last sum component is some fixed polynomial for given f(x).

So, each step of this cycle do the following:

shift result by 1 bit left - equivalent to multiplication by x
if result contains x^N then xor result by x^N mod f(x)

Oh, well, there are some more details. Please read a painless guide to CRC error detection algorithms for real explanation.


What does Dijkstra's algorithm become, when you replace path cost with edge cost?

The following answer assumes that you know the working of Dijkstra's algorithm. Here, we are working with a variant of Dijkstra's algorithm as mentioned in the question. Hope it will be helpful.
Suppose $s$ is the source vertex and $v$ be any vertex in $V$.
Statement: Dijkstra's algorithm outputs the lexicographically smallest path from $s$ to $v$ if all the edge weights in the graph are positive and distinct.
Proof: Suppose $p = (s,u_{1},\dotsc,u_{q},v)$ is the lexicographically smallest path from $s$ to $v$. For the sake of contradiction, assume that the algorithm outputs $p' = (s,w_{1},\dotsc,w_{r},v)$ and $p' \neq p$. Let $(w_{i},w_{i+1})$ be an edge in $p'$ that act as a tie breaker when we compare the orderings of $p$ and $p'$. In other words, every edges in $p'$ that has the higher weight than the weight of $(w_{i},w_{i+1})$ does also appears in $p$. Let $E_{h}$ be the set of edges in $p'$ that have weight higher than the weight of $(w_{i},w_{i+1})$.

Claim: There is an edge $e$ in $p$ such that $e \notin E_{h}$ and $weight(e) > weight(w_{i},w_{i+1})$.
Proof: I will assume that you are familiar with the fact that the algorithm maintains a cut $(S, V \setminus S)$ such that all the vertices in $S$ are declared visited and the shortest path to them has been found. Now, suppose that just before the algorithm adds $(w_{i},w_{i+1})$, the cut is $(S_{i}, V \setminus S_{i})$. It implies that for all $j \leq i$, $w_{j} \in S_{i}$ and for all $j > i$, $w_{j} \in V \setminus S_{i}$. Also, $s \in S_{}$ and $v \in V \setminus S_{i}$. Now, consider path $p$. Since $p$ is a path from $s$ to $v$, there is an edge $e$ in $p$ that is also present in the cut $(S_{i}, V \setminus S_{i})$. Firstly, we will show that $e$ does not belongs to $p'$. For the sake of contradiction assume that $e$ also belongs to $p'$. Therefore, let us define $e$ to $(w_{t},w_{t+1}) \in p'$.
Case $1$:  $e$ appears before $(w_{i},w_{i+1})$ in the path sequence
$p'$. It means $w_{t}$ and $w_{t+1}$ belongs to $S_{i}$. It
contradicts that $(w_{t},w_{t+1})$ belongs to the cut $(S_{i},V \setminus S_{i})$.
Case $2$: $e$ appears after $(w_{i},w_{i+1})$ in the path sequence
$p'$. Let $(S_{t-1},V \setminus S_{t-1})$ be the cut just before
$(w_{t-1},w_{t})$ was added to the solution. We know that  $w_{t-1} \in S_{t-1}$ and also $w_{t} \in S_{i} \subset S_{t-1}$. Therefore, it
contradicts that $(w_{t-1},w_{t})$ belongs to the cut
$(S_{t-1},V\setminus S_{t-1})$.
From the above two cases, we can say that $e \notin p'$ and therefore $e \notin E_{h}$.
Also, note that the edges $e$ and $(w_{i},w_{i+1})$ both belongs to the cut $(S_{i},V \setminus S_{i})$, and the algorithm chooses $(w_{i},w_{i+1})$ over $e$. Therefore, the weight of $e$ is greater than the weight of $(w_{i},w_{i+1})$. This
proves the claim.

The above claim implies that $p'$ is lexicographically smaller than $p$. Therefore $p = p'$. It contradicts our initial assumtion that $p \neq p'$. Hence proved.


Prove the time complexity of this algorithm of finding longest subarray with maximum value in the middle

Let an array $a[1],\ldots,a[n]$ be given. For an index $i$, let $\ell(i)$ be the largest $\ell$ such that $\{i-\ell,\ldots,i+\ell\} \subseteq \{1,\ldots,n\}$ and $a[i]$ is larger than all elements $a[i-\ell],\ldots,a[i-1],a[i+1],a[i+\ell]$. It is not difficult to see that the running time of the algorithm on the array is $\Theta(n + \sum_{i=1}^n \ell(i))$.

This prompts the following definition:

  Given $n$, the quantity $M(n)$ is the maximum of $\sum_{i=1}^n \ell(i)$ over all arrays of length $n$.

Let $a$ be an array for which $M(n)$ is achieved, and let $a[i]$ be an element of maximum value. Then $\ell(i) = \min(i-1,n-i)$. Moreover, since $a[i]$ is not smaller than any other element, we have $\sum_{j=1}^{i-1} \ell(j) \leq M(i-1)$ and $\sum_{j=i+1}^n \ell(j) \leq M(n-i)$. This shows that
$$
M(n) \leq \max_{i=1}^n M(i-1) + M(n-i) + \min(i-1,n-i).
$$
In fact it is not hard to check that equality holds: take the maximum $i$, and combine two arrays attaining $M(i-1)$ and $M(n-i)$ with a larger element in the middle. This gives the recurrence
$$
M(0)=0, \; M(n) = \max_{i=1}^n [M(i-1) + M(n-i) + \min(i-1,n-i)].
$$
This recurrence is A078903. It is intuitively clear that the best choice for $i$ is $\lfloor \frac{n+1}{2} \rfloor$ or $\lceil \frac{n+1}{2} \rceil$.

We can solve the recurrence explicitly: for $0 \leq k < 2^m$, we have
$$
M(2^m+k) = (m-2)2^{m-1}+1+N_2(k),
$$
where $N_2(k)$ is the total number of 1s in the binary expansions of $1,\ldots,k$ (this is A000788). It is known that $N_2(k) = k\log_2 k + O(k)$, and so $M(n) = \Theta(n\log n)$. This asymptotic estimate also follows from the monotonicity of $M(n)$, by considering the cases $k = 0$.

We conclude that the running time of the algorithm is indeed $O(n\log n)$, and moreover this estimate is tight.


Complexity of domino tiling with dominoes placed in a line

This is just the Eulerian path problem on a multigraph. The colors are the vertices, and the dominos are the edges. You want to know whether there is a path that goes passes through each edge exactly once. It's polynomial time, and you should be able to find the algorithm by googling "Eulerian path".


Is the set of languages recognized by a Turing machine with an oracle countable?

Every language can be accepted by a Turing machine with an appropriate oracle, for example an oracle for the very language you want to accept. So if you understand "languages recognized by a Turing machine with an oracle" in this way, then certainly their number is uncountable.

Another way to understand this phrase is the you fix the oracle and then ask how many languages are recognized by a Turing machine with access to this specific oracle. In this case the number of languages is countable, since there are countably many ways to specify a Turing machine.


The square language $L^2$ is defined as follows:
$$
L^2 = LL = \{ xy : x,y \in L \}.
$$
There is no requirement that $x = y$. Indeed, in your case $L^2 \supsetneq \{ w^2 : w \in L \}$.


Efficient algorithm to map two differently-sized sets of numbers as closely as possible?

This can be solved by reduction to the unbalanced assignment problem.

Build a bipartite graph where the vertices are the two sets of numbers, and there is an edge from a vertex in one set to a vertex in the other set if and only if the distance between the numbers is less than or equal to 0.18. Set the weight of each edge to the distance between the two numbers.

The goal is to find a minimum-weight maximum bipartite matching in this graph. Some minimum-weight bipartite matching implementations will do this directly.

If you only have access to an implementation that requires a fixed output matching size, you can still solve this by adding extra edges with arbitrarily huge weights (any value larger than 0.18 times the size of the smaller vertex set) to make a complete bipartite graph. Then throw out any mappings in the output that have the arbitrarily huge weights. This works because the minimum weight guarantee ensures that as few as possible of the edges with arbitrarily huge weights will be chosen in the output assignment.


Maximize the number of edges in subgraph

Your problem is known as densest subgraph. According to Wikipedia, there is a polynomial time algorithm based on flow networks, due to Goldberg. See Goldberg's technical report Finding a maximum density subgraph.


How can Karger's algorithm (and other randomized algorithms) be used in practice?

Karger's algorithm is a randomized algorithm.  It has a small probability of error, but that probability can be made arbitrarily (exponentially) small simply by repeating the approach.

If we do one round of the algorithm, it has a probability of success of $p$.  If you repeat it $100/p$ times and take the best cut found in any of those iterations, then the probability of success is incredibly high: the algorithm fails only if all $100/p$ iterations fail, so the probability of failure is

$$(1-p)^{100/p} \approx e^{-100} < 2^{-128},$$

and the probability of success is larger than $1 - 2^{-128}$.  For Karger's algorithm, $p=1/{n \choose 2}$, so we repeat it $100 {n \choose 2}$ times, and we obtain a probability of success that is larger than $1 - 2^{-128}$.

For all engineering purposes this is equivalent to a guarantee of success.  For instance, the probability that a cosmic ray hits your computer and causes a bitflip error that causes the algorithm to produce the wrong result is far higher than $2^{-128}$, but we're apparently willing to accept that -- so we should be glad to accept Karger's algorithm too, as long as we repeat it enough times.

See the Wikipedia article for more explanation: https://en.wikipedia.org/wiki/Karger%27s_algorithm


Are different assignments allowed for the implication graph proof of 2-SAT being in P?

You have to understand that $a \implies b$ cannot be interpreted as $\neg a \implies \neg b$. Only the contraposition $b \implies a$ is true, but this one is already in the implication graph by construction.
Thus, with your algorithm, you will make abrirtrary assignments. This will probably leads to an impossibility even if the problem does have a solution. Of course, on trivial examples, one can see that this algorithm may produce a solution.
Also note that  $a \implies b \implies c$ means there is elsewhere in the graph $\neg c \implies \neg b \implies \neg a$. So when you decide to assign false in order to $a, b, c$, you are reading the graph and the strongly connected components reversly.


Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start?

When considering algorithms for multiplying large numbers, the first think to keep in mind is the asymptotic complexity. Generally speaking, algorithms with better (smaller) asymptotic complexity are faster, though this only goes so far. So the first thing to do to find out whether Japanese multiplication is "worthwhile" is to calculate its asymptotic complexity. You have to be careful with respect to the model of computation, but in your case it probably won't make a big difference; probably your algorithm has "bad" asymptotic complexity.

The second thing to notice is that the multiplication logic is already there in the CPU, and no code that you can write will be faster than calling the built-in multiplication instruction. Of course, this is only good for multiplying machine words (or multiwords, in some cases). That means that your algorithm had better take advantage of the multiplication capabilities of your processor. While not affecting the asymptotic complexity, it does considerably affect the constants. All fast multiplication algorithms use machine multiplication instructions.

The best way to know whether the algorithm is any good in practice is to program and optimize it. Use a language like C which produces fast code, and then you can compare it to libraries such as GMP. This is the only convincing way to claim that your algorithm is better than existing ones, though you should expend some effort on optimization.

Finally, you claim that Japanese multiplication is better than CPU multiplication algorithms since it only uses addition. Textbook multiplication algorithm also only use addition, since everything is in binary. But probably this can be optimized further at the expense of using more gates, by having logic for small multiplications. You can look up what algorithms CPUs use, perhaps they're similar to Japanese multiplication.