What are appropriate isomorphisms between formal languages?

Has my problem already been solved, so that I just need to read the right references?

The theory of abstract family of languages is relevant. For example, the morphisms defined by finite state transducers lead to the cone family. Eilenberg's short ICM talk from 1970 nicely explains this framework, see also chapter 11 "Closure properties of families of languages" from Introduction to Automata Theory, Languages, and Computation (1st ed.) by J. Hopcroft and J. Ullman from 1979. However, only nondeterministic languages fit into this framework1. In the end, the book Theory of codes by J. Berstel and D. Perrin from 1985 helped me to come up with reasonable solutions for my problem. Codes and Automata by J. Berstel, D. Perrin and C. Reutenauer from 2009 is a major revision of this book with a much broader coverage.

  Has this line of reasoning any chance of "resolving" my problem? Does my problem itself makes any sense, or is this just as misguided as ...?

The assumption that there is one correct category for modeling isomorphisms between languages to "formalize the concept of a problem" is misguided. There are many different categories which can be interesting in the context of formal languages.

Here are three interesting categories related to many-one reductions, which will be referred to as total, partial, and relational. The objects of the categories are pairs $(\Sigma, L)$ of a finite alphabet $\Sigma$ and a language $L\subset\Sigma^*$ of words over $\Sigma$. For total, the morphisms between the source object $(\Sigma, L)$ and the target object $(\Sigma', L')$ are total functions $f : \Sigma^* \to \Sigma'^*$ with $L=f^{-1}(L')$. For partial, the morphisms are partial functions $f : \Sigma^* \to \Sigma'^*$ with $L=f^{-1}(L')$, where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$. For relational, the morphisms are relations $R\subset \Sigma^* \times \Sigma'^*$ with $L=R^{-1}(L')$, and any two morphisms between the same source and target are considered to be equal. The set of allowed functions or relations can be restricted to various simple "translators" to get categories with interesting isomorphisms.

The monoid homomorphisms from $\Sigma^*$ to $\Sigma'^*$ give a very basic total category. The isomorphisms of this category are basically just the bijections between $\Sigma$ and $\Sigma'$. Any reasonable family of languages should better respect these isomorphisms, i.e. be closed under inverse homomorphisms.
The partial functions defined by deterministic log-space Turing machine translators give a quite natural partial category. It is able to perform many trivial syntactic transformations (like applying De Morgan's laws to move negations to the atoms), includes the morphism defined by functional finite state transducers1, and also can sort. Still it won't identify two completely unrelated languages as isomorphic, because equality of the composition of two morphisms to an identity morphism is a much stronger requirement than just existence of many-one reductions in both directions.
The relations defined by nondeterministic log-space Turing machine translators give an interesting relational category. SAT is isomorphic to HORNSAT in this category, but it is an open question whether TAUTOLOGY or any other co-NP-complete problem is isomorphic to HORNSAT.

  Two languages $L$ and $L'$ over alphabets $\Sigma=\{a,b\}$ and $\Sigma'=\{c,d\}$ (where $a$, $b$, $c$ and $d$ are distinct letters) can never be equal, even if they describe "exactly" the same "problem." But they should be isomorphic, if they really describe "exactly" the same "problem."

The very basic total category described above solves this problem.

The problem becomes more interesting if "exactly the same" is replaced by "nearly the same for most practical purposes": Let $L$ be a language over $\Sigma=\{U,C,A,G\}$ and let $L'$ be the language over $\Sigma'=\{0,1\}$ obtained from $L$ by the substitution $U \to 00$, $C \to 01$, $A \to 10$, and $G \to 11$. Note that in any total category, $L$ and $L'$ are not isomorphic for $L=\Sigma^*$. The same would be true for partial categories, if the part "where two partial functions $f$, $g$ are considered equal (as morphisms) if $f(x)=g(x)$ for all $x\in L$" were omitted from the definition.

The quite natural partial category described above is sufficient for making $L$ and $L'$ isomorphic. It would be nice to have a more basic (i.e. more restrictive) category that makes them isomorphic. The following (successively more restrictive) categories look reasonable to me:

The partial functions realized by unambiguous finite state transducers2 where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between recognizable variable length codes.
The partial functions realized by deterministic finite state transducers where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between prefix codes.
The partial functions realized simultaneously by both a forward and a backward deterministic transducer where the only accepting state is the initial state. The isomorphisms of this partial category are (a subset of the) bijections between bifix codes.
Further restriction of the partial functions such that the isomorphisms are (a subset of the) bijections between block codes could also make sense.

  One can use languages in complexity theory to formalize the concept of a "problem."

Even before I learned about category theory, I have wondered about whether there are "more faithful" ways to formalize the concept of a "problem". After becoming familiar with category theory, I sometimes tried to come up with possible solutions, but always quickly gave up at the first stumbling block (because nobody cares anyway). I know that Yuri Gurevich has solved some related questions, but his solutions are practically applicable, whereas I was looking more for something nice and abstract, independent of practical applicability.

Most of my spare time for the last three weeks went into finally making some progress on this problem. Most often the time was spend finding annoying issues in the possible solutions I had in mind. The sense of making progress arose from reading (old) books and articles, and learning many basic concepts and facts about transducers and rational sets.
Finally I learned the notions of a prefix code and a bifix code (formerly biprefix code in Berstel's book), which allowed me to come up with the reasonable3 categories described above.

It may be hard to appreciate those (code related) categories, without having seen some issues of the more obvious categories. A general issue is that closure under composition can make it hard to define a nicely restricted class of partial functions. Another issue is related to the fact that addition of one (or multiplication by a constant) is an "easy to compute function" if the digits of the number are given in low-endian order, but not if the digits are given in big-endian order.

1
A functional finite state transducer is a nondeterministic finite state transducer that realizes a partial function. These partial functions cannot be realized by deterministic finite state transducers. They can be realized by deterministic bimachines, but those may need $O(n)$ forward and backward scans over the input, if they want to operate in $O(1)$ space.

2
An unambiguous finite state transducer is a nondeterministic finite state transducer with at most one accepting path for each input. It realizes a partial function, hence it is also a functional finite state transducer. It is decidable whether a given finite state transducer is unambiguous.

3
I'm not sure how reasonable the total and the relational categories introduced above really are. I just wanted to show straightforward alternatives to the partial category. More alternatives are easy to come up with, for example co-relational, where the morphisms are relations $R\subset \Sigma^* \times \Sigma'^*$ with $L=R^{-1}(L')-R^{-1}(\Sigma'^*-L')$, and any two morphisms between the same source and target are considered to be equal.


What is it called when two problems are similar?

In complexity theory we prefer, when possible, to use formal definitions. Two problems $P,Q$ are polynomially equivalent if there are polytime functions $f,g$ such that $x \in P$ iff $f(x) \in Q$ and $y \in Q$ iff $g(x) \in P$. This is the usual notion of equivalence in complexity theory.

Sometimes we prefer a coarser notion of equivalence which allows using a problem as an oracle. Two problems $Q,R$ are polynomially equivalent with respect to oracle reductions if $Q \in \mathsf{P}^R$ and $R \in \mathsf{P}^Q$, or in other words, $Q$ can be solved in polynomial time with oracle access to $R$, and $R$ can be solved in polynomial time with oracle access to $Q$. Under this notion, 3SAT and co-3SAT (its complement) are equivalent.

Unless I have made a blunder, both these notions are equivalence relations. In both cases, if one problem can be solved in polynomial time, then so can the other. Since the second is more general, it seems to fit your description better, though in complexity theory we usually prefer the finer first notion, or even finer notions such as logspace reducibility and AC0 reducibility.


Prove that $\text{EXACT-TRIPLE}$ is not in NP

The problem is coNP-hard, and so not likely to be in NP. Indeed, given a formula $\phi$, you can construct a formula $\phi'$ such that if $\phi$ has $x$ satisfying assignments then $\phi'$ has $x+3$. This gives a reduction from the coNP-complete problem UN-SAT to EXACT-TRIPLE.


Why 'let' can not be reduce to a lambda application in (extended) Calculus of Constructions

In an untyped language, those expressions would be equivalent. When working with types, instead, one might have a type while the other one has no type.

Assume that numbers and arithmetic operators all work on $\sf nat$. Then $e_0 = 2+2$ can be typed as $\sf nat$. Now, we can try to perform a $\beta$-expansion, i.e. to "apply $\beta$ backwards", and reach $e_1 = (\lambda x:{\sf nat}.\ x+2)2$.

$$(\lambda x:{\sf nat}.\ x+2)2 \to_\beta 2+2$$

This new expression $e_1$ would still have type $\sf nat$. But we could also go further
to $e_2=(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat}$.

$$(\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2){\sf nat} \to_\beta(\lambda x:{\sf nat}.\ x+2)2 \to_\beta 2+2$$

Now, $e_2$ can not be typed. If it had a type, every subterm of $e_2$ would also be typeable, including $e_2' = (\lambda \tau:{\sf Type}.\ (\lambda x:\tau.\ x+2)2)$, but this subterm can not be typed. The only type we can assign here would be of the form

$$
e_2' : \prod_{\tau:{\sf Type}} (\mbox{something})
$$

in which case this would also be typeable:

$$
e_2' \, {\sf bool} \to_\beta (\lambda x:{\sf bool}.\ x+2)2
$$

The above is nonsense, since $2$ is not a $\sf bool$, so it should not be bound to $x$.

Indeed, we just discovered that types are not preserved under $\beta$-expansion.

A first question arises:

  Couldn't we $\beta$-reduce the expression before typing?

Yes, and that's (roughly) what ${\sf let}\ \tau = {\sf nat}\ {\sf in}\ e$ does: it types $e$ knowing that what $\tau$ actually is.

And now one might counter with:

  If $\sf let$ works in that way, why don't we use the same technique for lambdas?

We can't do that, since lambdas are not always immediately applied to an argument. The syntax ${\sf let}\ x = t\ {\sf in}\ e$ shows what is the value of $x$, namely $t$. The syntax $(\lambda x. e) t$ also shows the value of $x$ but not all lambdas are used in that way: sometimes we want to use $(\lambda x. e)$ without an argument. Say, we want to pass that to another function $F (\lambda x. e)$, or build a pair of functions $(\lambda x. e, \lambda x. e')$. Here, we don't know what $x$ is. Unlike the $\sf let$ case, here $x$ could even take many values, e.g. if $F = \lambda k. k 0 + k 1$ then $F (\lambda x. e)$ makes $x$ to be $0$ on one call and $1$ in the other call.

So, $\sf let$ is less general than a lambda, and we can have a "special" typing rule for that.


Efficiently compute the sum of edge weights product of all possible path in a DAG

You can actually solve this in $O(|V|+|E|)$ time. Since it is a DAG, we can apply dynamic programming.

Let $p = u_1u_2\dots u_k$ be a path and $cost(p) = w(u_1,u_2)\times w(u_2,u_3)\times\dots \times w(u_{k-1}, u_k)$ be the edge weight product of the path. One important observation is that $cost(u_0p_1) = w(u_0,u_1)\times cost(p_1)$.

Now, for each node $u$, let $dp(u)$ be the sum of edge weight products of all paths originating from $u$.

Let the children of $u$ be $v_1,v_2,\dots,v_m$. We can compute $dp(u)$ using the relation

$$dp(u)=\sum_{i=0}^m w(u,v_i) \times dp(v_i)$$

A Topological sorting can find the order of nodes to compute. Then, the final answer is the sum of all $dp$

$$\sum_{u\in V} dp(u)$$


Big-O notation for Polynomial Time Complexity

The question is worded in a tricky way. When it says "polynomial" it really means "all functions that represent a polynomial complexity class". Essentially, they want the asymptotic notation for the functions $f(n)=1$, $f(n)=n$, $f(n)=n^2$, etc. The reason we want this is because you would see this inside big-O like $O(1)$, $O(n)$, $O(n^2)$, etc. Those functions represent these big-O sets.
The reason we talk about it this way is because we are talking about it in the world of complexity classes. An example is $P$.
\begin{align}
P = DTIME(poly(n)) = \bigcup\limits_{k\in\mathbb{N}}DTIME(n^k)
\end{align}
From the wiki on DTIME.

If a problem of input size $n$ can be solved in $O(f(n))$, we have a complexity class $DTIME(f(n))$ (or $TIME(f(n))$).

So the asymptotic notation for the set of these functions is $n^{O(1)}$. The following is a way to reason about it.
\begin{align}
n^{O(1)}
&= n^{\{0,1,2,...\}} \\
&= \{1,\ n,\ n^2,\ ...\}
\end{align}
To show that $2^{O(\log n)} = poly(n)$ is with the same reasoning as above.
\begin{align}
2^{O(\log{n})}
&= 2^{\{0\cdot\log{n},\ 1\cdot\log{n},\ 2\cdot\log{n},\ ...\}} \\
&= 2^{\{0,\ \log(n^1),\ \log(n^2),\ ...\}} \\
&= \{2^0,\ 2^{\log(n)},\ 2^{\log(n^2)},\ ...\} \\
&= \{1,\ n^1,\ n^2,\ ...\} \\
&= n^{O(1)}
\end{align}
To formally show these are equal, you would have to use set notation.
Finally, "polynomial in x" means that $poly(x)$ grows polynomially depending on $x$. You can see that some of the entries in the table have a function as the argument to $poly$. For instance, $poly(\log{n})$ (polylogarithmic) grows slower than $poly(n)$ (polynomial) since $O(\log{n}) < O(n)$.


What you are describing is part of the area of knowledge known as compiler theory, specifically parsing. One of the classical books is the dragon book. Parsing and evaluating expressions like yours is usually done in three interlocked steps:

Lexical analysis. This part is in charge of converting the input into a sequence of "lexemes". It will convert your example into the lexemes "(" VARIABLE "=" NUMBER ")" "or" "(" VARIABLE ">" NUMBER ")". This step is implemented using regular automata.
Syntax analysis. This part construct a parse tree of your expression. In your case, the parse tree (generated using Miles Shang's online tool) will be:

This step is implemented using context-free languages, either using a table-based approach or using recursive descent.
Semantic analysis. In your case, this part will evaluate the expression recursively using the parse tree, making use of attributes stored at the meta-lexemes VARIABLE and NUMBER.


Is address bus size same as physical address size and is that the same as word size?

Is address bus size same as physical address size

No, not necessarily. Especially with modern 64 bit address bus sizes, it is quite common that CPUs do not actually support 64 bit physical addresses.
For example, the first AMD64 CPUs had 40 bit physical addresses, the current ones have 48 bit. In fact, due to the Page Table Entry format, physical addresses cannot be larger than 52 bit.

and is that the same as word size?

No, not necessarily. It makes stuff easier, but there have been architectures where the bus was half the word size, and you had to transmit a word in two bus cycles. Conversely, it is also possible to have the bus width be an integer multiple of the word size, making it possible to transmit multiple words per bus cycle.
Just as an example: the IBM 704, one of the most famous computers of all time (both FORTRAN and LISP were first implemented for the IBM 704, the trajectory data for Gemini and Apollo was computed on one) has 36 bit words but 15 bit addresses.


Well, of course you have to merge the two empty states and there should be two transitions $(\{q_5\}, a, \emptyset)$ and $(\{q_5\}, b, \emptyset)$ if you want a complete automaton, but otherwise, it looks right and I agree with Subhayan: both automata accept $ab^+ \cup ab^+a$.


Non-deterministic Turing machine and palindromes

Guess a position $\ell$ and add it to the left of the input. Copy it to the beginning of the tape, on top of the input string (use an expanded alphabet). Now go to position $\ell$, carrying your counter around with you. For each position you move, you need to spend $O(\log n)$ time to copy the counter, but that's fine. Decrementing the counter and comparing it to zero also take only $O(\log n)$. Once at position $\ell$, remember the symbol there, and go back to the beginning. Now move your counter all the way to the other end of the string, and count $\ell$ positions from there. Compare the symbol you find to the one you remember.


Consider any two codewords based on $b_2b_1b_0$ and $c_2c_1c_0$. The Hamming distance between the two codewords is at least twice the Hamming distance between $b_2b_1b_0$ and $c_2c_1c_0$ (why?). Furthermore, if the Hamming distance between $b_2b_1b_0$ and $c_2c_1c_0$ is exactly $1$, then your argument shows that the Hamming distance between the codewords is $3$. We can conclude that the Hamming distance is always at least $3$.


Successful applications of fuzzy logic to reasoning in AI?

There are plenty of papers on fuzzy logic, and applications of it.

Fuzzy logic models a piece-wise control function, and is regarded as a non-linear controller. Generally, fuzzy logic can approximate any non-linear function if you divided the state-space into enough fuzzy sets.

Because it is non-linear, it is generally useful if it is controlling a non-linear system. If it were a linear system, a linear controller would be able to control it optimally already.

It is appropriate when you want to control things like movement or position (which is often the case in robots). When a system can rotate, the rotation will create the non-linearity that fuzzy logic may try to control.

In any case, the success of fuzzy logic more often has to do with how well you select the fuzzy sets (ie. their boundaries and membership functions), and how well you tune the fuzzy logic controller. In general, any controller can be successful if appropriately tuned - though their ideal performance may differ. And the most difficult part is probably tuning it - although it is not hard to get something that works, it may be hard to get something close to optimal.

If you are thinking of using a fuzzy controller, it may be a good choice if:

your system is moderately non-linear (if it is close to linear, a linear controller is sufficient)
your system is not mathematically modelled (if it is modelled, look at LQR and perhaps gain scheduling or SDRE)
or you are unsure of the parameters of your system
and any intuition of what the controller should do would be useful when trying to select the fuzzy sets and their appropriate control responses


How do i tell if a grammar is regular or not?

It's important to distinguish between regular grammars and regular languages.

Your first grammar is regular.

A regular grammar is either a right-regular grammar or a left-regular grammar. In a right-regular grammar, every production's right-hand side has at most one non-terminal, and that non-terminal is the last symbol in the right-hand side. A left-regular grammar is the same except that all the non-terminals are at the beginning of their respective right-hand sides.

As you observe, your second grammar is not a regular grammar, since there is a right-hand side with more than one non-terminal.

A regular language is a language for which a regular grammar exists. That's a much trickier criterion, since the fact that a particular grammar is not regular does not in any way prove anything about the regularity of the language generated by that grammar. The language might or might not be regular, and there is no algorithm which will even tell you for sure.

So your statement "Which also means that I can't turn this into a regex." does not follow. As it happens, your second grammar does not generate a regular language, but many non-regular grammars do recognise regular languages. Here's a simple example:

$$\begin{align}S &\to aS\\
S &\to Sb\\
S &\to \lambda
\end{align}$$

That grammar generates the language $a^*b^*$, which is certainly a regular language. But this particular grammar is not regular because one production is left recursive and the other production is right recursive; in a regular grammar, either all productions with a non-terminal are left-regular, or all productions with a non-terminal are right-regular.


Continuing where @ijkilchenko left off.

$2\to 3$: Let $T$ have the cut property and let $T'$ be any other spanning tree of $G$. For each $e\in T$, there is some edge $e'\in T'$ that crosses the cut defined by $e$. Define $f : E(T) \to E(T')$ by mapping each edge $e \in E(T)$ to the edge $e' \in E(T)'$ with smallest weight among those crossing the cut defined by $e$.  According to the cut property $w(e)\le w(f(e))$, so we get
$$ w(T) = \sum_{e \in T} w(e) \le \sum_{e\in T} w(f(e))\le \sum_{e'\in T'} w(e') = w(T')$$
where the third inequality comes from the fact that if $f$ is not injective, it only decreases weights.  Since $T'$ was arbitrary, we have shown that $w(T)$ is minimum among all spanning trees of $G$, and we are done.

$3\to 1$: If $T$ does not have the cycle property, the definition supplies us with an edge $e\in T$ and $e'\notin T$ such that $w(e') < w(e)$, so $T - e + e'$ is a tree with weight less than $T$. Therefore $T$ does not have minimum weight.


Bounded Integer Edge Weights, Dijkstra's Algorithm

In the case of your example, the shortest path is of length C since all paths are 1 edge long; there is an edge between each pair of node.

The figure of (|V|-1)C comes from the situation where all your nodes form a single chain, with edge weights of C. Then, the path between the first and last node on the chain is of length (|V|-1)C.


Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

Savitch's theorem shows that $\mathsf{NSPACE}(f(n)) \subseteq \mathsf{SPACE}(f(n)^2)$.


Round-Robin Scheduler - What exactly is the quantum time used for?

For the Round-Robin Scheduler the quantum time is to ensure that each process has a share to the CPU and we don't have starvation problems. It's known for being fair, such that each process shares the CPU equality. Quantum time is it's the amount of time spent on each process in the CPU until we context switch to the next process in the ready queue. For example say you have P1, P2, and P3 in the ready queue. And some P4 enters the ready queue at 550ms. The RR would perform something like this:

P1 - 0   to 100ms
P2 - 100 to 200ms
P3 - 200 to 300ms
P1 - 300 to 400ms
P2 - 400 to 500ms
P3 - 500 to 600ms [P4 enters]
P4 - 600 to 700ms
... [P1 to P4 cycles]

If a process has a CPU-bound execution that is less than the time slice. Then we move to the next process keeping the same time slice. For example let's say P1 only needs to run for 50ms until it's done. Then you have:

P1 - 0   to 50ms [finnished, start P2]
P2 - 50  to 150ms
P3 - 150 to 250ms
P2 - 250 to 350ms
P3 - 350 to 450ms
...


Yes, you are understanding this correctly.
The set of SCCs of a graph is uniquely determined. So if the algorithms were returning different sets, this would imply that one of them is incorrect. For the Wikipedia version a correctness proof is linked at the bottom of the article. If Sedgewick also gives a correctness proof of his algorithm, these two proofs together imply the property.
Reversing a graph twice will give you the original graph. Thus, if one algorithm performs especially well/bad on a certain graph, the other one will show that performance on the reversal of the graph in question. So neither algorithm will perform better in the general case.

The comment on SO that the WP version does use $O(n)$ extra space for the stack is not entirely correct: Sedgewick also has to store the order of traversal in some way, which wll also take $O(n)$ space (though possibly with a smaller hidden constant). Additionally, you can replace the stack with a different way of storing the order in the WP algorithm as well.


How to perform alphabetically ordered DFS?

$L$ has an edge to $K$, other than that, the DFS forest you've drawn is correct.  And since $K$ would not be expanded before $L$, there should be an edge $LK$ in the BFS forest.


What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?

Your archetypical $\Theta(n \log n)$ is a divide-and-conquer algorithm, which divides (and recombines) the work in linear time and recurses over the pieces. Merge sort works that way: spend $O(n)$ time splitting the input into two roughly equal pieces, recursively sort each piece, and spend $\Theta(n)$ time combining the two sorted halves.

Intuitively, continuing the divide-and-conquer idea, each division stage takes linear time in total, because the increase in the number of pieces to divide exactly matches the decrease in the size of the pieces, since the time taken by division is linear. The total running time is the product of the total cost of a division stage multiplied by the number of division stages. Since the size of the pieces is halved at each time, there are $\log_2(n)$ division stages, so the total running time is $n \cdot \log(n)$. (Up to a multiplicative constant, the base of the logarithm is irrelevant.)

Putting it in equations (), one way to estimate the running time $T(n)$ of such an algorithm is to express it recursively: $T(n) = 2 T(n/2) + \Theta(n)$. It's clear that this algorithm takes more than linear time, and we can see how much more by dividing by $n$:
$$ \frac{T(n)}{n} = \frac{T(n/2)}{n/2} + \Theta(1) $$
When $n$ doubles, $T(n)/n$ increases by a constant amount: $T(n)/n$ increases logarithmically, or in other words, $T(n) = \Theta(n \log n)$.

This is an instance of a more general pattern: the master theorem. For any recursive algorithm that divides its input of size $n$ into $a$ pieces of size $n/b$ and takes a time $f(n)$ to perform the division and recombination, the running time satisfies $T(n) = a \cdot T(n/b) + f(n)$. This leads to a closed form that depends on the values of $a$ and $b$ and the shape of $f$. If $a = b$ and $f(n) = \Theta(n)$, the master theorem states that $T(n) = \Theta(n \log n)$.


Worst case $O(n \ln n)$ in place stable sort?

You can write an in-place, stable mergesort. See this for details. In the author's own words:

  A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays.  This code is litteraly copied from the C++ stl library and translated in Java.

I won't copy the code here, but you can find it at the link or by checking the C++ STL. Please let me know if you would like me to try to provide a more detailed description of what's going on here.


Number of Combinations of Connected Bipartite Graphs

The answer is was given by David Eisenstadt in his answer to my question.
The answer can be computed by starting with the fully connected bipartite graph and evaluating the Tutte polynomial at (1,2).
While I don't fully understand everything about this problem, the intuitive reasoning is as follows:
Start with the fully connected-graph. The Contraction-Deletion Algorithm and the Tutte polynomial at (1,1) give the number of possible spanning trees. But we are actually not interested in the number of spanning trees but also along all the still-connected graphs along the paths to get to the spanning trees.
Note:
If you can explain this further, either add your own answer, or edit mine. If you add your own answer, I will accept yours.


Converting 4 variable if else condition to Linear integer program

Every logical formula can be converted to conjunctive normal form (CNF), that is, into a conjunction (AND) of clauses (OR). In turn, a clause $\ell_1 \lor \cdots \lor \ell_m$ can be expressed as the constraint $\ell_1 + \cdots + \ell_m \geq 1$. In this way, you can express any logical condition in an integer program.
As an example, consider the logical formula $x \oplus y$, that is, exactly one of $x,y$ is true. While it can be expressed directly as $x + y = 1$, let's see how to do it using CNF. Putting it into CNF, we get $(x \lor y) \land (\lnot x \lor \lnot y)$. Therefore we add the following constraints: $x + y \geq 1$ and $(1-x) + (1-y) \geq 1$, i.e., $-x-y \geq -1$.


Graph isomorphism and the automorphism group

As the comments suggest there can be confusion over what you call "GI". But  the idea here is correct.  It is polynomial-time equivalent to find generators of an automorphism group as it is to find an isomorphism between two groups.  The idea is "classical" in that it appears in early work such as Luks' Group Isomorphism in bounded valence is in polynomial-time, and even there I think the idea was considered "well-known".

Claim. Let $G$ and $H$ be connected graphs.  Then $G\cong H$ if, and only if, every generating set $S$ of $\mathrm{Aut}(G\sqcup H)$ contains an element $g\in S$ such that $G^g=H$.

Remark Important here is that every generating set exchange the graphs as otherwise you would sometimes compute generators that don't solve the problem.  So for example, isomorphism of two groups does not so easily yield in this way.  That is because not all generating sets of $\mathrm{Aut}(G\times H)$ will interchange $G$ and $H$ when $G\cong H$.  instead they can go to diagonal copies.  That situation can be fixed, but it requires a stronger argument.  So the approach here is not one that applies in all categories.

Proof.  For the converse if every (or even if one) generating set of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$ then $G\cong H$ by the restriction of that function to $G$.  So this is all about the forward direction.  (But I mention this because the proof is by contrapositive so it can look like I'm about to go the same direction.)

Suppose $\mathrm{Aut}(G\sqcup H)$ is generated by a set $S$ all of whose elements send $G$ to $G$, and $H$ to $H$, (note by connectivity assumption if one vertex of $G$ is sent to one vertex of $H$ then the entire graph $G$ is sent to $H$ and so by pigeon hole some vertex in $H$ will be sent to $G$ and so $|G|=|H|$ and we will have interchanged the two graphs).  Since $S$ sends $G$ to $G$, then every composition of functions in $S$ sends $G$ to $G$, and so do inverses of these functions.  So every word in $S$ sends $G$ to $G$ (and also $H$ to $H$).  So no element of $\mathrm{Aut}(G\sqcup H)$ interchanges $G$ and $H$.

Finally if $G\cong H$ then an isomorphism $\phi:G\to H$ affords an automorphism $\phi\sqcup \phi^{-1}$ of $G\sqcup H$.  So the absence of elements in $\mathrm{Aut}(G\sqcup H)$ to interchange $G$ and $H$ implies $G\not\cong H$.  The result follows. $\Box$

But now the point to be clear on is that going from decision (Is $G\cong H$?) to search (Give me $\phi:G\to H$ or a certificate that $G\not\cong H$) has still to be argued (and can be).  Also from one isomorphism to generators of automorphisms is another argument (individualize the graphs and repeat the isomorphism test).  So all told you have a couple pages of argument to make these equivalences.  None will show canonical labeling though.  That is much harder (NP-hard if I recall).  Even though NAutY and Traces handle many examples quickly.


Context Free or Context Sensitive and why

Hint 1: You can write the languages as $0^k1^k0^k0^{m-k}$ and $a^mb^mb$.

Hint 2: If a language looks non-context-free, but the pumping lemma does not show this, you can try Ogden's lemma.


Is there a different resolution of the "dangling else" problem other than "match closest"?

This problem is an exact analogue of the problem of matching parentheses in an expression in which some of the close parentheses have been omitted. Here an "if" (or $a$ in the representative grammar) is an open parenthesis and an "else" ($b$) is a close parenthesis. (From the sequence of $a$s and $b$s you can mechanically insert $c$s by placing one before each $b$ and one at the very end.) Because it fits better with my parenthetic brain, I write as though that were the problem at hand.

The traditional "match closest" dangling-else resolution matches each close with the most recent as-yet-unmatched open. That means that there is never an unmatched open (or close, for that matter) between a matched open and its matching close.

One possible alternative would be to match each close with the earliest feasible unmatched open. "Feasible" here means that the open could be matched without violating parenthetic nesting (eg. the first $($ in $()()$ cannot feasibly match the last $)$).

This matching has to be done outside-in, so that a match for a close is not attempted until all the enclosing pairs have been matched. This fact makes it impossible to produce a parse with a bounded-lookahead algorithm, since the parse has to work inwards from both ends, after having split the string into completely matched segments (because those effectively limit the range of potential matches).

However, the fact that an online left-to-right parser doesn't exist does not imply that there is no unambiguous CFG. (Evidently: a palindromic language must be parsed from both ends towards the middle, but it's easy to write an unambiguous grammar).

To produce a grammar for the "furthest-match" parenthesis problem, I relied on the fact that an unmatched open cannot be followed by a matched open. If it were, then the furthest-match property wouldn't apply because the unmatched open could have matched the matched open's close, so the fact that it is unmatched violates the furthest-match property.

So here's the slightly clunky grammar:

$$
\begin{aligned}
S&\to U \;|\; M \\
U&\to T \;|\; a U b T \;|\; a U b c \;|\; a M b U \\
M&\to a M b M \;|\; c \\
T&\to a T \;|\; a c \\
\end{aligned}
$$

$S$ is the start symbol; $M$ are fully-matched statements; $U$ are definitely unmatched statements (which means they include at least one unmatched $a$, so they can't be empty) and $T$ is a "tail" consisting only of unmatched $a$s. The above fact about unmatched open's can be read directly from the grammar: all unmatched opens are derived from $T$, a $T$ can only appear at the end of a $U$, and a $U$ can only be followed by a $T$.

The clunkiness comes from preventing $U$ from matching the empty string. That prevents a bunch of what I consider spurious ambiguities: They are spurious in the sense that the matching of the opens and closes is the same in all alternative parses. If $U$ is allowed be nullable, it will also derive a completely balanced string. Since $S$ is, in effect, $M^* U$, that leads to an ambiguity in which you could consider a completely-balanced $S$ to be a series of $M$ followed by an empty $U$, or one fewer $M$ followed by a completely balanced $U$.

Probably there's a better workaround than the one I chose. But this one seems to work, and it plays well with Bison's GLR parser which I used to test it; that parser complains about ambiguous parses unless you write extra code to handle the ambiguity, and I was too lazy to do that. I tested it with strings of up to 20 open+closes, and it seems to have produced an unambiguous parse for every correctly-nested sequence, without producing parses for incorrectly-nested sequences.


What exactly is the LL(k) grammar condition?

It's actually a definition of a strong LL(k) grammar.

First of all, see Raphael's comment.

In short, the condition means that while parsing $A$ you can choose the next production rule in a deterministic manner using only the next $k$ lookahead symbols.

An important thing is you don't need any context for that decision, i.e. you don't need to remember the previous steps in the left-most derivation that led you to the non-terminal $A$ to parse $A$ itself.

By the way, every LL(1) grammar is strong, but there are non-strong LL(k) grammars, $k > 1$.

If you need a more detailed explanation, then I think it's better to use a book for that (it's too long for an answer here). I'd suggest "Parsing Techniques - A Practical Guide" by Dick Grune et al.


Using Dijkstra to find shortest path in relation to two weight functions?

Let $\epsilon>0$ be an infinitesimal. Define a new weight function $w(v) = w_2(v) + \epsilon w_1(v)$, and run Dijkstra with respect to this weight function.

How do you implement infinitesimals? There are two options. The first is to let $\epsilon$ be a small enough number. For example, if $W_1$ is the maximal $w_1$-weight and there are $n$ nodes, then $\epsilon < 1/(nW_1)$ should be small enough (why?). The other option is to notice that you only have to be able to compare numbers of the form $w_2 + \epsilon w_1$. We have $x_2 + \epsilon x_1 \leq y_2 + \epsilon y_1$ if either $x_2 < y_2$ or $x_2 = y_2$ and $x_1 \leq y_1$. Using this comparison oracle, you can implement infinitesimals in earnest.


Comparing growth of two sums of functions

Yes, asymptotically. You can see that $n + n^4 = \omega(n^3 + n^2)$ by taking the limit:

$$
\lim_{n \to \infty} \frac{n^4 +n}{n^3 + n^2} =  \lim_{n \to \infty}\frac{n + n^{-2}}{1 + n^{-1}} = + \infty
$$.

See also this answer.


Is the language $\{0^n 1^m \mid n \text{ and } m \text{ are co-prime}\}$ context-free?

Ridiculous that I didn't see this earlier...

The proof that the language (call it $\mathcal{L}$) isn't context free is by contradiction. Assume $\mathcal{L}$ is context free, by the pumping lemma for CFGs there is a constant $N$ such that each string $\sigma \in \mathcal{L}$ such that $\lvert \sigma \rvert \ge N$ it can be written $\sigma = u v x y z$ with $v y \ne \epsilon$ such that for all $k \ge 0$ the string $u v^k x y^k z \in \mathcal{L}$. Take $m, n$ different primes (such that $\gcd(m, n) = 1$) and $m, n > 2N$, and take $\sigma = 0^m 1^n$. The pumped string will be $0^{m + k a} 1^{n + k b}$ for some constants $a$, $b$, not both zero, and such that $a < m$ and $b < n$ (we have $a, b \le N < m / 2, n / 2$ by the way $m$, $n$ were selected). The case of one of them zero was covered by OP, so consider $a, b \ne 0$. Now:

$$
\begin{align*}
m + k a &\equiv 0 \pmod{n} \\
n + k b &\equiv 0 \pmod{m}
\end{align*}
$$

This has a unique solution $k^*$ modulo $m n$ by the chinese remainder theorem
(we have $a < n$, and as $n$ is prime, $\gcd(a, n) = 1$; similarly $b$ and $m$),
and thus we can write:
$$
\begin{align*}
m + k^* a &\equiv 0 \pmod{mn} \\
n + k^* b &\equiv 0 \pmod{mn}
\end{align*}
$$
i.e., $m n \mid \gcd(m + k^* a, n + k^* b)$. Contradiction.


Show that a set is turing reducible to another set

The definition of Turing reducible, is that there exists a Turing reduction - an algorithm for $A+B$ that uses an oracle to $A$.
To understand this, you must first understand oracle machines. Those machines, are like turing machines, but can ask an "oracle" whether any $x$ is in $A$ or not, and would get an answer in $O(1)$, regardless of what $A$ is (doesn't even matter if it is not decidable!)
So, a turing reduction basically means that if you know for any $x$ whether its in $A$ or not in $A$, then you can decide whether a given $x$ is in $A+B$. Formally, this statement can be written as ${(A+B)}^A\in R$.
So basically the question asks you to show that ${(A+B)}^A,{(A+B)}^B\in R$


Are $\log_{10}(x)$ and $\log_2(x)$ in the same big-O class of functions?

Yes. Because they differ only by a constant factor. Remember high school math:

$\log_2 x = \dfrac{\log_{10} x}{\log_{10}2}$.


How to prove P = NP if problem Π ϵ NP-complete and Problem complement Πc ϵ NP?

Proving $NP=co-NP$ doesn't necessarily mean that $P=NP$. Although, the other way around is correct:
Assume $P=NP$, then $co-NP=co-P=P=NP$.


Analysis of algorithms, 'big O' question

There is no such formula. If there were, it would solve the halting problem, because we could take an algorithm (Turing machine), find its big-$\Theta$ complexity, then return true or false depending on if it was $\Theta (\infty)$.

For Big-O (upper bounds), there's technically a formula, since all functions are in $O(\infty)$. However, there's no way to find a tight upper bound, nor to test if an algorithm has a bound tighter than $O(\infty)$.

That said, there are certainly tools and heuristics for determining these things, as well as limited models of computation for which the problem is decidable.

For example, if you can express your routine using recursion, often you can find a recurrence relation for the running time, which you can solve to find the Big-O time. However, none of these techniques will work all the time.


What is a 'dynamic entity' in computer science?

There are no scientific term "dynamic entity", so meaning of this pair of words can be well stretched. In this particular case they could write something like "A computing system ... is a dynamic system", but apparently they didn't like the repetition, so they have decided to use a fuzzy word "entity". Also, there is a mathematical term Dynamical System, which doesn't have anything in common with what they are trying to say.

Essentially they mean that there is a lot of parts in a real computing system, which can change with time - hardware and software can be installed and uninstalled, software can be configured in many different ways, data comes into the system and gets out of it and so on. Sometimes even users and people, supporting a complex computing system, can be considered as a part of it.


At what point do electrical signals become actually logic and programmable language?

Most your questions are covered by the field of "Switching Circuits" (and more generally, "Circuits and Logic Design", which are both part of computer engineering.

Try to find a textbook on switching circuits: it will explain how to take transistors and create AND / OR / NOT gates out of them.
Then find a book on logic design: it will explain how to use AND/OR/NOT gates to build more sophisticated logic primitives such as flip-flops and latches (as well as adders, subtractors, or even a CPU)

Then you will (hopefully) have more insight regarding how the low-level works to realize the high-level ideas.


difference between lzw and huffman coding technique

Lempel–Ziv encoding (or rather, encodings, since there are many different variants) and Huffman coding are very different algorithms.

Huffman coding. Choose a block length, usually one byte. For each possible value of the block, we choose some bit string, so that no bit string is a prefix of another one (this is known as a prefix-free code). This choice is either fixed (like the JPEG Huffman code, which while in principle adaptive, is often fixed to some standard code) or adaptive (chosen according to the actual text being compressed). Each block is encoded by its bit string, and the results are concatenated.

The name Huffman code proper refers to the optimal choice of code given a distribution on the value of the blocks. Huffman code satisfy the following optimality property: if the source being compressed consists of i.i.d. copies of some distribution, then as the block length tends to infinity, the average number of bits used to encode one copy is the entropy of the source.

Lempel–Ziv encoding. Here the idea is to separate the input bits (instead of bits, we can choose longer blocks) into pieces, where each piece consists of an earlier piece plus an additional bit at the end. For example, the input 01011100010 can be partitioned as (0)(1)(01)(11)(00)(010). The idea is to encode each piece by referring to an earlier piece, including the additional bit. For example, if we number the pieces from 1, 0 being the empty piece, then the previous example could be encoded as (0,0)(0,1)(1,1)(2,1)(1,0)(3,0).

There are many different variants of Lempel–Ziv encoding. In particular, in practice we don't keep all earlier pieces in memory, and there is some specific encoding for the pairs (p,b) encoding the earlier piece and the new bit. Lempel–Ziv encoding is optimal for ergodic sources – the expected length of the compressed stream tends to the entropy.


Double, down facing arrow in operational semantics

The language of inference rules are much more general than what is usually given in Logic. Indeed you can look at systems with rules of the shape

$$ \frac{\Theta_1\ldots \Theta_n}{\Theta}$$

Where the $\Theta_i, \Theta$ are some kind of statement and ask: what are all the possible $\Theta$ I can get by repeated application of these rules?

In the above case, $s \vdash M \Downarrow P, s'$ expresses the statement:

  With starting state $s$, program $M$ evaluates to $P$ and the resulting state is $s'$.

This is a very general framework for expressing the operational semantics of a program, and it means that if you can build a finite derivation tree with $s \vdash M\Downarrow P, s'$ at the base, then you have shown that the program $M$ is well-defined and evaluates to $P$.

Let's give an example. Say $s$ is the state in which variable $b$ is sent to true and $n$ is sent to $2$, which I will write $\{b\mapsto \mathrm{true}, n\mapsto 2 \}$. Then the following should be derivable:

$$\{b\mapsto \mathrm{true}, n\mapsto 2 \}\vdash \mathrm{if}\ b\ \mathrm{then}\ n+1\ \mathrm{else}\ 0 \Downarrow 3, \{b\mapsto \mathrm{true}, n\mapsto 2 \}$$

Note that in your question, the rule:

$$\frac{s_0 \vdash M_1 \Downarrow P_1, s_1 \; ... \; s_{n-1} \vdash M_n \Downarrow P_n, s_n}{s_0 \vdash M \Downarrow P, s_n}$$

Means:

  If, starting from state $s_0$, $M_1$ reduces to $P_1$ and new state $s_1$, and starting with state $s_1$ $M_2$ reduces to $P_2$ and new state $s_2$ etc. then starting from state $s_0$, $M$ reduces to $P$ with new state $s_n$.

In particular, the order in which you do the reduction is important: the state may change after the evaluation of $M_1$, which in turn will influence the evaluation of $M_2$, etc. This is why in a language with state (side-effects), the order of evaluation of arguments passed to a function is important: we may get a different result depending on which argument we evaluate first.

In Haskell, laziness makes it impossible to know which arguments will be evaluated first (or at all!), so having side effects is pretty much out of the question.

I suggest reading the classic Types and Programming Languages, by Benjamin Pierce, which treats all of this in much detail.


If we allow numbers to be unbounded while keeping the unit cost model (each operation costs one unit), we get a very powerful machine. For example, here is how to solve 3SAT in this model. Recall that a 3CNF is a formula of the form

$$ (x_1 \lor \lnot x_2 \lor x_3) \land (x_1 \lor x_4 \lor \lnot x_5) \land \cdots. $$

Here $\lor$ is logical OR, $\land$ is logical AND, and $\lnot$ is logical NOT. The 3CNF is an AND of clauses, each of which is the OR of three literals; a literal is either a variable or its negation. The 3SAT problem asks whether a given 3CNF is satisfiable, that is, whether there is a truth assignment to the variables under which the formula evaluates to TRUE.

Suppose the given 3CNF has $n$ variables. For a formula $\varphi$, let $T(\varphi)$ be a "bit-vector" of length $2^n$, indexed by truth assignments to the variables, such that the bit at position $x$ is the truth value of $\varphi$ evaluated at the assignment $x$ (i.e. 1 if $\varphi$ is TRUE and 0 if $\varphi$ is FALSE). We order the truth assignments in lexicographic order; for example, if $n=2$ then the truth assignments are $(F,F),(F,T),(T,F),(T,T)$, given in the format $(x_2,x_1)$. Continuing the example, $T(x_1) = 1010$ and $T(x_2) = 1100$ (we read the bits from right to left), both in binary notation.

Consider now the following operations:

For each $i$, we can compute $T(x_i)$ as follows:
$$
\begin{align*}
T(x_i) &= \sum_{a=0}^{2^{i-1}-1} \sum_{b=0}^{2^{n-i}-1} 2^{2^i b + 2^{i-1} + a} \\ &= 2^{2^{i-1}} \sum_{a=0}^{2^{i-1}-1} 2^a \sum_{b=0}^{2^{n-i}-1} (2^{2^i})^b \\ &=
2^{2^{i-1}} (2^{2^{i-1}}-1) \frac{(2^{2^i})^{2^{n-i}}-1}{2^{2^i}-1} \\ &=
\frac{2^{2^{i-1}} (2^{2^{i-1}}-1)(2^{2^n}-1)}{2^{2^i}-1}.
\end{align*}
$$
Given $T(\alpha),T(\beta)$, we can compute $T(\lnot \alpha), T(\alpha\land\beta), T(\alpha\lor\beta)$ using bitwise NOT, AND, OR.

In this way, we can efficiently compute $T(\varphi)$, where $\varphi$ is the given 3CNF. The formula $\varphi$ is satisfiable iff $T(\varphi) \neq 0$. This gives a polynomial time algorithm for 3SAT in the unit cost model. Obviously something is wrong and needs fixing, which is what Tarjan is getting at.


Efficiently check if any vertex has a path to its partner vertex

Observation: Each weakly connected component can contain at most 1 cycle, and every vertex in such a cycle is reachable from every vertex in the weakly connected component.  That's because every vertex that participates in a cycle exhausts its single out-edge by connecting to the next vertex in the cycle, so the only other edges that can be incident on any vertex in this cycle must be in-edges from other vertices.

In more detail: Suppose to the contrary that a single component contains 2 cycles: Then either they are vertex-disjoint or not.  In the former case, there must be an undirected path of edges (i.e., a path in the graph where edge orientation has been forgotten) connecting the two cycles.  But the first and last edges in this undirected path must be "outwards" (i.e., the first must be an in-edge to the first cycle, and the last must be an in-edge to the second cycle), implying that some vertex on the path must have 2 out-edges, so this case cannot happen.  In the latter case, let the two cycles be $C_1$ and $C_2$, and w.l.o.g. suppose $|C_1| \geq |C_2|$.  Let $uv$ be an edge in $C_1$ such that $u \in C_1 \cap C_2$ but $v \notin C_2$.  (Such an edge must exist if $C_1 \neq C_2$.)  Then $u$ must have a successor $w \neq v$ in $C_2$; but this immediately implies that $u$ has outdegree at least 2, so this cannot happen either.

Algorithm phase 1: Detecting a cycle

So, starting at any vertex and successively traversing the single out-edge can only give one of two possible outcomes:

We reach a vertex with no out-edge.  In this case, the component has no cycle.
We reach a vertex we have seen before.  In this case, the component has a single cycle consisting of all vertices visited since the last time the final vertex was visited.  In a $k$-vertex component, the cycle vertices can be identified in $O(k)$ time by numbering the vertices in visitation order and gathering them together in a subsequent pass.

To simplify notation I'll label the vertices with positive and negative integers, instead of upper- and lower-case letters.  We will maintain a counter $c_i$ for each pair of vertices $i, -i$: at the end of the algorithm, $c_i = 2$ if and only if at least one of the vertices $i$ and $-i$ can reach the other by some path.

If a cycle was detected, we can start at any vertex in the cycle and continue following out-edges until we hit the first vertex again, incrementing $c_{|i|}$ for each vertex $i$ encountered.  Also, we (at least conceptually) create a new vertex $x$ to represent "the cycle", and as we proceed through each vertex $v$ in the cycle, we change every non-cycle edge $uv$ to $ux$.  (Conceptually) delete the cycle vertices, and set $z = x$.

If no cycle was detected, set $z$ to the last vertex we found, say $i$, which by construction has no out-edge.  Increment $c_i$.

Observe that since any cycle has been deleted, the component is now a tree with all edges directed toward $z$.

Algorithm phase 2: Reverse DFS

We now perform a DFS starting at $z$ and proceeding "against" the direction of each edge.  During this traversal:

Upon entering a vertex $i$: If $c_{|i|} < 2$, then increment it.
Upon leaving a vertex $i$: If $c_{|i|} = 1$, then decrement it.

This asymmetric increment/decrement scheme ensures that, whenever we discover a path from the root $z$ that contains both vertices in a pair, the discovery (which is recorded as a count of 2) "sticks", while OTOH whenever we discover that no path from the root $z$ through some vertex $i$ also contains $-i$, the discovery of $i$ is "forgotten" -- this has the important effect of not recording as matched any pair $i, -i$ that occur in the same component but such that neither is the ancestor of the other.

The above can all be implemented to take linear time in the number of edges within a component, so the overall time to process the graph is $O(|V|+|E|)$.


At the suggestion of Raphael, I have turned a previous comment into this answer.

It is not true that $O(f(n)) \subset \Theta(f(n))$. In fact, $\Theta(f(n)) = O(f(n)) \cap \Omega(f(n))$, by definition. So we have $\Theta(f(n)) \subset O(f(n))$.


Because - according to the rules above - each player must divide a stack into two stacks that must be unequal.


Why does SAT-UNSAT $\in NP \implies NP = coNP$

Suppose that $X$ is a coNP problem which is NP-hard.
Let $A$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction from $A$ to $X$. Since $X$ is in coNP, this shows that $A$ is in coNP.
We have shown that $\mathsf{NP} \subseteq \mathsf{coNP}$. Now suppose $B$ is in coNP. Then $\overline{B}$ is in NP, and so in coNP. Hence $B$ is in NP. This shows that also $\mathsf{coNP} \subseteq \mathsf{NP}$, and so $\mathsf{NP} = \mathsf{coNP}$.


Why is low-dimensional discrete representation of input space useful?

It may or may not be useful, depending upon the circumstances.

In some cases it can be useful as a visualization technique.  The representation is low-dimensional, and often 2-dimensional -- which means it can be visualized.  That said, there are many other methods of representing data in a low-dimensional space so it can be visualized, and it's not clear that self-organizing maps are the best way to do that.

Sometimes self-organizing maps are used as a general form of clustering, and can be useful anywhere that (unsupervised) clustering is useful.

That said, I agree with your general reaction.  Often, self-organizing maps aren't very useful.  I would not expect neural networks or other algorithms to benefit from being combined with self-organizing maps.  Self-organizing maps don't really solve any clearly defined problem, and probably aren't of all that much use in many/most practical situations.

If you had never heard of self-organizing maps, you probably wouldn't be missing much (in my personal opinion).


Why $\operatorname{gap-A}[1.5a, 1.5b + 1/4]$ has an efficient solution?

Given an instance $x$ of $\mathsf{gap\text{-}A}(1.5a,1.5b+1/4)$, calculate $y_x$ using the $a/b$ approximation algorithm, so that
$$
\frac{a}{b} opt(x) \leq val(y_x) \leq opt(x).
$$
If $opt(x) \geq 1.5b+1/4$ then
$$
val(y_x) \geq \frac{a}{b} (1.5b+1/4) > 1.5a.
$$
Conversely, if $opt(x) \leq 1.5a$ then
$$
val(y_x) \leq 1.5a.
$$
You take it from here.


Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

Why not give it the input of $\langle D,w\rangle$?

What's $w$? The machine $D$ is given some input, which it interprets as the coding of a Turing machine $M$. It's not given any $w$: only $\langle M\rangle$.

Imagine instead that you're given a function $f$ which is defined as $f(x)=x^x$. I ask you to calculate $f(10)$ and your question is a bit like asking, "Why does it have to be $10^{10}$?  Why can't it be $10^y$?"


Find all vertices that are included in a simple cycle through a fixed vertex in a directed graph

I believe the problem is NP-hard, by reduction from the two disjoint paths problem.
The two disjoint paths problem is as follows:

Given a directed graph $G$ and $(s_1,t_1),(s_2,t_2)$, find two paths $s_1 \leadsto t_1$ and $s_2 \leadsto t_2$ that are vertex-disjoint (they have no vertex in common).

This problem is NP-hard.
We can reduce two disjoint paths to your problem.  In particular, given $G$ and $(s_1,t_1),(s_2,t_2)$, we construct a new graph $G'$ by adding new vertices $v,v'$ and  adding edges $v \to s_1$, $t_1 \to v'$, $v' \to s_2$, $t_2 \to v$.
Notice that any pair of vertex-disjoint paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ will yield a simple cycle
$$v \to s_1 \leadsto t_1 \to v' \to s_2 \leadsto t_2 \to v.$$
Also, within any simple cycle $v \leadsto v' \leadsto v$ we can find simple paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ that are vertex-disjoint.  It follows that there exists a simple cycle $v \leadsto v' \leadsto v$ in $G'$ iff there exist two vertex-disjoint paths $s_1 \leadsto t_1$, $s_2 \leadsto t_2$ in $G$.  So, any algorithm for solving your problem would immediately yield an algorithm for solving the two disjoint paths problem.


Counting strings with balanced substrings

For a good string $s$ of length $k$, let $M(n,s)$ denote the number of strings of length $n$ terminating in $s$ in which every $k$-letter substring is good. The quantity $M(n,s)$ is given by the following recurrence:
$$
\begin{align}
&M(k,s) = 1 \\
&M(n+1,ta) = M(n+1,tb) = M(n,at) + M(n,bt) \\
&M(n+1,tc) = M(n,ct)
\end{align}
$$
Here $t$ is a string of length $k-1$. Summing over all good strings $s$, we can solve your problem.

Since $a$ and $b$ are really interchangeable, we can also consider a slightly different recurrence, in which $s$ only consists of $a$'s and $c$'s:
$$
\begin{align*}
&M'(k,s) = 2^{\#_a(s)} \\
&M'(n+1,ta) = 2M'(n,at) \\
&M'(n+1,tc) = M'(n,ct)
\end{align*}
$$
Here the second parameter is a "template" in which $a$ stands for either $a$ or $b$.

Using either recurrence, you can find explicit formulas for any given value of $k$.


Historical relation between computer science and the theory of dynamical systems

Yes there did seem to be historically a strong connection between study of dynamical systems and advanced theoretical computer science, that is shifted dramatically over time. Some of this has become mainstream and incorporated into more "core CS" (for example the empirical study of algorithms running on the SAT transition point and their strong thermodynamic/physics analogies, or empirically studied behavior of differential equations too difficult to solve exactly, etc) and some of it has moved into separate areas of more "applied" research, eg simulations of complex systems. Here are some refs on the history that might be helpful:

Chaos, the making of a new science by Gleick
Complexity, the emerging science at the edge of order and chaos by Waldrop


Regular languages closed under prefix operation

(1) If the regular language is given by a finite state automaton $M$ the language of prefixes can be obtaines by extending the set of accepting states. Choose all states that lie on a path from initial state to one of the original accepting states.
The prefix operation is a special case of the operation quotient
$K/L = \{ x \mid xy\in L, \text{ for some } y\in K\}$
where we take $L$ to be the language $A^*$ of all strings. Surprisingly, the regular languages are closed under quotient by arbitrary languages.
See are regular languages closed under division, and Closure against right quotient with a fixed language.
(2) If the regular language is given by a regular expression instead, then we can construct a new regular expression for the prefix language, directly using the inductive definition of regular expressions. See Regularity of “middles” of words from regular language.
(3) Also, there is a characterization in terms of Myhill-Nerode equivalence classes: a language is regular iff its number of equivalence classes is finite. In can be observed that $x \equiv_L y$ implies $x\equiv_{\text{pref }L} y$, so if $\equiv$ is of finite index, then so is $\equiv_{\text{pref }L}$.
More on this see Myhill-Nerode and closure properties.
(As Yuval noted, the exercise is somewhat standard, but I would like to have some remarks here to close the issue. Feel free to add relevant links.)


calculating a shortest path in a table structure that changes in real time

There are many; you can find a list here. The most applicable is probably D*-lite.

However, there are not many off-the-shelf implementations for it, so the vast majority of games just recalculate the best path using A*.  There are many visual and technical tricks for recalculating as infrequently as possible without negatively affecting the game, but that's more of a question for gamedev.stackexchange.com.

For NPCs in particular, you may also want to look into pathfinding with many units at once.  Some typical search-terms for this are "swarm pathfinding", "boids", "flocking behaviors", and "collision avoidance pathfinding"


In the spirit of "give a man a fish, and he'll be fed for a day; teach a man to fish, and he never need be hungry again", I'll share with you some problem-solving techniques that might be helpful for approaching this problem (and other problems) -- but I'm not going to spoil it for you by solving your exercise for you.

Technique #1:  If you don't know how to solve a problem, change the problem: look for "nearby"/"similar" problems you do know how to solve.  If you can't reduce SAT to the original language, is there some related/variant language you can reduce SAT to?  You may need to try multiple variants, and get a feeling for which ones you can easily find a reduction for and which ones you struggle with.  This may give you some intuition about what the barrier/difficult part of your problem is, which may help you identify what aspect to focus your energy on.

Hint #1 (possible spoilers):

   If you changed "less than or equal to w" to "equal to w", would the problem be any easier?  What if you changed it to "greater than or equal to w"?

Technique #2: You can chain reductions.  If you can reduce SAT to some variant, and reduce that variant to the original problem, you're in business.

Hint #2 (possible spoilers):

   It seems that short cycles are a headache.  If you have a graph $G$, can you think of some way to transform it to remove all short cycles (without changing whether or not it contains a cycle of length $w$)?  (If you can't immediately see how to do it, can you write out a precise specification of what such an algorithm would need to do?)

And that's as much as I'm going to say.  It's a good exercise, and it's your exercise, so you should have the chance to play around with it and discover a solution for yourself.  It's tricky but doable.


Assistance with Notation in the Paper Entitled: "Search Through Systematic Set Enumeration"

Please, one question per question.

The answer to your first question: No, prime most likely does not indicate complement, absent some specific indication of that.  It is just another variable.  $e$ is one variable; $e'$ is another variable (the author could have used a different letter, like $f$ or $x$ or something, but chose to use $e'$ instead).

The answer to your second question: The ind function is defined in the text immediately preceding the definition.  Read it again?

Yes, it's possible you might lack the necessary mathematical background.  You might try taking an online course (or working through a textbook) on discrete mathematics for computer science.


Efficient algorithm to find the nth number in a base-k numeral system with only different digits

Your problem is known as unranking permutations in lexicographic order.  Bonet, Efficient Algorithms to Rank and Unrank Permutations
in Lexicographic Order describes efficient algorithms, and contains some pointers to the literature.

As described in the paper, more efficient algorithms are possible if you don't insist on lexicographic order.


We can proof this claim by contradiction. If there exists an α-approximation algorithm for Vertex Cover, we will be able to use it for solving SAT problem in polynomial time and it's a contradiction by giving P≠NP.

We assume that there exists a gap introducing reduction that converts an instance of SAT to an instance of Vertex Cover giving:

• if φ is satisfiable, OPT(VC) ≤ 2/3 * |V|, and

• if φ is not satisfiable, OPT(VC) > α * 2/3 * |V|.

We can use this reduction and convert φ to I(VC) in polynomial time, then use the α-approximation algorithm for Vertex Cover in polynomial time and calculate objective function value (we call it f) for it.

As we know value of f stands between two bounds:

OPT(VC) ≤ f ≤ α*OPT(VC)

After that, we can use f to make a decision about φ satisfaction state:

If f ≤ α * 2/3 * |V|, then yes, else no.

We claim that if f is less than α * 2/3 * |V|, φ should be satisfiable because if φ isn't satisfiable, f can't be less than α * 2/3 * |V| which is lower bound to OPT(VC) (according to reduction assumptions) and objective function value can't be less than optimum.

Also we claim that if f is greater than α * 2/3 * |V|, φ shouldn't be satisfiable because if φ is satisfiable, it violates the approximation inequality. (f ≤ α*OPT(VC))


Expected number of independent sets of size $k$ in random graph $G(n,p)$

The probability that a specific set of size $k$ is independent is exactly $(1-p)^{\binom{k}{2}}$ (why?). Linearity of expectation shows that the expected number of independent sets of size $k$ is $\binom{n}{k} (1-p)^{\binom{k}{2}}$ (why?).

If you can't follow this calculation, please follow Denis Pankratov's advice and look up linearity of expectation and indicator random variables.


This variant decreases number of main loop passes by factor of 2, but in return loop body uses twice workload.
Since the change is minor, you can simply read complexity from basic selection sort.

The selection sort has this property that number of swaps is at most $n$, finding element to its proper place, so it takes $\mathcal O(n)$ swaps in the worst case. There is no mechanism to ignore swaps or detect sortedness, two loops are passing through every element, so we can simply infer that best case is equal worst case and equal average case.
Two nested loops with arithmetic progression (array elements to be viewed decrease by one each step) $\sum_{i=1}^{n-1}i = \frac{1}{2}(n^2-n)$ are now decreased, giving $\frac{1}{4}(n^2-n)$, so still $\mathcal O(n^2)$ for all cases.


What is a non-contrived example of static type-checking being too conservative?

I've always viewed it more as a matter of convenience, than about whether an algorithm can or can not be expressed at all.  If I really wanted to run programs like Mitchell's contrived one, I'd just write the appropriate Turing Machine simulator in my statically typed language.

The trick with a static type system is to offer the right kinds of flexibility just for the cases where the flexibility allows you to write code that is more easily maintainable.

Here's some examples of program structuring techniques that are sometimes thought to be easier to manage in dynamically than statically typed languages.

Generics and Containers

In statically typed languages before ML (c. 1973) and CLU (c. 1974) it was not difficult to create a red-black tree of strings, a red-black tree of integers, a red-black tree of floats, or a red-black tree of elements of specific type Foo.  It was, however, difficult (maybe impossible) to create a single implementation of a red-black tree that was both statically checked and which could handle any one of these data types.  The ways around the problem were (1) to break out of the type system completely (for example: by using void * in C), (2) to write yourself some kind of macro preprocessor and then write macros that produce the code for each specific type you want or (3) use the Lisp/Smalltalk (and Java) approach of checking the type of the extracted object dynamically.

ML and CLU introduced the notion of, respectively, inferred and explicitly declared (static) parameterized types, which allow you to write generic, statically typed, container types.

Subtype Polymorphism

In statically typed languages before Simula67 (c. 1967) and Hope (c. 1977) it was not possible to both do dynamic dispatch and statically check that you had covered the case for every subtype.  Many languages had some form of tagged unions, but it was the responsibility of the programmer to make sure that their case or switch statements, or their jump tables, covered every possible tag.

Languages following the Simula model (C++, Java, C#, Eiffel) provide abstract classes with subclassing where the compiler can check that each subclass has implemented all the methods declared by the parent class.  Languages following the Hope model (all the ML variants, from SML/NJ through Haskell) have algebraic subtypes where the compiler can check that every typecase statement covers all the subtypes.

Monkey Patching and Aspect Oriented Programming

Dynamic type systems make a variety of prototyping techniques much easier.  In languages where types are represented by hash maps from strings to functions (e.g., Python, Javascript, Ruby) it is quite easy to globally change the behavior of every module that relies on a particular type, simply by dynamically modifying the hash map representing that type.

While there are obvious ways in which monkey patching can be used to make programs harder to maintain, there are also ways in which it can actually be used for "good" rather than "evil".  In particular with aspect oriented programming one can use monkey-patching like techniques to do things like modify the file type to point to a virtualized file system, permitting the construction of unit-testing infrastructures for "free", or modify simple exception types so they print log messages every time they are caught for better debuggability.

Unlike Generics and Subtype Polymorphism where the key static checking ideas were available in the 1970s, static checking for aspect oriented programming is (I think) an active research area.  I don't know much about it except that there's a language called AspectJ since about 2001.


Theoretical CS and Math - self-study recommendations

Your list is extremely problematic.

To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a theoretical researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced topics in logic, whereas you only need to know very basic logic.

Out of books 1,2,3, I would choose just one to serve as a general introduction to mathematics and proofs.

Books 5,7,8,9,10,13 cover several subjects: automata theory, algorithms, and complexity theory. Let me suggest that you follow Sipser (Book 7) for automata theory and complexity theory, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein ("CLRS") for algorithms.

Book 4 deals with functional programming. While my computer science education has never included any courses on this subject, it is fair to say that many researchers in theoretical computer science count functional programming as part of the essential foundations.

Summarizing: what you remain with is

One of books 1-3 (or any comparable "introduction to proof" text)
CLRS
Book 4 (functional programming)
Book 7 (automata theory and complexity theory)


Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance

The following assumes that you can store words in $O(1)$ space and compare them in $O(1)$ time.

For each letter $\ell$ keep:

The number of appearances $n_\ell$  of the word starting with $\ell$ that appears the least amount of times.
A list $L_\ell$ of words starting with $\ell$ that appeared $n_\ell$ times, in lexicographic order.
A list $R_\ell$ of words starting with $\ell$ that appeared $n_\ell + 1$ times and are smaller than the first word in $L_\ell$, in lexicographic order.
A sorted list $S_\ell$ of pairs $(n_w, w)$, where $w$ is a word starting with $\ell$ that appears $n_w \ge n_\ell+1$ times and is not in $R_\ell$. The pairs are sorted in lexicographic order.

Notice that you can construct everything above in $O(n \log n)$ overall time for all the letters $\ell$.

When you have to return a word starting with letter $\ell$, do the following:

Remove the first word $w^*$ from $L_\ell$ and output it.
Insert $w^*$ into $R_\ell$.
Insert all the words $w$ from a pair $(n_w, w)$ of $S_\ell$ such that (i) $n_w = n_\ell + 1$, and (ii) $w$ precedes the smallest word of $L_\ell$, into $R_\ell$. Delete the corresponding pairs from $S_\ell$. Notice that these are always the first elements in $S_\ell$. If $L_\ell$ is empty, then ignore constraint (ii).
If $L_\ell$ is empty, increase $n_\ell$ by 1, swap $R_\ell$ and $L_\ell$, and repeat step 3.

Steps 1, 2, and 4 can be performed in constant time. Step 3 requires a constant amount of time, plus a time proportional to the number of words $w$ moved from $S_\ell$ into $R_\ell$. This second term is upper bounded by $O(n)$ across all letters as this is an upper bound on the number of pairs contained in all $S_\ell$.


How to solve Tower of Hanoi iteratively?

You can transform the recursive solution to an iterative solution. To do this, create a stack that will contain items consisting of quadruples ("from", "to", "via", "num_disks"). For every function "call" in your recursive algorithm, push the parameters to a stack in the iterative algorithm. For every function "return" in your recursive algorithm, pop the parameters from the stack in the iterative algorithm.

Wikipedia has the complete iterative solution.


Is Morse code without spaces uniquely decipherable?


How to prove a set has infinite cardinality?

A general way of showing this is proof by contradiction.

Assume (towards a contradiction) that the given set $S$ is finite, i.e.

$\qquad S = \{s_1, \dots, s_n\}$.
Show that there is an element $s \in S$ but for which $s \neq s_i$ for all $i \in [1..n]$.

One way to do this is to construct $s$ from $s_1, \dots, s_n$ explicity; that would be an instance of a diagonal argument.
Above step provides a contradiction, hence the assumption must be false: $S$ does not have this form.

Important: This only works if you make no assumptions whatsoever about the $s_i$ and $n$ (beyond what you know about $S$ already). If you do, you have not argued against all finite candidates for $S$.

Example

Show that $\mathbb{N}$ is infinite.

   Assume the opposite. Then, $\mathbb{N} = \{n_1, \dots, n_N\}$ for some $N$. Let $n = \max \mathbb{N}$. Then, by the definition of the natural numbers, $n+1 \in \mathbb{N}$ as well. But that contradicts that $n$ is the largest number in $\mathbb{N}$; the assumption must be false.


A Yuval said, you can just go ahead with any algorithm. In fact, you should probably be able to find a solution by trial and error.

In case you are stuck for some time, move your mouse over to see a solution below.

   We can use Prim's algorithm, which iteratively selects an edge of the least weight from the available edges as long as it does not introduce a cycle.

 We will select the edge of weight 1, two edges of weight 2, all edges of weight 3,4,5,6,7 respectively. We will skip the vertical edge of weight 8 since it introduces a cycle. We will select the horizontal edge of weight 8. Now all vertices have been included except the bottom left one. So we will select the edge of weight 12 to connect vertex.

 The total weight is 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 12 = 50. So the answer should be "none of the listed".


Average number of exchanges during first partition stage in Quicksort

The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort.
Here is the situation. There are $n$ numbers that are non-equal pairwise. Array $a=(a_0, a_1, \cdots, a_{n-1})$ is a uniformly-random permutation of those $n$ numbers. We will run the method partition(a, 0, n-1). What is the number of exchanges executed inside the loop while(true)? (Note that the exchange exch(a, lo, j) outside the loop is not counted.)
WLOG, let the $n$ numbers be $1, 2, \cdots, n$.
Suppose the first element of $a$ is $p$ (for pivot). Excluding that first element, split $a$ into one segment of $p-1$ numbers followed by another segment of $n-p$ numbers.
$$a = (p,\ \underbrace{a_1,\ a_2,\ \cdots,\ a_{p-1},}_{p-1\text{ numbers}}\ \ \underbrace{a_p,\ a_{p+1},\ \cdots\ a_{n-1}}_{n-p\text{ numbers}})$$
Observe the number of elements greater than $p$ in the front segment is always the same as the number of elements smaller than $p$ in the back segment. (Proof: let the two numbers be $x$ and $y$ respectively. The total number of elements greater than $p$ in $a$ is $x + ( n-p-y)$. On the other hand, the total number of numbers greater than $p$, which are $p+1, p+2, \cdots, n$, is $n-p$. That means, $x+(n-p-y)=n-p$, which means $x=y$.)
In the while loop of partition(a, 0, n-1), the first element greater than $p$ in the front segment is exchanged with the last element smaller than $p$ in the back segment. Then the second element greater than $p$ in the front segment is exchanged with the second last element smaller than $p$ in the back segment. And so on, until we have exhausted elements greater than $p$ in the front segment (and, in the meantime, we have exhausted elements smaller than $p$ in the back segment as well). So the number of exchanges made is equal to the number of elements greater than $p$ in the front segment.
To calculate the average number of exchanges made, let us run partition(a, 0, n-1) as $a$ ranges over all permutations of $1, 2, \cdots, n$. Then
$$\text{total number of exchanges}=\sum_{p=1}^n\sum_{a_0=p}\text{number of exchanges on }a\\
=\sum_{p=1}^n\sum_{x}^{}x\cdot(\text{number of permutations that starts with }p\text{
 with }x\text{ exchanges performed})$$
As we have explained above, for a permutation that starts with $p$, $x$ exchanges will be performed on it if and only if that permutation has $x$ elements greater than $p$ in its front segment of $p-1$ elements. The number of such kind of permutations is the product of the following four factors.
$$
\underbrace{\binom{n-p}{x}}_{\text{the number of ways to choose }\quad\ \  \\x\text{ elements out of all }n-p\\\text{numbers that are greater than }\ \\p \text{ for the front segment}}
\underbrace{\binom{p-1}{p-1-x}}_{\text{the number of ways to chose }\\p-1-x\text{ elements out of all}\\p-1 \text{ numbers that are smaller }\quad\ \ \\\text{than }p\text{ for the front segment}}
\underbrace{(p-1)!}_{\text{the number of ways}\\\text{to permute all }p-1\\\text{elements in the}\\\text{front segment}}\quad\ \
\underbrace{(n-p)!}_{\text{the number of ways}\\\text{to permute all }\\n-p\text{ elements in}\\\text{the back segment}}\\
$$
So,
$$\begin{aligned}&\quad\text{total number of exchanges}\\
&=\sum_{p=1}^n\sum_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}(p-1)!(n-p)!\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!\sum_{x=0}^{\min(n-p, p-1)}x\binom{n-p}{x}\binom{p-1}{p-1-x}\right)\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!\sum_{x=1}^{\min(n-p, p-1)}(n-p)\binom{n-p-1}{x-1}\binom{p-1}{p-1-x}\right)\\
&=\sum_{p=1}^n\left((p-1)!(n-p)!(n-p)\sum_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\right)\\
&\stackrel{\bigstar}{=}\sum_{p=1}^n(p-1)!(n-p)!(n-p)\binom{n-2}{p-2}\\
&=\sum_{p=1}^n(p-1)(n-p)(n-2)!\\
&=(n-2)!\left((n+1)\sum_{p=1}^np-\sum_{p=1}^nn-\sum_{p=1}^np^2\right)\\
&=(n-2)!\left((n+1)\frac{n(n+1)}2-n^2-\frac{n(n+1)(2n+1)}6\right)\\
&=n-2)!\,\frac{n(n-1)(n-2)}6=n!\,\frac{n-2}6.\\
\end{aligned}$$
The average number of exchanges is
$$\frac{\text{total number of exchanges}}{\text{number of permutations}}
=\frac n6-\frac13 \color{#d0d0d0}{\quad\text{for } n\ge2}.$$

You might wonder the equality above that is marked with a $\bigstar$. It can be established by splitting into two cases, when $n-p-1\lt p-2$ and when $n-p-1\ge p-2$, and then using Vandermonde's identity.

Another way to prove it uniformly is to rewrite the Vandermonde's identity as, for any
non-negative integer $m, n, k$,
$$\sum_{r=-\infty}^{\infty}\binom{m}{k}\binom{n}{r-k}=\binom{m+n}{r},$$
where we extend the definition of the binomial coefficient $\binom nk$ so that for all $n\ge0$ we have $\binom nk=0$ for all $k\lt 0$ or $k\gt n$. Note that the summation on the left-hand-side ranges is well-defined, since it contains, in fact, only finitely many non-zero items. We have,
$$\sum_{y=0}^{\min(n-p-1, p-2)}\binom{n-p-1}{y}\binom{p-1}{p-2-y}=\sum_{y=-\infty}^{\infty}\binom{n-p-1}{y}\binom{p-1}{p-2-y}\\=\binom{(n-p-1)+(p-1)}{y+(p-2-y)}=\binom{n-2}{p-2}.$$


How can merging two sorted arrays of N items require at least 2N - 1 comparisons in every case?

What is meant by "lower bound" in this case is a lower bound on the worst-case number of comparisons. In this case, it happens to also be an upper bound.

  The lower bound has to be something that is true for every possible N and every possible combination of elements in both arrays, right? 2*N* - 1 seems more like it would be the upper bound since there is no way there can be more comparisons than that.

No, it just needs to be true for some input (for infinitely many N).

For example, when we say that $\Omega(n \log n)$ is a lower bound for sorting, this does not mean that every array requires $\Omega(n\log n)$ comparisons. It just means that some arrays require that many comparisons, and thus there is no $o(n\log n)$-time algorithm for sorting.


"The Annotated Turing" on listing all binary numbers between 0 and 1

You haven't shown the full proof, but it most likely has the form "Assume that the set is countable.  Consider any enumeration.  Then (blah-blah-blah) shows that there is a number not in the enumeration.  That's a contradiction, so our assumption must have been wrong."
If that's the structure of the proof, then pointing out that the proof appears to say two contradictory things is not a surprise; that's entirely the point of the line of reasoning, to show that if you start with a particular assumption, you reach absurd results.
What's actually true?  The truth: that list doesn't actually contain all the real numbers.  Assuming that it does is a faulty assumption.
It's possible that the text could have been written a little more carefully to caveat that the statement about it containing all numbers; but oh well, no one's perfect.  Books written for a popular audience, in particular, aren't always the best source if you want a precise and careful proof of a mathematical theorem.


Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU?

When you are using two processors, not every task your GPU's encounter is parallel by nature. There are a certain portion of tasks which are strictly serial, and can be processed by only one processor at a given time.

If a set of tasks were to be 100% parallel your dual GPU set up should give double the speed (in theory).

A little mathematics for you: Ahmdal's law for speedup is given by

$$S = \frac{1}{[B+\frac{(1-B)}{n}]}$$, where B is the percentage of tasks that is serial in nature, n is the number of processors and S is the speedup.

Put B=0 and you wil get S, ie Speedup=2.

Practically dual GPU gives us maximum 80% speedup.


Hint: rewrite $L$ as $L = \{a^p b^r b^q c^s d^t d^q e^r e^p \mid p,q,r,s \ge 0, s>t\}$.

Does $L$ now look like something you can generate with a CFG?


Is the infinite language unrecognizable in a Turing machine?

I'm a bit confused by your question: you're asking if the Turing machine is recognizable, but I think you mean to ask if the language $\{1^x \mid x \in \mathbb{N}\}$ is recognizable.

A language is recognizable if and only if we can build a Turing machine that accepts every string in the language, and does not accept any string not in the language. And we can indeed build a Turing machine that does this!

Algorithm:
    Check the number under the head.
    If it's 0, fail.
    If it's the end of the string, accept.
    If it's 1, move to the right and repeat.

The key is, while there's no upper limit, $x$ has to be a natural number—and $\infty$ is not a natural number. In other words, while $x$ can be arbitrarily large, it has to have some finite value. It can't actually be $\infty$.


algorithm to find shortest path connecting EVERY node

There is no polynomial-time algorithm for your problem unless $P=NP$, since it captures the Hamiltonian path problem as a special case.
Moreover, unless the exponential time hypothesis fails, there is no $2^{o(n)}$-time algorithm for your problem, where $n$ is the number of vertices.


Can a $k$-ary relation have polymorphisms of arity greater than $k$?

Let's say that there's a [$k$-ary] relation $R$ and [$m$-ary] function $f$ such that $m>k$. Is $f$ a polymorphism of $R$?

Maybe, maybe not: it depends on the function and the relation.  A given $k$-ary relation may have polymorphisms of arity arity less than, equal to, and/or greater than $k$. In fact, every relation has polymorphisms of all arities. For example, the ($1$-ary) identity function is a polymorphism of every relation, as are the projection functions $f_\ell(x_1, \dots, x_m) = x_\ell$ for all $1\leq \ell\leq m$. (Exercise: check these examples.) Notice that the identity function is just the case $\ell=m=1$.

  Concrete example: Assuming an $\wedge$ relation $\{ (1,1) \}$ (i.e. arity is 2), is the majority function $f(a,b,c) = (a \wedge b) \vee (a \wedge c) \vee (b \wedge c)$ a polymorphism of this relation?

Check the definition! $f$ is a polymorphism of $R_\land = \{(1,1)\}$ if, and only if, for all $(x_1,x_2),(y_1,y_2),(z_1,z_2)\in R_\land$, we have $(f(x_1,y_1,z_1),f(x_2,y_2,z_2))\in R_\land$. Well, the only tuple in $R_\land$ is $(1,1)$, so we only care about the case $x_1=y_1=z_1=x_2=y_2=z_2=1$. And we see that $f(1,1,1)=1$, so $(f(1,1,1),f(1,1,1))\in R_\land$, so $f$ is, indeed, a polymorphism of $R_\land$. Further, by exactly the same argument, any function such that $f(1, \dots, 1) = 1$ is a polymorphism of $R_\land$.

The polymorphism property is often represented as a table: given a $k$-ary relation $R$ and an $m$-ary function $f$, we can write

$$\begin{matrix}
    (t_{1,1} & t_{1,2} & \cdots & t_{1,k}) & \in R\\
    (t_{2,1} & t_{2,2} & \cdots & t_{2,k}) & \in R\\
    \vdots   & \vdots  & \ddots & \vdots   & \\
    (t_{m,1} & t_{m,2} & \cdots & t_{m,k}) & \in R\\
\hline
    (f(t_{1,1}, \dots, t_{m,1}) & f(t_{1,2}, \dots, t_{m,2}) &\cdots & f(t_{1,k}, \dots, t_{m,k})) &\in R
\end{matrix}$$

The meaning is that we require that, whenever the tuples above the line are in $R$, the tuple below the line must also be in $R$.  Notice that nothing in the structure of the table requires any relation between $k$ and $m$: the property could hold (or not hold) for a relation of any arity and a function of any arity.  It's just required that, whenever we write a collection of tuples in $R$ and "apply $f$ to each column", the resulting tuple is always still in $R$.


Why is it hard to show that the euclidean Steiner tree problem is in NP?

I'm guessing the difficulty lies in the fact that euclidean distance is involved, and we don't know if comparing sums of integrer square roots is in NP.
The problem is the following: for integers $a_1, \ldots a_n$ and $b_1, \ldots b_m$, is $\sum\sqrt{a_i} < \sum\sqrt{b_j}$?
This is not known to be in NP and is a major barrier in adapting a lot of computational geometry algorithms from the Real-RAM model to Word-RAM.


Weighted Matching with multiple assignments and min assignments

Your problem can be solved with minimum-cost network flow, by solving a circulation problem.  The circulation problem is a variation on network flow where edges have an upper bound on the amount of flow through that edge (called the capacity of the edge), a lower bound on the amount of flow through the edge, and a per-unit cost for sending flow through the edge.  In your problem, you have a source vertex $s$, a vertex $v_i$ for each professor, a vertex $w_j$ for each student, and a sink vertex $t$.  You have edges $s \to v_i$, $v_i \to w_j$, and $w_j \to t$.  You put a lower bound on the edge $s \to v_i$ corresponding to the number of students who professor $i$ must be matched with, an upper bound of $1$ on each edge $v_i \to w_j$, and a cost on the edge $v_i \to w_j$ that corresponds to the negative of the weight.  There exist polynomial-time algorithms to solve this variant of network flow.


Your objective-function seems to only concern inventory (that's the only variable aspect of your problem). Indeed $\sum x_i =12345$ is constant, your profit, excluding inventory cost, will be $5$ times this in any case ($12 - 7$). Your objective can be written more simply as $\min \sum y_i$

$b_i=\max\{0, d_i-x_i-y_{i-1}\}$ and $y_i=\max\{0, x_i+y_{i-1}-d_i\}$ should be the additional constraints.
If production + previous inventory is not enough to satisfy demand, you get a backlog at period $i$ and inventory at $i$ is what remains after satisfying the current demand with the current production + previous inventory.

So $b_i\geq d_i-x_i-y_{i-1}$ and $y_i\geq x_i+y_{i-1}-d_i$ should do.

Since $y_i$ are to be minimized, these variables would equal their lowest feasible bound ($0$ or the difference above).

You will just pay $\$2$ for every unit you produce above demand on a given period. However, from an inventory management point of view, the cost of inventory in your model seems unusually simplistic. A more realistic cost for inventory would consider a holding/carrying cost (cost of holding one unit of inventory for one unit of time) and an ordering cost (cost of ordering raw material or components). The difficulty of inventory problems is typically determining when and how much to order to find the best trade-off between these two costs.

PS. It may make sense at the aggregate level, and intermediate-planning time horizon, to make such a simplification regarding inventory costs. However, aggregate planning and inventory management are two strategic problems in their own rights, over two different time-horizons. They cannot be easily solved by one simple, integrated model (mostly because of different levels of uncertainty in demand over the two time-horizons and at the aggregate vs individual level).


To what extent is an x86 machine equivalent to a Turing Machine?

The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine.

As I explained before, the idea of 'the set of decidable computations' is a category error.  Decidability is a property of formal languages (or equivalently, of decision problems), not of computations.  So, no, the statement in the second paragraph of your question is not correct.  It's not even wrong -- it is neither true nor false.

I suspect that perhaps you have found a statement of the Church-Turing thesis that is worded in a way that is confusing.  I suggest reading a standard reference on the Church-Turing thesis, and don't rely solely on the wording you have bolded.

It is true that every decision problem that can be solved by an x86 machine can be solved by a Turing machine (or, equivalently, every language that can be decided by an x86 machine can be decided by a Turing machine).  This is true because you can program a Turing machine to simulate the behavior of an x86 machine.  However, the converse is not the case: any real x86 machine has a fixed and finite amount of memory, while a Turing machine can use an unlimited amount of storage on its tape, so there are decision problems that can be solved by a Turing machine, but not by an x86 machine.  (Even if we take into account the amount of storage provided by disks, disks use fixed-length addresses, so there is a fixed and finite upper bound on the maximum amount of disk storage that can be addressed from a standard x86 machine.)

If you wanted an x86 machine to be equivalent in power to a Turing machine, you'd have to provide some way to extend its amount of storage without limits.  If you had a way to do that, then yes, any decision problem that can be decided by one could be decided by the other: each one could simulate the other.


Computer Science and Programming for a complete novice

I started progamming as a kid and (at adulthood) graduated in Computer Science. I really don't know what's the best to learn first.

Computer Science is a breed of mathematics and programming is a craftworking. To implement the ideas of the first you must use the second.

IMHO programming is something you learn by demand while CS is a knowledge you study by passion.

The modern languages today (C#, Java, Javascript) are complex tools of trade and one learning it must dive in to learn it idiosyncracies (and not to mention the libraries and frameworks like jQuery, Hibernate, etc).

So while you are not willing to become a pro programmer I can advice you to use more "crude" languages like C||C++.

To get start in CS go to the basics: Algorithms.

There are a lot of classical and well studied problems like sorting, path finding/evalutaion, finding substring, etc.

While studing these problems you can learn how to implement some know solutions again IMHO that's can the best approach to get starting.


Can all Turing-computable problems be solved with a machine with finite tape and infinite controls?

Assuming the tape is always made long enough to hold the input, then infinite control allows you to decide any language at all. The infinite control can just contain one state for each possible string that's been read so far. When it reaches the end of the input, it can accept or reject as appropriate.


Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2

Your approach is to try every possible $x$ and $y$ and see if $x^2+y^2=n^2$. However, $n$ is fixed and, for any $x$, either $n^2-x^2$ is a perfect square or it isn't. You can calculate what $y$ is, instead of looping and trying every possible value.

Actual code is off-topic but it's confusing that you're trying to solve a problem about $x$ and $y$, but you've represented those quantities in variables called i and j. And even worse that you have a variable called x that represents something else entirely. (In fact, I'm not sure it's even correct. You seem to be using x to avoid reporting, e.g., $x=3$, $y=4$ and $x=4$, $y=3$ as separate solutions for $n=5$. But they are separate solutions and the question, at least as you've summarized it, doesn't say that they should be counted as the same.)


Reductions where the number of certificates from one problem can be computed for another to varying degrees

Parsimonious reduction.
Polynomial-time Turing reduction (a.k.a. Cook reduction).
Polynomial-time many-one reduction (a.k.a. Karp reduction).

I've not come across cardinality restrictions of the form you mention in (2) so I don't know any name for them. If you find there isn't a name already, "monotone" would be a good one to choose.  In the case where the number of solutions to $B$ is less than $A$, you need "less than or equal to" since, if $A$ has exactly one solution, you still need to reduct it to a "yes" instance of $B$.


How to reconstruct the image from a neural network output?

You can't necessarily use the output of a neural network to reconstruct the image, like you want.  The output signals indicate how the neural network has classified the input image.  Beyond that, they don't necessarily have any interpretation as a representation of the original image.  There isn't necessarily any way to do what you want (to reconstruct the image given the output of the neural network), as this kind of neural network inherently throws away information.

Are you familiar with the notion of training "autoencoders"?  One way to train multi-layer neural networks is by building a series of auto-encoders: e.g., to construct the weights for the first layer, you train a 2-layer autoencoder, then throw away the second layer of the autoencoder and use the first layer of the autoencoder as the first layer of your neural network.  You repeatedly do this for each layer of your network.  Autoencoders do reconstruct the original input, so if you're training each layer of the neural network in this way, then you automatically have a way to reconstruct (an approximation to) the original input from the signals at any layer -- if you saved the entire autoencoder at each stage.  However, if your real end goal is to understand why an image was classified a certain way or debug your neural network, I expect this probably won't be helpful for that.

I'm not 100% sure what your real goal is.  You mention "test each solution for fitness", but I'm not sure what you meant by that.  However, my guess is that your best bet will be to figure out what your real goal is, and then ask about how to achieve that goal (which might not be by trying to reconstruct the original image).


feature selection in decision tree classifier

This depends on your application but the trend is to use Deep Learning.  That is, allow the algorithm to learn the features as opposed to do feature engineering (e.g. choose between BOW, n-gram etc).

See for example this paper (Gender Classification with Deep Learning by Aric Bartle, Jim Zheng) where they compare the performance of BOW/n-gram/vs Deep Learning via Recurrent Convolutional Networks.   Deep Learning generally outperforms classic feature engineering.

https://cs224d.stanford.edu/reports/BartleAric.pdf


Would the following grammar be ambiguous?

Indeed, both of those derivations produce the same parse tree.

A grammar is ambiguous iff it has two different leftmost derivations for a sentence. (Equivalently, if it has two different rightmost derivations.) Only one of the provided derivations is leftmost, so these two derivations do not constitute a demonstration of ambiguity.

The grammar is ambiguous, though:

$$\begin{align}&S\to aSbS \to abS \to abaSbS\to ababS \to abab\\
&S\to aSbS \to abSaSbS \to abaSbS \to ababS \to abab\\
\end{align}$$