The trick is to use linearity of expectation. Let $E_k$ be the event that the $k$th input is a left-to-right minimum (i.e., requires an update), and let $X_k$ be an indicator variable for $E_k$, that is, $X_k$ is $1$ if $E_k$ happens and $0$ otherwise. Let $U = X_1 + \cdots + X_n$ be the number of updates. The expected number of updates is
$$ \mathbb{E}[U] = \sum_{k=1}^n \mathbb{E}[X_k] = \sum_{k=1}^n \Pr[E_k]. $$
It remains to compute $\Pr[E_k]$. We can construct a random permutation $\pi$ of $[n] = \{1,\ldots,n\}$ in the following way: take a random permutation of $[n]$, and randomly permute the first $k$ elements. This shows that the probability that $\pi(k) = \min(\pi(1),\ldots,\pi(k))$ is exactly $1/k$, and so $\Pr[E_k] = 1/k$. All in all, we get
$$ \mathbb{E}[U] = \sum_{k=1}^n \Pr[E_k] = \sum_{k=1}^n \frac{1}{k} = H_n, $$
the $n$th Harmonic number. It is well-known that $H_n = \ln n + \gamma + O(1/n)$ (Wikipedia contains the entire asymptotic expansion).

We can also compute the variance in this way:
$$
\begin{align*}
\mathbb{E}[U^2] &= \sum_{k=1}^n \mathbb{E}[X_k^2] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \mathbb{E}[X_k X_\ell] \\ &=
\sum_{k=1}^n \Pr[E_k] + 2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell],
\end{align*}
$$
where $\land$ is logical AND. We already know that $\Pr[E_k] = 1/k$. In order to compute $\Pr[E_k \land E_\ell]$ (where $k < \ell$), we follow the same route as before. With probability $1/\ell$, $\pi(\ell)$ is a left-to-right minimum. Given that, the probability that $\pi(k)$ is a left-to-right minimum is $1/k$. Therefore $\Pr[E_k \land E_\ell] = 1/(k\ell)$, and so
$$
\begin{align*}
2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \Pr[E_k \land E_\ell] &=
2\sum_{k=1}^{n-1} \sum_{\ell=k+1}^n \frac{1}{k\ell} \\ &=
\left(\sum_{k=1}^n \frac{1}{k}\right)^2 - \sum_{k=1}^n \frac{1}{k^2} \\ &=
H_n^2 - \sum_{k=1}^n \frac{1}{k^2}.
\end{align*}
$$
Therefore
$$
\begin{align*}
\mathbb{E}[U^2] &= H_n + H_n^2 - \sum_{k=1}^n \frac{1}{k^2}, \\
\mathbb{V}[U] &= H_n - \sum_{k=1}^n \frac{1}{k^2} = \ln n + \gamma - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right).
\end{align*}
$$
We can compute all other moments in a similar way using (essentially) the inclusion-exclusion principle and the formula
$$
\mathbb{E}[U^d] = \sum_{i_1,\ldots,i_d=1}^n \prod_{i \in \{i_1,\ldots,i_d\}} \frac{1}{i}.
$$
If we are careful enough then we can probably establish the asymptotic normality of $U$.


Presumably it can check any "liveness" property that that can be formulated in LTL. A "liveness" property is typically described as a property stating that "something good eventually happens". This is usually contrasted to a "safety" property which states that "nothing bad ever happens". See e.g. Slide 20 of this SPIN tutorial. Basically, a basic safety property will look like $\square P$ which states that it is always the case that $P$ holds, e.g. the temperature is always below boiling. A basic liveness property  might look like $\lozenge Q$ which states that $Q$ eventually happens, e.g. eventually the HALT state is reached.

A seminal paper is An Automata-Theoretic Approach to Automatic Program Verification. The idea is to use a Büchi automaton, which is just a normal finite state automaton with a notion of acceptance that works on infinite words. The key result is that you can turn an LTL formula into a Büchi automaton that accepts exactly the computations that satisfy the LTL formula. A model checker takes your specification and produces a Büchi automaton, then it takes the LTL constraint, negates it, and produces a Büchi automaton for it. Finally, it intersects the two Büchi automata and endeavors to show that the resulting automaton accepts nothing, i.e. describes the empty language. It does this by conceptually (and to a large extent actually) enumerating all the states. In practice, the state space is way too large to be completely enumerated and this is why model checkers are not theorem provers.

So what's the issue with "liveness" properties that would cause them not to be included from the beginning? To check (the failure of) $\square P$ in a model checker is straightforward. You simply check $P$ for each state. If $P$ ever fails to hold, then you've found a counter-example to $\square P$. On the other hand, checking $\lozenge Q$ requires producing a trace that will never hit a state satisfying $Q$. There are two ways this could happen. First, we could reach a final state without ever going through a state satisfying $Q$. This is straightforward to check. Second, we could enter an infinite loop without ever reaching a state satisfying $Q$. To check this, we need to check if we reach a state that this particular trace has been to before without ever passing through a state satisfying $Q$.

It's the "this particular trace" that is problematic. For safety properties, it is enough to visit each state. How you get to a state for the most part doesn't matter. You'll want to keep track of which states have been visited to avoid (potentially infinite) repeated work, but it doesn't matter which trace visited a state. For liveness properties, it is not enough to know that some trace has visited a state. You need to know if this trace has visited that state. The upshot is that checking a safety property just requires enumerating the reachable states, while checking a liveness property requires cycle detection. Of course, there are linear-time algorithms for calculating strongly connected components.  Due to the sheer number of states, transcribing textbook algorithms is often not adequate. You can see an indication of some of the issues here. As far as I can tell from the source code and that page, TLC does just do Tarjan's algorithm, but this interacts poorly with distribution (i.e. liveness checking is not supported in the distributed mode) and with symmetry reduction techniques to reduce the state space. It is also just inherently slower than checking safety properties.


Is there a TM that halts on all inputs but that property is not provable?

Yes. The Turing machine that computes the Goodstein sequence beginning from its input and terminates when the sequence hits zero.  It always terminates but this can't be proven in Peano arithmetic.  I'm sure there are equivalent things for ZFC or any other system you might choose.

Edit For ZF, Hartmanis and Hopcroft show that there's a Turing machine $M$ that rejects every input but that this can't be proven in ZF.  I'm not sure if ZF can prove that $M$ always halts but it certainly can't prove that the machine $M'(x)$ $=$ "If $M$ accepts $x$ then loop forever, else halt" always halts, even though it does.  That still leaves ZFC open but ZF is more powerful than PA.

See Sec. 3 of Scott Aaronson's survey on independence of P=NP for an exposition of the Hartmanis–Hopcroft result and citations to their original papers.


The algorithm $B$ is described in a mildly sloppy way. You can look at it as a two-step process:

Find suitable $P_k$.
Run $P_k$.

Now, step 1 can be done one program at a time since the set of all programs is recursively enumerable and we assume that a recursive (and total) elegance tester $\mathrm{ET}$ exists. Note that we use $\mathrm{ET}$ as an oracle.

So, the algorithm is this:

def B(N,x)
  E = program_enumerator

  do
    P = E.next
    if ( length(P) <= N )
      continue
  while ( !ET(P) )

  return P(x)
end

Why is this a proof? We call the underlying technique proof by contradiction. Here is what happens:

Assume that a general, total elegance checker $\mathrm{ET}$ exists.
Under this assumption, construct a (computable!) program $B$ that is equivalent to a program $P$ so that $B$ is smaller than $P$ but $\mathrm{ET}$ says that $P$ is elegant (i.e. smallest).
Since this is a contradiction, the assumption has to be false; that is, such an elegance checker can not exist.


How can I understand which element from A is reduced only by looking at C?

I guess you can make $C$ array two-dimensional $C[2][n]$ and in the second array you will initially (and after the counting step) store 0-es only. (This means when counting you will fill only the $C[0][n])

After, the counting step, your $C$ array should look like (taking the example above):

0 1 0 0 2  <- count of the elements with value i (i >= 0)
0 0 0 0 0  <- flag if the i-th element has been reduced.

When you reduce an element with value $j$, you will do:

$C[0][j]$--; // decrease the count of $j$
$C[0][j - x]++$; // increase the count of $(j - x)$
$C[1][j]$ = 1; // set $j$ as decreased

This way, when you want to check if a value $j$ was reduced, you can just get the value of $C[1][j]$ and check if it is $1$. The complexity of this will be $O(1)$.

  How can I sort it now in $O(k)$?

For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, shift the decreased element to the left or to the right.


Is there a generalization of Huffman Coding to Arithmetic coding?

Let's look at a slightly different way of thinking about Huffman coding.

Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for this example.

Suppose our state is a large integer, which we will call $s$. You can think of encoding as a function which takes the current state, and a symbol to encode, and returns the new state:

$$\begin{align*}
\hbox{encode}(s, A) &= 2s\\
\hbox{encode}(s, B) &= 4s + 2\\
\hbox{encode}(s, C) &= 4s + 3\\
\end{align*}$$

So let's start with the state 11 (which is 1011 in binary), encode the symbol B.  The new state is 46, which is 101110 in binary. As you can see, this is the "old" state with the sequence 10 added to the end. We have essentially "output" the bit sequence 10.

So far, so good.

Now think for a moment about how arithmetic coding works. If you put the probabilities over a common denominator, the symbol A actually represents the range $[\frac{0}{4},\frac{2}{4})$, the symbol B represents the range $[\frac{2}{4},\frac{3}{4})$ and the symbol C represents the range $[\frac{3}{4},\frac{4}{4})$.

Basically what we're doing here is multiplying everything by the common denominator. Imagine that the state was actually in base 4. Encoding a symbol B is really outputting the digit 2 in that base, and encoding a symbol C is outputting the digit 3 in that base.

However, symbol A is a little different, because it isn't a whole digit in base 4.

Instead, we can think of the alphabet as the set of symbols A_0, A_1, B, C, with equal probability. This, again, has an optimal Huffman code 00, 01, 10, 11. Or, again, we can think of this in base 4. To encode a symbol, we just do:

$$\begin{align*}
\hbox{encode}(s, A_0) &= 4s + 0\\
\hbox{encode}(s, A_1) &= 4s + 1\\
\hbox{encode}(s, B) &= 4s + 2\\
\hbox{encode}(s, C) &= 4s + 3
\end{align*}$$

So now it's clear how to encode symbols B and C, but to encode a symbol A, we have a choice. Which of $A_0$ and $A_1$ should we use?

Now here's the clever idea: we steal one bit of information from the state $s$:

$$s' = \left\lfloor \frac{s}{2} \right\rfloor$$
$$i = s \bmod 2$$

and then $\hbox{encode}(s', A_i)$.

Using our previous example, $s=11$, we find that $s'=5$ and $i=1$, and then $\hbox{encode}(5, A_1) = 4\times 5+1 = 21$. The new state is 10101 in binary.

Now this doesn't produce exactly the same bit output as Huffman coding, but it does generate an output which has the same length. And what I hope you can see is that this is also uniquely decodable. To decode a symbol, we take the remainder when divided by 4. If the value is 2 or 3, then the symbol is B or C respectively. If it's 0 or 1, then the symbol is A, and then we can put the bit of information back by multiplying the state by 2 and adding either 0 or 1.

The nice thing about this approach is that it extends naturally to fractional-bit encoding, when the numerator and/or denominator of the probabilities are not powers of two. Suppose we have two symbols, A and B, where the probability of A is $\frac{3}{5}$ and the probability of B is $\frac{2}{5}$. Then we can encode a symbol with:

$$\begin{align*}
\hbox{encode}(s, A_0) &= 5s + 0\\
\hbox{encode}(s, A_1) &= 5s + 1\\
\hbox{encode}(s, A_2) &= 5s + 2\\
\hbox{encode}(s, B_0) &= 5s + 3\\
\hbox{encode}(s, B_1) &= 5s + 4
\end{align*}$$

To encode the symbol A, we take $s' = \left\lfloor \frac{s}{3} \right\rfloor$ and $i = s \bmod 3$, and then $\hbox{encode}(s', A_i)$.

This is equivalent to arithmetic coding. It's actually a family of methods known as Asymmetric Numeral Systems, and was developed over the last few years by Jarek Duda. The meaning of the name should be obvious: to encode a symbol with probability $\frac{p}{q}$, you conceptually steal a base-p digit from the state, and then add a base-q digit. The asymmetry comes from interpreting the state as a numeral in two different bases.

The reason why it's a family of coding methods is that what we've seen here is impractical by itself; it needs some modifications to deal with the fact that you probably don't have infinite-precision integers to manipulate the state variable efficiently, and there are various ways that you can achieve this. Arithmetic coding, of course, has a similar issue with precision for its state.

Practical variants include rANS (the "r" means "ratio") and tANS ("table-driven").

ANS has a few interesting advantages over arithmetic coding, both practical and theoretical:

Unlike arithmetic coding, the "state" is a single word, rather than a pair of words.
Not only that, but an ANS encoder and its corresponding decoder have identical states and their operations are completely symmetric. This raises some interesting possibilities, such as that you can interleave different streams of encoded symbols and everything synchronises perfectly.
Practical implementations need, of course, to "output" information as you go, and not just collect it in a big integer to be written at the end. However, the size of the "output" can be configured in return for (usually modest) compression loss. So where arithmetic coders must output a bit at a time, ANS can output a byte or a nybble at a time. This gives you a direct tradeoff between speed and compression.
It appears to be about as fast on current-generation hardware as binary arithmetic coding, and hence competitive with Huffman coding. This makes it much faster than large-alphabet arithmetic coding and its variants (e.g. range coding).
It appears to be patent-free.

I don't think I'm ever going to do arithmetic coding again.


For what kinds of languages is min |NFA| = Ω(min |DFA|)?

Perhaps this is too trivial to bear mentioning, but I'll mention it anyway: one class of languages comes to mind (although there may be much more interesting classes of languages than this which satisfy the property).

Consider a family of languages $\{\{\epsilon\}, \{w\}, \{ww\}, ..., \{w^n\}, ...\}$ where $w \in \Sigma^*$. A minimal NFA for the $n$th language will have $n|w|+1$ states (assuming no dead state), whereas a minimal DFA will have $n|w|+2$ states (assuming a single dead state). We have that $n|w|+1 = \Omega(n|w|+2)$.

We get another family by allowing each language to accept up to $n|w|$; this is the family $\{\{\epsilon, w, ww, ..., w^n\} \mid n \geq 0\}$. The automata for these languages are practically identical to the corresponding automata from the other family, except these have more accepting states.

These happen to be families of finite languages. We could, of course, get a family of infinite languages as follows: $\{\{w^nw^*\} \mid n \geq 0\}$.

Consider any family of languages which consist of a single word. For any such language, the ratio of $|\min DFA|$ to $|\min NFA|$ will be less than $2$, so such a family of languages must satisfy the property. Since there are countably many finite strings over any alphabet, and since we're considering any possible subset thereof, we get an uncountable number of language families in this manner.

FWIW, to get these examples, my thinking was that we're looking for languages that involve doing something which an NFA can't do much better than a DFA. Accepting some random string, and nothing else, is notable in this regard. I guess more generally, there's an informal notion of "straightforwardness of the DFA" that seems to be related to what's being asked.

You know, come to think of it, I think we can generalize this a bit more: any family of languages with the following form should work: $L_n = \{s_0s_1...s_i\}L$ for $n \geq 0$, where $L$ is any regular language and $s_n$ is any finite string. Suppose for $L$ that $|\min DFA| = x$ and $|\min NFA| = y$. Then the family $L_n$ should always have $|\min DFA| / |\min NFA| \leq x/y$.

I don't know whether this is pertinent, interesting or useful, but I thought if nothing else this might revive the question.


Complexity of factoring products of distinct prime numbers

As far as I know, there are no non-trivial lower bounds on factoring, and in particular, no variant is conjectured to be NP-hard. (While factoring is not a decision problem per se, you can make up a corresponding decision problem that gives the $k$bit of the $\ell$th smallest factor.)

As far as algorithms go, there are a great many of them, including the following subexponential ones:

Quadratic sieve: this factors an integer $n$ in time $2^{O(\sqrt{\log n\log\log n})}$. There are many variants of this algorithm resulting in different constants for the big O, and one of them (due to Dixon) provably has the stated running time.
Elliptic curve method: this factors an integer $n$ with smallest prime factor $p$ in time $2^{O(\sqrt{\log p \log\log p})}$ (in general, this is the time it takes to find the factor $p$ rather than the complete factorization). No variant of this algorithm has a provable running time guarantee. The algorithm relies on the fact that random elliptic curves modulo $p$ have a certain order (number of points) distribution, and this empirically verifiable property isn't proven. (What you really need to know is the probability that the order is $\alpha$-smooth, whose conjectured behavior is satisfied for any reasonably smooth probability distribution.)
Number-field sieve: this factors an integer $n$ in time $2^{O(\sqrt[3]{\log n (\log \log n)^2})}$. No variant of this algorithm has a provable running time guarantee. The algorithm relies on the probability that a random element of a number field is smooth (in terms of its norm), a property which can be empirically verified but is unproven.

In practice, one first runs simpler algorithm which are able to find small prime factors more quickly. Some of the algorithms might run into problem if all prime factors are repeated, which is ruled out by your constraints, but I can't think of any concrete example.

There is no consensus on the conjectured complexity of the problem. Recent advances in the related discrete logarithm problem suggest that factoring might be in quasipolynomial time, and some people (Charles Rackoff, for example) wouldn't even rule out a polynomial algorithm for factoring. Others would concede that the number-field sieve algorithm might not be optimal, but that factoring should require time $2^{\Omega((\log n)^c)}$ for some $c > 0$.


Huffman coding (asymptotically) gets within one bit of the entropy of the sequence.  This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code.  You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.


Minimum number of intersections to arrive at specific set

Your problem (or rather, its decision version: are there $k$ sets whose intersection is a singleton) is NP-complete, so I doubt there is a simple solution that always works, even for your numbers.

The problem is clearly in NP. We show that it is NP-hard by reduction from SAT. Let $\varphi$ be a CNF on variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. We form an instance of your problem on the universe $x_1,\ldots,x_n,C_1,\ldots,C_m,\Delta$. For every $x_i$ and every truth value $t$, there is a set $S_i^t$ which contains (1) $\{x_1,\ldots,x_n\} \setminus \{x_i\}$, (2) all clauses not satisfied by $x_i=t$, and (3) $\Delta$.

All sets contain $\Delta$. In order to get rid of all $x_i$, we need to choose at least one set $S_i^t$ for each $i$. The intersection consists only of $\Delta$ if and only if the choice corresponds to a satisfying assignment. Hence there are $n$ sets whose intersection is a singleton iff $\varphi$ is satisfiable.


MAX,MAJ variants of NP complete problems

MAJ-Subset-Sum is easy to solve. A majority of partitions sum to $K$ iff $K = 0$ and all elements are equal to $0$. Indeed, let $S$ be the (multi)set, and suppose that there were some element $x \neq 0$ in $S$. For each subset $A$ of $S \setminus \{x\}$, either $\sum A \neq K$ or $\sum A + x \neq K$, and so $K$ can be the sum of at most half the subsets. We conclude that if $K$ is a sum of the majority of the subsets that $S$ consists only of zeroes, and so $K = 0$ as well.


Concise Way To Specify The Space Of All Python Programs Under A Certain Size And Running Time?

You can't determine the running time of a generic program automatically, this is an undecidable problem similar to the Halting problem.

Maybe you can try to enumerate a very well defined subset of the possible codes up to certain size. But in order to be useful for an search/optimization algorithm (other than random search), this subset needs to be equipped with some sort of vicinity function. Moreover, this vicinity function should allow you to explore genuinely different programs. Preferably this function should form a connected space among all plausible programs in this subset, and have a short diameter so optimizer can succeed on the search. All that said, is pretty clear that the problem is far from being easy.

I read recently a very interesting post about applying genetic algorithm to produce brainfuck code to solve specific simple tasks. You can read it here. The post is from 2013, but there is no particular breakthrough in this area that I'm aware. This field is known as program-synthesis and there are a lot of teams working on it, most recently they are trying to use classic combinatorial algorithms boosted with deep learning to prune the search space.


Variable $a_i$ set means class $a$ is in timeslot $i$, with a similar encoding for class $b$.  Higher values of $i$ means later time slots.  If class $a$ must occur before class b then you need clauses to declare that exactly one of $a_i$ or $b_{i+1}$, $b_{i+2}$ ... is set.  You need one such declaration for each $a_i$ possibility.  E.g.

ExactlyOne($a_1, b_2, b_3, b_4, ...$)

ExactlyOne($a_2, b_3, b_4, b_5, ...$)

ExactlyOne($a_3, b_4, b_5, b_6, ...$)

which is efficiently encoded using commander variable encoding as described in Efficient CNF Encoding for Selecting 1 to N Objects.  The scheme requires $O(n)$ clause growth, unlike the naive encoding method which requires $O(n^2)$ clause growth.


What algorithm should I use to find the closest solution to a given total using a list of integers?

When packing luggage into a car, you put the biggest items in first and then fit the smaller items around them. By analogy, a heuristic approach to your problem is to start with the member of your set that is as large as possible while still being smaller than your target. Then repeat the process for the difference between you current total and your target, and so on. This is known as a greedy algorithm.
For example, if your set is $\{2,3,5,8,13,21, 34\}$ and you target is $32$, start with $21$ (the largest value less than $32$), then add $8$ (because this is the large value less than $32-21=11$), and then add $3$.
A greedy algorithm is quick and simple, but will not always give you the best solution. For example, if your set is $\{1, 5, 23, 26\}$ and you target is $30$ then the greedy algorithm gives $26+1=27$, whereas the best solution is $23+5+1=29$.


How can I build a fool proof security system?

It is true that there is no general algorithm $D$ which can take as input any program $M$ and decide whether $M$ is malicious or not. Rice's theorem applies, here.

However, Rice's theorem does not imply that there is no $D$ that can do its job on a useful subset of programs $M$. This subset can not be the whole set of programs, according to Rice, but it could still be large enough to be useful in practice.

I'd say that most of the research in formal verification is about finding such a $D$ for specific cases. Usually the typical verifier $D$ outputs results meaning "I established that $M$ is malicious", "I established that $M$ is not malicious", or "my analysis was inconclusive, $M$ is too complex for me".

Essentially, we allow $D$ to throw the sponge, but hope that it won't.
We can't have a guaranteed YES or NO without also having, in infinitely many cases, the "inconclusive" result.

A naive technique to implement a $D$ could be to run $M$ for 1000 steps, and sees is $M$ does something bad. If it does, output "$M$ is malicious", otherwise output "inconclusive".

Static analyzers and model checkers (to mention two common approaches) only succeed on a subset of cases, but they can still be quite useful.


Can a regular expression based "grammatic" be programatically minimized?

I will describe a way that you could optimize the operation "find the first pattern that matches the input".  Given a way to do that, you can repeatedly apply that operation: i.e., repeatedly find the first pattern that matches the input, apply the substitution, then repeat.

However, I'm not sure that this will be any better in practice, so this might be useless (unless the number of regexps is quite small).

Union of NFAs

Any (language-theoretic) regular expression can be converted to a nondeterministic finite automaton (NFA) that recognizes the set of strings matched by the regexp (e.g., via Thompson's algorithm).

So, you can build a NFA for each pattern; and there are standard ways to build a NFA to represent the union of two or more NFAs, i.e., a NFA that accepts any input that is accepted by at least one of the NFAs.  In particular, you use the product construction.

You can modify the product construction to find the first NFA that accepts an input.  Let $N_1,\dots,N_k$ be $k$ NFAs.  Each state of the new NFA is of the form $(q_1,\dots,q_k)$ where $q_i$ is a state in $N_i$.  A state $(q_1,\dots,q_k)$ is accepting if any of the $q_i$ are an accepting state in $i$.  Also transitions are defined following the product construction, except that all transitions out of an accepting state go back to itself.  If $(q_1,\dots,q_k)$ is accepting, then find the smallest $i$ such that $q_i$ is accepting in $N_i$; this indicates that the $i$th regexp was the first match.

In principle you can use standard algorithms to run this NFA on the input, or convert the NFA to a DFA via the powerset construction and then run this DFA on the input.  In principle this provides a way to find the first matching pattern.  In practice you might run into problems: running this NFA on the input might be no faster than running all regexps; and converting to a DFA might cause you to run out of available memory.


A trivial language is one that has no strings, or one that has every string in some alphabet.

In terms of models of computation, a trivial language is one that can be decided by a Turing Machine or lambda function that completely ignores its input.


Cache lines are evicted :

When the OS requests it, it may occur for example in non cache-coherent systems when a peripheral does a DMA transfer (direct transfer from a peripheral to main memory), or if the CPU is shut down to save its state to RAM...
When all the ways of the cache are already used for the requested line.

In a write-through cache, new data can be directly loaded, overwriting previous contents. In a write-back cache, if the cache line was modified, it must be written back before loading new data.

There could be other exceptional cases, for example if a parity error is detected and new data must be loaded...
But, generally, caches are filled but never emptied.


Fast solution for a combinatorial maximizaton problem

You seem to be looking for the optimal single-deletion-correcting code of length n. As far as I know, it's an open problem.

This paper states that

The Varshamov-Tenengolts code (specifically $VT_0$) is a good candidate, but there has been no proof of this as of yet. It is the set of all words for which $\sum_{i=0}^{n} i\cdot x_i \equiv 0 \mod n+1$ where $x_i$ is the $i$-th digit in $x$'s binary representation. Its size can be computed as $$\frac{1}{2(n+1)}\sum_{d\mid n+1 \land 2\not \mid d} \phi(d)2^\frac{n+1}{d}$$. The first few values of the above formula can be found at A000016.
The above code has been proven to be optimal for small values of $n$, and to be asymptotically optimal for large $n$.
No efficient algorithm has been found to generate/check the optimal code. The largest value of $n$ for which an optimal code is known (and confirmed to be the above) is $9$ (actually $10$).


Question about a semi-decidable property of languages

Let $M$ be any computably enumerable set and define the set $$J_M = \lbrace n \in \mathbb{N} \mid W_n \cap M \neq \emptyset\rbrace,$$
where $W_n$ is the $n$-th computably enumerable set. Then $J_M$ is a computably enumerable set because
$$m \in J_m \iff W_n \cap M \neq \emptyset \iff \exists m . m \in W_n \land m \in M$$
is obviously a semidecidable condition, as c.e. sets are closed under finite intersections and  existential quantification over $\mathbb{N}$.

We may now get your result by taking $M = L_{\mathrm{uni}}$.

If you are wondering about the "obviously semidecidable" condition, we can put in a bit more details: to semidecide whether $W_n \cap M \neq \emptyset$ just keep enumerating the elements of $W_n$ and $M$ in parallel, until an $m$ appears in both enumerations.


Kolmogorov randomness for Pseudo random number generator

You can't.  Kolmogorov complexity is not computable.  See, e.g., https://en.wikipedia.org/wiki/Kolmogorov_complexity.


[The reviews are based on my first hand experience with the materials.]

Quick Read:

Essentials of game theory
(Leyton-Brown, Shoham) - This is a ~100 page book, which will give a strong intuition (and more) on Game theory, this mostly covers the basics, the math here is also pretty lightweight, and this is very much readable (even by a college junior). After this book the reader should be able to (atleast) sit through an advance GT Talk.
An Algorithmic Game Theory
Primer (Tim
Roughgarden) - A really nice survey by Tim Roughgarden. It talks about various disciplines like Mechanism Design, Complexity of Equilibria, among many other things.This should motivate the reader to identify the other areas of research.

Books:

Algorithmic Game Theory (Nisan et al) - This is perhaps the most popular book among Computational Game Theorists.. It covers a lot of ground, and the content is very rich. (IMHO) This is one of the books, that every researcher should read before diving into the subject.
Lectures in Game Theory for Computer Scientists (eds. Apt and Grädel) This is yet another book that contains essays from several authors and is rich in application content. As the name suggests, this is for a great resource for computer scientists who want to use game theory for their research.

Also, if you are done with these, want more advanced material take a look at the LNCS Proceedings of SAGT.


Decide if binary encoded number is divisible by 3

you have to use the fact that $2^n\mod 3 = n\mod 2 + 1$:

2 mod 3 = 2
4 mod 3 = 1
8 mod 3 = 2
16 mod 3 = 1
32 mod 3 = 2

and so on.

The solution then for an $n$ bit number is to use $n$ processors, the $i$th processor will calculate $f_0(i) = i\mod 2 +1 * w[i]$ where w is the little-endian array of bits.

Then, each of the processors can calculate the following: $f_{t+1}(i) <= f_{t}(i) + f_{t}(i+2^t)\mod 3$, for $t \in \{1...log_2(n)\}$ (increasing sequentially of course). $f_{log_2(n)}(0)$ will then contain the sum of the bits mod 3.


Using Brzozowski's derivatives method to construct a minimal DFA

The Brzozowski derivative of a language $L$ with respect to a symbol $a$ consists of all words $w$ such that $aw \in L$.

In your case, $L$ is the language generated by the regular expression $X$. Instead of solving your exact exercise, I will show how to compute the other Brzozowski derivative, with respect to $b$. A word generated by $(aa+b)^*ab(bb)^*$ has the form
$$ x_1 \ldots x_n ab (bb)^{2m}, $$
where $n \geq 0$, $x_i \in \{aa,b\}$, and $m \geq 0$. The only way that this can start with $b$ is if $n \geq 1$ and $x_1 = b$. Taking away $b$, we are left with
$$ x_2 \ldots x_n an (bb)^{2m}, $$
a collection of words which is described by the regular expression $(aa+b)^*ab(bb)^*$, the same one we started with.

Computing the derivative with respect to $a$ is slightly more complicated since there are two different cases, but I'll leave you to ponder that.

You might have also learned some rules for computing the derivative. In that case, you can compute the derivative by applying them mechanically.


Who invented the adder, full-adder, half-adder?

In 1966, I was taught by Professor Tom Kilburn at Manchester University.

He said the half adder was sometimes called the Kilburn adder because he invented it!


Recognizably turing machine question (reject / loop)

As commented by dkaeae, there is no way to verify whether a general Turing machine (TM) loops forever on some input. No matter how many operations has been run by an algorithm that simulates the TM on that input, that algorithm cannot be sure the TM will loop forever. The TM may or may not stop at the next moment.

The intuition is pretty simple. The only way to know the behavior of a TM on some input is to run it, unless there are some extra information or restriction about the TM that we can take advantage of, such as only finitely many cells are used.

We can recognize all Turing machines that accepts some string that ends with 111 since we can list all such strings and we can use an universal TM to simulate all Turing machines on all such strings sort of in parallel, thanks to dovetailing. Ditto with the case of rejecting.

However, a simulation cannot be finished if the TM keeps running. There is no point of time that an algorithm can be sure that the Turing machine (TM) under inspection will loop forever. Even if it looks like the simulated TM will never stop, it might halt at the next moment. The very fact that it keeps running prevents us from making a foolproof decision on whether it will eventually halt or loop forever. So we should believe that $L_{*111}$ is not recognizable. In fact, we should believe the simpler language $L_{111} = \{\langle M \rangle \mid M$ is a TM that loop on $111\}$ is not recognizable either.

Of course, we still need a rigorous proof that shows neither $L_{*111}$ nor $L_{111}$ is recognizable. We can make a reduction from the known unrecognizable language $\overline{HALT}=\{\langle M \rangle \mid M$ is a TM that does not halt on the empty string$\}$ to both of them.


Why would this be a deterministic context free language? $L = \{a^n b^n | n>0 \}$ $\cup$ $\{ a^n b^{2n} | n < 100 \}$

Maybe you can create 100 states that push two $a$'s onto the stack for every $a$, and then pop these $a$'s for every $b$. In the event of getting to the 100th state, when you read the 101st $a$, pop 100 $b$s from the stack and continue as you would for the first language alone.


Construct a TM for checking if a set of parentheses are well formed

A very important fact about Turing machines is that there may be many equivalent Turing machines for the same language. In other words, just because your answer and the book's answer are different Turing machines, they may both be correct answers. There is not just one Turing machine for any given task.

I am not sure if your Turing machine is actually correct (building a Turing machine without any errors is hard!), but if you answer the questions in my comments I can probably figure it out and update this answer. We can also try a few more input strings to check.


I come from a database / transaction background which will influence this answer.

My take would be to serialize the downvotes and handle one at a time. The banned function will be handled this way. Unbanning (is this a Word? ) will need to be handle separately: imagine that a troll is banned, a while later the total weight has increased enough for that player to be undammed.

When a player does a downvote, add the downvote to a queue (or similar). Save the id of the downvoted player, the id of the downvoter and the downvote quotient = downvoter current weight divided by current total weight.
In the serial function handle one item from the queue at a time.
Link the downvote to a list for the downvoted person. If one downvoter has downvoted a person several times, save only the latest. If the downvote player is already banned, nothing more needs to be done.
Now calculate the total downvote quotient by traversing the list. Only sum quotient for currently not banned users.
If the quotient is above 66% ban the user.
Take next item from the queue, see above

Now in order to unban a user you need to have a separate function. It might be a good idea to remove all old downvotes Before unbanning, or perhaps mark them as invalid?


The pigeonhole principle. If you go through $|Q|+1$ states, then there must be a state you have been in twice already. This means that because the input is $\sqcup$ almost all of the time, then we are stuck in a loop and the machine wont halt


Usual distances on DFAs (Deterministic Finite Automata)?

There are many possible distance metrics, and without any criteria, we have no basis to choose.  Here are two plausible ones.

Let $L_1,L_2$ be the languages of the two DFAs.  Let $L$ be the symmetric difference of those languages (i.e., $(L_1 \setminus L_2) \cup (L_2 \setminus L_1)$).

One dissimilarity measure is $d(L_1,L_2) = 2^{-n}$ where $n=\min\{|x| : x \in L\}$, i.e., $n$ is the length of the shortest word in $L$.  This is not a distance metric, because it does not satisfy the triangle inequality.

Another possibility is to use the density of $L$, i.e.,

$$d(L_1,L_2) = \sum_{n=0}^\infty {|L \cap \Sigma^n| \over 2^n |\Sigma|^n}.$$

This one is a distance metric.

These can be computed given DFAs for $L_1,L_2$.  You can easily compute a DFA for $L$.  Then, it is easy to find the length of the shortest word in $L$ using breadth-first search.

Computing the density is a bit trickier, but can be done efficiently using a little more math.  Let $A$ denote the transition matrix of the DFA for $L$, i.e., $A_{ij}=1$ if there is a transition (on any input symbol) from state $i$ to state $j$, or $A_{ij}=0$ if not.  Let $s$ denote the one-hot vector indicating the start state, i.e., $s_i=1$ iff $i$ is the start state, and $f$ denote the one-hot vector indicating the final states, i.e., $f_i=1$ iff $i$ is an accepting state.  Now $|L \cap \Sigma^n| = s^\top A^n f$, so the distance is given by

$$d(L_1,L_2) = \sum_{n=0}^\infty {s^\top A^n f \over 2^n |\Sigma|^n}
= s^\top C f$$

where

$$C = \sum_{n=0}^\infty B^n = {1 \over I - B} = (I - B)^{-1}$$

where $B={1 \over 2|\Sigma} A$ and $I$ represents the identity matrix.  This can be computed in time proportional to the cube of the number of states in the DFA for $L$ using standard algorithms for matrix inversion.


Robust two lines/segments intersection point in 2D

If you choose a formula with parameter $t$ you'll get the $P_x$ value as a result of a number of operations - additions, multiplications and one division:

$$t = \frac{(x_1-x_3)(y_3-y_4)-(y_1-y_3)(x_3-x_4)}{(x_1-x_2)(y_3-y_4)-(y_1-y_2)(x_3-x_4)}$$
$$P_x = x_1 + t(x_2-x_1)$$

The number $x_2=72057594037954921$ contains 17 significant decimal digits - so it can't be represented exactly using double-precision floating numbers. Apparently, a small error is introduced during some operation (most probably - the division), and this error is propagated to the result. This is a form of the Round-off error.

This bunch of calculations doesn't happen when you choose a formula with parameter $u$, because the numerator there is equal to zero.

Conclusion: if you need to work with numbers, containing a big number of significant digits - use floating numbers with bigger precision, or may be - with arbitrary precision. An example: mpmath.

Another option - use rational numbers. For example, kernels, based on rational numbers, can be found in the computational geometry library CGAL. Developers of this library have invested a lot of efforts to solve this robustness problem - please see this page for more information.

If you want to go deeper into this research area, called Exact Geometric Computation (EGC), you can start from this review. You'll need a good knowledge of Linear Algebra and Linear Systems.


Let me first formalize the problem:

Cluster edition
Instance: A graph $G$ and an integer $k$.
Question: Can $G$ be transformed into a cluster graph by deleting at most $k$ edges?

It is not difficult to see that the problem is, already for general graphs, fixed-parameter tractable (FPT) parameterized by the number of edge deletions $k$. Being FPT means the problem is solvable in time $f(k) n^{O(1)}$, where $f$ is a computable function depending solely on $k$.
The observation is the following: cluster graphs are precisely the $P_3$-free graphs, i.e., the graphs that don't contain the path on 3 vertices as an induced subgraph. So, in order to produce a cluster from $G$, the $k$ edge deletions must "hit" each $P_3$. Clearly, there are two ways to destroy a $P_3$: either we remove edge $a$ or edge $b$. The algorithm is as follows: as long as there is a $P_3$, branch by choosing either one of its edges to delete. This will give you a straightforward $2^k n^{O(1)}$-time algorithm, that will be quite practical if $k$ is not too large.
Looking up the literature, the problem can be solved in $O^*(1.77^k)$ time by a more clever yet simple branching algorithm (see Gramm et al. [1]). Here the $O^*$ notation hides polynomially bounded factors.
It is interesting to ask whether you can do better for chordal graphs, or indeed $q$-trees (I'm using $q$ here to make a distinction between $k$). The problem is solvable in polynomial-time for cographs [2], but NP-complete for chordal graphs [3]. I don't know if the complexity for $q$-trees is known, and I also didn't think hard about it but merely glanced the literature.

[1] Gramm, Jens, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. "Graph-modeled data clustering: Fixed-parameter algorithms for clique generation." In Italian Conference on Algorithms and Complexity, pp. 108-119. Springer Berlin Heidelberg, 2003.
[2] Gao, Yong, Donovan R. Hare, and James Nastos. "The cluster deletion problem for cographs." Discrete Mathematics 313, no. 23 (2013): 2763-2771.
[3] Bonomo, Flavia, Guillermo Duran, and Mario Valencia-Pabon. "Complexity of the cluster deletion problem on subclasses of chordal graphs." Theoretical Computer Science 600 (2015): 59-69.


Effects of parity bit on odd code length regarding its size after alternation

Normally a code's hamming distance is limited to some maximum message length. For example in the case of a 32 bit CRC, for Hamming distance = 3 (2 bit error detection), the maximum length for a message is 2^32-1 bits (including the 32 bits of CRC), depending on the CRC used. With a larger message, a  2 bit error can fail. For a parity check or Hamming distance = 2 (1 bit error detection), there is no maximum length limit.

If the message length is <= maximum message length for that Hamming distance, and k is odd (maximum # of error bits detected is even), then adding a parity check in addition to the CRC should increase Hamming distance to k+1.

For example, CRC16 based on polynomial x^16 + x^12 + x^5 + 1 (0x11021) is the product of 2 irreducible polynomials : (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) (0xf01f) and (x + 1) (0x3). For message length (including CRC bits) CRC poly (x^15 + x^14 + x^13 + x^12 + x^4 + x^3 + x^2 + x + 1) Hamming distance is 3 for message length up to 32767 (2^15-1) bits, and the (x + 1) term increases this to Hamming distance 4. As mentioned above, it can detect any odd number of bit errors for any length message.


How to apply a Hadamard gate to one qubit in a 2-qubit system?

The problem is in the order of the transformations. The first transformation you apply in the circuit is $I\otimes X$, whereas in the computation of $M$ it is actually the last. Recall that the rightmost operator is the first to act on the state (matrix multiplication is not commutative).

Fixing that we obtain:

$$
M=(H\otimes I)(I\otimes X)CNOT(I\otimes X) =
\begin{bmatrix}
H & 0 \\
0 & H
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}=
\begin{bmatrix}
H & 0 \\
0 & H
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & X
\end{bmatrix}
\begin{bmatrix}
X & 0 \\
0 & I
\end{bmatrix}=
\begin{bmatrix}
I & I \\
I & -I
\end{bmatrix}
\begin{bmatrix}
I & 0 \\
0 & X
\end{bmatrix}=
\begin{bmatrix}
I & X \\
I & -X
\end{bmatrix}
$$

Now applying $M$ on $|00\rangle$ will yield the right result.


If you consider $k$ a constant, then k-clique can be solved be enumerating all $O(n^k)$ sets of vertices and checking that there are edges present in polynomial time (since the exponent is constant).

Enumerating k-Tuples of numbers up to n can be done in $k\log n$ space, you only have to figure out how to check for the presence of an edge between two vertices without using much space. Depending on how much details you have to give this is either obvious or very tedious to write down.


The first thing you should realize to understand it is that the $H(Y)$ notation corresponds to the calculation of the information entropy for the states in $Y$, such that $H(Y) = -\sum\limits_{y \in Y} p(y) \log[p(y)]$.  With that in mind, we can interpret the expression and equate the terms.  You are correct that the three parts correspond to the probability of $0$, $e$, and $1$, where $e$ is the state of erased information.  Expanding it we get:

$H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha)) $
$\quad= -(1-\pi)(1-\alpha)\log[(1-\pi)(1-\alpha)] - \alpha\log(\alpha) - \pi(1-\alpha)\log[\pi(1-\alpha)]$

This gives us the full expression for calculating the entropy of the system composed of those three states.  Next, as we usually do when proving an equality, we cheat and look at the answer to see what form we need it in.  Your last term has all the $\pi$ terms clumped onto one side, and all the $\alpha$ terms clumped onto another (except for where they are also a coefficient).  Thus we will organize the log terms in this manner.  First we use the log rules to expand the products:

$ \quad= -(1-\pi)(1-\alpha)\log(1-\pi) - (1-\pi)(1-\alpha)\log(1-\alpha) $
$\quad\phantom{=} - \alpha\log(\alpha) - \pi(1-\alpha)\log(\pi) - \pi(1-\alpha)\log(1-\alpha)$

Then we sort all the log terms in the order of the final expression:

$ \quad = -\alpha\log(\alpha) - (1-\pi)(1-\alpha)\log(1-\alpha)  - \pi(1-\alpha)\log(1-\alpha) $
$ \quad\phantom{=} - \pi(1-\alpha)\log(\pi) -(1-\pi)(1-\alpha)\log(1-\pi)$

Then we simplify and factor:

$ \quad = -\alpha\log(\alpha) - (1-\alpha)\log(1-\alpha) + (1-\alpha) \cdot [ -\pi\log(\pi) - (1-\pi)\log(1-\pi) ]$

And this is equivalent to:

$$H(\alpha, 1-\alpha) + (1-\alpha) H(\pi, 1-\pi)$$

This can be interpreted as the left part being the entropy from erasing (probability $\alpha$) or not erasing, and the right part being, in the event it was not erased, the entropy from it being a 1 (probability $\pi$) or a 0.  It should also make some intuitive sense that this will be equal to the entropy from the distribution of final states of $0$, $e$ (erased), and $1$.


Yes, $|w|$ is the length of $w$.

So $|w| \equiv 2 \mod 3$ means that the length of w divided by three should have the remainder 2. It should be from the set $\{2, 5, 8, \dots\}$.


A better upper bound to a recursive function

Solving your recurrence, assuming the base case $T(0) = 1$, we get
$$
\begin{align*}
T(n) &= 1 + nT(n-1) \\ &=
1 + n + n(n-1)T(n-2) \\ &=
1 + n + n(n-1) + n(n-1)(n-2)T(n-3) \\ &= \cdots \\ &=
1 + n + n(n-1) + \cdots + n(n-1)\cdots2 + n! \\ &=
n! \left(\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \cdots + \frac{1}{n!}\right) \\ &=
n! \left(e - O\left(\frac{1}{(n+1)!}\right)\right) \\ &= e \cdot n! - O\left(\frac{1}{n}\right).
\end{align*}
$$
In particular, $T(n) = \Theta(n!) = \Theta(\sqrt{n}(n/e)^n)$.


Multiplying two bivariate polynomials using FFT

The product is
$$
F(x,y) G(x,y) = \sum_{i=0}^{2n-2} x^i \sum_{i'=0}^{n-1} \left(\sum_{j=0}^{n-1} f_{i',j} y^j \right) \left(\sum_{j=0}^{n-1} g_{i-i',j} y^j\right).
$$
You take it from here.


Secretary Problem with 2 positions - Maximizing the difference

One trivial algorithm for the problem is exactly the same as the usual algorithm: observe $n/e$ of the applicants, then pick the first (if any) secretaries who are better than, or worse than, all applicants seen so far. This succeeds with probability roughly $1/e^2$. Answers to a question on math.se which includes your question claim that this algorithm (which is proposed in the answers) is obviously optimal.

To see that the success probability is roughly $1/e^2$, we follow the analysis in Wikipedia. We will analyze a more general algorithm, in which $n/e$ is replaced by $pn$, and then will show that the best choice for $p$ is roughly $1/e$. Let $q_{ij}$ be the success probability given that the $i$th secretary is the best one and the $j$th secretary is the worst one. If $i,j > pn$ then $q_{ij}$ is the probability that:

$i$ is the best secretary.
$j$ is the worst secretary.
Among the first $i-1$ secretaries, the best is one of the first $pn$.
Among the first $j-1$ secretaries, the worst is one of the first $pn$.

Calculation shows that
$$
q_{ij} = \begin{cases}
\frac{pn(pn-1)}{n(n-1)(i-1)(j-2)} & i < j, \\
\frac{pn(pn-1)}{n(n-1)(i-2)(j-1)} & i > j.
\end{cases}
$$
The overall success probability is thus at least
$$
\sum_{i=pn+1}^n \sum_{\substack{j=pn+1\\j \neq i}}^n \frac{pn(pn-1)}{n(n-1)(i-1)(j-1)} \approx p^2 \left(\int_{pn}^n \frac{dx}{x}\right)^2 = \left(p\log\frac{1}{p}\right)^2.
$$
This is just the square of the usual formula, so it is maximized at $p = 1/e$, for which the success probability is roughly $1/e^2$.


What is a dichotomy? Whether 2-SAT itself is a dichotomy of SAT?

A (coarse) dichotomy theorem states that in a certain class of problems, each problem is either in P or NP-hard. For example, Schaefer's dichotomy theorem concerns the class of problems of the form $\mathrm{SAT}(S)$. Here $S$ is a collection of Boolean relations, and $\mathrm{SAT}(S)$ is the problem of deciding satisfiability of propositions which are conjunctions of relations from $S$. This is best explained by an example. The problem 2SAT is $\mathrm{SAT}(S_2)$ with $S_2$ consisting of the following three predicates:
$$ (x,y) \mapsto x \lor y, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y. $$
That is, each instance of 2SAT is a conjunctions of clauses of one of these three forms, where you can substitute any variables you want for $x,y$. As another example, HORNSAT is $\mathrm{SAT}(S_H)$ where $S_H$ is the following infinite collection:
$$\begin{gather*}
x \mapsto x, \quad x \mapsto \lnot x, \quad (x,y) \mapsto x \lor \lnot y, \quad (x,y) \mapsto \lnot x \lor \lnot y, \\
(x,y,z) \mapsto x \lor \lnot y \lor \lnot z, \quad
(x,y,z) \mapsto \lnot x \lor \lnot y \lor \lnot z, \\
(x,y,z,w) \mapsto x \lor \lnot y \lor \lnot z \lor \lnot w, \quad
(x,y,z,w) \mapsto \lnot x \lor \lnot y \lor \lnot z \lor \lnot w, \ldots
\end{gather*}$$
Schaefer's dichotomy theorem states that for each finite $S$, the problem $\mathrm{SAT}(S)$ is either in P or it is NP-complete (this is a dichotomy since there are only two possibilities). For example, 2SAT and $k$-HORNSAT are in P for every $k$, while 3SAT is NP-complete. This is surprising since if we believe that P$\neq$NP then Ladner's theorem shows that there are intermediate problems - problems which are neither in P nor NP-complete. Schaefer's theorem shows that these problems cannot be of the form $\mathrm{SAT}(S)$.

A more refined version of Schaefer's theorem states that $\mathrm{SAT}(S)$ is either in co-NLOGTIME, L-complete, NL-complete, $\oplus$L-complete, P-complete or NP-complete. In the past few years, countless generalizations of Schaefer's theorem have been proven or conjectured, including results about counting solutions and approximating the maximum number of satisfiable clauses, as well as results over non-Boolean domains. The main conjecture is the Feder-Vardi dichotomy conjecture which states that Schaefer's theorem holds for relations on an arbitrary finite-sized domains. For the status of Schaefer's original theorem in the case where $S$ is infinite, see this question.


Time complexity of computing binomial coefficients (with binary representation of integers)

There is no sub-exponential algorithm. For example, $\binom{2n}{n}$ has $\log\binom{2n}{n}$ bits, and according to Stirling's approximation,

$$
\binom{2n}{n}=\Theta\left(\frac{2\sqrt{\pi n}\left(\frac{2n}{\mathrm{e}}\right)^{2n}}{\left(\sqrt{2\pi n}\left(\frac{n}{\mathrm{e}}\right)^{n}\right)^2}\right)=\Theta\left(\frac{4^n}{\sqrt{n}}\right),
$$

we have

$$
\begin{align*}
\log\binom{2n}{n}=\Omega(n).
\end{align*}
$$

So we need at least $\Omega(n)$ time to output the result of $\binom{2n}{n}$.


What is the contradiction in the proof of the halting theorem?

You actually have a missing detail on how the machine $TM_2$ is defined (and a bit of confusion between $TM_1$ and $TM_0$). Let's clear this up. You start by the assumption that there is a machine $TM_0$ that operates as follows. On input $x = <TM_1, w>$, the machine $TM_0$ answers "yes" whenever $TM_1$ halts on its input $w$, and $TM_0$ answers "no" whenever $TM_1$ does not halt on its input $w$.
Now we define a machine $TM_2$. On input $z = <TM_1>$ which a description of a machine, denoted $TM_1$, the machine $TM_2$ runs $TM_0$ on $x = <TM_1, TM_1>$ and returns the opposite answer of $TM_0$. In words, the machine $TM_2$ answers "no" when $TM_1$ halts on itself, and answers "yes" when $TM_1$ does not halt on itself.
To get a contradiction, consider what happens when we feed $TM_2$ to itself as an input. That is, consider the case where the input of $TM_2$ is $z = <TM_2>$. One of the following holds:

$TM_2(TM_2)$ = "yes", and so in this case $TM_0(<TM_2, TM_2>)$ = "no". Hence, by the definition of $TM_0$, $TM_2$ does not halt on itself.
$TM_2(TM_2)$ = "no", and so in this case $TM_0(<TM_2, TM_2>)$ = "yes". Hence, by the definition of $TM_0$, $TM_2$ halts on itself.

All in all, we have that by the two items above that $TM_2(TM_2)$ = "yes" iff $TM_2$ halts on itself, which is clearly a contradiction to $TM_2$'s definition (see the bolded sentence above).


Regular expression for binary words with 1 in the middle

The intersection of your language with $0^*10^*$ is $\{ 0^n 1 0^n : n \geq 0 \}$, which can be shown to be non-regular by reduction to the more well-known $\{ a^n b^n : n \geq 0 \}$. This shows that your language indeed isn't regular.


We use the pumping lemma for regular languages.

$w \in L$, $|w| = n$, and $n$ is prime.

according to the lemma, $w$ can distribute to $xyz$ s.t:

$\bullet y \neq \epsilon $

$\bullet |xy| < n$

$\bullet$ for any $i \geq 0$ $ xy^iz \in L$

Now, let us denote $|y| = k$.

Now we only need to think of an $i$, where $|xy^iz|$ is not prime.

let's choose $ i = n$.

$|xy^{i+1}z| = n+ik = n+kn= (k+1)n$

since $(k+1)n$ is not prime (divides by $k+1$), we reached a contradiction and we can conclude $L$ is not regular.


Average length of s-t (simple) paths in a directed graph

calculating/estimating/approximating the average path length has been studied for some random graph models including the Erdos-Renyi model and the Barabasi-Albert scale free networks, and also the Strogatz small world graphs which may be suitable as approximations for your graphs. [it would be better if you could narrow down/detail some nature/characteristics of the graphs you're studying.]

Computing the average path length and a label-based routing in a small-world graph — Philippe J. Giabbanelli, Dorian Mazauric, and Stephane Perennes
Average path length in random networks — Agata Fronczak, Piotr Fronczak, Janusz A. Holyst
The average distance in a random graph with given expected degrees
— Fan Chung, Linyuan Lu
AN ESTIMATION OF THE SHORTEST AND LARGEST AVERAGE PATH LENGTH IN GRAPHS OF GIVEN DENSITY — Laszlo Gulyas, Gabor Horvath, Tamas Cseri and George Kampis


Is the language $\{a^{n^2-1} | n \in \mathbb{N}\}$ context free? and how to prove it?

A unary language (a subset of $a^*$) is context-free iff it is regular. This is a special case of Parikh's theorem. It is not too hard to show that a unary language $L$ is regular if and only if there exist $n,m$ such that for all $N \geq n$, $a^N \in L$ iff $a^{N+m} \in L$. See if this condition holds for your language.


Decidability of Equality of Radical Expressions

Algebraic numbers are solutions of polynomials with rational coefficients.
$+,\times,-,/$ of algebraic numbers result in algebraic numbers because algebraic numbers form a field (1). This means nested radicals are algebraic numbers too (2).
Nested radicals can be denested by algorithm (3,4).
Each algebraic number of degree $n$ can be uniquely represented as a $n$ by $n$ matrix of integers under a suitable basis (for example, $[1,x, (x^2+1)/2]$). This representation allows symbolic evaluation of $+,\times,-,/$ by matrix addition, multiplication, and inverse (p.159 of 5,6,7).
Two terms are equal if their unique representations are identical.


If $L$ is recursively enumerable (or recursive) then so is $L′$

The second item is in fact false. Consider the language $L$ consisting of $u\# w$ such that the $u$th Turing machine halts within $w$ steps. This is recursive, but $L'$ is the language corresponding to the halting problem.


Maximum number of inversions that can be removed by swapping two elements?

The question is indeed not completely clear, but they definitely wanted you to search the "worst possible" array $a$ (the one leading to the largest number of removed inversions). Otherwise there is nothing to do - just look at the array and calculate the number of inversions resulting from the swap.

What is somewhat less clear is whether they also wanted you to optimize over $i$ and $j$. Your answer, which doesn't assume that, is on the safe side.

One thing you haven't shown is that your example leads to the maximal number of inversions being removed. The argument is very simple, but it's still needed for completeness.


Why use joint trees in Graphical Models?

I view junction trees as basically an implementation/analysis tool for doing exact MAP and marginal inference in graphical models.  They are needed so that you can safely localize the effects of of maxing or summing (in the case of MAP and marginal inference) out a variable.

When wouldn't you use a junction tee?  Well, that's the same case as when you wouldn't do exact inference in your model.  Why wouldn't you do exact inference?  In general, because it can be expensive; it's exponential in the treewidth of your junction tree.


Unambiguous grammar for regular expressions

I need to define a context free grammar to recognize regular expression. I know also that CF grammars are used to recognize mathematical expressions. so the grammar $G$ should recognize regular expressions.

$G:$

$ E \rightarrow E + T \mid T $

$ T \rightarrow  T \cdot F \mid F $

$ F \rightarrow(E) \mid E^* \mid a\mid b\mid\emptyset$


Context Free Grammar for $\{0^n1^n \mid n \geq 0\}^*$

Hints:

Start with a context-free grammar for $L_1$.
Modify it to a context-free grammar for $L = L_1^*$. There is a simple transformation which works for any context-free language $L_1$ and any context-free grammar generating it.


Examples of undecidable problems whose intersection is decidable

So here is a example, which is probably not as nice as you wanted it to be, but less trivial than the one you have mentioned.

Let $L_1,L_2\subset \{a,b,c\}^*$ be two undecidable languages, and $L_3\subseteq \{a,b,c\}^*$ a decidable language. We define

\begin{align}
L_A&:=\{a\,w \mid w\in L_1\} \cup \{c\,w \mid w\in L_3\}, \\
L_B&:=\{b\,w \mid w\in L_2\} \cup \{c\,w \mid w\in L_3\} .\\
  \end{align}

Clearly, both $L_A$ and $L_B$ are not decidable, however their nonempty intersection
$$ L_A\cap L_B =\{c\,w \mid w\in L_3\}$$
is decidable.


If NP is not a proper subset of coNP, why does NP not equal coNP?

$\{2,3\}$ is not a proper subset of $\{3,4\}$, yet the two clearly are not equal.

Comparing sets is not like comparing numbers: two sets might not be comparable.

Additionally, NP is not a subset of coNP, or at least, it is not known that this is the case. You are either misreading the textbook, or your textbook is wrong, since proving that $NP \subseteq coNP$ would be a massive result.

$P\subseteq coNP$, perhaps that is what you actually read?


There are multiple techniques to compute the minimum Hamming distance for a given CRC polynomial.  I don't know what technique they used, but here are three techniques that seem suitable.

I will assume the problem is as follows:

Given a CRC polynomial $p(x)$, determine whether there exists a $d$-bit error pattern of length $n$ that isn't detected.

This is equivalent to asking whether there exists a word of length $n$ with Hamming weight $d$ whose CRC is zero; or whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that $p(x)$ divides $q(x)$.

Method #1: Exhaustive enumeration

One can enumerate all words of length $n$ and Hamming weight $d$, and check each one to see if that error pattern would be detected.  This involves checking ${n \choose d}$ possibilities, which is feasible if $d$ is small and $n$ is not too large, but rapidly becomes infeasible for larger parameters.

For instance, their Table 1 lists results for $n=48$ and $d=1,2,3,4,5,6$.  These are feasible to compute by exhaustive enumeration.  For instance, for $n=48$ and $d=6$, we have ${48 \choose 6} \approx 2^{37.3}$, and it's feasible to do $2^{37.3}$ computations on a computer in a reasonable amount of time.

As another example, for $n=2048$, it's feasible to compute results for $d=1,2,3$.  We have ${2048 \choose 3} \approx 2^{32.4}$, which isn't too large.  However, ${2048 \choose 4} \approx 2^{44.6}$ which is feasible but uncomfortably large.

Method #2: Meet-in-the-middle

We can speed up method #1 using a trick.  The trick reduces the amount of computation time to something like $\sqrt{{n \choose d}}$, at the cost of requiring much more space (memory).

Note that the CRC is linear.  Suppose there exists a data word $x$ of weight $d$ whose CRC is zero.  We can express $x$ as $x=y \oplus z$ (where $\oplus$ denotes the xor), where $y,z$ each have weight $d/2$.  Then by the linearity of the CRC, the CRC of $x$ is the xor of the CRC of $y$ and the CRC of $z$.  So, if we want to search for an $x$ whose CRC is zero, it suffices to search for $y,z$ whose CRC xors to zero -- i.e., to search for $y,z$ that have the same CRC.

Now the method becomes this.  We enumerate all data words $y$ of length $n$ and weight $d/2$, compute their CRC, and store them in a hashtable (or sorted list) keyed on the CRC.  Next, we enumerate all data words $z$ of length $n$ and weight $d/2$, compute each one's CRC, and look up that CRC in the hashtable to look for matches.  This will require $2 {n \choose d/2}$ CRC computations and ${n \choose d/2}$ space.  Note that ${n \choose d/2}$ is roughly $\sqrt{{n \choose d}}$, so this is a big reduction in the running time.

If $d$ is not even, then we split into $y$ of weight $(d-1)/2$ and $z$ of weight $(d+1)/2$, so the running time is ${n \choose (d+1)/2}$ and ${n \choose (d-1)/2}$ space.

Of course, we can trade off memory for space, so we can find an algorithm with running time ${n \choose d_1}$ and space ${n \choose d_2}$ for any $d_1,d_2$ such that $d_1+d_2=d$.

As an example, for $n=48$ and $d=6$, there is an algorithm with ${48 \choose 3} \approx 2^{16.1}$ running time and ${48 \choose 3} \approx 2^{16.1}$ space -- easily computable on a computer.  As another example, for $n=2048$ and $d=4$, the running time is $2^{21}$ and the space is $2^{21}$ -- again, easily feasible.  For $n=2048$ and $d=5$, the running time is $2^{32.4}$ and $2^{21}$ space, which is again easily feasible.  So this readily explains how one could compute the results in Figures 1-2.

(In fact, it turns out you can speed up this method by a small additional factor, at the price of an exponentially small probability of error.  There are many ways to split $x=y \oplus z$, so in some sense the above method is doing more work than necessary.  An optimization is to require that $y$ be zero in the last $n/2$ bits and $z$ be zero in the first $n/2$ bits, and search for such a split.  This reduces the running time and space to ${n/2 \choose d/2}$ time and space.  However, there is no guarantee that $x$ can be split in this way.  So, instead, we pick a random subset $S \subseteq \{1,2,\dots,n\}$ of $n/2$ positions, and we require $y$ to be zero in all bit positions of $S$ and $z$ to be zero in all bit positions of $\overline{S}$, and we search for any solution.  Then, we repeat this again multiple times with multiple different random choices of $S$.  If there is a solution, then we have about a $1/\sqrt{\pi d/2}$ chance of finding it, so after $O(\sqrt{d})$ repetitions, there is an overwhelming chance that we find it.  This provides a speedup by about a factor of $\Theta(2^{d/2}/\sqrt{d})$, at the cost of some implementation complexity.)

Method #3: Discrete logs in finite fields

Finally, there is one more method, which involves a lot more implementation complexity and requires knowledge of finite fields.  Given $p(x)$, we'll try to determine whether there exists a polynomial $q(x)$ of degree $n$ and weight $d$ such that

$$q(x) \equiv 0 \pmod{p(x)}.$$

We can think of this as working in the finite field $\mathbb{F}_{2^m}$ where $m$ is the degree of $p(x)$.  Note that there are fairly efficient algorithms for computing the discrete log in $\mathbb{F}_{2^m}$ when $m$ is not too large (as is the case for CRC polynomials, where typically $m \le 32$).  We can think of any polynomial as an element in this finite field.  For example, we can think of the degree-1 polynomial $x$ as an element in the finite field.

We'll use a subroutine for computing the discrete log of an arbitrary polynomial $s(x)$, to the base $x$.  In other words, given $s(x),p(x)$, this subroutine returns us a number $k$ such that

$$s(x) \equiv x^k \pmod{p(x)}.$$

Now we'll split $q(x)=r(x)+s(x)$ where $r(x)$ has weight $d-1$ and $s(x)$ has weight $1$.  If $q(x) \equiv 0 \pmod{p(x)}$, it follows that

$$r(x) \equiv s(x) \pmod{p(x)}.$$

Thus we'll enumerate all possible polynomials $r(x)$ of degree $< n$ and weight $d-1$, and for each, we will compute the discrete logarithm of $r(x)$ to the base $x$.  If the resulting discrete log, call it $k$, is less than $n$, we have found a valid $s(x)$ of weight $1$ and thus $q(x) = r(x) +  x^k$ is a multiple of $p(x)$ with degree $<n$ and weight $d$, so we have found a valid solution.  If the resulting discrete log is $\ge n$, we discard this possibility $r(x)$ and continue enumerating other values of $r(x)$.

The running time is ${n \choose d-1}$ computations of a discrete log and $O(1)$ space.  This is unlikely to be better than Method #2 except for very large values of $n$ and small values of $d$, but there are some parameter settings where it might be probably faster than Method #2.


Partial recursive function and Turing machine

You first define what a partial recursive function is, and then what a Turing machine is.  Then you show that for every set (problem), there is a Turing machine computing it if and only if it is definable by a partial recursive function.

What you actually would do is to simulate a Turing machine by a partial recursive function and vice versa.  Right to left is simple, left to right takes some work.  You must define an encoding of the machine states (use of e.g. powers of prime numbers), the transition function, a configuration of a machine (i.e., what is currently on the tape, where is the head, and in which state is the machine) etc.


I don't see why they should have the same length, given that one can succinctly output large amounts of whitespace using something like

for i=1 to 1000 do
    print " "

So, given any mutual Quines $A$ and $B$, one could surely add 1000 spaces to $A$ and 2000 spaces to $B$ and adjust the programs to use for loops like the above.


Does selecting the same arm has the same reward?

In the version of the Multi-Armed Bandit problem I'm familiar with, there is a fixed list of distributions $B = R_1, R_2 \cdots R_n$, and the reward for pulling lever $k$ is chosen from the distribution $R_k$.

So pulling the same lever twice might lead to different rewards, but the rewards are connected through the distribution $R_k$.


How do I calculate the time complexity of this memoized algorithm?

Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:

The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique)
The time it takes to process an item, assuming you know the results of every recursive call it would have done (or a bound on this number)

In your case:

The memoization saves elements up to $n=len(s)$ (every element in the dictionary is smaller or equal to $n$ and therefore you will calculate at most $n$ values)
Processing each element takes $O(n)$ time (in the recurse function, there is a for i in range(n):)

Therefore, for every new element you calculate (there are at most $n$ such values) you will spend $O(n)$ time, and thus the algorithm will take $n\cdot O(n)=O(n^2)$ in the worst case analysis.
Notice this is not an improvement from any naive algorithm that goes through every sublist - as by combinatorical counting there are ${n\choose2}={n!\over2!\cdot(n-2)!}={n\cdot(n-1)\over2}=O(n^2)$ different sublists


How should i guide a program to perform correct things?

The "Infinite Monkey Theorem" doesn't say that monkeys will learn.  On the contrary: it says that if monkeys keep typing random stuff long enough (i.e. not using any sort of learning), the works of Shakespeare will eventually come out purely by chance.  It is the Law of Truly Large Numbers.

So you're right: you need to build feedback into the system.  The program should change its behavior based on your feedback.  This is known as reinforcement learning and it is used a lot in AI.  An overarching term for this, I believe, is machine learning.


Hashing algorithm for millions of variable length strings (URLs)

Any string hashing algorithm designed for ASCII text should work fine. Take a look at the Wikipedia article, consider if the set could be manipulated by an adversary to create pile-ups (algoritmic vulnerabilities). If that isn't an issue, at strchr and partow several "classical" hash algorithms are given and compared. Get a subset of your data and use the parameters suggested there for your own comparison. And please tell us the results.


I have several options for you.  Here is the simplest:

1.1 Direct Option

Use an inequality to enforce that one out of $M_{i,1},\dots,M_{i,L}$ are true:

$$M_{i,1} + \dots + M_{i,L} = 1.$$

Use a second inequality to link that to $a_i$:

$$a_i = M_{i,1} + 2 M_{i,2} + 3 M_{i,3} + \dots + L M_{i,L}.$$

2 Indirect Options

Alternatively, we could try to follow more closely to the approach you outlined, but using ideas from one-out-of-n constraints for SAT solvers.  In particular, the entries $M_{i,1},\dots,M_{i,L}$ are a one-hot encoding of a one-out-of-L constraint, and you want them to be consistent with an encoding directly as an integer.  There are standard techniques for enforcing one-out-of-n constraints for SAT, and you could using them with ILP as well.

2.1 Improved Binary Encoding

We can use the idea in https://cs.stackexchange.com/a/51512/755 to improve your option 2.  Let $a_{i,k}$ denote the $k$th bit of $a$.  We add the constraint

$$M_{i,j} \implies a_{i,k} \text{ if } bit^*_{j,k}=1,$$

otherwise add the constraint

$$M_{i,j} \implies \neg a_{i,k} \text{ if } bit^*_{j,k}=0.$$

Next, we add the constraint

$$M_{i,1} + \dots + M_{i,L} \ge 1.$$

This requires only $n+nL\log L$ constraints and $n\log L$ new variables, instead of $5nL \log L$ constraints and $2nL \log L$ new variables.

Commander Encoding

You could use a a recursive commander encoding to enforce that exactly one out of $M_{i,1},\dots,M_{i,L}$ are true.  Note that the constraint for "at most one variable in a group can be true" requires $O(m^2)$ clauses in SAT but can be represented in a single inequality in ILP, so the number of constraints needed will be smaller than for SAT.  Then, you could use any of the above techniques to link the $M$'s to the $a'$.

That said, I don't expect these indirect options to be worth implementation; my expectation is that the direct option will be more natural, and it is what I would try first.


$L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Hint -- You need to show that your TM has the same power as a finite-state automaton (as the commenter Dave Clarke said), that is, given such a TM, construct a FSA that accepts the same language.

But since the TM has no memory but the tape, ask yourself what a right-only TM can do with its tape.  It should be relatively straightforward to actually construct the parts of the FSA you are looking for. Just go through them -- the states, the input alphabet and most crucially the move function (usually $\delta$) and define them in terms of the parts of the TM you started with. Then you have to show that the two accept the same language, in terms of the definition of "accept" for each, being sure to mention potential looping behavior in the TM.

BTW, this sort of problem is amenable to a pretty convincing "hand-waving" proof that would actually be of a type that is quite acceptable in a research paper.  Your course, however, may be expecting a precise proof, using $\delta$ and the other components of the tuples that constitute the TM and FSA.


According to lecture notes of Sam Palermo, there are three common I/O clocking architectures:

Common clock (synchronous)
Forward clock (source synchronous)
Embedded clock (clock recovery)


In fact, $Q$ is in NP (since you can reduce it to $S$ in poly-time and $S$ is in NP). It's just not necessarily NP-complete or NP-hard.
For example, let's let $Q$ be the following decision problem:

Given a number $n$, is $n$ prime?

This problem is known to be in $P$. But I can reduce it to something NP-complete, like HamiltonianPath:

First, determine whether $n$ is prime (in poly-time).
If it's prime, let $G$ be a graph with two vertices and one edge between them.
If it's not prime, let $G$ be a graph with two vertices and no edges.
Now, pass $G$ to HamiltonianPath, which will give you your answer.

In this case, $Q$ can be reduced to the NP-complete HamiltonianPath, but it clearly isn't NP-hard or NP-complete (since it can be solved in poly-time).


If two languages together cover all words and one is regular, is the other one as well?

In fact, the answer is no.

If $L_1$$\subseteq$ $\Sigma^*$, $L_2$$\subseteq$ $\Sigma^*$ , $L_1$ is regular and $L_1$$\cup$ $L_2$ = $\Sigma^*$ then is $L_2$ is not necessarily regular.

We can prove this through counter-example.

If we let $L_1$ = $\Sigma^*$, then we can choose any non-regular language in $\Sigma$  for $L_2$.

If we take $\Sigma$ = {a,b} and then let $L_2$ = $a^n$$b^n$ (A non-regular language) then  $L_1$$\cup$ $L_2$ = $\Sigma^*$ and $L_2$ is non-regular as required.


Is turing completeness related to recursive enumerable languages?

A language $L$ is computable if there is a Turing machine $M$ such that:

If $x \in L$ then $M$ halts on input $x$ with "YES" written on the output tape.
If $x \notin L$ then $M$ halts on input $x$ with "NO" written on the output tape.

A language $L$ is recursively enumerable if there is a Turing machine $M$ such that:

If $x \in L$ then $M$ halts on input $x$.
If $x \notin L$ then $M$ doesn't halt on input $x$.

As an example, consider the language HALT of all Turing machines that halt on the empty input. HALT is recursively enumerable, since given a Turing machine $M$, we can simulate it on the empty input. However, HALT is not decidable, as Turing showed using diagonalization.

Turing completeness is an informal concept (though it can probably be formalized). According tot he Wikipedia definition, a computing system is Turing-complete if:

Everything that can be computed by the system is computable (on a Turing machine).
Every computable language can be computed by the system.

However, we could just as well define Turing completeness with respect to recursive enumerability. The two definitions are probably equivalent for all reasonable computing systems.


Algorithms for 2-colouring a 2 x N matrix

One can view this problem as a dynamic programming problem with $3N$ subproblems.
Let $RR(N)$ be the number of solutions for a $2\times N$ matrix where the first row is colored with red-red, $RB(N)$ the number of solutions where the top cell is red and the bottom one blue, and $BR(N)$ the number of solutions where the top cell is blue and the bottom one red. By symmetry $RB(N)=BR(N)$.
We thus get the recurrences:
$$RR(N)=RR(N-1)+2BR(N-1)$$
$$BR(N)=RR(N-1)+BR(N-1)$$
Note that the total number of solutions for a $2\times N$ matrix is equal to $RR(N+1)$.
If one enters the first few terms (1, 3, 7, 17, 41, 99, 239, 577, 1393, 3363,...) of this recurrence in OEIS one finds that it is A078057:

Expansion of $(1+x)/(1-2*x-x^2)$.
[...]
Number of length-$n$ strings of 3 letters $\{0,1,2\}$ with no two adjacent nonzero letters identical. The general case (strings of $L$ letters) is the sequence with g.f. $(1+x)/(1-(L-1)*x-x^2)$. - Joerg Arndt, Oct 11 2012

An algorithm which computes $RR(N)$ by evaluating the recurrence above can do so with $O(N)$ additions. The numbers can get as large as $\Omega(N)$-bit, so the complexity is $O(N^2)$.


Predicate Logics - double negation HELP me understand

The semantics of negation are very simple:

  $\lnot \alpha$ is True iff $\alpha$ is false.

In your example, $\lnot (\lnot \forall x \lnot A(x))$ is True iff $\lnot \forall x \lnot A(x)$ is False iff $\forall x \lnot A(x)$ is True iff for all $x$, $\lnot A(x)$ is True iff for all $x$, $A(x)$ is false.

Perhaps the issue would become simpler if we fully parenthesize your expression:
$$
\lnot \stackrel 1( \lnot \stackrel2( \forall x \stackrel3( \lnot \stackrel4( A\stackrel5( x \stackrel 5) \stackrel 4) \stackrel 3) \stackrel 2) \stackrel 1).
$$
The superscripts count the nesting depth.


Find equivalent LTL formula, without Y (Yesterday) operator. How can I handle first state?

Initial states are somewhat of an anomaly. A similar problem is encountered in the $X$ operator when you try to define LTL over finite words. That is, it somehow would have made more sense to define PLTL over computations that are "infinite on both sides".

So, being an anomaly, it is probably easiest to treat it as such, and just explicitly deal with the initial state, requiring the first state not to have $a$.

Thus, an equivalent formula would be $G(Xa\to b)\wedge \neg a$.


Is the following language recursively enumerable?

I'll provide some hint. Try building a reduction $\overline{L_{acc}} \leq L$
changing your argument as follows:

... where $<M_w>$ is a TM that, on an input $x$ it performs:

Run $M$ on $w$ for $|x|$ steps
If $M$ rejected within $|x|$ steps ...
If $M$ accepted within $|x|$ steps ...
If $M$ did not halt within $|x|$ steps ...

When $M$ does not accept $w$, you want the above to diverge only on finitely many $x$s.

When $M$ accepts $w$, you want the above to diverge on infinitely many $x$s.

Alternatively, you can try to exploit the Rice-Shapiro theorem.


reducing a decision problem to a local search problem

To compare search problems, polytime many-one reductions work as follows: $A$ is reducible to $B$ if there are polynomial-time computable functions $f$, $g$ such that for any $A$-instance $x$, if $y$ is a $B$-solution to $g(x)$, then $f(x,y)$ is an $A$-solution to $x$.

We can view decision problems as special cases of search problems with unique binary answers, but note that the reduction notions disagree. In particular, we cannot really see the difference between yes and no instances in the search problem view.


How does lexical analyzer remove white spaces from source file?

A brief answer is "by ignoring them".
A compiler may scan the entire code more than once, but of course at least once in which case we call it a single-pass compiler. The task of lexical analyzer (or sometimes called simply scanner) is to generate tokens. This is done simply by scanning the entire code (in linear manner by loading it for example into an array) from the beginning to the end symbol-by-symbol and grouping them into tokens. Thus, while checking each symbol (of the source code) you just skip the white-space symbols. Similarly you skip comments in the source code.

As to my personal experience, I had to implement a single-pass compiler for a made-up simple language which allowed both white space symbols (TAB, NEW-LINE, SPACE) and comments. I loaded the entire source code into a linear array and as my lexical analyzer went over the code character by character it simply skipped all white space symbols and comments by moving forward the pointer pointing to the current character.

But depending on the implementation you could first pass over the source code just to remove all white spaces, and then on the second pass generate tokens.

Caution:  "ignoring whitespace" shouldn't be interpreted as "remove all white space symbols from the source and then further process the source code". In some cases depending on the language construct white spaces may indicate when a token ends for example in the following piece of code

  int foo(int x)
  {
    return x+2;
  }

The tokens TYPE (int) and the IDENTIFIER (foo) are separated by a single SPACE. But the IDENTIFIER (foo) and immediate LEFTPAR are not separated by any white space symbol.

Also (on Derek Elkins' comment) real compilers usually use whitespace for producing clear error messages, for example for keeping track of line numbers.


Explaination for Variation of Boyer-Moore Majority voting algorithm

Here is a different way to consider the same algorithm, or rather its general form with $k$ counters (in your case, $k=2$). There are $k$ "containers" and a trash bag. Each container will contain one type of element at a time. Initially everything is empty. When we read a new element $x$, we consider the following cases:

If there is a container containing $x$'s, add $x$ to that container.
If there is no container containing $x$ and there is an empty container, put $x$ in the empty container.
If there is no container containing $x$ and there are no empty containers, remove one element from each container, and put $x$ in the trash.

When the algorithm terminates, each of the $n$ elements is either found in one of the $k$ containers, or in the trash bag.

Suppose that element $x$, not found in any of the containers, is found $m$ times in the input. Thus all $m$ copies of $x$ are in the trash bag. Each time an element is put in the trash bag, $k$ other elements are also put in the trash bag together with it. This means that the trash bag contains at least $(k+1)m$ elements, and so $(k+1)m \leq n$ or $m \leq n/(k+1)$.

Consequently, if an element appears more than $n/(k+1)$ times in the input then it will necessarily be found in one the $k$ containers. In other words, the algorithm correctly identifies all elements appearing more than $n/(k+1)$ times.

Note how this analysis crucially depends on the fact that when trashing $x$ in the third case above, we also trash $k$ additional elements together with it.


$W^R$ means the reverse string of $W$.
You are right about the DFA. If a DFA $A$ accepts the language $L$ then it rejects all the words that are not in $L$. But the word $\sigma = 0110100$ is in the language!. Consider $W=0$ and $x=11010$.
As G.Bach eloquently stated in his comment(a very interesting property of the language):

$$\{WxW^R : W,x\in \{0,1\}^+\} = \{WxW : W\in\{0,1\} , x\in \{0,1\}^+\}$$

¿Why?

Because there is little restriction to $x$. We can consider that $x$ is almost the whole word with the exception of the first and the last symbol(because in the original language $|W|>0$). The reverse string of any word with unitary size is the same word. So words like:

$$\sigma_1 = 01110000$$
$$\sigma_2 = 11111101$$

Are in the language. All that matter is the first and the last symbol. This language is very interesting because it appears to be irregular at the first sight.


Is the term $(\lambda x.x)(y y)$ a normal form in call-by-value reduction strategy?

After some research, I think I can answer this question by myself now.
Short answer
Wikipedia is correct, that is
If the $\lambda $-calculus uses call by value reduction strategy, the term $(\lambda x.x)(y y)$ is a normal form.
Long answer
Standard $\lambda $-calculus does not distinguish reduction strategies. It only gives you some Reduction Rules (e.g. $\beta $-rule). You searching for a β-redex in a given term, as long as you find a β-redex, you can reduce one step.
This means that

You can reduce a $\beta $-redex inside a $\lambda $-abstraction.
You can reduce the operand $\beta $-redex first and then reduce the operator $\beta $-redex.
At any step, you can use either call-by-value or call-by-name reduction strategy.

Church–Rosser Theorem tells us that the outcome of $\lambda $-calculus (if it exists) is independent of the order in which the calculations are executed.
The benefit of Church–Rosser Theorem is that we can define an Equational Theory at top of the Reduction Rules.
Note that in the description above, I used extremely imprecise terminology, i.e. reduction strategy. Now i will fix this impreciseness:

I think reduction strategy and evaluation strategy mean the same thing.
For now, we cannot use the term "evaluation" because we have not yet defined an Evaluation Theory.

Unfortunately, there is very little literature describe how to define the Evaluation Theory for standard $\lambda $-calculus. The reason may be that:
In general, to define the Evaluation Theory, we need an abstract machine, but the use of an abstract machine means a fixed evaluation strategy, but standard $\lambda $-calculus does not depend on the evaluation strategy!
Therefore standard $\lambda $-calculus has no corresponding Evaluation Theory is logical.
OK, so far so good.
However the standard $\lambda $-calculus is not suitable to reason about programming languages. For example, Scheme/SML use call-by-value evaluation strategy, Haskell use call-by-name (or more precisely call-by-need) evaluation strategy.
To reason about these programming languages, a new $\lambda $-calculus needs to be devised. For example, Plotkin's call-by-value $\lambda $-calculus ($\lambda_v$ for short).
As standard $\lambda $-calculus, we now need to devise Reduction Rules, Equational theory and Evaluation theory for $\lambda_v$. I won't repeat Plotkin's formula here, but give two key points:

In Plotkin's paper, "value" does not mean "has no β-redexes", but "not a combination" (A term of form $(MN)$ is a combination).
Equational theory must satisfy Church–Rosser Theorem (for $\lambda_v$ version).

Back to the original question:
Is the term $(\lambda x.x)(y y)$ a normal form in call by value reduction strategy?
Answer:

The question involved "normal form" and "reduction strategy" (which is another name of evaluation strategy). It doesn't make sense, because one refers to an Equational Theory and the other refers to an Evaluation Theory.

The question involved  "call by value", we can fix this ill-question by assuming the calculus to be $\lambda_v$ and since the question also involved "normal form" and $(\lambda x.x)(y y)$ is not a closed term, we use Equational theory of $\lambda_v$.
The answer is:
$(\lambda x.x)(y y)$ has been a normal form, because $(y y)$ is not a value but a combination.

$(\lambda x.M)N = [N/x]M$ (if $N$ is a value)     ($\beta$ -rule)

You may argue that why $(y y)$ is not a value?
Can I define my own $\lambda_v$-calculus and let a normal form (e.g. $(y y)$) a value?
The answer is no.
For example, suppose that a normal form can be a value, then there are two ways to normal the term $(λx.(λy.z) (x (λx.xx))) (λx.xx)$.

$ \to (λy.z)((λx.xx) (λx.xx))$, then loop
$\to (λx.z)(λx.xx) \to z$

This make Church-Rosser theorem fail.
Similarly, adding $\eta$ rule also makes Church-Rosser theorem fail.
For example, suppose that we add $\eta$ rule, then there are two ways to normal the term $ (λx.y) (λx.((λx.xx) (λx.xx))x)$.

$ \to (λx.y) ((λx.xx) (λx.xx))$, then loop
$\to y $

Reference
Call-by-name, call-by-value and the λ-calculus
Reasoning about programs in continuation-passing style


$\newcommand{\co}{\mathsf{co}\text{-}}$
$\newcommand{\class}[1]{\mathsf{#1}}$

If $\class{PP}=\class{RP}$ then you have a collapse to the first level, namely $\class{PH}=\class{NP}$.

Assume $\class{PP}=\class{RP}$, since $\class{PP}$ is closed under complement we have $\mathsf{RP}=\co{\class{RP}}=\class{ZPP}$, thus $\class{PP}=\class{ZPP}$.

Using Toda's theorem:

$\class{PH}\subseteq\class{P^{\class{PP}}}=\class{P}^{\class{ZPP}}=\class{ZPP}\subseteq{\class{NP}}$.

You actually get something stronger, if $\class{PP}=\class{RP}$, then the hierarchy collapses to $\class{ZPP}$.

In fact, you could show that the counting hierarchy collapses to $\class{ZPP}$, using simpler arguments than Toda's theorem, and acheive $\class{PH}\subseteq\class{CH}\subseteq\class{ZPP}$.

A tempting argument would be to say that since $\class{PP}=\class{ZPP}$, and $\class{ZPP}$ is low for itself, i.e. $\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ then $\class{PP}^{\class{PP}}=\class{ZPP}^{\class{ZPP}}=\class{ZPP}$ and $\class{CH}$ collapses to $\class{ZPP}$. This is obviously false, since $\class{A}=\class{B}$ where $\class{A},\class{B}$ are sets of languages "decidable" by specific types of Turing machines (types $\class{A}$ and $\class{B}$), does not imply $\class{A}^{\mathcal{O}}=\class{B}^{\mathcal{O}}$ for any oracle $\mathcal{O}$. See this answer for further explanation.

What you actually need to show, in order to obtain $\class{CH}\subseteq{ZPP}$ (of course, under the original assumption of $\class{PP}=\class{RP})$, is that $\class{ZPP}$ is low for $\class{PP}$, i.e. $\class{PP}^{\class{ZPP}}=\class{PP}$. If this holds, then $\class{PP}^{\class{PP}}=\class{PP}^{\class{ZPP}}=\class{PP}=\class{ZPP}$, and thus $\class{CH}\subseteq\class{ZPP}$. Fortunately, this is not too difficult (and can even be strengthened to $\class{BPP}$ is low for $\class{PP}$).

Let $L$ be a language in $\class{PP}^{\class{ZPP}}$, then there exists a probabilistic polynomial time Turing machine with access to a $\class{ZPP}$ oracle $\mathcal{O}$, call it $M_{\mathcal{O}}$, such that:

$x\in L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]>\frac{1}{2}$, and

$x\notin L\Rightarrow \Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\le\frac{1}{2}-\frac{1}{2^{n^c}}$.

Where $n^c$ is the running time of $M_{\mathcal{O}}$ (in the standard definition, the second inequality appears with $\le\frac{1}{2}$, however it can be improved to $<\frac{1}{2}$ and thus to the above).

Suppose that the Turing machine which decides $\mathcal{O}$ has expected runtime $n^d$. Now, let us look at the machine $M$, which replaces each oracle call of $M_{\mathcal{O}}$ by a $t$ steps simulation of the $\class{ZPP}$ machine for $\mathcal{O}$, and repeats this simulation $k$ times. If we come upon an oracle call, for which this process did not result in an answer (none of the $k$ $t$-steps simulations halted), then $M$ rejects.

Let $H$ denote the event that all of the simulations halted in the given time, then:

$\Pr\left[\text{M accepts x}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]+\Pr\left[\text{M accepts x}\Big| \overline{H}\right]\Pr\left[\overline{H}\right]=\Pr\left[\text{M accepts x} | H\right]\Pr[H]=\Pr\left[M_{\mathcal{O}} \text{ accepts x}\right]\Pr[H]$.

Thus, we have:

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\Pr[H]$, and

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le\left(\frac{1}{2}-\frac{1}{2^{n^c}}\right)\Pr[H]\le \frac{1}{2}-\frac{1}{2^{n^c}}$.

By Markov's inequality, a single simulation does not halt with probability $\le \frac{n^d}{t}$, so $k$ $t$-steps simulations do not output an answer with probability $\le \left(\frac{n^{d}}{t}\right)^k$. By the union bound we have $\Pr[H]\ge 1-n^c\left(\frac{n^{d}}{t}\right)^k\ge 1-\frac{1}{2^{n^c}}$, for $t=2n^d$ and $k=2n^c$. In this case $M$ acheives the following separation:

$x\in L\Rightarrow \Pr\left[\text{M accepts x}\right]>\frac{1}{2}\left(1-2^{-n^c}\right)$, and

$x\notin L\Rightarrow \Pr\left[\text{M accepts x}\right]\le \frac{1}{2}-2^{-n^c}<\frac{1}{2}-\frac{1}{2}2^{-n^c}$

Which proves $L\in \class{PP}$, since we can replace the constant $\frac{1}{2}$ with any function $f(x)\in \class{FP}$. See this question for a proof to why we can replace $\frac{1}{2}$ with any rational constant, and convince yourself that it generalizes immediately to any $f\in \class{FP}$.


Can all languages have semantic and logical errors?

I think most likely the explanation for some authors using "logic error" and "semantic error" interchangeably and some authors drawing a distinction is simply that they don't have a precise universally accepted definition, and so people are using the terminology slightly differently. I wouldn't get hung up on it.

Both "logic" and "semantic" imply something to do with the meaning of the programming, so it would be easy to regard them as the same.

If I were to draw a distinction, a useful one I can see is that a logic error is when the program ends up meaning something other than what the programmer intended, and a semantic error is when the program ends up not meaning anything (consistent) at all. With those definitions, you could either regard logic errors as a superset of semantic errors, or that logic errors exclude errors that result in the program being inconsistent.

For example, the following pseudo code contains only a logic error:

x = read_number_from_user("x: ")
y = read_number_from_user("x: ")
print("The product of x and y is: ")
print(stringify(x + y))

The meaning of this program (taken solely as-is and without considering the programmer's intent) is perfectly straightforward and consistent. But it doesn't mean what the programmer intended it to mean.

OTOH, the following pseudo code contains a semantic error:

name = read_string_from_user("What is your name?")
print(name + 1)

At least, it does if we assume that adding a string and a number doesn't mean anything. In languages like PHP it does mean something, and this wouldn't be a semantic error.

Your example of a semantic error in PHP as calling a function with an incorrect number of parameters is actually interesting, because it's debatable whether you should call that a semantic error (with the definition I'm using).

Functions are defined dynamically at runtime in PHP. So calling a function with an incorrect number of parameters could be regarded as a logic error; perhaps the wrong include statement was executed, causing a different function with the same name to be included than the one the call was supposed to go to. Even if not, calling a function with the wrong number of arguments does mean something; it means lookup the function with this name and pass it these arguments. It's only operationally at runtime that it turns out the interpreter is unable to carry out those requests; just as x / y means something, but may be impossible to carry out if y happens to be 0 at runtime.

Ultimately, how you classify errors using a distinction like the one I'm making here between logic and semantic errors (even if it's not exactly the one I'm making) depends very much on the particular language you're talking about and how you assign meaning to programs in the language. Most commonly used languages do not have a standard way of assigning meaning to their programs, which means that everyone uses a slightly different way of doing so (though everyone's interpretation would agree very closely on almost all operational effects), and would analyse the "logical" vs "semantic" distinction differently.

Another similar way of looking at it would be to say that semantic errors are whatever causes the programming language to reject the program as invalid (apart from syntactic errors, though again you could call those a subset of semantic errors if you want). If the programming language accepts the program then it means something, and if it fails at runtime then that is the result of a logic error. This is pretty much assigning the programming language implementation (interpreter, compiler + runtime system, whatever) as the definition of what programs mean.


In order to show decidability, you need to provide an algorithm that will always halt, and yields a yes / no answer.

The following algorithm will return if there is a useless state in a given DFA (and can return the useless state).

Given a DFA $A$, run a BFS from the initial state ($q_0$), and mark every node that is being visited.

When BFS terminate (and it will, because we're dealing with a deterministic finite automata), every state that wasn't visited during the scan is a useless state.