Programming language where every expression makes sense

Redcode, the assembly language behind codewars, was explicitly written to have very few halting instructions, because the code often gets mangled before it finally gives out, and the more opportunities it has to halt, the less interesting the game is.

You see very few such languages in practice because we don't just want a program to run, we want it to run in the way we expect.  If you can make a typo and change the way the program ran, it must be acceptably close to the original expected behavior, or the programmers with seethe in frustration.

There is some precedence for such things by using natural languages rather than formal languages, but it's not what I would call a large field when you compare it to the use of formal languages.  If you're interested in such programming languages, the natural language processing community is where I'd look.

Another field you could look at is genetics.  There are remarkably few genetic sequences which are simply invalid.  Plenty of them that aren't very effective at reproductions, but very few invalid ones.


What is an example of a weakly universal hash function that is not pairwise independent?

Let $U = [m]$, and let $h$ be the identity function.

If you insist that $|U| > m$, then you can take $U = [m+1]$, and consider the functions $h_i$, for $i \in [m]$, given by
$$
h_i(x) = \begin{cases}
x & \text{if } x \neq m+1, \\
i & \text{if } x = m+1.
\end{cases}
$$
The same approach can be used for arbitrary $|U|$: fix the first $m$ coordinates, and make all other coordinates uniformly and independently random.


What is the relation between parsing languages and checking languages?

There is a simple relation between the two problems, but it goes in only one side: if you can parse, then you can recognize. Indeed, if you run the parser and it outputs failure, then the input is not in the language; if the parser produces a parse tree, the input is in the language.

Note, however, that a parser and a recognizer are not only solving different problems, but are also given different specs. A recognizer is given a language in some abstract form. In contrast, a parser is given a grammar, which not only implicitly defines a language, but also instructs the parser how to convert a valid input into a parse tree. Since the same language can have many equivalent grammars, it's not clear what it even means to convert a recognizer to a parser – what grammar should the parser use?

Why are recognizers interesting, then? Precisely because of the one-sided connection, which states that a parser can be converted to a recognizer. This relation implies that if your language is hard to recognize, then you won't be able to parse it (using a certain class of algorithms).


Your language consists of all words over $\{a,b\}$ which contain $a$. This is a regular language, and so it has an unambiguous regular grammar - essentially a DFA - which is not so difficult to construct for this language. Regular grammars constructed from DFAs are unambiguous, so this would be an unambiguous grammar for the same language.


On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

Let us consider the simplest case, that of a path of length two edges, which are drawn uniformly and independently from $[0,1]$. Let us suppose that the first edge is sub-dominant, which happens with probability 1/2. The probability that the weight of second edge is at most $t \in [0,1]$ is
$$
\Pr[x \leq y \leq t \mid x \leq y] = \Pr[x,y \leq t] = t^2.
$$
Here $x$ is the weight of the first edge, and $y$ is the weight of the second edge. We see that even before doubling, the distribution of $y$ is non-uniform.

Next, let us examine the case of a star with three edges, again drawn uniformly and independently from $[0,1]$. Again suppose that the first edge is sub-dominant, which happens with probability 1/3. The probability that the weight of the second edge is at most $t \in [0,1]$ while that of the third edge is at most $u \in [0,1]$ is
$$
\Pr[y \leq t, z \leq u \mid x \leq y,z] =
3 \int_0^{\min(t,u)} (t-x)(u-x) \, dx = \\
3tum - \frac{3}{2}(t+u)m^2 + m^3.
$$
Here $x,y,z$ are the weights of the first, second, and third edges, respectively, and $m = \min(t,u)$. Substituting $u = 1$, we obtain
$$
\Pr[y \leq t \mid x \leq y,z] = \frac{3t^2-t^3}{2}.
$$
Calculation shows that for generic $t,u$,
$$
\Pr[y \leq t, z \leq u \mid x \leq y,z] \neq
\Pr[y \leq t \mid x \leq y,z] \Pr[z \leq u \mid x \leq y,z],
$$
that is, the remaining weights are no longer independent.


Is a k counter automata a special kind of PDA?

A two-counter automaton has two counters, so two push-downs, each with a single stack symbol (agaun ignoring bottom). Such an automaton is not equavalent to push-down automata.

Any PDA can be shown to be equivalent with a PDA with two different stack symbols, so in itself characterize the context-free languages.

Two-counter automata are much more powerful, they can simulate Turing machines, and hance form the recursively enumarable languages.  The special bottom symbol is essential here. In that way the machine is able to do a zero test (i.e., check the contents of the counter is zero). The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...)  in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).


optimize string search on black-box function

The most optimal algorithm would be to perform a binary search for each character sequentially (bin-search for 1st char, bin-search for 2nd char, ...etc).


The time hierarchy theorem already does the diagonalization for you.

Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any problem in $\mathbf{EXP}$ by using the polynomial-time reduction to $X$ followed by the polynomial-time algorithm for $X$. But $\mathbf{EXP}=\mathbf{P}$ contradicts the time hierarchy theorem, because that tells us that there are problems in $\mathbf{EXP}$ that are not in $\mathbf{P}$. Therefore, $X\notin\mathbf{P}$ for any $\mathbf{EXP}$-complete $X$.

Honestly, the proof that checkers is $\mathbf{EXP}$-complete will be long and not at all enlightening: the only thing that simulating Turing machines with checkers positions will teach you is that the craziest systems can support computation. It's much easier to see that the following problem is $\mathbf{EXP}$-complete. The input is the description of a Turing machine $M$, and an input $x$. You accept if $M(x)$ halts within $2^{|x|}$ steps and reject otherwise. Call the language of accepted strings $L$.

So, let $Y\in\mathbf{EXP}$ be a set of strings over, e.g., $\{0,1\}^*$. It is decided by a Turing machine $M$ that runs in at most $2^{n^c}$ steps for some integer constant $c$, on inputs of length $n$. We define a new Turing machine $M'$ with input alphabet $\{0,1,p\}$ ("$p$" for "pad") that behaves as follows:

if its input is of the form $z\,p^{|z|^c-|z|}$ for some $z\in\{0,1\}^*$, it simulates $M(z)$ and accepts or rejects as that machine does;
otherwise, it rejects.

Note that $|z\,p^{|z|^c-|z|}| = |z|^c$.

Now, the reduction of $Y$ to $L$ is as follows. Given a string $y\in\{0,1\}^*$ for which we want to know whether $y\in Y$, we ask whether $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$. We can construct this query in polynomial time, since the description of $M'$ is some constant string, and we just need to write an easily computed polynomial number of $p$'s after $y$. And we have $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$ iff $M'$ accepts $y\,p^{|y|^c-|y|}$ in at most $2^{|y\,p^{|y|^c-|y|}|}=2^{|y|^c}$ steps, iff $M$ accepts $y$ in at most $2^{|y|^c}$ steps, iff $y\in Y$.

Similar techniques give you complete problems for any time or space complexity class.


Most likely it means an axis-aligned rectangle, i.e., a rectangle whose bottom edge is horizontal (parallel to the $x$-axis) and whose left edge is vertical (parallel to the $y$-axis).  This is the standard meaning of "bounding box".  For future reference, before asking it is useful to check Wikipedia and search thoroughly.  In this case you would have found lots of information on the phrase "bounding box": see, e.g. https://en.wikipedia.org/wiki/Minimum_bounding_box and https://en.wikipedia.org/wiki/Minimum_bounding_rectangle


Generating regular expressions not containing abc

Design a DFA that recognizes "abc" (make sure to include all transitions). Complement it (make accepting states non-accepting, and make non-accepting states accepting) in order to get a DFA for $L = \Sigma^* \setminus \{ abc \}$. Finally, write down the regular expression of the complemented DFA.

As a brute force solution that does not use DFAs: write a regular expression for all words of lengths 0, 1, 2, and more than 3. This should be easy.
Then write, a regular expression for all words of length 3 except abc.
For example:
$(b+c)(a+b+c)^2 + ab(a+b) + a(a+c)(a+b+c)$

Take the union of all the above REs.


Finding a pair of non-overlapping bit vectors

Warmup: random bitvectors

As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random.  Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$).

We'll consider the following two-set variant of the problem:

Given sets $S,T \subseteq \{0,1\}^k$ of bitvectors, determine where there exists a non-overlapping pair $s \in S, t \in T$.

The basic technique to solve this is divide-and-conquer.  Here is a $O(n^{1.6} k)$ time algorithm using divide-and-conquer:

Split $S$ and $T$ based upon the first bit position.  In other words, form $S_0 = \{s \in S : s_0=0\}$, $S_1 = \{s \in S : s_0 = 1\}$, $T_0 = \{t \in T : t_0 = 0\}$, $T_1 = \{t \in T : t_0 = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

Since all bitvectors are chosen at random, we can expect $|S_b| \approx |S|/2$ and $|T_b| \approx |T|/2$.  Thus, we have three recursive calls, and we've reduced the size of the problem by a factor of two (both sets are reduced in size by a factor of two).  After $\lg \min(|S|,|T|)$ splits, one of the two sets is down to size 1, and the problem can be solved in linear time.  We get a recurrence relation along the lines of $T(n) = 3T(n/2) + O(nk)$, whose solution is $T(n) = O(n^{1.6} k)$.  Accounting for running time more precisely in the two-set case, we see the running time is $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$.

This can be further improved, by noting that if $k \ge 2.5\lg n+100$, then the probability that a non-overlapping pair exists is exponentially small.  In particular, if $x,y$ are two random vectors, the probability that they're non-overlapping is $(3/4)^k$.  If $|S|=|T|=n$, there are $n^2$ such pairs, so by a union bound, the probability a non-overlapping pair exists is at most $n^2 (3/4)^k$.  When $k \ge 2.5 \lg n+100$, this is $\le 1/2^{100}$.  So, as a pre-processing step, if $k \ge 2.5 \lg n + 100$, then we can immediately return "No non-overlapping pair exists" (the probability this is incorrect is negligibly small), otherwise we run the above algorithm.

Thus we achieve a running time of $O(n^{1.6} \min(k, \lg n))$ (or $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$ for the two-set variant proposed above), for the special case where the bitvectors are chosen uniformly at random.

Of course, this is not a worst-case analysis.  Random bitvectors are considerably easier than the worst case -- but let's treat it as a warmup, to get some ideas that perhaps we can apply to the general case.

Lessons from the warmup

We can learn a few lessons from the warmup above.  First, divide-and-conquer (splitting on a bit position) seems helpful.  Second, you want to split on a bit position with as many $1$'s in that position as possible; the more $0$'s there are, the less reduction in subproblem size you get.

Third, this suggests that the problem gets harder as the density of $1$'s gets smaller -- if there are very few $1$'s among the bitvectors (they are mostly $0$'s), the problem looks quite hard, as each split reduces the size of the subproblems a little bit.  So, define the density $\Delta$ to be the fraction of bits that are $1$ (i.e., out of all $nk$ bits), and the density of bit position $i$ to be the fraction of bitvectors that are $1$ at position $i$.

Handling very low density

As a next step, we might wonder what happens if the density is extremely small.  It turns out that if the density in every bit position is smaller than $1/\sqrt{k}$, we're guaranteed that a non-overlapping pair exists: there is a (non-constructive) existence argument showing that some non-overlapping pair must exist.  This doesn't help us find it, but at least we know it exists.

Why is this the case?  Let's say that a pair of bitvectors $x,y$ is covered by bit position $i$ if $x_i=y_i=1$.  Note that every pair of overlapping bitvectors must be covered by some bit position.  Now, if we fix a particular bit position $i$, the number of pairs that can be covered by that bit position is at most $(n \Delta(i))^2 < n^2/k$.  Summing across all $k$ of the bit positions, we find that the total number of pairs that are covered by some bit position is $< n^2$.  This means there must exist some pair that's not covered by any bit position, which implies that this pair is non-overlapping.  So if the density is sufficiently low in every bit position, then a non-overlapping pair surely exists.

However, I'm at a loss to identify a fast algorithm to find such a non-overlapping pair, in these regime, even though one is guaranteed to exist.  I don't immediately see any techniques that would yield a running time that has a sub-quadratic dependence on $n$.  So, this is a nice special case to focus on, if you want to spend some time thinking about this problem.

Towards a general-case algorithm

In the general case, a natural heuristic seems to be: pick the bit position $i$ with the most number of $1$'s (i.e., with the highest density), and split on it.  In other words:

Find a bit position $i$ that maximizes $\Delta(i)$.
Split $S$ and $T$ based upon bit position $i$.  In other words, form $S_0 = \{s \in S : s_i=0\}$, $S_1 = \{s \in S : s_i = 1\}$, $T_0 = \{t \in T : t_i = 0\}$, $T_1 = \{t \in T : t_i = 1\}$.
Now recursively look for a non-overlapping pair from $S_0,T_0$, from $S_0,T_1$, and from $T_1,S_0$.  If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

The challenge is to analyze its performance in the worst case.

Let's assume that as a pre-processing step we first compute the density of every bit position.  Also, if $\Delta(i) < 1/\sqrt{k}$ for every $i$, assume that the pre-processing step outputs "An overlapping pair exists" (I realize that this doesn't exhibit an example of an overlapping pair, but let's set that aside as a separate challenge).  All this can be done in $O(nk)$ time.  The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be?  I'm not sure, but here are a few observations that might help.  Each level of recursion reduces the problem size by about $n/\sqrt{k}$ bitvectors (e.g., from $n$ bitvectors to $n-n/\sqrt{k}$ bitvectors).  Therefore, the recursion can only go about $\sqrt{k}$ levels deep.  However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than $3^{\sqrt{k}}$ leaves), so I'm not sure what running time this should lead to.


What exactly is execution-time address binding?

Until the program is running, physical addresses make little (or no) sense: The instructions make reference to logical addresses.
While the program runs, the CPU maps logical addresses to physical addresses (they could be just exactly the same, or change e.g. by paging or just by relocation --- add the contents of a special register to each logical address to give the pysical address, used in some early machines to be able to place several programs tightly in memory and be able to move them around). If you look e.g. at the intel 8088/8086 (infamous CPUs for the original PC), it sports segment registers, so you can move say the stack around in RAM and the program doesn't care where it is.


You can prove the existence of an object satisfying properties in many ways. The simplest is to exhibit such an object explicitly, which is what you can do in your case. But there are also other possibilities:

Use a probabilistic argument. If you choose a uniformly random graph on $n$ vertices, then it will have no large clique or independent set. We don't know how to construct such graphs explicitly.  Sometimes it is not enough to just choose a random graph. The well-known construction of graphs with high girth and high chromatic numbers modify a random graph so that it satisfies the requirements. A more sophisticated version is the recent interlacing polynomials method, used to construct Ramanujan graphs.
Use a non-constructive argument. The is an algorithm that given $n$, determines whether the decimal expansion of $\pi$ contains a block of $n$ zeroes. Indeed, such a program either always returns YES, or it returns whether $n \leq N$, where $N$ is the longest such stretch of zeroes. While we do not at the moment know which of the two options is correct, one of them must be correct, and so the algorithm exists.
Use a proof by compactness. Consider the problem of determining whether a graph can be embedded into a torus (without edge crossings). This is a minor-closed family of graphs, and we can consider the set of forbidden minors, i.e., minimal graphs (with respect to the minor relation) not embeddable into a torus. This is an antichain of graphs (with respect to the minor relation), so according to the graph minor theorem, it must be finite. Since we can test whether a graph on $n$ vertices has a given graph as a minor in time $O(n^2)$, it follows that we can determine whether a graph is embeddable in a torus in time $O(n^2)$. But we can't actually construct the algorithm, so we don't know the complete list of forbidden minors.


Analog of PP for computability rather than complexity?

The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to RE.

First, let's introduce some notation. Let's call the complexity class described in this problem PRE for "probabilistic RE." We'll say that a language $L$ is in PRE if and only if there is a randomized TM $M$ such that

$$w \in L \leftrightarrow Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$$

The question now is how RE and PRE relate to one another. The goal will be to prove this theorem:

  Theorem: PRE = RE

To prove this, we'll show that each set is a subset of the other. One direction here happens to be relatively easy:

  Theorem: RE $\subseteq$ PRE.

  Proof: Consider an arbitrary $L \in$ RE. Since $L$ is in RE, there must be a TM $M$ that recognizes $L$. Specifically, for any string $w$, if $w \in L$, then $M$ accepts $w$, and if $w \notin L$, then $M$ does not accept $w$. Now, we can construct a randomized TM $M'$ that's basically the same as $M$; it doesn't actually use any randomness. As a result, if $w \in L$, then $Pr[M \mbox{ accepts } w] = 1$ and if $w \notin L$, then $Pr[M \mbox{ accepts } w] = 0$. Consequently, $L \in $ PRE.

The other direction of implication is the harder one. We're going to show that if you start with an arbitrary PRE language, you can prove that it's also an RE language. Equivalently, we'll show how to start with a randomized TM $M$ meeting the criteria of PRE and then show how to construct a recognizer for it.

Let $$M$$ be any randomized TM. Our goal will be to prove the following key lemma:

  Lemma: $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$ if and only if there is some $n \in \mathbb{N}$ where $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$

For now, let's assume the lemma is true. This gives rise to an elegant way to build a recognizer for any PRE language. Counting up from $n=1$, exhaustively list all computation paths through $M$ whose length is at most $n$ and explicitly compute the probability that $M$ accepts within $n$ steps. If at any point we find that this probability is greater than 1/2, by the lemma we know that the overall probability that $M$ accepts is greater than 1/2, so the input string $w$ must belong to $L$.

On the other hand, suppose that we never find an $n$ for which the acceptance probability within $n$ steps is greater than 1/2. That means that the acceptance probability for each computation length is at most 1/2. Since

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

we would conclude that $Pr[M \mbox{ accepts } w] \le \frac{1}{2}$, meaning that $w \notin L$. In other words, the TM that just brute-force checks the acceptance probability for each computation length would be a recognizer for $L$, and so we'd see that PRE $\subseteq$ RE.

Everything hinges on this key lemma, so let's see how we might go about proving it. One direction is easier. Let's argue that if $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, then there must be some $n$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{steps}] \gt 1/2$. As mentioned above, we know that

$$Pr[M \mbox{ accepts } w] = \lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Therefore, if we assume that $Pr[M \mbox{ accepts } w] \gt \frac{1}{2}$, we know that

$$\lim_{n \rightarrow \infty} Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$$

We can use the formal definition of a limit to conclude from this that there must be at least one $n \in \mathbb{N}$ such that $Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}] \gt \frac{1}{2}$.

For the other direction, we need this additional result: if $m \le n$, then

$$Pr[M \mbox{ accepts } w \mbox{ within } m \mbox{ steps}] \le Pr[M \mbox{ accepts } w \mbox{ within } n \mbox{ steps}]$$

Intuitively, this says that the acceptance probability as a function of the length of the computations considered is nondecreasing. Why is this? If you run a computation for $m$ steps and then continue to run it for one more step, all of the branches that were already accepting are still accepting. If none of the new branches exposed by running the TM for one more step are accepting, then the new acceptance probability is the same as the old acceptance probability. If any of the new branches exposed are accepting, the acceptance probability goes up.

Given this, we can say that if the acceptance probability after some number of steps $n$ ever exceeds $\frac{1}{2}$, then the acceptance probability for all larger numbers of steps also exceeds $\frac{1}{2}$, so the limit of the acceptance probability is also greater than $\frac{1}{2}$.

To summarize:

RE $\subseteq$ PRE since any recognizer fulfills the conditions of a randomized TM for a PRE language.
If we have a randomized TM meeting the requirements for a PRE language, then that TM accepts a string with probability greater than one half if and only if after some finite number of steps the acceptance probability exceeds one half. We can then build a recognizer for the language by simulating branches of the randomized TM and checking, at each point, whether the acceptance probability is at least one half.

Hope this helps!


Preservation of context-free languages under prefix and suffix elimination

I answer for the case that an arbitrary number of leading or trailing $0$ can be deleted. This supposes that your $L=0M0$ is wrong; it would mean that all words in $L$ start and end with $0$. Since the rest of your question does ot seem to imply this and since that case would be rather trivial, I ignore this equation and answer what I understand from the rest of the question.

You are right. There is no bound on the number of 0 in the beginning, and each one of them can put something on the stack. Thus there is an infinite number of possible stack configurations that can be reached after reading them.

My idea is this: essentially we replace the transitions that read $0$ by ones that read the empty string $\lambda$. The problems are now that $0$ inside $M$ must still be read and that the $\lambda$-transitions could be executed inside $M$, too.

Therefore we make three copies of the sets of states and transitions. In the first one we replace input $0$s  by $\lambda$ in all transitions. All transitions reading an input different from $0$ lead to the corresponding state in the second copy of the state set.

The second set works like the original PDA reading the word from $M$. For every transition that reads $0$ we add a copy that leads to the corresponding state in the third set; these amount to guesses that the current $0$ starts a final block of only $0$.

The third set works much like the first (reading $\lambda$ instead of $0$), only for inputs other than $0$ it rejects.

For the $L=0M0$ case you can adapt this contruction as follows: all the new $\lambda$-transitions from the first set lead immediately to states of the second set. In this way only one leading $0$ is simulated. For the termination: go to a special final state after simulating the read of one $0$.


Is the powerset of a regular set also a regular set?

No.  In computer science, a language is normally defined to be a subset of $\{0,1\}^*$.  If $L$ is a language, then the powerset $2^L$ is not a subset of $\{0,1\}^*$, so it is not a language.

(See e.g., https://en.wikipedia.org/wiki/Formal_language#Definition.)

If $L$ is finite, then the powerset $2^L$ is finite, so as Emil Jeřábek points out, there is a way you can encode it so its encoding is a regular language, since all finite languages are regular.

If $L$ is infinite, then as Yuval Filmus points out, the powerset $2^L$ is not countable, so there is no way to encode it as a language.  Thus, when $L$ is an infinite regular language, then the answer to your question is "no, not even if you're allowed to choose a reasonable encoding".


Does closure under intersection and complementation imply closure under union?

This is immediate from De Morgan's laws.

  Does closure under intersection and union imply closure under complementation?

This one is slightly trickier. The answer is no.

Both intersection and union are what is called "monotone". That means that, if you make $X$ or $Y$ bigger then $X\cup Y$ and $X\cap Y$ can't get smaller. By induction, you can prove that any operator defined using only intersections and unions must also be monotone. But complement is not monotone: when you make $X$ bigger, its complement definitely gets smaller. So complement cannot be defined using only intersection and union.


Proving that no two state DFA accept the language L = {$0^i : \forall i \ge 0$} $\lor$ {$^i : \forall i \ge 0$}

Use Myhill–Nerode theory. Here are four words which are pairwise incomparable:
$$ \epsilon,0,1,01. $$

The following table gives words separating them:
$$
\begin{array}{c|c|c|c|c}
& \epsilon & 0 & 1 & 01 \\\hline
\epsilon & & 1 & 0 & \epsilon\\\hline
0 & 1 & & 0 & \epsilon\\\hline
1 & 0 & 0 & & \epsilon\\\hline
01 & \epsilon & \epsilon & \epsilon &
\end{array}
$$

According to Myhill–Nerode theory, every DFA for $L$ must contain at least four states. It is not too hard to construct a DFA containing four states, so four is the minimal number of states.


Swap elements using integer addition and multiplication gates

Let's say we have inputs $x, y$ and $c$, where $c$ is either 0 or 1, 0 = no swap, 1 = swap. We can make a conditional swap function like this:

notc = 1 + (-1)*c
x' = notc*x + c*y
y' = c*x + notc*y

Even if you have no negative integers, as long as your integers are modulo $2^n$, you can use $-1 \equiv 2^n - 1 \mod 2^n$ and everything works out.


Reinforcement learining basics - is it possible to deal with environment with random events

Yes, in general reinforcement learning algorithms can handle random events in the environment. Think about the q-learning update rule
$$ Q(s_t,a_t)= Q_{s_t, a_t} + \alpha \left(r_{t+1} + \gamma max_aQ(s_{t+1},a)\right) $$
But remember $$Q(s_{t+1},a) = \mathbb{E}_\pi\left( \sum_{i=t+2}^T\gamma^{i-1}r_{i} \right)$$
that is the expected value of the discounted sum of future rewards. This handles randomness in the environment quite well and eventually the value will adjust to factor in these random events. In a tabular environment this will always converge to the optimal value function and corresponding policy.
If you know the environment dynamics (which it seems like you do here)
$$ p\left(s', r\mid s,a\right)$$
you can use a dynamic programming method like policy iteration or value iteration to efficiently compute an optimal policy and value function. I recommend looking at the first 4 chapters of Reinforcement Learning: An Introduction by Sutton and Barto (at least chapters 3 and 4). The text is available freely online on their website at their website.


Partial type inference for dependent types

I recommend to look at (1) first, which might be the canonical early work on this problem and lead to the ATS programming language. (2) is a recent work on the same problem.

As to using constraints for type inference, (3) is probably the canonical reference.

H. Xi, F. Pfenning, Dependent Types in Practical Programming.
T. Terauchi, Dependent Types from Counterexamples.
F. Pottier, D. Remy, The Essence of ML Type Inference.


Existence of walk in undirected connected graph where nodes must end with assigned value

Let $k$ be the value where we wrap around, in this case $10$. Then the problem can be solved in $\mathcal{O}(n^2 k^2)$ with DP. With some tricks we will improve this to $\mathcal{O}(n k^2 \log n)$. For fixed $k$ this complexity is nearly linear, $\mathcal{O}(n \log n)$. Both algorithms work even on worst-case inputs: the assumption of random assignment of values is unnecessary.

We start from the $\mathcal{O}(n^2 k^2)$ algorithm. A connected graph with $n$ vertices and $n-1$ edges is a tree. To check if we can start from some vertex $r$, root the tree at that vertex. We will store the dp states $DP[i][t]$, which will denote if the subtree of vertex $i$ can be made to contain only the value $k$, if we cross the edge between $i$ and its parent $t$ times $(\text{mod}\ 2k)$, and our path starts from an ancestor of $i$. After calculating the $DP$, we know that the path may begin from $r$ iff $DP[r][2k-1] = 1$.

Note that we may assume that all edges are traversed at least once, since traversing any path back and forth $k$ times changes nothing. Additionally, crossing some edge $2k$ more or less times doesn't change whether a solution exists as long as we still cross it at least once, as we can re-connect the tours visiting these vertices such that we get a path that visits every vertex the same amount of times $(\text{mod}\ k)$.

Let $C_{i, j}$ denote the $j$th child of vertex $i$. Let $V_i$ denote the number of times we have to visit the vertex $(\text{mod}\ k)$ for its value to equal $k$. We have the requrrences

\begin{gather}
DP[i][2t_0] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j]\\
DP[i][2t_0 - 1] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \max_{r = 0, \dots, |C_i|} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j + \mathbb{I}_{r}(j)]
\end{gather}
where $\mathbb{I}_{r}(j) = 1$ iff $r = j$.

The first recurrence holds, since if we cross the edge from $i$ to its parent $2t_0$ times and the edge from $i$ to its $j$th child $2t_j$ times, we visit $i$ exactly $\sum_j t_j$ times, which must equal $V_i\ (\text{mod}\ k)$. On the other hand, since the edges crossed an odd number of times form a path starting from $r$, and we cross the edge from $i$ to its parent an even number of times, we must likewise cross the edges from $i$ to its children an even number of times.

The second recurrence similarly holds, since if we cross the edge from $i$s parent to $i$ $2t_0 - 1$ times, $t_0$ of those crossings end in $i$, and if we cross the edge from $i$ to its $j$th child $2t_j + 1$ times, $t_j$ of those crossings end in $i$. Thus this sum must equal $V_i\ (\text{mod}\ k)$. The same path argument gives us that we may cross at most one edge from $i$ to its children an odd number of times.

These recurrences can be computed in $\mathcal{O}(|C_i| k^2)$ by initialising $DP[i][t] = \mathbb{I}_{0}(t)$, then looping over the children, at child $j$ assigning
\begin{gather}
DP[i][2t-1] \gets \max_{0 \leq t_1 < 2k} \max_{r = 0, 1} \min(DP[i][2t - 2t_1 - r],\ DP[C_{i, j}][2t_1 + (1 - r)])\\
DP[i][2t] \gets \max_{0 \leq t_1 < 2k} \min(DP[i][2t - 2t_1],\ DP[C_{i, j}][2t_1])\\
\end{gather}
At this point, $DP[i][2t-r]$, for $r \in {0, 1}$, is one if we can visit $i$ in total $t$ times, crossing the edge from $i$s parent to $i$ exactly $-r$ times $(\text{mod}\ 2k)$, but we need the amount of visits to equal $V_i$, so we finally assign
\begin{gather}
DP[i][2t] \gets DP[i][2V_i - 2t]\\
DP[i][2t-1] \gets DP[i][2V_i - 2t - 1]\\
\end{gather}

The complexity of checking one $r$ is thus $\mathcal{O}(\sum_i |C_i| k^2) = \mathcal{O}(n k^2)$, giving the complexity $\mathcal{O}(n^2 k^2)$.

We can optimise this by noticing that we calculate the same $DP$ values multiple times. However, the straightforward approach of leveraging this fails: calculating $DP'[i][p][t]$, where $p$ is the neighbour of $i$ that is an ancestor of $i$ might take $\mathcal{O}(n^2 k^2)$ time, even though there are only $4(n-1)k$ states: consider the star graph. To fix this issue, we use centroid decomposition.

The centroid is a vertex of the tree, such that if we root the tree at that vertex, every subtree will have size at most $\frac{n}{2}$. Such a vertex always exists. Our algorithm will work as follows:

Root the tree at the centroid $r$
Calculate $DP'[C_{r,j}][i][t]$ for all $j, t$ in $\mathcal{O}(nk^{2})$. This gives us the answer for $r$
Using these values, calculate $DP'[i][C_{r,j}][t]$ for all $j, t$ in $\mathcal{O}(|C_r| \log |C_r| k^2)$
Disable vertex $r$ and recurse to the remaining subtrees. Whenever we try to visit vertex $r$, just return the already calculated $DP$ values.

Before addressing how to do step 3, we'll calculate the complexity of this approach. At the $m$th (0-indexed) round, the size of every remaining subtree is at most $n2^{-m}$. Thus there are at most $\log n$ rounds. During the $m$th round, every remaining subtree is adjacent to at most $m \leq \log n$ already handled vertices. If $n_r$ is the size of the remaining subtree $r$ is in when $r$ is picked centroid, then steps 1-3 for that subtree take $\mathcal{O}((n_i + \log n) k^2 + |C_r| \log |C_r| k^2)$ time (due to the already handled at most $\log n$ vertices).

Since there are at most $\log n$ rounds, and the sum of $n_r$ of $r$ participating in that round is at most $n$, we have $\sum_{i} n_i \leq n \log n$. Thus the total complexity is

\begin{equation}
\mathcal{O}(\sum_{i} n_i k^2 + k^2 \log n + |C_i| \log |C_i| k^2) = \mathcal{O}(n k^2 \log n)
\end{equation}

since each term sums to at most this.

It remains to show how to do step 3. Note that our approach to calculating $DP[i][t]$ doesn't care about the processing order of the children. Say $|C_r| = 2^{m}$. First, using our approach, calculate the intermediate values for children with index in $[1, 2^{m-1}]$ and in $[2^{m-1} + 1, 2^{m}]$. At the $s$th (1-indexed) step, using the previously calculated values, calculate the values for children with index not in $[x 2^{m-s} + 1, (x+1) 2^{m-s}]$, for all $x$, in $\mathcal{O}(2^{m-s} k^2)$ time per interval (by including the other $2^{m-s}$ indices not in this inteval but in the interval in the previous step containing this interval). After the last step, we get $DP'[C_{r, j}][r]$ from the intermediate value for all children but $C_{r, j}$. This is indeed $\mathcal{O}(|C_r| \log |C_r| k^2)$.


How to find min or max in constant time using infinite # processors?

I managed to solve this so hoping it's alright to answer your own question.
Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number against every other number on $n \choose 2$ processors. Each processor switches the bit corresponding to the smaller of its two elements to 1. Assumption is that the processors can do concurrent writes to $A$. The bit in $A$ remaining off denotes the maximum element.

This is $\Theta(1)$ (constant time) as the depth of the computational graph is independent of the number of elements. The work required is however $\mathcal {O(n^{2})}$.


Using two hash functions for increased password security?

Simply hashed passwords are susceptible to brute force or rainbow table attacks.  Hashing the passwords again will simply increase the cost of computing an entry in these tables (by one hash), but that is not an appreciable increase in the challenge of cracking them.

Several techniques available in practice including salt ing the password, wherein you prepend the password with a random substring (known as the salt), which you also prepend (in plaintext) to the hash.  So, whereas a password "hello" might hash to h("hello"), the salted password would be foo || h("foo" || "hello").  If "foo" is random, then this means that I may need to store all possible salted hashes for a given password in order to crack it.

To complicate the crack-ability of the password hash even further, one may add a pepper, which is a random (but not published) string prepended to password before hashing.  Checking a password in this case requires checking all possible peppers with a given password to see if any hash to the stored hash value.


A context-free grammar is just a string such as "$A\to 0A0\mid 1A1\mid 0\mid 1$".  Forget for the moment that such a string happens to define a language (in this case, the set of all odd-length binary palindromes) and focus on the fact that it's a string over some alphabet.

Now, let $L$ be the set of strings that are regular grammars.  A set of strings is a language.  The question is asking if $L$ is a regular language.


You can use dynamic programming (in this case, known as the Floyd–Warshall algorithm) to calculate the least weight of a walk of length $\ell$ from $x$ to $y$, for all vertices $x,y$ and $\ell \geq 0$. The first $\ell$ (if any) such that this weight is negative is the length of the shortest negative cycle. (This breaks if there are bidirectional negative edges, unless you consider them as simple cycles.)


You can compute the exact distribution of $\sum_{i=1}^n s_i$ using dynamic programming: for each vertex $v$, index $m \in \{0,\ldots,n\}$ and index $S \in \{0,\ldots,9m\}$, calculate the number of walks of length $m$ starting at $0$, ending at $v$, and summing to $S$. The running time is roughly $O(n^3)$ (the extra $n$ factor is due to the length of the numbers involved).

If you want an estimate, you should first find the stationary distribution of the Markov chain corresponding to a random walk on your graph. Given that, $\sum_{i=1}^n s_i$ has roughly Gaussian distribution with parameters that you can calculate from the stationary distribution; more specifically, roughly $N(n\mu, n\sigma^2)$ (this requires a version of the central limit theorem for Markov chains). This Gaussian approximation shows that the sum lies inside the interval of width $n$ centered around $n\mu$ with high probability, so taking modulo $n$ doesn't have much effect beyond shifting this interval to $\{0,\ldots,n-1\}$.


First, let me state that you may have things to unlearn. Files that are a stream of bytes are very much the rule, and have been for a long time. Almost all filesystems store a sequence of bytes, and leave the interpretation of that sequence of bytes up to applications or at least to higher-level libraries. Sequential files, consisting of a sequence (typically of variable length) of fixed-size records, went out of fashion in the 1980s if not in the 1970s. They still exist in big iron¹ (running VMS or “bigger” systems such as IBM mainframe OSes), but most programmers can go through their whole career without seeing one of those. Any book teaching sequential files as common is good only to teach operating system history, not operating systems.

Unix sees all files as byte streams. Simplifying operating system interfaces was one of Unix's major contributions, and that one stuck. Windows also sees all files as byte streams. Between them, that's essentially the whole server ecosystem, the whole workstation ecosystem, the whole mobile ecosystem², and a large chunk of the embedded ecosystem. Small embedded operating systems may have structured files, but if so I think they're generally files with a fixed structure (a single record, if you like, with set of possible formats imposed by the system) rather than a sequence of records.

In a sequential files, all the record play equivalent roles. There isn't a record for different kinds of data, but a record for different elements in a list. You can see an example in the VMS documentation. In modern terms, a sequential file is a table, a record is a row, and tables are stored in databases, not in filesystems. Although filesystems and databases are conceptually related, databases are focused on data with structure (and relations between data elements), while filesystems are focused on independent files. These approaches have different desirable security and stability guarantees, different interfaces, different performance goals, etc.

Things like the creation date³, the access permissions, etc. are generically called metadata. They are also stored in the filesystem, but outside the file's main data area. Operating systems generally report only the size of the “main” data when they report a file's size: the size isn't how much space the file occupies on the disk, but how much data is in the file. Accounting for disk usage completely accurately is rather complex — have a look at this, and keep in mind that this is only on one specific operating system.

A basic way to store files is to have every directory entry be a fixed-size structure containing the file name, other end-user metadata (timestamps, ownership information, access permissions, etc.), and some internal metadata that lets the operating system know where on the disk the file data is. A common extension to this approach is to create a level of indirection, where each directory entry contains just the file name and a pointer to another location (called an inode in the Unix world) containing the rest of the metadata.

The technical term for having multiple parts in a file with different roles (the data, the access control list, the timestamps, etc.) is a fork or stream (beware that both of these words also have different meanings). Many filesystems support only a single stream per file (the data stream), plus some fixed-size metadata. The metadata can be viewed as a stream from a conceptual point of view, but there's often no way to access it as a stream of bytes, only through dedicated functions. Some examples of uses of alternate streams are the resource fork on Mac OS, and extended (variable-size) security attributes on Linux.

The reason many file copy tools copy metadata together with the file content is that they're programmed to do so, i.e. rather than “open existing file, create new file, read data from existing file, write data to new file”, the copy algorithm also includes steps such as “read existing file's permissions, set new file's permissions to those, read existing file's timestamp, set new file's timestamp to that”.

¹  Mainframes — or mainframes emulated on x86 hardware, but running a 20-year-old emulator in which a 40-year-old operating system is running a 50-year-old application written in COBOL that nobody dares touch!
²  Maybe add Symbian — where files are byte streams too.


Graph with $\Theta(2^n)$ minimum $(s, t)$-cuts

If we fix the vertices $s$ and $t$ in the graph, then we can have an exponential number of $(s,t)$ min-cuts.
Following is an example of a graph that contains an exponential number of $(s,t)$-min cuts.
Let the vertex set be $V = \{s\} \cup \{u_{1},\dotsc,u_{n}\} \cup \{v_1,\dotsc,v_n\} \cup \{t\}$. Let the edges set contains the edges $(s,u_{i})$, $(u_{i},v_{i})$, and $(v_{i},t)$ for each $i \in \{1,\dotsc,n\}$. Therefore, there are total $3 n$ edges. Each edge has capacity $1$.
Let $C = (S,T)$ be a cut such that $s \in S$ and $t \in T$. Consider the vertices $u_{i}$ and $v_i$. There are four possibilities:

$u_i \in S$ and $v_i \in T$. Then edge $(u_i,v_i)$ is in the cut.
$u_i \in T$ and $v_i \in S$. Then edge $(u_i,v_i)$ is in the cut.
$u_i \in S$ and $v_i \in S$. Then edge $(v_i,t)$ is in the cut.
$u_i \in T$ and $v_i \in T$. Then edge $(s,u_i)$ is in the cut.

For every pair of $u_i$ and $v_i$ at least one edge adds to the cut. Therefore, minimum cut cost is at least $n$.
To find all the cuts of size exactly $n$, add all the vertices: $u_1,\dotsc,u_n$ to $S$. It is optional to include a vertex $v_{i}$ in the set $S$.  The remaining vertices, i.e.,  $V \setminus S$ belongs to $T$. Any such cut has a capacity $n$. Therefore, it is a min-cut. Since there are $2^n$ choices of including $v_{i}$'s, the total number of min-cuts are $2^n \in 2^{\Theta(|V|)}$. Hence, we get an exponential number of min-cuts.

Note: This is an asymptotically tight bound since the possible number of $(S,T)$ cuts are at most $2^{|V|}$.


You are asking for all paths of length 3 emanating from a given vertex. There are $O(n^3)$ of these, the worst case being a clique. If you want to actually output all of them, then exhaustive search (on the adjacency matrix) is the perfect algorithm, and it is efficient, since there are only $O(n^3)$ paths (or less).


Efficiently find elements which are out of place in an otherwise sorted list

If I'm understanding the problem correctly, you have a list that's supposed to be monotonically increasing (aka sorted), and need to discard any items that break this rule. The trick being, an item that's greater than its predecessor might still be invalid, if its predecessor was invalid.

I'm going to make one additional assumption: the first row is always correct. (Because I don't see any way it could be wrong, and if there is, you can check that by hand in $O(1)$ before running.)

If this is correct, then here's how I would solve it.

define FlagBadItems(timestamps[0..n]):
    last_good = timestamps[0]
    for item in timestamps[1..n]:
        if item < last_good:
            flag item as bad
        else:
            last_good = item

In other words, we keep a variable called last_good which is the last timestamp we know to be correct. Each row is considered bad if it's lower than last_good. If it's bad, last_good remains the same, otherwise, last_good is updated.

This runs in $O(n)$, since there's a single run through the data set, with constant work per iteration. The space complexity is $O(1)$ for overhead plus $O(n)$ for your input list.


Each element in that data path is purely logical, thus in each cycle an element can perform only a single operation.
If you had only one memory element, you would've possibly need to perform two operations in one cycle: (1) read the instruction (2) read/write data. This is impossible with a logic-only (sateless) elements within a single cycle.


What is the real reason that Bubble Sort runs at O(n) in best case?

Understanding how Bubble Sort works is of course really the key here.

The main part for unraveling this is that Bubble Sort goes back to the start if it ever performs a swap. If it never performs a swap, it runs along the array once, comparing each element to the one after it, and thus performing $O(n)$ comparisons.

So both sources are correct. The comparisons are counted in the complexity, you just do more of them (and some other things) if you need to swap stuff.

The reason this doesn't work for something like Selection Sort is that Selection Sort looks for the next element to place at the end of the sorted section in each pass. It doesn't know where that element is, and moreover, it always "moves" something (even if it's a trivial move), and whether you made a trivial move doesn't affect whether you will next time either (whereas in Bubble Sort, if you don't move anything, you know you never will).

You could add a check at the start to see if the array is already sorted of course.

Other sorting algorithms can benefit from similar cases to that in Bubble Sort though; Insertion Sort for example has best case $O(n)$ behaviour as well.


I do not understand why finding the minimum of elements take O(n) time

Sorting the array using comparison-based method takes $\Omega(n \log n)$. So sorting is obviously more expensive than finding minimum in $\mathcal O(n)$.

In fact finding minimum or sorting takes $\Omega(n)$ to at least read the whole array. For finding minimum it is actually $\Theta(n)$.

If it were true that sorting takes $\mathcal O(\log n)$ then you would be right to use sorting instead.


Can anybody suggest some algorithms for computing the edit distance other than Wagner–Fischer algorithm?

The fastest known exact algorithm is due to Masek and Paterson, and runs in time $O(n^2/\log n)$ for two strings of length $n$. Bačkurs and Indyk show that an $O(n^{2-\epsilon})$ algorithm would refute a (somewhat) widely believed conjecture, SETH, and Abboud et al. gave stronger results in this direction.


Pagination of results from different sources merged by a unified scoring function

I think $F$ and its details are irrelevant, an appropriate comparison function that uses $F$ internally turns your problem into a regular sorting one. Then your problem is solved in $O(n)$ using a regular selection problem.

Find the element with rank $pk$ in $O(n)$ using a selection algorithm. Similarly find the element with rank $(p+1)k$. Then do a single linear scan over the array to find all elements that have a value between these two in $O(n)$.


Check if given vertices form a connected subtree in a graph

You can do this in linear time.  You can tell if they're connected by keeping only those vertices and edges between them, and testing if the resulting graph is connected using standard algorithms (e.g., DFS).  You can tell if they're a tree by testing if the resulting graph has any cycles (e.g., using DFS).


Language intersections (set theory) - Understanding better

In your last example, when trying to deduce $L \cap L'$, the trick is to trying to understand which strings in $L$ have even length. You can do this as follows:

$$L = \{a^{2n} b^m a^k | n,m >= 0, k = m \pmod 2\}.$$

We can forgot about the first substring of $a$'s, because they always come in pairs (or there are none. In either case, they contribute an even number of characters. Now consider $\{b^m a^k | m >= 0, k = m \pmod 2\}$. The length of the strings in this set is $m+k$. Since $k = m \pmod 2$, we have $m+k = m + m = 2m = 0 \mod 2$. Therefore, $m+k$ is always even, and so $b^m a^k$ always contributes an even number of characters as well. Since $even + even = even$, every string in $L$ is even. Therefore, $L \cap L' = L$.


When our two-state PDA constructed from CFG is non-deterministic PDA?

Your construction starts with a CFG $G$ in Greibach normal form. So each of the productions of $G$ is of the form $A \to a \alpha$, with $A$ nonterminal, $a$ terminal and $\alpha$ a string of nonterminals. Such a production is then directly translated into a PDA instruction $(q,a,A) \mapsto (q,\alpha)$. "read $a$ from the tape, pop $A$ and push $\alpha$"

In general PDA is deterministic if there is no configuration in which two different instructions can be applied. So, no two instructions in the same state, the same input symbol, and the same top of stack. Looking back at the CFG that means there are no two productions of the form $A \to a \alpha$, $A \to a \alpha' $, with $\alpha\neq \alpha' $.
If there are two such productions, then in configuration $(q,aw,A\gamma)$ - state $q$, string $aw$ to be read, and $A\gamma$ on the stack, the PDA can make to moves, pushing $\alpha$ or $\alpha'$.

This analysis is not complete. There are two additional instructions  $(q,\varepsilon,Z) \mapsto (q,SZ')$ ("on initial stack symbol $Z$ push the axiom of the grammar") and   $(q,\varepsilon,Z') \mapsto (f,Z')$ ("when the stack is empty, derivation has ended, move to final state"). Although these are $\varepsilon$ instructions, they can only be applied when none of the CFG rules is applicable (start and end) so they will not cause nondeterminism.


Filling a 3x3 board with connected tiles

There are only $9^9$ possible ways to fill each cell with one of the 9 tiles.  That's a bit under 400 million possibilities.  So, I suggest a simple approach: enumerate all of them, and for each, check whether or not it meets your conditions.  That should run pretty fast: you should be able to very quickly test a candidate configuration to see if it satisfies your requirements, and then a computer should be able to do that 400 million times pretty rapidly.  Repeatedly doing some tedious task is what computers are really good at.

You could also use backtracking or other more sophisticated methods to reduce the number of configurations you need to examine, but it might not be worthwhile to implement.  You might spend 10 hours programming to save 1 hour of CPU time -- might not be worth it.  I suggest you try the simple, dumb, brute-force search first, before thinking too hard about more sophisticated algorithms.


In the simply-typed lambda calculus, the type of a function must be fully specified, even when it's irrelevant. A trivial example is the identity function: in the lambda calculus, it's $\lambda x.x$; in the simply-typed lambda calculus, there isn't a single identity function but rather a family of identity functions $\lambda x:T. x$ for every type $T$. This means that the simply-typed lambda calculus has no polymorphism. If you think about data structures, more concrete examples come up — you can't write, say, a generic function like list reversal, you have to write it all over again for each type of list elements. You can't even write basic primitives like nil and cons, only typed-indexed primitives $\texttt{nil}_T$ and $\texttt{cons}_T$.

To give a concrete example in the pure lambda-calculus (without constants), natural numbers can be encoded as Church numerals in the untyped lambda calculus:
$$\begin{align}
  0 &= \lambda f. \lambda x. x \\
  1 &= \lambda f. \lambda x. f x \\
  2 &= \lambda f. \lambda x. f (f x) \\
  &\ldots
\end{align}$$
In the simply-typed lambda calculs, there is a separate family of Church numerals for each type:
$$\begin{align}
  0_T &= \lambda f : T\to T. \lambda x : T. x \\
  1_T &= \lambda f : T\to T. \lambda x : T. f x \\
  2_T &= \lambda f : T\to T. \lambda x : T. f (f x) \\
  &\ldots
\end{align}$$
You can't compose Church numerals of different types, which makes it difficult to use the same number for different things.

In the Hindley-Milner type system (which I'm including because it's an important step), polymorphic functions are possible, but with restrictions. Hindley-Milner requires a new syntactic form in addition to variables, application and abstraction: the let binding $\texttt{let } x = M \texttt{ in } N$. If all or part of the type of $M$ is irrelevant then it can be left as a variable, and the variable $x$ has not a type but a type scheme of the form $\forall \alpha_1,\ldots,\alpha_k, T$ where the $\alpha_i$ are type variables and the type expression $T$ can contain these variables. For example, it is possible to define the identity function once and for all:
$$
\texttt{let } \texttt{id} : (\forall \alpha, \alpha\to\alpha) = (\lambda x:\alpha. x) \texttt{ in } \ldots
$$
Similarly one can define Church numerals and (more practically) data structure manipulation (e.g. of lists, arrays, etc.) without having to duplicate the definitions for every type of element.

This form of polymorphism is known as parametric polymorphism; HM does not allow functions to behave differently depending on the types of their arguments. This allows proving properties of programs, such as “a function of type $\forall \alpha, \texttt{list}(\alpha) \to \texttt{int}$ only depends on the length of the list and not on the value of the elements”. This is known as “theorems for free” after the famous paper by Phil Wadler. An example of a practically useful function that cannot be expressed in HM is $\ge : \forall \alpha, \alpha \to \alpha \to \texttt{bool}$ which defines a total order — by parametricity, any such function is consant or non-terminating. More generally, HM cannot express ad hoc polymorphism (also known as generic programming in type theoretist circles, but beware that “generics” means parametric polymorphism in OOP circles).

In System F, functions can be parametrically polymorphic with no restrictions. Any lambda term can have universal quantifiers on types, which removes the distinction between $\lambda$ and $\texttt{let}$. Ad hoc polymorphism is still impossible (parametricity results still hold). System F allows more polymorphism than HM, at the expense of type inference (which is relatively easy for HM, and undecidable in System F).

Above I gave examples of programs that can't be expressed in HM and can't be expressed in System F either. Let me now give examples of programs that can be expressed in System F but not in HM. Simple examples are a bit more subtle. One simple example is the lambda term $\lambda x. x \, x$. What does it take to type it? In order for $\lambda x:T. x\,x$ to be well-typed, $T$ must satisfy the equations $T = T_1 \to T_2$ (for the occurrence of $x$ in function position) and $T_1 = T$ (for the occurrence of $x$ in application position). In Hindley-Milner, this is impossible, because types have a simple tree structure and a type satisfying these equations would have to be infinite. In System F, this term can be typed by breaking the recursion with a type abstraction:
$$
\Delta_F = \lambda x: (\forall \alpha, \alpha\to\alpha). x \, (\forall \alpha, \alpha\to\alpha) \, x
$$
While this may look of theoretical interest only, this is of highly practical interest when generalized to data structures. The term $\Delta$ condenses the wish for a single object to behave in a polymorphic way. System F, unlike HM, can express objects with polymorphic methods.

Besides ad hoc polymorphism, an important class of terms that still cannot be typed in System F is non-terminating functions. While $\Delta = \lambda x. x \, x$ can be typed in System F, the “utmost” non-terminating term $\Delta \Delta$ cannot be typed.

System F expands the simply-typed lambda calculus by adding terms depending on types. Other directions for expansion are types depending on types, and types depending on terms. These three dimensions for expansion are known as the Barendregt cube or lambda cube. (This should actually be a hypercube, but the lambda calculus itself is built on terms depending on terms, and the half of the hypercube that doesn't have terms depending on terms isn't studied often.)

Types depending on types allow generic data structures to be defined. For example, although HM is sufficient to write polymorphic functions on lists, defining a list type operator requires more than a basic Hindley-Milner or System F type system: it requires the ability to parametrize the types of lists by the type of their elements.

Types depending on terms are known as dependent types. Dependent types are very powerful, at the expense of making type checking more difficult and requiring often large annotations. An example of constraint that requires dependent types is tracking array lengths through a type family $\texttt{array} : \mathsf{Type} \to \mathbb{N} \to \mathsf{Type}$, allowing the typing of functions such as
$$
\texttt{concatenate}_T : \forall n:\mathbb{N}, \forall m:\mathbb{N}, \texttt{array}\,T\,n \to \texttt{array}\,T\,m \to \texttt{array}\,T\,(n+m)
$$

The calculus of constructions includes all possible abstractions (terms depending on terms or types, types depending on terms or types). Even in the calculus of constructions, neither ad hoc polymorphism nor non-terminating functions are possible.


Excellent question.  This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag).  Basically, you want to know whether y is reachable from x by following edges in the graph -- that's known as a reachability query.  (And symmetrically, you also want to know whether x is reachable from y -- that's a second reachability query.)  Answering reachability queries efficiently is challenging: there are good algorithms for trees, but dags are harder.

One approach is to do a depth-first search from x and see if y is reachable.  However, in the worst case you might end up traversing the entire graph; the worst-case running time is $O(V+E)$.  That's fine if the graph is small, but might take an uncomfortably long time if the graph is large.  So there's been a lot of work on determining whether or not you can do some preprocessing or precomputation on the graph to make it easier to later answer reachability queries more efficiently than that.  If the graph is static (doesn't change), this is known as the reachability problem in dags; if the graph is also changing, then this is known as the dynamic reachability problem for dags.  These problems have been studied in both the CS theory and the databases communities.

Here are some resources to get you started in learning about the state of the art on this problem:

https://cstheory.stackexchange.com/q/37074/5038
https://cstheory.stackexchange.com/q/25298/5038
https://cstheory.stackexchange.com/q/21503/5038
https://cstheory.stackexchange.com/q/5176/5038
https://cstheory.stackexchange.com/q/18787/5038
https://cstheory.stackexchange.com/q/14343/5038
An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Finally, note that MySQL is a relational database, which is intended for relational data -- i.e., data in a tabular structure.  I believe there are also graph-based databases, intended for data with a graph structure.  I don't know much about that subject, but it's possible they might have built-in support that eases some kinds of queries and computations on graphs.


It's not easy to give a full explanation without knowing your axioms and rules, however, $A \land \neg A$ is a contradiction, and it is by exploiting that, that you can prove whatever you like.
First, let $\top = A \lor \neg A$.
We know that "true or whatever else" must be true.  Since $\top$ is a tautology, then $\top \lor B$ must be true.
But since $A \land \neg A = \neg (A \lor \neg A) = \neg \top$ is assumed to be true we conclude the following:

from $\top \lor B$ and $\neg \top$
$B$

It all hinges on the fact that $A \lor \neg A$ is a tautology and that you assume that the negation of a tautology is true.
So to answer your question "actually how can $A$ and $\neg A$ occur at the same time?" It cannot, unless you have a contradiction.  When you assume a contradiction, you can prove anything.


Understanding On-policy First Visit Monte Carlo Control algorithm

The highlighted line basically says that time $t$ must be the first occurrence of the pair $(S_t, A_t)$ in the complete trajectory from $0$ up to and including $t$. This is why there is "first-visit" in the name of the algorithm; it only runs updates for $(S_t, A_t)$ pairs if $t$ is the first occurrence (first "visit") of a particular state-action pair in a trajectory.

This condition:

Is always trivially satisfied for the pair $(S_0, A_0)$ (it's the beginning of the trajectory, so we can't possible have observed that state-action pair before)
Is satisfied at time $t = 1$ if and only if $(S_1, A_1) \neq (S_0, A_0)$ (so at least one of the state or the action must be different from the preceding ones)
Is satisfied at time $t = 2$ if and only if $(S_2, A_2) \neq (S_1, A_1)$ AND $(S_2, A_2) \neq (S_0, A_0)$.
etc.


Design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$

I suggest a deterministic solution using some basic TM trickery.

First you need to identify the parts. Suppose we tag the 0,1 symbols by replacing them by symbols, e.g. A,B (A~0, B~1) - so that we know what we already "tagged" but keep the data "intact". The TM works in a simple loop: move far left, tag the first untagged element, move to far right, tag first two untagged elements. If at some point the tags from left and the tags from right meet, we have found the end of W prefix. If the tags don't meet well, then the length of the input is not divisible by 3 and the TS says NO. Suppose we used A,B tags on left and C,D tags on right (so we can always find the end of W prefix). We split in the C,D part into WR and W in a similar way.

Suppose that the first part now consist of A,B symbols, the middle of C,D symbols and the last of E,F symbols. The TS now reads the three sections in parallel (while the middle one is read in reverse) and compares them in a simple loop, while rewriting the correct parts with some special # symbol. First, move to the left to find the first non-# symbol (which is either A or B). Remember it (use two sets of states, one corresponding to A and one corresponding to B) and replace the symbol by #. Move right until you reach the end of C,D section (the first symbol E,F or # signifies the end), and check if the previous symbol corresponds to the remembered value (A~C, B~D). If it does not, answer NO. Otherwise replace it by # and move to the first E/F-symbol and again check (A~E,B~F) and replace with #. Repeat until there are no non-# symbols left. Once that happens, the answer is YES.


Does every thread have its main function?

For any reasonable definition of a 'main function', no.
Each thread has to start at some point in the code. For the main thread that is usually called the main function.
Modern programming languages are often designed that when starting a new thread it starts in a given function. You could call that the 'main function' of that thread, but is more commonly called its entry point.
However the entry point of a thread does not have to be at some dedicated function, or even at the start of a function. As a counterexample I would invite you to look at POSIX fork().


Does there exist a finite automaton for the given language?

Your reasoning about comparisons would be correct, if there were infinitely many numbers. But there's only three of them modulo $3$.

The automaton can be constructed directly. You need three states, one for each of the residues: $0$, $1$ and $2$. Then every $a$-transition should correspond to an increment and $b$-transition to a decrement.


NPDA transitions to different states by taking same input and popping same top element of a stack

This is very well possible, the automaton nondeterministically chooses which transition is taken. So it may choose between $\lambda$-transitions and transitions reading input, all with the same symbol on top of the stack.

Sometimes this is written as
$\delta(q_1,a,A)=\{ (q_2,A), (q_3,Z)\}$,
where $\delta$ is considered as a function from $Q\times(\Sigma\cup\{\lambda\})\times\Gamma$ into finite subsets of $Q\times\Gamma^*$.

Alternatively $\delta$ can be seen as a finite relation in $Q\times(\Sigma\cup\{\lambda\})\times\Gamma\times Q\times\Gamma^*$, and we write $(q_1,a,A,q_2,A), (q_1,a,A,q_3,Z)\in\delta$.


Here's a more compact and mathematical description of what is going on.  Let $a$ and $b$ be the input, already reduced modulo $m$, so $a < m$ and $b < m$. (Code-wise, this means after the b %= m line.) We want to calculate $ab \mod m$, which is to say, setting $x=ab$, we want to find $r_x$ such that $x = q_xm + r_x$ for some $q_x$.

The Non-Overflowing Case

In the non-overflowing case, we could just calculate the modulus and be done with it. Instead, the code calculates: $$y = \left\lfloor\frac{x}{m}\right\rfloor = \left\lfloor q_x + \frac{r_x}{m}\right\rfloor = q_x + \left\lfloor\frac{r_x}{m}\right\rfloor = q_x$$
Now $x - ym = q_xm + r_x - q_xm = r_x$. I elided a concern here though. It could be that $x$ doesn't fit in the mantissa of our floating point variable. As long as $m$ fits, though, this will not be a problem as $x = ab < m^2$. We'll end up with $x' = x + e$ where $e$ is some round-off error whose magnitude is less than $m$. We proceed as before: $$y = \left\lfloor\frac{x'}{m}\right\rfloor = \left\lfloor q_x + \frac{r_x+e}{m}\right\rfloor = q_x + \left\lfloor\frac{r_x+e}{m}\right\rfloor$$
In this case, we can't eliminate the $\left\lfloor\frac{r_x+e}{m}\right\rfloor$ because, while $r_x < m$ and $e < m$, it may be the case that $r_x+e > m$ or $r_x+e < 0$, though it will certainly be (strictly) between $-m$ and $2m$, so $\left\lfloor\frac{r_x+e}{m}\right\rfloor$ is either $0$ or $\pm1$. Now $$x - ym = q_x m + r_x - q_x m - \left\lfloor\frac{r_x+e}{m}\right\rfloor m = r_x - \left\lfloor\frac{r_x+e}{m}\right\rfloor m$$
Performing the modulus operation now will get rid of that extra term, however, due to the convention C chooses, (-1)%m = -1. To get a convention where we always return a positive number, we can add $m$ to the result if negative.

The Overflowing Case

Let's assume that we are doing the integer arithmetic mod $N$, e.g. $2^{64}$, and let's assume $ab > N$ which means $m^2 > N > m$.  Now the multiplication is going to wrap. We'll write $x = ab = z + kN$ for an integer $k < m$. That means the computation a*b will give the number $z$. The floating point computation is as before assuming, again, that the $m$ fits in the mantissa (which may require 80-bit extended precision floats for larger $m$). For the modulus, define $z = q_z m + r_z$ and $kN = q_N m + r_N$ so $x = q_z m + q_N m + r_z + r_N$. As before storing $x$ as a floating point variable may produce some round-off error $|e| < m$ so again have $x' = x + e$. If we do the same calculation as before it looks like: $$\begin{align}
z - \left\lfloor\frac{x'}{m}\right\rfloor m
& = q_zm + r_z - q_z m - q_N m - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
& = r_z - q_N m - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
& = r_z + r_N - \left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor m \\
\end{align}$$
I've pulled a rabbit out of the hat here. Here, we're doing addition mod $N$, and mod $N$ $q_N m + r_N = kN = 0$ so $q_N m = -r_N$. As before, we mod by $m$ to get $r_z + r_N = x \mod m$, and, as before, the C convention may lead to this being negative which will need correcting.

There's one potential remaining issue. $\left\lfloor\frac{r_z+r_N+e}{m}\right\rfloor$ could be $2$. This causes no problem unless $2m > N$ in which case you'd get the wrong answer. For $N = 2^{64}$ this means $m > 2^{63}$. (As an aside, if $2m = N$ it causes no issue since we'll end up with $0$.) If we configure the floating point hardware to round down so that $e \leq 0$, this case will not come up. (Though don't forget my restriction that the mantissa can hold $m$!).

Connecting this to most/least significant bits

To specifically address the part that you quoted, consider an integer, $B$, greater than 2 which we'll think of as a base, as in "base $10$".  In the usual $B=10$ case, the number $21$ is represented as $21 = 2B+1$. In a floating point representation we'd write this as $2.1\times B^1$. Now let's say we wanted to multiply two (positive) single base-$B$ digit numbers, the result would require at most two digits, say $cB+d$ where (as required by a [standard] base-$B$ representation) $0 \leq c < B$ and $0\leq d < B$. If we're restricted to only being able to store one base-$B$ digit of the result, there are two obvious choices, either $c$ or $d$.

Choosing $d$ is equivalent to working mod $B$ as $cB + d = d\mod B$, this is what happens with integer arithmetic. (Incidentally, at the assembly level, integer multiplication often does produce both of these digits.)

Floating point arithmetic, on the other hand, effectively corresponds to choosing $c$, but compensating that by incrementing the exponent. In effect, we represent the result as $c.d\times B^1$ but since we can store only one base-$B$ digit, this becomes just $c\times B^1$. (In practice, we'll consider numbers as multi-digit numbers in a small base (i.e. 2), rather than 1- or 2-digit numbers in a large base. This allows us to save some of the higher digits of $d$ if they aren't needed to store $c$, but in the worst-case scenario all of $d$ is lost. None of $c$ is lost until we start running out of room in the exponent. For the code above, this is not an issue.)

As long as $m$ can be represented faithfully in the floating point format, the expression $\left\lfloor\frac{ab}{m}\right\rfloor$ can be viewed as extracting that upper digit in base-$m$.  You can view the code and math above as the interplay between base-$N$ and base-$m$ representations of a number.

Practicalities

Based on section 5.2.4.2.2 of this draft, the C11 standard appears to only require long double to have a mantissa roughly 33 bits in length. (In particular, it appears to only specify the minimum number of decimal digits that can be faithfully represented.) In practice, most C compilers when targeting general purpose CPUs and particularly x86-family CPUs, will use IEEE754 types. In this case double will effectively have a 53-bit mantissa. x86-family CPUs support an 80-bit format with a mantissa with effectively 64-bits, and several but not all compilers will have long double indicate that when targeting x86. The range of validity of the code depends on these implementation details.


Difference between multimethods and overloading

Overloading is when two or more methods have the same name but different signature (different argument types, different number of arguments). Overloading is resolved statically, depending only on the static types of the arguments. (The interaction of overloading and overriding, in Java, for example, makes the story a little more complicated). Overloading resolves statically to a particular method signature. Then at runtime, dynamic dispatch will select the most appropriate method with that signature.

Multimethods are a collection of methods that have the same name, the same number of arguments, and overlapping type signatures. Whenever a call is made to a multimethod (using the name of the multimethod), all of the methods in the collection is considered as a possible candidate for dispatch. The precise candidate is chosen depending on the runtime types of the arguments – the most specific method is selected. The actual runtime types of all arguments are used to determine which one to run, which differs from traditional single dispatch in Java, where only the first argument (the target) of the method is used to determine which method body is run.


Trouble understanding how to pick constants to prove big theta

For $n \leq 6$,
$$
1/2 - 3/n \le0,
$$
so if you are taking integer value of $n$, put $n = 7$ as it gives $1/14$. This is how he arrived in the conclusion i.e., for $n \geq 7$,
$$
1/2 - 3/n \ge1/14,
$$
because $n$ is in the denominator it will only decrease the value of -ve term, so overall value will increase with $n$, which is the constant $c_1$.


It's a description of how a certain processor is designed, e.g. which commands it understands, how many registers it has, how it handles interrupts, etc. Any program you write (in assembly) or compile (e.g. from C) for a specific ISA can run on any processor that uses that ISA.

To run a program compiled for one ISA on a different ISA, you need an emulator that translates commands and potentially simulates registers, etc.

For example, desktop PCs use the x86 ISA family, which is why you can run Windows, Ubuntu, etc on any x86 processor.

Smartphones and Raspberry Pis have processors with the ARM ISA, which is why you can't run regular x86 Windows on a RaspPi, instead requiring one specially built for ARM.


This is a good question. As you study more, will find that all the Aloha protocol variants are highly inefficient and ambiguous. And yes, slotted Aloha’s central concept seems to suggest that a collision sparks an infinite loop of data collision. Let’s look at the (only) two tenets of the Pure Aloha protocol from UOH, 1971:

If any device has data to send, send it
If a collision occurs, scrap and try again later

Slotted Aloha is just an extension of Pure Aloha that adds one more tenet:
Data must be sent at regular intervals (slots)

The use of regular intervals increases efficiency significantly.

Now, about collisions, observe the following diagram:

Source: Wikimedia

Notice how devices C, F, and H encounter a collision when they all try to send data in the same interval? Device C tries to resend the data right away, device F waits for a few frames and device H has yet to try sending the data again.

When it comes to the Aloha protocols, what does one mean by sending the data “later”? One second from now is later. Three slots is later. Two years is later. That is up to each device to decide.

If later means the same frame for every device, than yes, infinite collision will occur. This is why a quality method must be developed to prevent this behavior. In programming this is called a back-off scheme.

A predictable and efficient back-off scheme will attempt to implement a probable generation of frames (both new frames and repeats from data that collided) that reduces the probability of collision, such as a Poisson Distribution.

Recommend Reading: Poisson Distribution


Calculating the probability of data loss of a RAID 1+0 system

A RAID 1 system with two disks fails if both disks fails. If each disk fails with probability $p$, then this happens with probability $p^2$.

The RAID 1+0 system fails if any of the two RAID 1 component systems fails. Since each of them fails with probability $p^2$, the probability that either fails is $2p^2 - p^4$ (using inclusion-exclusion).

In symbols, let $x_1,x_2,x_3,x_4$ be the failure status of the disks, that is, $x_i$ is true if the $i$th disk failed. The entire system fails if
$$ (x_1 \land x_2) \lor (x_3 \land x_4). $$
The variables $x_1,x_2,x_3,x_4$ are independent $\mathrm{Bernoulli}(p)$ random variables. A short calculation (given above) shows that
$$ \Pr[(x_1 \land x_2) \lor (x_3 \land x_4)] = 2p^2 - p^4. $$

You can solve all similar questions in the same way.


I missed the part where $\omega(e) \neq \omega(e')$ for $e\neq e'$ so please only consider my answer for the general case, i.e. Given a graph $G =(V,E)$ how to check if $G$ admits a unique MST.

The answer is based on the following claim.

Claim. An MST $T$ is unique, if and only if each edge $\{u, v\}$ not in $T$ has greater weight than all edges on the path in $T$ between $u$ and $v$.

Assuming for now that the claim is true, the task turns into checking for each edge $\{u, v\} \in E \setminus E(T)$, if the path in $T$ between $u$ and $v$ contains an edge with weight at least $w$. If this is the case the answer is No. If this is not the case for all edges not in the tree, output Yes.

Now we need an algorithmic approach to solve the previous problem. Naively, We start by building an arbitrary MST, then we can traverse the path for each such pair $u, v$, where $\{u, v\}$ is not in the tree. However, in a dense graph (say the complete graph $K_n$), this algorithm has running time of $\theta((n+e)\log n + n^3) = O(n^3)$ since we have $\Theta(n^2)$ edges not in the tree and the length of the path is linear. In the following we show how to do each check in $O(\log n)$ time instead achieving a better total running time.

The trick is to use LCA (lowest common ancestor), a data structure defined on rooted trees, that answers the following queries efficiently. Given a pair of vertices $u, v$ in the tree, find a vertex $w$ with the lowest height, such that $w$ is an ancestor of $u$ and an ancestor of $v$. Note that $x$ is an ancestor of $y$ if it lays on the path from the root of the tree to $y$. LCA can be built in running time $O(n \log n)$ answering queries can be done in $O(\log n)$. there are also better "theoretical" results using sparse-tables. However, this ones suffices our needs. We also need to tweak the data structure to answer queries of the form (what is the maximum weight of a vertex on the unique path from $u$ to $v$), note that this is doable by keeping more data about the tree while building the data structure. Also note the choice of the root in this case does not matter and you can choose any vertex to be root.

Now assuming a black-box is given (the LCA data structure) that in $O(\log n)$ time for two given vertices $u$ and $v$ finds the maximum weight of an edge on the path from $u$ to $v$ in the tree. We can do the following, for each edge $\{u, v\}$ not in the tree, call the black-box on $u, v$. If the answer is at least the weight of the edge, output No. If the answer is less than the weight for all edges not present in the tree, output Yes. The running time can be found as follows. We need $O((n+m)\log n)$ to build an MST. We need $O(n \log n)$ to build the LCA data structure (including rooting the tree and computing the depth and the parent of each vertex). We need $O(\log n)$ pro query totaling in $O(m \log n)$ for all queries. Hence a total running time of $O((n+m)\log n)$.

Now we still have to prove the claim presented in the beginning, namely that the tree is unique if and only if for each edge $\{u, v\}$ not in the tree, all the edges on the path between $u$ and $v$ in the tree have strictly smaller weight than the edge $\{u, v\}$.

Proof. Let $\omega: E \rightarrow R$  be the weight function. Assuming there is an edge $\{u, v\}$, such that the path in $T$ between $u$ and $v$ contains and edge $\{x, y\}$ where $w(\{u, v\} \leq w(\{x, y\})$. Then by removing $\{x, y\}$ from the tree adn adding $\{u, v\}$ we get a spanning tree of total weight at least as good as $T$ and hence an MST is not unique. Try to see why the resulting structure is a tree.

For the other direction, we prove the following claim. If there is a simple cycle $C$ where an edge $\{u, v\} \in C$ is heavier than all other edges in the cycle, then there is no $MST$ containing $\{u, v\}$ as an edge. Assuming there is such a tree, by removing $\{u, v\}$ from the tree, we get two connected components. One of the edges in the cycle (say $e'$) must also connect these two components (since cycles are 2-connected) and hence we can  add $e'$ to build a strictly lighter MST, contradicting the claim that the given tree was an MST. Hence $\{u,  v\}$ is not in any MST as claimed. Now complete the original proof, note that the path in the tree from $u$ to $v$ with the edge $\{u, v\}$ build a cycle. Hence, we output Yes if all edges not in the tree are heavy for some cycle and hence cannot appear in any minimum spanning tree.


Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given

It’s not very difficult really, assuming we only care about the cost and don’t have any preferences for drinks.

If we want to make a single order that lasts for n days as cheap as possible, we order the cheapest drink with expiry k, for each 0 <= k < n. That supply costs the cost of the drinks plus d. We can calculate this cost for 1 <= n <= E+1, where E is the longest expiry of any drink.

If we want drinks for N days, we make 1 or more orders to minimise the total cost. We may assume the orders are ordered by size in descending order (and if we find the best sequence of orders with this restriction, we can rearrange it any way we like). Finding the best orders is now a simple dynamic programming problem.

If you are looking for something complicated, it’s not needed.


Does randomness make exponential difference?

It is a common belief that P=BPP. This means that any randomized polynomial time algorithm can be derandomized. The idea of the proof is to use a deterministic pseudorandom number generator to supply the randomized algorithm random bits. Such a pseudorandom number generator exists, for example, if SAT takes exponential time to solve (roughly).

Polynomial identity testing is usually presented as a slightly different kind of problem (or rather as several different kinds of problems), but again the common belief is that one should be able to do it deterministically.

(As common beliefs go, some people disagree.)


How to choose symbols to replace for this left-most derivation?

The term "left-derivation" only pertains to choosing the left-most non-terminal in the sentential form.

It does not force you to choose the left-most rule; that would be silly since the rules are a set, i.e. they are unordered. Also, you couldn't derive that word at all then, now wouldn't you?

Also, keep in mind that there is no "choosing" going on. This is not a parsing algorithm; grammars only give you a declarative definition of languages. There exists a derivation that results in that word, and the one you have is an example.

Note that there are ambiguous grammars, that is grammars that have multiple left-most derivations for some words.

If you are really asking about how to find syntax trees algorithmically, take your pick; there are a lot, and then some.


Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so.

Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating $arctan$, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the universal one), which took as input the description of any machine and simulated it. But what is a "description of a machine"? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?

We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples $0$'s and $1$'s), and then manipulate the string with a Turing machine.

In practice we do not write down sequences of $0$'s and $1$'s when we program. We use another layer of encoding and write "source code" which is translated to $0$'s and $1$'s (the "machine code") by compilers. But in fact early computer scientists did write down $0$'s and $1$'s directly by flipping switches. That was Gödelization in its pure form.

In practice we represent programs and data in a variety of formats known as .java, .py, .mp3, .jpg, etc. In logic and theory of computing people prefer to stick with the good old numbers because they are more easily manipulated within mathematics.

Nowadays everybody knows that "computers do everything in terms of $0$'s and $1$'s". This fact has become so familiar that it is hard to appreciate its originality. Many years ago, when no modern computers existed, it was far from obvious that machines, text, music, pictures and movies could all be encoded with numbers, or sequences of $0$'s and $1$'s.


Find similar vector by Locality Sensitive Hashing

Yes.  This is one plausible method, if you want to find pairs of vectors that are very close to each other.  Two vectors that are close in Hamming distance are likely to end up in the same bin at some point.

Suppose two vectors $v,w$ agree in fraction $p$ of their coordinates (where $0\le p \le 1$).  Then, heuristically, if we look at a pair of coordinates, the probability that $v,w$ agree on those coordinates is $p^2$; and if we choose those two coordinates for hashing, then $v,w$ will end up in the same bin.  If you hash each vector $n$ times, choosing a random pair of coordinates each time, then with probability $1-(1-p^2)^n$, there will be at least one time when they show up in the same bin.

For instance, if two vectors agree on half of their coordinates, and if you hash them 10 times, then 94% of the time they will end up in the same bin for at least one of those 10 hashes.

To know how well it will work on your particular application, you may need to try it (or at least work out the parameters of how close vectors will be, when they are close; how many dimensions they have; how many times you will hash them; etc.).


Is there anything lower than the bit level of 1s and 0s?

Digital computers work so that (almost) at any given point in time, any wire carries (roughly) one of two possible voltages, one signifying $0$ and the other signifying $1$. The voltages depend on the convention being used. In this sense, digital computing does work with $0$s and $1$s. However, even digital computers interface with analog devices, such as physical storage and networks. The way that data is encoded in networks can be somewhat different, since several bits can be encoded at once, depending on the encoding.

Let me explain my qualifications in the first sentence above. "Almost" refers to the fact that when wires switch from $0$ to $1$ or vice versa, there will be intermediate voltages. These switches are synchronized across all the wires so that whenever wires are "read", the switch (if any) has already occurred. "Roughly" refers to the fact that the voltages are not exact. There are two small ranges of voltages which correspond to $0$ and $1$. The devices should be able to "read" bits throughout these ranges, but usually "write" them more restrictively.


Books on finite languages and automata theory with examples, problems and solutions

Try this question to get an idea. I think the classical ones at universities are the one from Sipser and Hopcroft's one. For Hopcroft I would really look for the old version if you are mathematically inclined. They removed a lot of proofs in new versions.

For specific examples of problems you'll get solutions here and there over the Internet. It is good not to have a straight look to the solution and having the solution very near can be very tempting at times.

While looking for books to get an idea of what's on them I like this Internet library. Then you can always buy the book on paper or borrow it from your University library.

Hope this helps.

Some books with solutions: (under construction)

Hopcroft's et alii. solutions to their book.

Apparently, Sipser's book contains solutions after each chapter.


There are three main ways I'm aware of that could prove that P$\,\neq\,$NP.

Showing that there is some problem that is in NP but not in P. You're probably familiar with the proof that comparison-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other NP-complete problem can't be solved in time $O(n^c)$ for any constant $c$. Geometric Complexity Theory seeks to use tools from algebraic geometry and group representation theory to prove such lower bounds, by considering the symmetries that problems possess.  Circuit Complexity is another.

Showing that P and NP have different structural properties. For example, P is closed under complementation. If you could show that NP$\,\neq\,$co-NP (i.e., that NP is not closed under complementation), then is must be that P$\,\neq\,$NP. Of course, this is just pushing the problem one level deeper – how would you prove that NP$\,\neq\,$co-NP?
Another possibility is that we know that NP is exactly the class of problems that can be defined in something called existential second-order logic.  If one could show that there's no logic corresponding exactly to P (or if there is a logic but it's different to $\exists\mathrm{SO}$), then P and NP must be different. A related (in fact, equivalent) idea is to show that P doesn't have complete problems under reductions defined by first-order logic, since it's known that NP does have complete problems under these reductions.

Prove that some problem isn't NP-complete.  If P$\,=\,$NP, then every non-trivial problem in NP is NP-complete under polynomial-time many-one reductions ("non-trivial" here means not $\emptyset$ or $\Sigma^*$). So, if you can show that some problem in NP isn't NP-complete, then we must have P$\,\neq\,$NP.


Checking whether all integers appear exactly once

Let $A$ contain $n$ elements. Scan $A$ to determine the maximum value $m$ in $A$. Then, initialize a bit vector $B$ of size $m$ to all zeros. Then scan $A$ and use $B$ for bookkeeping: when you encounter $i$ in $A$, set $B[i]$ to one (if $B[i]$ is already set, return false). In the end, return true if and only if $B$ contains exactly $n$ ones. This algorithm runs in $\Theta(n+m)$ time, or even in $\Theta(n)$ time if we assume $m = O(n)$.

We can also be a little bit more clever with David Richerby's idea. Let us scan $A$ to find its minimum value $s$. Then initialize an array $B$, this time of size $n$, to all zeros. Go through $A$ again, and when you encounter the value $i$ in $A$: if $i - s > n$ or $B[i-s]=1$, return false. Otherwise, set $B[i-s]=1$. Obviously, this algorithm runs in $\Theta(n)$ time (independent of $m$).

In both cases we assume reading the index of an array is done in unit time, and also that arbitrary width arithmetic is performed in unit time.


Creating regular expression with sub sequences of strings

The following regular language should match your specification. I've used a slightly different notation than yours, denoting $(a \cup b)$ as $\{a,b\}$.

$\mathcal{L} = c \cup c \{a,b\} \cup c \{a,b\} \{a,b\} \cup \{a,b\} \cup \{a,b\}\{a,b\} \cup \left( ((\{a,b\}c) \cup c)? (\{a,b\}\{a,b\}c)*\right)$

$?$ denotes repetition  zero or one time, and $*$ repetition zero or more times.

It can be written in a more compact representation as:
$\mathcal{L} = c\{a,b\}\{a,b\} \cup \{a,b\}?c?\{a,b\}? \cup (\{a,b\}?\{a,b\}?c)?(\{a,b\}\{a,b\}c)* $


CharSet is not a subtype of Set<E>, but it is a subtype of Set<Character>.  If you compare the signatures of the contains methods for Set<Character> and CharSet, you'll see that the preconditions are identical.
It might be helpful to imagine that Set is not a type and is not meaningful on its own; you have to instantiate the generic parameter to obtain a type.


Could two decidable languages ever not have a mapping reduction?

If you are talking about reduction in general (not polynomial reduction), then you basically can put all the logic in the reduction function. Suppose $L_1$ and $L_2$ are decidable languages. To reduce $L_1$ to $L_2$ we need a computable function $f$ such that $x\in L_1 \Leftrightarrow f(x)\in L_2$. The function $f$ just works as follows. Given a word $a\in L_2$ and a word $b \notin L_2$:

  $f(x) = \begin{cases} a & \text{if } x \in L_1 \\ b & \text{if } x \notin L_1 \end{cases}$

This function is computable because $L_1$ is decidable by assumption.

However, the above also points you to the exceptions. It assumes that there is a word $a\in L_2$ and a word $b\notin L_2$, and there exactly two languages for which this is not the case. Both of those languages are decidable.


Subintervals during backward search of a BWT

The answer is deceptively simple. After a paired $rank$ query for a character $P[i]$ you can compute the positions of $P[i]$ in the BWT by performing a paired $select$ query with the ranks from the paired $rank$ query. As seen in the image below taken from the linked example in the question, the character at position $i$ in a BWT is the left extension of the suffix at position $i$ in the corresponding suffix array. This means the positions of $P[i]$ in the BWT found by the paired $select$ query are also the subinterval of $P[i+1]$'s interval that lead to $P[i]$'s interval.

In other words, the subinterval can be computed during the paired $rank$ query with a complimentary paired $select$ query as follows
\begin{align}
r_s &= rank(s-1, P[i]) + 1 \\
r_e &= rank(e, P[i]) \\
s^\prime &= C[P[i]] + r_s \\
e^\prime &= C[P[i]] + r_e \\
s^{\prime\prime} &= select(r_s, P[i]) \\
e^{\prime\prime} &= select(r_e, P[i])
\end{align}
where $s^{\prime\prime}$ and $e^{\prime\prime}$ denote the subinterval of $s$ and $e$ that lead to the $P[i]$ interval $s^\prime$ and $e^\prime$. As previously described, $s^{\prime\prime}$ and $e^{\prime\prime}$ are also the positions of $P[i]$ in the BWT.