Algorithms for minimizing Moore automata

The original DFA minimization algorithm was actually designed for Moore Machines, guided by their apparently more observable behavior.
But the algorithm presented here is a reconstruction from the DFA minimization,
since I discovered the historical evidence after the fact.

After Wikipedia (with some notational changes):

  A Moore machine can be defined as a 6-tuple $(Q, q_0, \Sigma, \Pi, \delta, \gamma)$ consisting of the following:

  a finite set of states $Q$
  a start state (also called initial state) $q_0$ which is an element of $Q$
  a finite set called the input alphabet $\Sigma$
  a finite set called the output alphabet $\Lambda$
  a transition function $\delta : Q \times \Sigma \rightarrow Q$ mapping a state and the input alphabet to the next state
  an output function $\gamma : Q \rightarrow \Pi$ mapping each state to the output alphabet

From this definition, a Moore machine is a deterministic finite state
transducer.

I have no reference for minimization of Moore automata. However it
seems not too hard to imagine an algorithm, derived from the algorithm used for
deterministic finite state automata.

The idea in DFA minimization is based on the Myhill-Nerode
characterization of regular languages.

  Given a language $L$, and a pair of strings $x$ and $y$, define a
    distinguishing extension to be a string $z$ such that exactly one of
    the two strings $xz$ and $yz$ belongs to $L$. Define a relation
    $R_L$ on strings by the rule that $x R_L y$ iff there is no
    distinguishing extension for $x$ and $y$. It is easy to show that
    $R_L$ is an equivalence relation on strings, and thus it divides the
    set of all strings into equivalence classes.

  The Myhill-Nerode theorem states that $L$ is regular if and only if
    $R_L$ has a finite number of equivalence classes, and moreover that
    the number of states in the smallest deterministic finite automaton
    (DFA) recognizing $L$ is equal to the number of equivalence classes
    in $R_L$.

Indeed each state $q$ of the smallest DFA is such that $W_q$ as
defined above is one of the equivalence classes for the relation $R_L$.

For a non-minimal DFA for the regular language $L$,
it is easy to show that each set $W_q$ contains
strings that all belong to a same equivalent class with respect to
$R_L$.

Hence, the minimization of the DFA actually consists of merging states
(considered as sets of equivalent strings), whenever it is shown that
two distinct states contain equivalent strings.

Two reasonably fast algorithms exists for that purpose, Moore
algorithm (1956) which is in time $O(n^2)$ and Hopcroft's algorithm
(1971) in time $O(n\log n)$.

The extension to Moore automata is best understood in redefining the
equivalence relation as $R_T$ for a transducer $T$. The relation $R_L$
was concerned with whether future input would lead equivalently to an
accepting state. The $R_T$ equivalence relation of Moore automata is
concerned with whether future input will produce the same output.

Hence, given a transducer $T$, and two strings $x$ and $y$, we define a
distinguishing extension to be a string $z$ such that $T(xz)=T(x)u$
and $T(yz)=T(y)v$ with $u\neq v$, i.e. such that the output behaviour
of the transducer differs for $z$ depending on whther it is following
$x$ or $y$.

Again, $R_T$ is an equivalence relation, dividing all strings in
$\Sigma^*$ into equivalence classes. In the case of a Moore machine,
these classes will again correspond to state of the minimal
transducer.

The following algorithm mimics the Moore algorithm for DFA minimisation.

We define an initial partition $\mathcal P$ of $Q$  into classes of states $S_e$ as follow:

$\forall e\in\Pi:\; S_e=\{q\in Q\mid \gamma(q)=e\}$

Then we split the classes in $\mathcal P$ as follows:

repeat successively for each class of states $S$, until none
  changes
$\ \ $ repeat $\forall a\in\Sigma,\;$
$\ \ \ \ $ If $ \exists S'\in \mathcal P,\; \forall q\in S,\;
\delta(q,a)\in S'$  then do nothing
$\ \ \ \ $ else split $S$ into subsets $S_i$ such that
$\ \ \ \ \ \ $ for each
  subset $S_i$,  there is a different class $S'\in \mathcal P$ such that $ \forall q\in S_i,\;
\delta(q,a)\in S'$
$\ \ \ \ \ \ $ (the subsets $S_i$ replace $S$ in $\mathcal P$)

When there is no class left that needs to be split, the remaining
classes of states will form the states of the minimal Moore
machine.

By construction, all states in a class have the same output which is
the output for the class.

Similarly, for any input $a\in\Sigma$, all states in a class go to some
state in the same other class, which defines the transition function
for the minimal Moore machine.

Complexity analysis:
Let $n=|Q|$ be the number of states, and $s=|\Sigma|$ the size of the input alphabet.
The main loop is executed at most $n$ times, since each iteration must
split at least one class of states, and each class contains at least
one state. Each iteration of the loop examines each state a finite
number of times, and in proportion to the number of input symbols. Hence the complexity of the algorithm is $O(sn^2)$,
the same as that of the DFA minimization algorithm that served as a guideline
for this one.

I do not have any reference for this minimization of Moore
machines. Possibly it is included in his paper:

  Moore, Edward F (1956). "Gedanken-experiments on Sequential Machines". Automata Studies, Annals of Mathematical Studies (Princeton, N.J.: Princeton University Press) (34): 129-153.

This paper is the main reference introducing Moore Machines. It is also the reference for Moore's DFA minimization algorithm. It should thus be surprising if the adaptation of the algorithm to the
minimization of Moore Machines were not at least suggested in that
paper. I did check the paper, and the version of the minimization
algorithm that is presented is actually for Moore machines, not for
DFA. The paper is well written, but the style of the time makes it a
bit harder to read. It is interesting to see that many of the ideas of the Myhill-Nerode theory of Finite State Machines are already sketched in this paper.

The more recent $O(sn\log n)$ algorithm due to John Hopcroft (1971) should be similarly adaptable to Moore machines. It is not clear that there was any reason to publish this adaptation anywhere, and the Hopcroft paper seems to have no reference to Moore machines.


I couldn't find anything on that particular game, but I found an analysis of a similar game called qubic in Victor Allis' PhD thesis chapter 4: http://fragrieu.free.fr/SearchingForSolutions.pdf

It is essentially Connect 4 in 3D without gravity.


Symmetric Difference of Turing Recognizable and Finite Languages

The symmetric difference $A\ominus B$ of a Turing Recognizable Language $A$ and a finite
language $B$ is Turing Recognizable (i.e. recursively enumerable, or RE).

What you must do is prove that there is a Turing machine that
recognizes $A\ominus B$, but you do not have to actually construct the
machine.  And that is very fortunate because, in general, you cannot.
[More precisely you can build that machine, but you will have in general no way to know it is the right one, as explained below.]

This is a sketch of the proof, which you should know how to complete.

First you prove that the union of a RE set $C$ and a finite set $D$ is
a RE set $C\cup D$
(i.e. a Turing recongnizable set). That is pretty easy.

Then you prove that subtracting a finite set $D$ from a RE set $C$ produces a
RE set $C\setminus D$. That is easily done by modifying the Turing machine that
recognizes the RE set.

   You simply modify the Turing machine recognizing $C$ so that it loops or reject when the input is an element of $D$

Now consider the finite set $B$. It can be split into two parts:

$B_1=B\setminus A$ containg all elements of $B$ that are not in $A$,
$B_2=B\cap A$, the intersection of $A$ and $B$.

Since $B$ is finite, both $B_1$ and $B_2$ are finite too.

It is easy to show that the symmetric difference is

$A\ominus B= (A\setminus B_2)\cup B_1$

Since we have shown that RE sets are closed under union with a finite
set, and under subtraction of a finite set, the set $A\ominus B$ is
also RE, i.e. Turing recognizable.

Thus there is a Turing machine that recognizes $A\ominus B$, but this
proof does not tell you which. The reason is that there is no general
way to determine what part of $B$ is the set $B_2$.

Actually you could construct $2^{|B|}$ Turing machines, each
corresponding to one possibility for the set $B_2$ as subset of $B$.
One of these Turing machines is the one you want. But there is no
general procedure to determine which.

This kind of proof is called non constructive, because you can prove
that an answer exists (i.e. the recognizer for the symmetric
difference), but you cannot actually tell what it is.


The other answers explain how the circuit behaves. This answer will explain how to directly manipulate the circuit into a simpler form.

Here's a surprising fact: surrounding a CNOT with Hadamards flips the CNOT.

(I get that checking this on paper requires already understanding the solution to your question. You can confirm it for yourself in a circuit simulator such as Quirk at least.)

Your CNOT circuit is surrounded by 3 Hadamards. By flipping the CNOT, and using the fact that H is its own inverse, we can turn that into a single Hadamard:

Leaving us with the standard make-an-entangled-bell-pair circuit. So, when the input is $|00\rangle$, the output is $\frac{1}{\sqrt 2}|00\rangle + \frac{1}{\sqrt 2}|11\rangle$.


Iota combinator and implicational propositional calculus

The axiom scheme you reference represents a classical logic, i.e. one with excluded middle.  The computational interpretation of Peirce's law (implicitly embodied in Łukasiewicz's system) is call/cc.  Neither iota nor jot support first-class continuations (or continuations of any sort), so they do not encode or imply Peirce's law.

Added much later:

I think I just now realized that the minimally functionally complete is talking about completeness of logical connectives and had originally thought it had been referring to the completeness of the SK basis. This realization doesn't invalidate my answer but makes it so that there is more to say.

The first thing to say is that functional completeness in the context of propositional logic is (usually) talking about Boolean functions and thus we usually talk about collections of connectives (like $\to$ and $\land$) being or not being functionally complete. It doesn't really make sense to use it to refer to programming languages which we usually want to be Turing-complete which is a very different notion.

Nevertheless, taking a logical view of the SK combinatory logic, as the question does, the only connective is $\to$ which is not functionally complete. This is mentioned on the referenced page on Łukasiewicz's system. That page also strongly implies that Axiom 3 is not derivable from Axiom 1 and Axiom 2 which correspond to $K$ and $S$ respectively. If true (which it, of course, is), that would mean that the single axiom can't be derived from Axiom 1 and 2 either, since you would then be able to derive Axiom 3. My original paragraph was a high-level argument of why this is the case. A more direct argument would be to provide a counter-model by using a non-classical model of intuitionistic logic which will validate Axioms 1 and 2 but not Axiom 3 and therefore not the single axiom.

As a final note, in the above I've been assuming a typed version of iota and jot which are untyped languages. This is necessary for the logical reading to be meaningful. It is worth noting that a type version of iota and jot would not be Turing-complete.


What is the job of Syntax Analyzer in a compiler?

The syntax analyser has two main purposes.

It checks if the program to be compiled is syntactically correct.
It converts the program, which is given as a string of characters,
into an abstract syntax tree, which is a representation of the
program that is much easier to use for the code generator.

The second part is not really necessary as one could, in principle,
generate code directly from the input string, but that would be painful,
both in terms of speed of compilation, and complexity of the code generator.


Definition of liveness property in model checking

I'm not sure where the particular liveness definition you wrote comes from, but the definition given in Defining Liveness (Schneider, Alpern, 1985) is as follows.
A property $P$ is a liveness property if and only if:
$$
\forall \alpha \in S^* : (\exists \beta \in S^\omega : \alpha\beta \vDash P)
$$
where $S^*$ is the set of all partial executions and $S^\omega$ is the set of all infinite executions.
This definition captures the intuition that the "good thing" (the "something good" that you mentioned) specified by a liveness property can always occur in the future. That is, no matter the finite prefix $\alpha$ you choose, you can always find an infinite suffix $\beta$ to extend it with that will satisfy a liveness property $P$. I am assuming that the $\leq$ symbol in the definition you gave is used to express a prefix relationship between traces, which makes it analogous to the definition from the paper.
You might make an argument for defining liveness in some alternative way. Indeed, two slightly different characterizations of liveness are given in that same paper (see uniform liveness and absolute liveness). The definition given above, though, provides a basis for the topological characterization of safety and liveness properties which they use to prove the decomposition theorem i.e. that any property can be expressed as a conjunction of a safety and liveness property. So, it would seem that the definition is relatively "natural".
As they remark in the final paragraph of that paper:

It seems naive to hope for a proof that a formal definition for liveness (or safety) is correct, because "good things" and "bad things" are not well-defined concepts. However, the simple topological characterization of the definitions suggests that they do indeed capture fundamental distinctions.


What is the difference between expected cost and average cost of an algorithm?

In short, the average is the expected value of the uniform distribution.

If $T(x)$ denotes the runtime of some algorithm on input $x \in \mathcal{X}$, then the expected runtime for input size $n$ is

$\qquad\displaystyle \mathbb{E}[T(X) \mid |X| = n] = \sum_{x\in\mathcal{X}_n} \operatorname{Pr}[X=x \mid |X| = n] \cdot T(x)$

given some random distribution for random variable $X$.

Average runtime is more specific and corresponds to

$\qquad\displaystyle \overline{T}(n) = \frac{1}{|\mathcal{X}_n|} \cdot \sum_{x\in\mathcal{X}_n} T(x)$

or, in other words, the expected runtime given a uniform distribution over inputs of the same size.

Since we usually use the uniform distribution the terms are often used interchangeably in algorithm analysis.


Are some Integer programming formulations completely useless for relaxation?

Yes, some IP formulations are less useful than others. The technique used to show that an LP relaxation can only be so good is showing integrality gaps. For a minimization problem, an integrality gap of $k$ in an instance in which the optimal integer solution has value $V$ but the LP has a solution of value at most $V/k$. This shows that any rounding mechanism cannot guarantee an approximation ratio better than $k$.

As a simple example, consider the relaxation of the vertex cover IP $x_i + x_j \geq 1$ for every edge $(i,j) \in E$ (the variables are $x_i$ for every vertex $i$, and they are constrained to lie in $[0,1]$). A triangle has minimum vertex cover 2, but the LP has a solution with value only 3/2 (namely, all vertices get the value 1/2). This is an integrality gap of 4/3. There are more complicated integrality gaps of $2-\epsilon$ for every $\epsilon > 0$.


Do expressions have much to do with referential transparency?

I think the question is a bit poorly stated because it uses the term "expression" in an unclear way. So for the purposes of this answer let us say that an expression is a term which does not trigger any computational effects (such as divergence, I/O, mutation of state, exceptions, etc.). In Algol-like languages the opposite of expression is a command. I will say term for any piece of syntax.

I shall take referential transparency to mean that we may replace a term with its value without changing the program. More precisely, we obtain an observationally equivalent program when we replace the term with its value. Note however that referential transparency is not sensitive to efficiency, as replacing a term with its value almost always results in a more efficient program.

For example:

print "Hello, world!" is not referentially transparent because it returns the unit value (void is a horrible, horrible misnomer because it suggests that no value is returned, when in fact the trivial value is returned; in contrast, raising an exception return no value) -- if we substitute the unit value, the program won't print anything anymore
x = x + 3 is not referentially transparent because it changes state (the value of x)
3 + 4 is referentially transparent because we may substitute it with 7 safely
while true do skip done is an infinite loop, which is not referentially transparent. If we replace it just with skip (the unit value) then the program might do things it otherwise would not, such as launch missiles.

I hope you see now why your question is unclear. If you define "expression" as "free from all effects" then almost by definition it will be referentially transparent. If you define "expression" syntactically as "such and such syntactic forms are expressions", then we would have to check whether the syntax allows us to construct terms which are not referentially transparent.

One more point: it does not make sense to say that a programming language is referentially transparent, but rather that a particular term or a program is referentially transparent. So we should interpret the question from the first sentence as "if a programming language contains terms that trigger computational effects, must it have some non-transparent terms?", and I think then "yes" is the obvious answer because we just consider a command which triggers a computational effect.

You then ask about languages in which "everything is an expression". Well, that would be a pure language whose only possible effect is non-termination (because of infinite recursive calls). Depending on the language evaluation strategy this may or may not cause expressions to be referentially non-transparent. For example, in Haskell sometimes it does not matter that an expression is non-terminating because Haskell won't evaluate it until it is needed, which may be never. But in general non-termination is the thing to worry about in a pure language.

There are languages in which all terms are referentially transparent by design. Such languages cannot be Turing complete, however (assuming they have sane syntax). An example is Agda, which does not allow you to write a non-terminating expression, but it is still very powerful as a programming language, and a proof assistant.

A far more interesting question is whether a term can be referentially transparent even though it triggers computational effects. The answer is positive, and useful. Many data structures are self-modifying but they look referentially transparent from the outside, let me just mention splay trees as a famous example. Another example are caching strategies where lookups are cached (state change) so that they may be answered faster in the future. It is an interesting challenge for programming languages to properly account for such phenomena so that compilers can see what is going on and take advantage of the situation. For example, in a splay tree we may reorder lookups and updates, or if we work with two splay trees it does not matter which tree we work with first (so long as the data is not migrating between them). Note however.

I hope that answers your questions a bit by putting them into wider context.


What's the difference between strong consistency and sequential consistency?

In the case of the Spanner doc: it appears to be more strict than linearizability due to transactions. The difference between linearizability and sequential consistency is that latter doesn't need to preserve the real time ordering of requests.
https://jepsen.io/consistency/models/linearizable
The combination of linearizability and transactions is called strict serializability:
https://jepsen.io/consistency/models/strict-serializable
I'm not sure if spanner is supporting strict serializability.


Multiplication mod 2 without extra registers

Your question is solved by Patel, Markov and Hayes in their paper Optimal synthesis of linear reversible circuits. They mention a simple $\Omega(n^2/\log n)$ lower bound for the worst-case $M$, obtained by counting, and show that it is tight, in the sense that there is an $O(n^2/\log n)$ algorithm for any reversible $M$.


Why do low fitness individuals have a chance to survive to the next generation?

The main idea is that by allowing suboptimal individuals to survive, you can switch from one "peak" in the evolutionary landscape to another through a sequence of small incremental mutations. On the other hand, if you only are allowed to go uphill it requires a gigantic and massively unlikely mutation to switch peaks.

Here is a diagram showing the difference:

Practically, this globalization property is the main sellling point of evolutionary algorithms - if you just want to find a local maxima there exist more efficient specialized techniques. (eg., L-BFGS with finite difference gradient and line search)

In the real world of biological evolution, allowing suboptimal individuals to survive creates robustness when the evolutionary landscape changes. If everyone is concentrated at a peak, then if that peak becomes a valley the whole population dies (eg., dinosaurs were the most fit species until there was an asteroid strike and the evolutionary landscape changed). On the other hand, if there is some diversity in the population then when the landscape changes some will survive.


b) Introduce a new start symbol $S_1$ and a new production rule $S_1 \rightarrow SSS$

c) Introduce a new start symbol $S_2$ and a new production rule $S_2 \rightarrow S_2S \mid \epsilon$


Using a stack for function calls does not require any special support from the processor. It's up to the compiler to decide where to put the data relative to a function call (return address, parameters, possibly reserved space for the return value). A common convention is to designate one particular register as the stack pointer. This does not require any special processor instruction, it can be a general-purpose register. A function call looks like this:

Write parameters to the memory region at address SP (stack pointer register)
Decrease SP by the size of the parameters
Write PC (program counter register) to the address SP
Decrease SP by the size of PC
Jump to the function entry point

Returning from the function looks like this:

Load a PC-sized value from SP into a register A
Increase SP by the size of PC
Jump to A

Some processors have a particular register R with instructions to store a word in memory at the address designated by R and decrement R, and to load a word in memory at the address designated by R and increment R. In this case, the processor documentation typically describes R as the stack pointer register and compilers use it to store the address of the function call stack. But if the processor doesn't have such instructions, the compiler just emits separate instructions for load/store and for increment/decrement. The register doesn't need any special properties.


How to implement recursive solution with large number or parameterized possible next steps

The way that that the short-circuit expression A || B is evaluated is as follows:

if A is True:
   return True
return B

In words:

Run $A$. If it returns True, return True. Otherwise, continue.
Run $B$, and return the result.

In particular, $A$ and $B$ are not run in parallel; they are run in sequence.

There is absolutely no problem generalizing this to a short-circuit OR of larger arity:

if A1 is True:
   return True
if A2 is True:
   return True
...
if An is True:
   return True
return False

We could also replace the last bit with simply return An, to make it match the previous pseudocode, but the form above is perhaps more easy to implement using a loop.


How is the number of states in a Turing machine bounded?

You seem to have misunderstood the definition of a Turing machine. The "state" refers not to the whole configuration of the machine (tape contents, position of the head, etc.) but to the state of the finite automaton that controls the tape head.  The automaton has a finite number of states by definition.


Term for size of maximum independent set

Yes, it's called the independence number and it's usually denoted $\alpha(G)$.


Modifying digraph to make it strongly connected

On solvable instances (not all instances are solvable; see narek Bojikian's comment on my other answer for a simple necessary and sufficient condition), this is NP-hard by reduction from Directed Hamiltonian Path. The basic idea is to add enough isolated vertices to the input digraph to force the only possible solution to be a single cycle, and then see whether it is possible to accomplish this with few enough moves that the unmoved edges must form a DHP in the original digraph.

Given an instance of Directed Hamiltonian Path consisting of a digraph $(V, E)$ with $n=|V|, m=|E|$, add $m-n$ isolated vertices. Observe that a single SCC can be formed by rearranging the $m$ edges into an arbitrary cycle that touches each of the $m$ vertices that now exist. This can be done trivially if we are prepared to move all $m$ edges, but if we limit ourselves to moving at most $m-n+1$ edges, then this is possible only if $m-n+1$ edges are moved from somewhere to form a path that connects some vertex $u$ of the original digraph to some new isolated vertex, visits each new isolated vertex in some order, and finally returns to some other vertex $v$ of the original digraph. (We have $u \ne v$ since $u=v$ would leave just $n-1$ edges available to visit all $n$ vertices of the original digraph, which is not enough.) In this case, the unmoved $n-1$ edges that remain necessarily form a path from $v$ to $u$ through the $n$ vertices of the original digraph, and thus constitute a DHP through it. This shows that a YES answer to the constructed instance implies a YES answer to the original problem.

To see that a YES answer to the original DHP problem implies a YES answer to the constructed instance, pick up the $m-n+1$ edges that are not part of the DHP, and construct a path as described above, forming a single cycle comprising all $m$ vertices using just $m-n+1$ moves.


Different between left-most and right-most derivation

Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. The rightmost derivation is the one in which you always expand the rightmost non-terminal.

For example, here are two parse trees borrowed from Wikipedia:

The leftmost derivation corresponding to the left parse tree is
$$
A \to A + A \to a + A \to a + A - A \to a + a - A \to a + a - a
$$
The rightmost derivation corresponding to the left parse tree is
$$
A \to A + A \to A + A - A \to A + A - a \to A + a - a \to a + a - a
$$
The leftmost derivation corresponding to the right parse tree is
$$
A \to A - A \to A + A - A \to a + A - A \to a + a - A \to a + a - a
$$
The rightmost derivation corresponding to the right parse tree is
$$
A \to A - A \to A - a \to A + A - a \to A + a - a \to a + a - a
$$


Big O relation between $2^n$ and $2^{2n}$

The more strong estimate is correct:

$2^n = o(2^{2n})$

Just look at definition of the little-o. For any constant $c \gt 0$ you need to find a constant $n_0$, such that for all $n \ge n_0$ you get $2^n \le c \cdot 2^{2n}$. Apparently, the following inequality will give you this $n_0$:

$n_0 \ge ln(1 / c)$


How to predict the next word in a sentence using N-grams

Store the n-grams in a tree or trie, with one level per word, starting from the leftmost word.  Then given some context, e.g., "I want to", you traverse the tree/trie (follow the edge out of the root that is labelled "I", then the edge labelled "want", then the edge labelled "to") and find all children of the resulting node.


Clock synchronization in a network with asymmetric delays

Inability to measure asymmetry

No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).

The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.

You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!

Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.

Can intermediate infrastructure help?

Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.

If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.

In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.

If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.


Minimal number of attempts at a multiple choice exam needed in order to pass, without any prior knowledge

Here is an algorithm to identify the answers with successive attempts.

It has a worst case complexity of $O(m(1+\log_2 k))$

This corresponds roughly to collecting in each attempt one bit of
information on the right answer, for each question in succession.

Of course we cannot do that, because we can only give one whole answer
per question. So the trick in to transpose the problem, by identifying k
correct answers and trying to find their questions.

Apologies for the rough presentation. I am running out of time.

The algorithm

We assume, to simplify the presentation, that $N\geq k$. But it does
not really matter. We also assume that $k=2^p$ for some positive
integer $p$, again to simplify the presentation.

We assume that the only result of an attempt $T\in [1,k]^N$ is a score $s(T)$
corresponding to the number of correct answers. The individual
answers for each question are noted $T[j]\in [1,k]$ for the answer to question
$j$, ($j\in [1,N]$), in attempt $T$.

We define $T_i=i^k1^{N-k}, \forall i\in[1,k]$

The $N-k$ last answers always contribute the same amount $r$ to the result
$s(T_i)$ since they do not change.

Together, the first $k$ answers of all $k$ attempts will produce $k$
good answers, distributed in some way over all $k$ attempts, since for
each question there is exactly one good answer among the $k$ being
proposed.

If one attempt has 2 good answers, or more, for one of the first $k$
questions, then another must have 0. Thus, if the scores $s(T_i)$ are
not all equal, the smallest is equal to $r$. Furthermore, if they are
all equal, then they are all equal to $r+1$. So the value of $r$ is easily determined.

We first assume $\exists r\in[0,N-k],\; \forall i\in[1,k],\; s(T_i)=r+1$

This implies that each attempt has exactly 1 good answer among the
first $k$ answers (to the first $k$ questions). But we do not know which.

We define a second set of $k-1$ attempts
$T_i'=i^{k/2}1^{N-k/2}, \forall i\in[1,k]$

Note, that $T_1'=T_1$, so that k-1 new attempts only are needed,
but the duplication makes things simpler to explain.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the first $k/2$ questions, then $1$ is a bad answer for questions
$Q_j,\; \forall j\in[k/2+1,k]$. Hence all the $T_i$ attempts that had
a good answer for one of these $k/2$ questions will lose 1 point in
score, thus falling to $r$. All other attempts, that had a good answer
in the first $k/2$ questions will have an unchanged score $r+1$.

If the good answer $1$ in the first $k$ questions in $T_1$ was for one of
the last $k/2$ questions, i.e. for questions  $Q_j,\; \forall
j\in[k/2+1,k]$, then all attempts $T_i'$ benefit from that good
answer $1$. Those that had a good answer for the first $k/2$ questions
will keep it and see their score increase from $r+1$ to $r+2$, while
the others will lose their good answer as before, but have it replaced
by the good answer $1$ for one question, thus keeping the score $r+1$.

Thus we can conclude that, if some score decrease, then the firat
attempt $T1$ has a good answer $1$ in one of the first $k/2$ questions,
and if some increase it is in one of the next $k/2$ questions.
Forall other attempts $T_i'$, those with the higher score have a good
answer for one of the first  $k/2$ questions, and those with the lower
score have a good answer in one of the next $k/2$ questions.

Recall that $k=2^p$, i.e. $p=\log_2 k$.

If we number the first $k$ questions in binary, starting from 0, we
can see that this is a way to determine the $p^{th}$ bit of the index
question that is correctly answered by some attempt $T_i$.

If for some $i>1$, the score decrease from $T_i$ to $T_i'$, then
$T_1$ has a good answer for a question $Q$ such that the $p_{th}$ bit
of its binary index is $0$, while it is $1$ for an increase. For the
other attempts $T_i$, those with the higher score for $T_i'$ have a
good answer for a questions with the index $p^{th}$ bit $0$, and the
lower scores have a good answer for a questions with the index
$p^{th}$ bit $1$

It is then quite simple to repeat the procedure identically for each of
the other bits of the binary index of the first $k$ questions.

That makes $p=\log_2k$ series of $k-1$ attempts, in addition to the
first $k$ attempts, that is a total of $k+(k-1)\log_2k$ attempts,
to get the first k answers.

However we can improve a bit on that count. We do $\log_2 k$ attempts
to identify the question associated with each answer, i.e. each index
$i\in [1,k]$. Actually we need to identify only $k-1$ such question.
The last one in necessarily the one that was not found yet.

Thus in the above algorithm, we do not need to compute $T_{k}'$, nor
any of the other attempts of index $k$, except for the first $T_k$ in
the first attempts of the algorithm. Since it is also unnecessary for
$T_1'$ and similar, we only need, at most $\log_2k$ series of $k-2$
attempts, in addition to the initial $k$ attempts, that is a total of
$k+(k-2)\log_2k$ attempts, to get the first k answers.

But this relied on the assumption that each of the first $k$ attempts
has exactly one good answer for the first $k$ questions. What if that
is not the case?

One of the first $k$ attempts had more than one good answer in the first $k$.

Then there is at least one attempt, say $T_h$ that failed on the first
$K$ questions, which means that answer $h$ is wrong for the first $k$
questions.

Actually there may be several such attempts caracterized by the fact
that they have the same smallest score $r$. They can all be discounted
as containing no information for the first $k$ questions, other than the
fact that their index is not the answer to these questions.

Futhermore, for any attempt $T_i$, we know that it has $s(T_i)-r$
correct answer $i$ in the first $k$ questions.

If there is only one answer, it can be identified with the previous
binary technique using $\log_2k$ attempts, given that we can replace
half the answers (as specfied by a bit in their binary index) by $h$
which is known to be wrong (which makes thing simpler than
previously).

If there are two correct answers, the same technique is used with a
small variation. The binary approach is used again for both answers
together, until one of the attempts separates them by indicating a bit
$0$ for one answer and a bit $1$ in the same position of the question
binary index for the other answer. From then on, one answer can be hidden
by using the answer $h$ in the questions corresponding to that index,
while the binary search is resumed for the other answer. Once that
answer has identified its question, it is replaced by the answer $h$
that is wrong so that the search can be resumed for the question of
the second answer.

The same technique can be used independently of the number of answers,
progressively splitting them until only one is searching for its
question, then replaced by wrong answer $h$ when its question is found, so that another can be searched, and
so on.

Since the splitting and searching is based on the bits of the binary
indexes of questions, it is quite clear that this costs never more
than $\log_2 k$ for each question to be associated with one of the $k$
answers.

So the cost in number of attempts for identifying the questions for
the first $k$ answers (I am deliberately inverting the view) is not
more than $k\log_2 k$, to be added to the first $k$ attempts. It might
be a bit less with a finer analysis.

However we can again use the fact that each question has necessarily
an answer, so as to skip the binary search on one line of answers (i.e., one
answer number).

First recall that we simply ignore all answer numbers that correspond
to no answer. Then we also set aside the answer number that
corresponds to the largest number of questions for which it is the
right answer. This corresponds by hypothesis to at least two good answers.

Then we determine the corresponding question for all other identified
good answers, at most $k-2$ of them, with a cost that is at most
$\log_2 k$ for each. The correct answer set aside can then be assigned
to all questions that have not been identified as associated with
another answer.

This makes for a total cost of at most $(k-2)\log_2k$ attempts, to be added to
the initial $k$ attempts, thus again a total of $k+(k-2)\log_2k$
attempts, to get the first k answers, as in the first case.

Overall

The cost of this algorithm, mesured in number of attemps, is bounded by $k(1+\log_2 k)-2\log_2 k$ for
identifying the $k$ answers to $k$ questions (as the above could have been done for any set of $k$ questions.

So for $m$ questions, assuming for simplicity that $m$ is a multiple of $k$, the total cost is bounded by $m/k$ times that cost,
i.e. $m(1+\log_2 k)-(2m/k)\log_2 k$.

Apparently the total number $N$ of questions does not matter. But the last questions are
not considered with this technique, except to identify their global effect to factor it out. We do not take advantage of the fact that some groups of question-answer pairs might be easier to identify (because their costs can be factored, for example). Possibly this could
help for the worst case analysis with a different technique that would identify  patterns of answers that are easier to analyze, but there might be a cost in finding them.

Regarding purely asymptotical complexity: this algorithm is $O(m\log_2k)$


Single Input Single Output Sequential Circuit Explanation Required

Create a FSA that falls on the same state at the end of a 100 sequence.
Create a second independent FSA that falls on the same state upon the end of 011 sequence.
Now feed a zero to both FSAs at the same time and take note of the pair of states reached. Now go back and feed a 1 and take note of the pair of states reached, and so on. You will end up with a new FSA made up of pairs of states belonging to the Cartesian product of the set of states of the first and second FSA.
The output at the transition between two pairs of states is the logical OR of the outputs of the original FSAs.

In fact, you can also build a non deterministic FSA that does the job then turn it into a FSA.

Another solution is to create a set of states representing the last one or two inputs, namely 0, 1, 00, 01, 10, 11 in addition to a start state. The transitions are obvious. 1 is emitted when transitioning from 01 to 11 or from 10 to 00. In fact state 11 can be merged with state 1 and state 00 can be merged with state 0. That leaves us with a total of 5 states that should do the job. I assume here that the outputs are emitted upon transitioning. Assuming the output is emitted upon entering a state, then states made of the last 3 inputs need to be made. Similarly, some states can be merged.


Asymptotic order of a recursive function

What you are asking is really, how many times do you need to apply the transformation $m \mapsto \frac{m}{\log m}$ in order for a value to drop from $n$ below some constant $C$; if the answer is $f(n)$, then $T(n) = \Theta(f(n))$.
Given $n$, define a sequence by $n_0 = n$ and $n_{i+1} = n_i/ \log n_i$. We would like to know the minimal value of $t$ which satisfies $n_t < C$.
Taking logarithm, we see that $\log n_{i+1} = \log n_i - \log\log n_i \geq \log n_i - \log\log n$. Since $\log n_0 = \log n$, this shows that $t \gtrsim \frac{\log n}{\log\log n}$.
In the other direction, as long as $n_i \geq \sqrt{n}$, we have $\log n_{i+1} \leq \log n_i - \log \log \sqrt{n} \leq \log n_i - \log \log n + \log(1/2)$. Hence we get from $n$ down to $\sqrt{n}$ in roughly $\frac{\log n}{\log\log n}$ steps. We then get down to $\sqrt[4]{n}$ in roughly $\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \approx \frac{\frac{1}{2} \log n}{\log\log n}$ steps. Continuing in this way, we see that $t \lesssim \frac{2\log n}{\log\log n}$ (summing the series $1+\frac{1}{2}+\frac{1}{4} + \cdots = 2$).


What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial?

Concrete example: Thorup's $O(n^{120})$ time algorithm to recognize half-squares of planar bipartite graphs.

https://arxiv.org/abs/1804.05793

Parameterized problem: Some parameterized $NP$-complete problems have arbitrarily large polynomial time algorithms. Like, finding a $k$-clique in a graph can be solved by $\Theta(n^k)$ algorithm. And we do not know how to do much better. There might be some improvement but in general when the parameter increases the degree of the polynomial run-time bound increases also.

Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.

Some other $NP$-complete problems (like Vertex Cover in the comment of kne below) have parameterized version with linear-time algorithm for each parameter value. So, it takes some careful investigations before naming a hard parameterized problems.


Weakly NP-complete problems and strongly NP-complete problems

Many problems involve integers, for example in the form of integer weights. There are two common ways to encode integers:

Binary encoding, or more generally base B encoding for some constant B.
Unary encoding, in which (ignoring signs) $n \geq 0$ is encoded as $0^n1$.

A problem is weakly NP-complete if it is NP-complete when weights are encoded in binary. It is strongly NP-complete if it is NP-complete when weights are encoded in unary. For example, SUBSET SUM is weakly NP-complete but not strongly NP-complete, whereas BIN PACKING is strongly NP-complete.

Every strongly NP-complete problem is also weakly NP-complete since the reduction which changes the encoding of integers from unary to binary runs in polynomial time. The reduction in the other direction, in contrast, could run in exponential time.

Primality testing can be done in polynomial time in both unary and binary encodings, though in the latter case it's a highly non-trivial result known as the AKS primality test.


Yes this problem is definitely NP hard. I am posting this answer since you require proof.

If you follow this link http://en.wikipedia.org/wiki/Set_cover_problem, it says that the optimization version of minimal set cover problem is NP-Hard.

The problem in the link:

  Given a set of elements {1,2,...,m} (called the universe) and a set
  S of n sets whose union equals the universe, the set cover problem is
  to identify the smallest subset of S whose union equals the universe.
  For example, consider the universe U = {1, 2, 3, 4, 5} and the set
  of sets S = {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Clearly the
  union of S is U. However, we can cover all of the elements with the
  following, smaller number of sets: {{1, 2, 3}, {4, 5}}

You can relate this to your problem as follows:

S is the set of nodes that cover at least one node in your input set. This can be found by conducting a DFS on the nodes of input set with the direction of edges reversed.

Now the problem described in the link is a special case of your problem, where the cost of each node is equal and you just want to minimize the number of nodes (sets).

Hence your problem is even more difficult to solve in the general case and hence it is NP Hard.


Can Floyd-Warshall be used to solve an APSP problem without copying the matrix?

No you are not lucky, it is possible to use the program that way. The notation $d_{ij}^k$ probably is used for better explaining what the algorithm has achieved in the $k$th step. Note that the variant where one overwrites the matrix as you suggest is presented in Exercise 25.2-4 (in my second edition of the book, which is not the latest).

The secret to that puzzle is in principle that an assignment to $d_{i,j}^k$ is only done once, and that value is never again used in the computation, except for the case where either $i=k$ or $j=k$. However, the algorithm does not change those values in the $k$th step. You figure out why.


Covering maximal number of sets using fixed number of elements

Your problem is essentially Minimum $k$-Union. In this problem (switching from $k$ to $\ell$), you want to find $\ell$ sets out of $A_1,\ldots,A_t$ which together cover the least number of elements. Denoting by $f(\ell)$ the solution of this problem and by $g(j)$ the solution of your problem, we have
$$
f(\ell) \leq j \Longleftrightarrow \ell \leq g(j).
$$
In other words, $g(j)$ is the maximal $\ell$ such that $f(\ell) \leq j$.

Unfortunately, Minimum $k$-Union is NP-hard. You can find some links in this question on StackOverflow.


Mathematical proof for why gradient descent algorithm always converges

It looks like you put some emphasis on mathematical rigor. It just happens my motto is currently "from math and larger than math".

Yes, there are many mathematical proofs for conclusions along the line that gradient descent method converges to local minimum when the steps are small enough. We will need some precise statement on the condition of $f$ and the steps taken. Let me quote from Wikipedia,

  With certain assumptions on the function $F$ (for example, $F$ convex and $\nabla F$ Lipschitz) and particular choices of $\gamma$ (e.g., chosen either via a line search that satisfies the Wolfe conditions or the Barzilai-Borwein method shown as following),
  $$ \gamma_n=\frac{(x_n-x_{n-1})^T[\nabla F(x_n) - \nabla F(x_{n-1})]}
{||\nabla F(x_n) - \nabla F(x_{n-1})||^2}$$
  convergence to a local minimum can be guaranteed. When the function $F$ is convex, all local minima are also global minima, so in this case gradient descent can converge to the global solution.

For some actual statements and proofs in their full clear detail, you can read a course note by Ryan Tibshirani at CMU. Unfortunately, because of the required mathematical rigor,  they are too long to be included here.


How to prove an identity of regular expressions

Regular expressions stand for languages. To show that two languages are equal, we show that every string in the first also belongs to the second, and vice versa.

As an example, let us prove the identity
$$
a(ba)^*b = ab(ab)^*.
$$
Denote the language of a regular expression $r$ by $L[r]$. A word $w$ belongs to $L[a(ba)^*b]$ if there exists $n \geq 0$ such that $w = a(ba)^nb$. Now $w = a(ba)^nb = (ab)^{n+1} = ab(ab)^n \in L[ab(ab)^*]$. Similarly, a word $w$ belongs to $L[ab(ab)^*]$ if there exists $n \geq 0$ such that $w = ab(ab)^n$. Now $w = ab(ab)^n = (ab)^{n+1} = a(ba)^nb \in L[a(ba)^*b]$.

(You can prove the various identities I used, such as $(ab)^{n+1} = a(ba)^nb$, by induction on $n$.)

Your particular identity states that if a word over $\{a,b\}$ contains an $a$ followed by $b$ (with possibly letters separating them) then it contains the substring $ab$, and vice versa. You should start by understanding why this holds.


Does spectral graph theory say anything about graph isomorphism

Graph isomorphism has been mentioned along with primality testing as early as 1971 in Cook's famous paper on NP-completeness. Cook mentions that he was unable to prove the NP-completeness of both problems. Nowadays we known that primality testing is in P, but the status of graph isomorphism is still unknown. Most experts conjecture that it is "NP-intermediate", that is, not in P but not NP-complete. Some conjecture that it should be solvable in quasipolynomial time (algorithms running in time $2^{\log^{O(1)} n}$). The best currently known algorithm, due to Luks, has running time $2^{O(\sqrt{n\log n})}$. It uses the so-called group theory method.

The two most common approaches are individualization/refinement and the group theory method. The former approach tries to match vertices of one graph to vertices of the other. Given a vertex of degree $d$ belonging to the first graph, it can only be matches to a vertex of degree $d$ in the other graph, but this offers no saving if both graphs are $d$-regular. Individualization/refinement is a framework for generating more detailed "types" of vertices.

It is possible that a similar approach can enhance the spectral method (which as stated fails for cospectral graphs), but I am not aware of any work along these lines (though it might exist; I'm not an expert in this area).

The group theory method reduces graph isomorphism to the problem of finding generators for the automorphism groups of graphs. Given two graphs $G_1,G_2$, the idea is to compute generators for $\operatorname{Aut}(G_1 \cup G_2)$, and check whether any of them switches a vertex of $G_1$ with a vertex of $G_2$. For more details, see for example lecture notes of Arvind.

For a recent overview of the state of the art, consult a paper by Babai; Babai is one of the principle researchers in the area.

Practical graph isomorphism is a completely different issue. A recent overview can be found in a paper of McKay, author of the popular package nauty.


Average branching factor of an undirected graph

Just to make it clear, the problem of finding a spanning tree with a maximum number of leaves is NP-hard. There's a simple 2-approximation algorithm due to Solis-Oba [1] which looks implementable with reasonable effort. In fact, I don't think anything better is known. There are other algorithmic approaches as well (e.g., FPT algorithms), but I'm not sure if these are that practical.

For a good overview of spanning trees in general, you can have a look at the survey of Ozeki and Yamashita [2]. Particularly, Section 6.1 is on spanning trees with many leaves and gives some combinatorial results.

[1] Solis-Oba, Roberto. "2-approximation algorithm for finding a spanning tree with maximum number of leaves." European Symposium on Algorithms. Springer, Berlin, Heidelberg, 1998.

[2] Ozeki, Kenta, and Tomoki Yamashita. "Spanning trees: A survey." Graphs and Combinatorics 27.1 (2011): 1-26.


Efficiently prime factorising an integer with an oracle

This does work (see the fundamental theorem of arithmetic), and is exactly how some efficient factoring algorithms work, such as Pollard-Brent. However they use a weaker oracle, one that just returns a factor, not necessarily a prime one.

Since Pollard-Brent (and maybe others) runs very slowly and/or not at all when passed a prime, there is often another specific prime check in place as well.

A proper recursive routine under those assumptions would be (in Python):

def factorize(n):
    if n == 1: return []
    if is_prime(n): return [n]
    f = one_factor(n)
    return factorize(f) + factorize(n//f)

  It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.

Analyzing it in terms of the number of prime factors is exactly right. You can then get an upper bound on the number of binary digits by noting that a $b$-bit number may have at most $b-1$ prime factors.


In two sets, identify set of pairs with maximal sum of connections

This is the assignment problem.  There are standard algorithms, such as the "Hungarian algorithm".

If you want to only include edges whose weight is below some threshold, delete those edges first before running the algorithm.


Do there exist any problems with optimal algorithms beyond $O(n)$?

(Deterministic) TMs with a single tape can recognize palindromes in time $O(n^2)$. It has been proven that this time bound is optimal (see, e.g., this paper).

Also, the time hierarchy theorems give you an endless supply of such examples (though they are not natural problems, of course).


Why models of computation are primarily focused on machines?

I suspect that there are two reasons:

Historical reasons. This is how we've always done it.  Academia can be slow to change.  Also, machines provide a platform for studying concepts like the power of non-determinism.  We don't know how to fully understand the power of non-determinism when considering realistic models of computation (for instance, we haven't resolved the P vs NP question), but when we look at more limited models of computation, it's possible to fully work out the power of nondeterminism.  So, this gives us a platform for understanding some interesting concepts about computation.
Pragmatic reasons. DFAs, NDFAs, and PDAs are useful and important to understand if you want to build a lexer or parser, so they're very useful when building compilers.  A few decades ago, this was a powerful motivation for studying the subject: here is a practical need (how do we structure the front-end of a compiler?) and one where there is some beautiful theory that is directly applicable.  Thus, such a course might gain support both from theoreticians who are most interested in the theory, and from compilers folks who are motivated by practical concerns.  It's not clear that this is still the most important thing for students to learn these days -- today, how many students are ever going to need to write a lexer or parser for a compiler? -- but academic courses are slow to change.

I'm not trying to argue this is the only reasonable way to do it.  A course on variants of the lambda calculus might be quite interesting, too.  But I suspect these factors might partly explain why such courses are common.


Brzozowski's algorithm for DFA minimization

Most of the below is from Parsing Theory by Sippu and Soisalon-Soininen.

Let $Q$ be the set of states of the DFA. Let $T$ be the input alphabet. Let $|M|=O(|T| \cdot |Q|)$ be the size of the machine. Exercise 3.40 gives a $O(|T|\cdot|Q|^2)$ algorithm for state minimization. As Wikipedia describes, Hopcroft's algorithm has a running time of $O(|T| \cdot |Q| \cdot \log|T|)$ and Moore's algorithm has a running time of $O(|T|^2 \cdot |Q|)$.

Theorem 3.30 states that the subset construction can be done in $O(2^{|T|+\log|T|+\log|Q|})$ yielding an automaton of size $O(2^{|T|+\log|Q|})$ (actually, if the resulting automaton has $|T'|$ states, the running time is $(|T'| + |T|\cdot|M|) \cdot |Q|$). The two reversals and the second determinisation are therefore inconsequential in the running time, so the asymptotic running time of Brzozowski's algorithm is the same as that of the subset construction.

This means that in the worst case, Brzozowski's algorithm is exponentially slower than the other three algorithms. Note that the worst case really does occur: the classic example of the NFA for the language $(a|b)^*a^k$ has $k+1$ states and its corresponding minimal DFA has $O(2^k)$ states, while the reverse of the NFA is deterministic, so running Brzozowski's algorithm on this reversed NFA triggers the worst-case behavior.

However, if the subset construction yields an automata of size $|T'|=O(|T|)$, then its running time is also $O(|T|^2 \cdot |Q|^2)$, which is often the case on real-life inputs. Furthermore, if proper care is taken when computing the closure of a state, then this can be done much faster in most cases (that is, cases where the closure is small), saving a factor $|T|$ in practice (for essentially the same reason that transitive closures can be computed quite quickly on real-world examples). Furthermore, if the input and intermediate automatons are sparse, which means that states have few transitions, then a factor $|Q|$ is saved, which gives a $O(|T| \cdot |Q|)$ running time on 'good' inputs.

Unfortunately, I'm not familiar enough with Hopcroft's or Moore's algorithms to give an analysis of their running times in typical cases. Wikipedia talks about a $O(|T| \log \log |T|)$ running time in some cases, which would make the three algorithms comparable.


Finding integrality gap for maximum weight independent set

Suppose you prove that an upper bound on the integrality gap is $\alpha$.
  The goal is to “create” an instance (weighted graph, or better yet, a family of weighted graphs) where the value of the optimal LP solution is $\alpha$
  times the value of the ILP solution.

Independent set ILP
$$O_{ILP}=\max\sum_{v\in V}x_{v}\cdot w(v) $$
such that
$$x_{v}+x_{u} \leq 1\ \ \ \forall u,v\in V$$
$$x_{v}\in\{0,1\}  \ \ \forall v\in V$$

The relaxation is straight forward. say the value of the optimal solution to the LP is $O_{LP}.$ Now, you want to upper bound $ O_{LP}/O_{ILP}.$
  To do this, try to consider a rounding scheme that converts a solution for the LP into a feasible solution for the corresponding ILP. One such scheme involves reasoning about the constraints, that is $x_{v}+x_{u}\leq1$
 for every edge in G.
  This implies that at least one of $x_{u}$
  or $x_{v}$
  is atleast $1/2$,
  and therefore all vertices in $v\in V$
  such that $x_{v}>\frac{1}{2}$
  is an independent set in $G$.
  I'll leave it to you to reason about how to compare $O_{LP}$
  and $O_{ILP}$, (i.e. determine the maximum of the ratio $\alpha=\max O_{LP}/O_{ILP}$), and to find an instance where $O_{LP}$ is atleast $\alpha.$


You're confusing three aspects of scheduling that can be chosen independently: preemptivity, ordering strategy, and time slice duration.

Preemptive vs non-preemptive determines when a context switch may happen. With a non-preemptive scheduler, a task¹ keeps executing until it voluntarily yields the processor back to the operating system², and at this point the operating system may schedule another task. With a preemptive scheduler, the operating system interrupts tasks whenever it wants — interrupting a task is called preemption. In practice, preemption happens when a hardware interrupt is triggered, and one of these interrupts is a timer interrupt that the operating system programs in order to limit how long a task will execute without interruption.

Round-robin is a scheduling strategy (also called scheduling discipline), i.e. a way to decide which task gets scheduled once the current task yields control to the operating system. Most scheduling strategies, including round-robin, make sense whether yielding is voluntary (non-preemptive scheduling) or forced (preemptive scheduling).

Round-robin is a simple strategy where the scheduler maintains a queue of tasks. On a context switch, the task that just stopped goes to the back of the queue, and the task at the front of the queue is resumed. In other words, the next task to execute is the one that has been stopped for the longest time. This strategy is fair³ in the sense that every task gets to execute eventually (no task is starved, waiting forever for CPU time): no task can prevent another task from executing (except in a non-preemptive setting, by never yielding).

Exercise: suppose that tasks can create other tasks. The new task has to be added to the scheduler's queue. Where do you put it?

This description above only considers ready tasks, i.e. tasks that have something to do. If a task is blocked, i.e if it can't do anything because it's waiting for an external event, then the task is removed from the scheduler's queue until it becomes unblocked because that event happened. Tasks become blocked because they're waiting for I/O — either communication with another task or communication with a peripheral.

Where do you put a task when it becomes unblocked? Even if you try to keep a “pure” round-robin scheme, there are several choices. A simple choice is to put the unblocked task at the back of the queue. This choice preserves the fairness property of round-robin. Another choice is to keep all the tasks in the queue, even the blocked ones, but skip over blocked ones when scheduling. This also preserves fairness.

However, schedulers usually deviate from a simple round-robin when it comes to I/O, because round-robin is bad for latency. Scheduling is often a compromise between throughput (getting as much work done as possible in total) and latency (responding to specific events quickly). Throughput is what matters for computational tasks, but I/O tasks often need low latency. If the CPU needs to read data from a peripheral, or to display the next frame of a video, or to send a signal to the brakes because the brake pedal was pressed, then a fast response is needed, and waiting for the task's next turn through a queue may not be acceptable. In practice, schedulers are often round-robin at the core, but with modifications to schedule tasks earlier when they're involved in I/O, in order to reduce latency.

So far I've discussed when preemption occurs and which task gets scheduled next. Time slice duration is another aspect of the scheduling strategy. Time slice duration is another example of a compromise between latency and throughput. Context switching has a cost. If the system performs a lot of context switches, the time spent doing context switches instead of useful work is wasted. To maximize throughput, there must be as few context switches as possible, meaning long time slices. On the other hand, a long time slice means high latency. Scheduling tasks immediately on I/O solves part of the latency aspect, but only part. For example, a video player needs CPU time to prepare for the next frame, even if it doesn't receive many I/O events. Complex schedulers tend to classify tasks as I/O-bound or CPU-bound. CPU-bound tasks get long time slices, but infrequently. I/O-bound get frequent but short time slices. Hardware events can always interrupt a time slice, which makes the interrupted task eligible for a longer time slice later or for an earlier re-schedule. The design space is very large. If you're interested in that, I recommend reading the literature around the Linux kernel in places like LWN, which has several different scheduling strategies (you'd pick a different one for an interactive device, for a networked server or for a number cruncher), with people actively working at improving them and writing up their findings.

¹  or thread. In this context, task and thread are synonymous.
²  In this context, operating system and kernel are synonymous.
³  Note that this is a technical sense of the word “fairness”, which ignores the fact that some tasks may need more time than others. There are many more complex notions of fairness which I won't go into in this answer.


How do learn the most important nodes in a tree?

The first thing you need to consider is that stemming rules are language-specific - a stemmer for the English language will not work for Spanish.

That being said, there is already an implementation which you can use, it's called Snowball and it already has a Spanish stemmer you can use.

The only thing you need to figure out is how you want to install and use it - how you feed it the raw data and what you want to do with the output (store it somewhere, run post-processing on it etc.). There's no point in trying to reinvent the wheel. I've used Snowball and successfully written a Romanian stemmer back in the day (about seven years ago) and I must warn you it's not easy to do it from scratch even when you have all the tools (I had Snowball and the stemmer Dana Cojocaru wrote back then, but I wanted to do it on my own).

Best of luck in your endeavors!


Sorting post numbers in a graph in $O(n)$ time

You cheat. At the moment where you assign the post number, you know that it's the greatest post number so far. So you just keep a list vertices and whenever a vertex gets assigned a post number, you push it at the head of the list. At the end, the list will contain all vertices in decreasing post order. If you want them in increasing post order, you just have to reverse it which is $O(n)$. The same thing works for pre numbers.


Let $S,T$ be two sets of size $n$.  Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector corresponding to $T$.

If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then
the expected value of the Hamming distance between these two bit-vectors is

$$\mathbb{E}[d(x_S,x_T)] \approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

This gives a relation between the similarity of the two sets (in terms of the number of elements they have in common) and the Hamming distance between their Bloom filters.  In particular: the greater their similarity, the smaller the (expected) Hamming distance between their Bloom filters.

Derivation and details

Where did I get this expression for the expected value of the Hamming distance from from?  Well, consider the $i$th bit of $x_S$.  The probability that this is 0 is

$$\Pr[x_S[i]=0] = \left( 1 - {1 \over m} \right)^{kn}.$$

For the corresponding bit of $x_T$, the probability it is 1 is

$$\Pr[x_T[i]=1] = 1 - \left( 1 - {1 \over m} \right)^{kn}.$$

How about the conjunction of these two events, i.e., that $x_S[i]=0$ and $x_T[i]=1$?  We can't just multiply the two probabilities, because the two events aren't independent: the $pn$ elements in $S \cap T$ will certainly hash to the same place.  However, we can take that into account by expressing the probability as

$$\Pr[x_S[i]=0 \land x_T[i]=1] = q_1 \times q_2 \times q_3$$

where $q_1$ is the probability that none of the elements of $S \setminus T$ hash to position $i$ (i.e., $\Pr[x_{S \setminus T}[i]=0]$); $q_2$ is the probability that none of the elements of $S \cap T$ hash to position $i$ (i.e., $\Pr[x_{S \cap T}[i]=0]$); and $q_3$ is the probability that at least one of the elements of $T \setminus S$ hashes to position $i$ (i.e., $\Pr[x_{T \setminus S}[i]=1]$).  Each of these can be computed as

$$\begin{align*}
q_1 &= \left(1 - {1 \over m}\right)^{k \cdot |S \setminus T|} = \left(1 - {1 \over m}\right)^{k(1-p)n}\\
q_2 &= \left(1 - {1 \over m}\right)^{k \cdot |S \cap T|} = \left(1 - {1 \over m}\right)^{kpn}\\
q_3 &= 1 - \left(1 - {1 \over m}\right)^{k \cdot |T \setminus S|} = 1 - \left(1 - {1 \over m}\right)^{k(1-p)n}.
\end{align*}$$

Therefore, multiplying these quantities, we find that

$$\Pr[x_S[i]=0 \land x_T[i]=1] =
\left(1 - {1 \over m}\right)^{kn} \times \left(1 - \left(1 - {1 \over m}\right)^{k(1-p)n} \right).$$

Using the approximation $(1 - 1/m)^t \approx e^{-t/m}$, we see that

$$\Pr[x_S[i]=0 \land x_T[i]=1] \approx
\exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

Now by symmetry,

$$\begin{align*}
\Pr[x_S[i] \ne x_T[i]]
 &= \Pr[x_S[i]=0 \land x_T[i]=1] + \Pr[x_S[i]=1 \land x_T[i]=0]\\
 &\approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).
\end{align*}$$

Finally, linearity of expectation tells us that the expected Hamming distance between $x_S$ and $x_T$ is $m$ times the above quantity.


Proof that whether a regular language is finite is decidable

If $L$ is infinite, it contains strings of unbounded length.  Think about the sequence of states visited by the automaton when these strings are accepted. This will give you a condition of the form "$M$ accepts an infinite language implies $X$".  Now check that it's actually "if and only if $X$."


Partition array into K subsets, each with balanced sum

Use dynamic programming.  This is a straightforward application of dynamic programming.  This is a very nice exercise, so I'll let you do the exercise yourself and won't spoil it for you -- but since you only wanted a hint, my hint is "use dynamic programming" (that's a huge, enormous hint that should be enough for you to work out the rest of the details).

In particular, you should be able to solve this in $O(kn^2)$ time.


What is the computational power of Parsing Expression Grammars?

$\#$ here is just a symbol; it has no special significance. (It's often used in the construction of an modified language to indicate a new symbol which is not in the alphabet of the original language.)

$\#^{g(x)}$ is, therefore, the unary encoding of $g(x)$; in that sense, it is a count.

The double-triangle used in the later proof is just another such symbol without special significance.

In response to your second question, the paper seems to be pretty clearly state (on page 4) that the question of whether there is a CFL with no PEG is still open. In particular, it is not known whether the language of even-length palindromes has a PEG, although it is certainly a CFL.


Language comprising of Turing machine encodings

As the question suggests, it is not too hard to show a reduction from the halting problem (HP) to the language $A$ stated in the question, $HP \le A$.
This means that $A$ is undecidable, $A\notin R$ (also, it is not in co$RE$). But, is it in $RE$ or not?

Lets show that $\overline{HP} \le A$ and conclude that $A\notin RE$.

The reduction goes like that: on input $(\langle M\rangle,x)$ we generate the TM $M_x$ that, on input $w$:

If $w$=$\varepsilon$, ACCEPT.
Run $M$ on $x$. If M halts, ACCEPT (otherwise, we're in a loop anyways)

The reduction is valid: if  $(\langle M\rangle,x) \in \overline{HP}$, then $M$ does not halt on $x$. This means that $M_x$ accepts only the empty string (and loops on any other input). Thus $\langle M_x\rangle \in A$.
On the other hand, if $(\langle M\rangle,x) \notin \overline{HP}$, then $M$ halts on $x$, and $M_x$ accepts any input, thus $\langle M_x\rangle \notin A$.

It is easy to verify that the reduction is computable and complete.


This issue is simply creating a weighted function modeling the importance of each assignment. The priority function should take into account the difficulty, due date, and other factors you choose with a weighted sum of these factors.

As for the difficulty, my suggestion would be to have a difficulty scale 1-10 that the user chooses, and create your weighted function based on that, so more difficult assignments will have a higher priority.


Haskell: implementation issues of some basic features

The Wikipedia article cites a wide range of sources and has a decent "Further reading" section.


How to calculate average waiting time for round robin cpu scheduling?

The average waiting time would depend on the order in which the processes are scheduled. Your round-robin scheduler does not mention of an optimization scheme to minimize the waiting time. Both schedules listed out are correct and produce the respective waiting times.


Sequence alignment with one to many characters

If I understood your problem correctly, a trie data structure may help you. The main challenge would be after the first mismatch, match the upcomming characters. I'm not sure how I would hack it, but it may not be that hard.

Hope it helps. Regards


What's the problem of using the clock to generate random numbers?

Quick answer:

If the run time of your algorithm to pick a random number is not random you could get a pattern of times which is not random.

As an example. Suppose the function to read the time is triggered by an event, and the event is timed to the clock, now your functions based on the clock.
If the run time of your algorithm is faster than the precision of the clock, then you will get duplicate times and thus duplicate numbers which are not random.

As an example. You write a function for use by others, and someone decides to generate 10,000 random numbers and store them. The loop is so tight for reading the clock and saving the values that you get 10,000 numbers all identical.

These are just cases that can make the data non-random. In reality if it is not security related I run a large sample through a test for randomness and if it were reasonable I would use it, but if it is security related I would ask at Security or Crypto


How does a turing machine with doubly infinite tape simulate a normal-taped turing machine?

Given the doubly infinite machine $M = (Q,\Gamma,\sqcup,\Sigma,\delta,q_{0},F)$ where:

$Q$ is the set of states,
$\Gamma$ is the tape alphabet,
$\sqcup \in \Gamma$ is the blank symbol,
$\Sigma \subseteq \Gamma\setminus\{\sqcup\}$ is the input alphabet,
$\delta: Q\setminus F\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\}$  is the transitions function (there are various common modifications to $\delta$ which you can add in if you wish),
$q_{0} \in Q$ is the start state, and
$F$ is the set of final states,

we can simulate a singly infinite Turing machine with the following modifications to $M$:

add a new symbol $\#$ to $\Gamma$ which will mark the "left-hand end" of the simulated tape,
add the new states $k_{0}$, $k_{1}$ and $r$ to $Q$,
make $k_{0}$ the new start state,
add the following transitions:

$(k_{0}, x) \mapsto (k_{1},x,L)$ for every $x \in \Gamma$
$(k_{1}, \sqcup) \mapsto (q_{0}, \#, R)$
$(q_{i}, \#) \mapsto (r, \#, L)$

make $r$ a reject state in whatever way you're handling reject states.

This new machine starts (as suggested in the question) by writing a new, special, end-of-tape symbol just to the left of the input. Then if it ever sees that symbol again, it rejects (it has "fallen off the tape").

A similar technique can be used to prevent a singly infinite TM from falling off the left-hand end of the tape, so you can also encode that into the machine, and it would work similarly.


Consider $w = a^nb^na^nb^n$, then it is similar to proving language {ww} is not CFL.

In the given language there is no restriction on length of y. So, let it be zero.
Now, for any valid decomposition w = uvxyz, $uv^ixy^iz$ belongs to L.


Approximate max weight path in directed graph

You can't.  That approach is a dead end.  Finding the maximum (simple) path is NP-hard, by reduction from Hamiltonian cycle.  See, e.g., How to prove NP-hardness of a longest-path problem?, How is the Longest Path Problem NP complete?, Longest cycle in a digraph, https://en.wikipedia.org/wiki/Longest_path_problem.  It is also known to be hard to approximate, so you shouldn't expect any such simple approach to give a good approximation for all graphs.


A visitor at a political convention with n delegates

You need to make sure what is returned from AMajorityPolitician(set of politicians S) is indeed a politician from the majority in S if there is a majority.
To ensure majority, we need to count the number of politicians who are in the same party as the chosen one. Here is the simple routine.
def number_of_friendly_politicians(person, all_people):
    count = 0
    for p in all_people:
        if smiles_between(person, p):
            count ++;
    return count

Now refactor AMajorityPolitician to the following function, which returns a majority politician in politicians whenever there is a majority.
def a_majority_politician(politicians):
    if size(politician) is 1:
        return that person

    L = a_majority_politician(half of politicians)
    R = a_majority_politician(other half of politicians)

    if number_of_friendly_politicians(L, politicians) * 2 > size(politicians):
       return L
    else:
       return R    # R may or may not in a majority.


Finding the values of x and y using base 8

I think the issue with your method is that your subtracts are neglecting to account for the carry values that happen during the addition. If we instead go right to left and account for carries, we get:

(abc+010 def+101 110+abc 111+101)=(111 001 def abc)
                         100
                 (110 + 100 + 1) // carrying the 1 here from the addition in the previous place
                 011
         (011 + 101 + 1) // carrying a 1 from the previous place again
         001
(100 + 010 + 1) // again, carrying a 1
111

Thus, we have that:

111 001 011 100 = (111 001 def abc)

Meaning that 100_2 = abc_2 and 011_2 = def_2, implying x=4 and y=3.


Scheduling of process manufacturing with setup times

We use the index $k$ for time such that $k \in [s_1, e_{n_t}]$

We introduce the following variables:

$\ell^{i,k}$ - line $i$ is leased at line $k$

$\alpha^{i,k}_{j,j'}$ - binary indicator for line $i$ is switching from $j$ to $j'$ at time $k$.

$p^{i,k}_j$ - binary indicator for line $i$ is producing good $j$ at time $k$.

$h^{i,j}_j$ - binary indicator that line $i$ is waiting to produce good $j$ at time $k$

$g^{i,k}_j$ - generated amount for line $i$ for good $j$ at time $k$ (either $v_{i,j}$ or $0$)

Then goal is to minimize $\sum_{i,k} c_i \ell^{i,k}$ subject to constraints:

Constraints for every $i,k$:

can only switch to 1 good at a time: $\textrm{at-most-1} \alpha^{i,k}_{j,j'}$
can only make 1 good at a time: $\textrm{at-most-1}  p^{i,k}_j$
can only hold for 1 good at a time: $\textrm{at-most-1}  h^{i,k}_j$
if producing, not switching: $\bigvee_j p^{i,k}_j \rightarrow \neg \bigwedge_{j,j'} \alpha^{i,k}_{j,j'}$
leasing iff producing or switching: $\ell^{i,k} \leftrightarrow \bigvee_{j,j'} \alpha^{i,k}_{j,j'} \vee \bigvee_j p^{i,k}_j$
not leasing implies holding for some good: $ \neg \ell^{i,k} \Rightarrow \bigvee_j h^{i,k}_j$

Constaints for every $i,k,j$:

Generating only if producing:
$$p^{i,k}_j \rightarrow g^{i,k}_j = v_{i,j}$$
$$\neg p^{i,k}_j \rightarrow g^{i,k}_j = 0$$
when stopping producing, it must immediately hold for same good or switch to another good (for $k < e_{n_t}$):
$p^{i,k}_j \wedge \neg p^{i,k+1}_j \Rightarrow h^{i,k+1}_j \vee \bigvee_{j'} \alpha^{i,k+1}_{j,j'}$
if producing or holding at $k+1$ must have been producing, holding, or switching at $k < e_{n_t}$:
$p^{i,k+1}_j \vee h^{i,k+1}_j \Rightarrow p^{i,k}_j \vee h^{i,k}_j \vee \bigvee_{j'} \alpha^{i,k}_{j',j}$

Constraints for every $i,k < e_{n_t},j,j'$:

when switching, it must switch long enough:
$(p^{i,k}_j \vee h^{i,k}_j) \wedge \alpha^{i,k+1}_{j,j'} \Rightarrow \bigwedge_{k'=k+2}^{\min(k+u_{j,j'}, e_{n,t})} \alpha^{i,k'}_{j,j'}$

Constraints for every $d_{j,t}$:

$\sum_{k=s_t}^{e_t} \sum_i g^{i,k}_j \geq d_{j,t}$


Simplifying the Boolean expression $A + \bar{A}\bar{B}$?

There is a Law of Distributivity of Boolean operation $\lor$ (disjunction, which is sometimes denoted by $+$) over Boolean operation $\land$ (conjunction, which is sometimes simply omitted):
$$x \lor (y \land z)= (x \lor y)\land(x \lor z)$$
So, in your case:
$$A \lor (\lnot A \land \lnot B) = (A \lor \lnot A) \land (A \lor \lnot B) = A \lor \lnot B$$
For more information please see: Boolean Algebra.


Suppose that $x = x_1 \cdots x_n$, where $|x_i| = k$, and there exists some $z \in \{0,1\}^k$ such that $x_i \neq z$ for all $i$. We can encode $x$ by first listing $z$, and then encoding each $x_i$ using $\log_2 (2^k-1)$ fractional bits. The program also needs to know $n$. This shows that
$$
K(x) \leq \log_2 (2^k-1) \cdot n + C_k + O(\log n),
$$
where $C_k$ is a constant that depends only on $k$. In particular, if $n$ is large enough that the upper bound will be less than $nk$.


Maximize rental income given a set of date intervals

The most common subproblems where a particular subsequence should be selected are parametrized by the index of the last element selected. The classical, simple and brilliant example is Kadane's algorithm.

Let the given intervals are $I_1, I_2,\cdots, I_n$, where $I_j=[l_j, r_j]$.

The subproblem $DP[i]$, where $1\le i\le n$ is the maximum rent if the last interval rented is the $i$-th interval. The answer is $\max_iDP[i]$.

We could add an artificial base case, $DP[0]=0$, which says that the maximum rent is 0 if there is no interval rented.

The recurrence relation is
$$DP[i] = \text{Length}(I_i) + \max_{r_j\lt l_i} DP[j].$$

That is it, basically. There is a minor problem with the above recurrence relation, however. When we compute $DP[i]$, not all of $DP[j]$ with $r_j\lt l_i$ has been computed. I will leave it for you to resolve this minor obstacle.


Show that moving one symbol to the end still makes a regular language

Consider a DFA for the original language with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct an NFA for the new language which operates roughly as follows:

It first guesses the initial symbol $a$.
It then reads the word $w$.
A state is accepting if $wa \in L$.

To implement this, the set of states will be $\Sigma \times Q$, that is, the set of pairs $(a,q)$ where $a \in \Sigma$ and $q \in Q$. The initial states are $(a,\delta(q_0,a))$. A state $(a,q)$ is final if $\delta(q,a) \in F$. Finally, the transition relation is $\delta((a,q),b) = (a,(q,b))$.

You can solve this in many other ways. One of the simplest is using closure properties. Let $a^{-1}L = \{w \in \Sigma^* : aw \in L\}$, which is a quotient $L \setminus \{a\}$ per your definition. Then
$$ \texttt{MOVE}(L) = \sum_{a \in \Sigma} (a^{-1}L)a. $$
You can even implement this using regular expression. Given a regular expression for $L$, construct a regular expression for $a^{-1}L$ using the following rules:

$a^{-1} \emptyset = a^{-1} \epsilon = \emptyset$.
$a^{-1}a = \epsilon$ and $a^{-1}b = \emptyset$, where $b \neq a$ is a symbol.
$a^{-1}(r_1+r_2) = a^{-1}r_1+a^{-2}r_2$.
If $r_1$ doesn't generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2$.
If $r_1$ does generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2 + a^{-1}r_2$.
$a^{-1}(r^*) = (a^{-1}r)r^*$.

You can determine whether $r$ generates $\epsilon$ recursively. Denoting this predicate by $E$,

$E(\emptyset) = E(a) = F$, $E(\epsilon) = T$.
$E(r_1+r_2) = E(r_1) \lor E(r_2)$.
$E(r_1r_2) = E(r_1) \land E(r_2)$.
$E(r^*) = T$.

This gives a mechanical procedure to compute a regular expression $a^{-1}r$ satisfying $L[a^{-1}r] = a^{-1}L[r]$. We can then define
$$ \texttt{MOVE}(r) = \sum_{a \in \Sigma} (a^{-1}r)a, $$
which satisfies $L[\texttt{MOVE}(r)] = \texttt{MOVE}(L[r])$.


Cook completeness of a variant of Vertex Cover

First it is obvious that the above problem is in NP.
I think there is even a Karp reduction from the well-known clique problem. It uses the well-known reductions from clique problem to independent set problem and from  independent set problem to vertex cover problem.

The clique problem is as follows:

Given: a graph $G$ of size $n$, parameter $k$

Output: Yes iff there is a clique in $G$ of size $k$.

Now, first we add a clique  of size $k-1$ in $G$. For sake of presentation, we denot the resulted graph by $G'$. Then, we create the corresponding complement of $G'$, denoted by  $\hat{G}$. Denote $\hat{G}=(\hat{V},\hat{E})$ and let $V_{clique} \subseteq \hat{V}$ be the set of vertices corresponding to the original clique of size $k-1$ in $G$. The reduction is a polynomial transformation. Note that $|\hat{V}|=n+k-1$

The graph $G$ contains a clique of size $k$ if and only if $G'$ contains a clique of size $k$, since adding a clique  of size $k-1$ does not effects if $G$ has a clique of a larger size. Using the same arguments done in reduction from clique problem to the independent set problem and from independent set problem to vertex cover problem,  we derive that    $G$ contains a clique of size $k$ if and only $\hat{G}$ contains a vertex cover of size $|\hat{V}|-k=n-1$.

Using similar arguments, we derive that $V_{clique}$ is an independent set in $\hat{G}$, and thus  the set $\hat{V}\setminus  V_{clique}$ is a vertex cover in $\hat{G}$ of size $|\hat{V}|-(k-1)=n$.

Finally, let $L_{clique}$ and $L_{vertex}$ be the corresponding languages of the clique and the described vertex cover problems. Then, $(G,k) \in L_{clique}$ iff $(\hat{G},\hat{V}\setminus  V_{clique}) \in L_{vertex}$ (i.e., there exists a clique of size $k$ in $G$ iff there is a vertex cover of size $|\hat{V}\setminus  V_{clique}|=n-1$ in $\hat{G}$).


ZK proof that I possess a ZK proof for membership in $L$?

Yes, it's possible. There is a ZK proof for every language in NP.  Roughly speaking, this means that if there's a way for someone to prove it (by giving a polynomial-size witness/proof), there's a way to prove it with a zero knowledge proof.

For instance, if you have a transcript of a ZK interaction, there's a polynomial-time algorithm to verify whether the ZK interaction should be accepted by the verifier, so it's possible to prove in ZK (i.e., it's possible to give a ZK proof) that you know a transcript of a ZK interaction that would be accepted by the verifier.  However, this might not be quite what you want, because this doesn't prove that the randomness was chosen randomly by the verifier.

Here's a better instance of what you're looking for.  Look up non-interactive zero knowledge proofs.  Suppose I know a string $p$ that is a valid non-interactive zero knowledge (NIZK) proof of some statement $s$.  Moreover, there is a polynomial-time algorithm that allows verifying whether $p$ is a valid NIZK proof of $s$.  Therefore, there's a way I can use a ZK proof to prove to Alice in zero-knowledge that I know a string $p$ that is a valid NIZK proof of $s$, without revealing $p$ to Alice (because this is proving a NP statement).

That said, this probably isn't useful.  What would be the point?  I don't think this lets Alice conclude anything more than if I just proved in ZK to her that $s$ is true.


red black tree and 2-3-4 tree isomorphism

It depends what you mean by isomorphic. Indeed a black node with its (zero, one or two) children corresponds to a 2-3-4 node (with 1,2,3 keys and 2,3,4 children). The basic operations on the two types of trees are really different but translate quite well.

There is a single difference in symmetry: there is only one type of 3-node (2 keys, 3 children), whereas in a red-black tree the red child to the black node may be at the left or right side.


Why run -time of N-Queens using backtracking algorithm fluctuates?

Consider that there might be something wrong with your experimental setup. The theoretical running time of an algorithm is based on an ideal model of a computer, but in practice there are lots of non-ideal behaviours. The running time of an experiment can vary based on lots of factors, and will be different from run-to-run.

You should repeat the experiment a number of times, and take the average running time of those runs to get a reliable reading. You could also compute the standard deviation of the running time, so you can get a good idea of whether the observed difference is statistically significant.

I implemented a straightforward backtracking approach to enumerate all solutions to the $n$-queens problem. The running time, taken as an average over 10,000 runs, was 0.045 ms for $n=7$, and 0.22 ms for $n=8$. This nicely fits with the fact that the number of (partial) solutions explored was 552 for $n=7$, and 2057 for $n=8$ (we have that $\frac{2057}{552}\times0.045\times\frac{8}{7}=0.19\approx 0.22$). So, based on my data, there is nothing that suggests $n=8$ is faster than $n=7$ -- if we want to enumerate all solutions.

Keep in mind that it is really hard to measure very low running times. There are other processes running at the same time, and how these are scheduled may affect the running time of your process. Your operating system may preempt your process for a while to run another process. For best accuracy, you should measure CPU time rather than "wall time", so that the time that your process is preempted is not taken into account.

If you're doing only a single run, the 0.773 or 0.492 (seconds?) you are measuring probably isn't the time required to do the backtracking (since that takes less than a millisecond), it's the time required to launch the process and load the executable from disk. The magnitude of the thing you're measuring is very small compared to the magnitude of the noise.

For completeness, here are my results for $n=1$ to $14$, giving the total number of valid partial solutions, the number of valid complete solutions (with $n$ queens), the first time (i.e., after how many partial solutions) a complete solution was found, average running time in ms, number of runs the average was taken over and the minimum/maximum number of timer ticks for a single run (to show how wide the spread in measured running times is).

n=1     total: 2        valid: 1        first: 2        0,0003ms        runs: 10000     min/max: 0/868
n=2     total: 3        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/55
n=3     total: 6        valid: 0        first: -1       0,0006ms        runs: 10000     min/max: 0/45
n=4     total: 17       valid: 2        first: 9        0,0009ms        runs: 10000     min/max: 1/96
n=5     total: 54       valid: 10       first: 6        0,0018ms        runs: 10000     min/max: 3/167
n=6     total: 153      valid: 4        first: 32       0,0071ms        runs: 10000     min/max: 15/286
n=7     total: 552      valid: 40       first: 10       0,0492ms        runs: 10000     min/max: 131/765
n=8     total: 2057     valid: 92       first: 114      0,2412ms        runs: 10000     min/max: 703/3107
n=9     total: 8394     valid: 352      first: 42       1,1385ms        runs: 2635      min/max: 3393/7416
n=10    total: 35539    valid: 724      first: 103      5,5285ms        runs: 543       min/max: 16869/29597
n=11    total: 166926   valid: 2680     first: 53       30,03 ms        runs: 100       min/max: 91033/116218
n=12    total: 856189   valid: 14200    first: 262      172,61ms        runs: 18        min/max: 543521/593573
n=13    total: 4674890  valid: 73712    first: 112      1037,2ms        runs: 10        min/max: 3379429/3490449
n=14    total: 27358553 valid: 365596   first: 1900     6736,1ms        runs: 10        min/max: 21845050/23117728

If we consider purely the time until finding the first solution, then the running time no longer is strictly increasing, but certain $n$'s are ``easier'' to solve in the sense that the backtracking strategy used happens to come across a valid solution earlier:

n=1     total: 2        0,0005ms        runs: 10000     min/max: 0/1199
n=2     total: 3        0,0005ms        runs: 10000     min/max: 0/50
n=3     total: 6        0,0004ms        runs: 10000     min/max: 0/50
n=4     total: 9        0,0004ms        runs: 10000     min/max: 0/56
n=5     total: 6        0,0004ms        runs: 10000     min/max: 0/44
n=6     total: 32       0,0016ms        runs: 10000     min/max: 2/64
n=7     total: 10       0,0006ms        runs: 10000     min/max: 1/54
n=8     total: 114      0,0089ms        runs: 10000     min/max: 21/232
n=9     total: 42       0,0033ms        runs: 10000     min/max: 7/199
n=10    total: 103      0,0107ms        runs: 10000     min/max: 29/140
n=11    total: 53       0,0052ms        runs: 10000     min/max: 14/77
n=12    total: 262      0,0533ms        runs: 10000     min/max: 138/2867
n=13    total: 112      0,0192ms        runs: 10000     min/max: 51/228
n=14    total: 1900     0,4925ms        runs: 6091      min/max: 1375/3820
n=15    total: 1360     0,3772ms        runs: 7953      min/max: 1072/3057
n=16    total: 10053    3,1402ms        runs: 956       min/max: 8997/17103
n=17    total: 5375     1,7544ms        runs: 1710      min/max: 5040/13332
n=18    total: 41300    14,813ms        runs: 203       min/max: 45021/60028
n=19    total: 2546     0,9637ms        runs: 3113      min/max: 2753/8341
n=20    total: 199636   83,5  ms        runs: 36        min/max: 264863/288246
n=21    total: 8563     3,9   ms        runs: 770       min/max: 11193/18734
n=22    total: 1737189  953,3 ms        runs: 10        min/max: 2900112/3477819
n=23    total: 25429    15,342ms        runs: 196       min/max: 41098/116394
n=24    total: 411609   251,833ms       runs: 12        min/max: 803905/970462
n=25    total: 48684    31,6211ms       runs: 95        min/max: 92880/133684

The total column reports the number of partial solutions considered before a valid complete solution is found (or the total number of partial solutions considered if there do not exist valid complete solutions). You can see that (for instance) when $n$ goes from 20 to 21 there is a large drop in number of solutions that need to be considered (and consequently a large drop in running time).

In this case, my backtracking algorithm (which uses the most obvious approach of starting at the top left, recursing, and moving the queen in each row from left to right), contrary to yours, takes longer to find a solution for $n=8$ than it does for $n=7$. However, the spread in running times (even though the algorithm is completely deterministic) is large: the fastest $n=8$ solution is more than twice as fast as the slowest $n=7$ solution.

It is difficult to quantify why a certain $n$ is more ``lucky'' than another, because this requires a deep understanding of the structure of the search space and how it interacts with a particular backtracking strategy.

One interesting fact is that if $n$ is odd, there always exists a solution placing a queen in the top left corner. This leads to the observation that the time to find the first solution for $2n+1$ is always much faster than that for $2n$, because the algorithm's guess (in the $2n+1$ case) for the first queen (top left corner) is always correct and the problem then reduces to solving a restricted version for the $2n$ case where no queens can be placed on the diagonal.


This is a common misconception many have. Subset sum, among others, is NP-complete only if the input is encoded in binary (or ternary etc). In unary encoding it's polynomial-time solvable by a simple dynamic programming approach. These problems are sometimes referred as weakly NP-complete.
If you're not quite sure what I mean by unary encoding: Unary encoding means we encode a number by a sequence of $1$'s of appropriate length.
All in all, I fear you haven't settled P/NP (unless, of course, your runtime refers to binary-encoded problems). But good luck!
As an example, suppose your input consists of $10$ numbers, each between $128$ and $256$. Then your input size is, in unary, about $10 \times 256=2560$, whereas your input size is, in binary, $10 \times \log_2 (256) =80$.
That's quite a difference!

Wikipedia describes an algorithm that works in polynomial time for unary encoding. Wikipedia's solution was taken from the book Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. Garey and D. Johnson.


Is it possible for a language and its complement to both be unrecognizable?

I'll write "corecognizable" as a shortcut for "complement of recognizable". There are countably many recognizable languages and countably many corecognizable languages. Therefore, there are uncountably many languages which are neither recognizable nor corecognizable.


Yes every AVL tree is a BST

also note that every binary search tree itself is a binary tree (binary tree is basically a tree that each node has at most two child)  so therefore every AVL is a binary tree as well.

AVL tree is just a binary search tree that tries to do rotations when its needed (when the tree becomes unbalanced) in order to stay balanced, and therefore the search time would be O(logn)

the reason behind using AVL instead of BST is to make sure the search time is O(logn) because if we use BST and insert the values in a decreasing or increasing order then the BST would be one sided and the search time will be O(n), but if we do that using AVL then the tree will balance itself using rotations.

i suggest you to read the definitions of all of them so you can understand better.