What is the optimal algorithm for finding all sets of overlapping ranges?

Sort the ranges by their start points. Then your overlapping ranges can be found in $O(k + n)$ where $k$ is the number of overlapping pairs and $n$ is the input size simply by a double loop. In C:

int i, j;
for (i = 0; i < n; ++i) {
    int start = start_points[i];
    for (j = i + 1; j < n && start_points[j] < end_points[i]; ++j) {
        output(i, j);
    }
}


1's complement addition of outer carry to the result

I only understand two's complement

Let's take two 3 bits numbers, X and Y

Complementing the bits is like calculating 111-X

(it is obvious as $\overline {b} = 1-b$, $\sum_{i=0}^n 2^i*(1-b_i) = \sum_{i=0}^n 2^i -  \sum_{i=0}^n 2^i*b_i$...)

The addition becomes 111-X+Y

If you add 1 you get 1000-X+Y. The leftmost carry is discarded.


Decidability of fullness of intersection of a CSL with a regular language

It is well-known that universality of context-free language is undecidable, making all your items undecidable already for context-free languages, so a fortiori for context sensitive languages (the particular case $L_r=\Sigma^*$ is already undecidable in all items).


How to find a path that connects all the dots in the matrix?

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach.

A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a genetic algorithm, ant colony optimization, or some more problem specific heuristic.

[1] Papadimitriou, Christos H., and Umesh V. Vazirani. "On two geometric problems related to the travelling salesman problem." Journal of Algorithms 5.2 (1984): 231-246.


What is the difference between Partition and Division?

I will explain this with an example :
Consider a set $S$ which contains a collections of sets with a constant k such that:
$$ S = \{ \{S_1\}, \{S_2\}, \{S_3\},\{S_4\},..........\{S_k\} \}$$
In Partition of Set S :
Then we can form the set again by
$ S=S_1\cup S_2\cup S_3\cup S_4...........\cup S_k$
$where\ S_i\cap S_j = \phi$
$and\ i\neq j\ and\ i,j\in \mathcal{N} $
In Division of Set S :
We just have this
$ S=S_1\cup S_2\cup S_3\cup S_4...........\cup S_k$


No that's not allowed, since $i$ and $j$ are not fixed.

Here is a solution using pumping lemma:

  The better approach is to apply pumping lemma.
Let $x = a^{n!}b^{(n+1)!}$, where $n$ is the pumping constant. Note that $u = a^i$ and $v=a^j$ for some $i\geq 0$ and $j>0$ plus $i+j\leq n$.

Then we let $k = 1+\frac{n\cdot n!}{j}$. After that, $uv^kw = a^mb^{(n+1)!}$ where $m = n!+(k-1)j = n!+n\cdot n! = (n+1)!$. Contradiction.

Here is another solution using closure result (which is less tricky):

  Suppose $L_2$ is regular. Then $(\Sigma^* - L)\cap a^*b^* = \{w\in\{a, b\}^*|w=a^ib^j, i=j\}$ is regular by closure result. Then it's easy to gain a contradiction by applying pumping lemma to $(\Sigma^* - L)\cap a^*b^*$.


I have n boys and n girls. I need to pair as much of them as possible for a dance in O(nlogn). Reduce this to a standard problem?

Algorithm: Pick girl #i where $P_i$ is as high as possible. Eligible boys are those with $A_j ≥ P_i ≥ B_j$. If there is no eligible boy then she is not matched, otherwise match her with eligible boy #j, where $B_j$ is as large as possible. Then match the remaining boys and girls in an optimal way.

If instead you match her with boy #k or with nobody, then you can just swap boy #j and boy #k, and you get a result either as good as promised.


Brzozowki's algorithm doesn't work for this corner case

I have looked into some other corner cases and have a tentative answer: when we are doing the determinization after reversal, there is a corner case where in the DFA before reversal, some states cannot be reached  by applying any word to the initial state (two possibilities: the initial state cannot go back to itself or we are adding a state as the new initial state, because when we are doing reversal, there are 2 or more final states). In these cases, two sets are considered the same set if the only differences between them are the "unreachable" states before reversal.

I think we can prove that by reversing the proof process in the link cited in the question.


Using analog values with Algebraic Normal Form?

Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement:

  Every function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$ can be represented uniquely as a multilinear polynomial.

Here $\mathbb{Z}_2$ is the field with two elements, and a polynomial is multilinear if all monomials are products of distinct variables (so you can't have $x_i^2$ in a monomial).

The upshot is that the modulo 2 operation is not the most natural way of understanding the computation involved in algebraic normal form; rather, addition is done over the field $\mathbb{Z}_2$. It seems rather unnatural to apply the modulo 2 operation to real numbers in this context.

One generalization of algebraic normal form to real numbers is the Fourier expansion over the Boolean cube:

  Every function from $\{-1,1\}^n$ to $\mathbb{R}$ can be represented uniquely as a multilinear polynomial (with real coefficients).

Here $\mathbb{R}$ is the field of real numbers.

Another generalization is the Hermite expansion in Gaussian space:

  Every function from $\mathbb{R}^n$ to $\mathbb{R}$ can be approximated arbitrarily well by a polynomial (with real coefficients).

Here arbitrarily well means up to $\epsilon$ distance in $L^2$ with respect to Gaussian measure (e.g., see this Wikipedia article).


Deterministic Nonfinite Automaton - Longest Block of Ones

Your guess is definitely on the right track, though you may need one more piece of information. As you have infinite states (of which each input will use some number of them according to a function of the length of the input), you can use (as you observe) the states to encode information that deals with the length of the input.

There are a number of ways to do this (you can use the same variables as the code essentially), but I think it's clearer to be more explicit. Each state can keep track of the following six things:

The starting position of the best run so far.
The ending position of the best run so far.
The length of the best run so far.
The starting position of the current run being counted.
The ending position of the current run being counted.
The length of the current run being counted.

So each state could be labeled something like:

$$q_{maxstart,maxend,maxlength,currentstart,currentend,currentlength}$$

This then solves the transition problem:

A zero in the input ends the current run, and resets to start counting again, but doesn't affect the best run so far
A one in the input increases the end point of the current run (and sets the starting point if the current run length is zero) AND if you happen to be in a state where the current run length is the same as the best run length, it also alters the best run length subscripts (that is, the transition takes you to a state where those change suitably).

There's no branching in either of those, so the process is completely deterministic.

A couple of examples to illustrate:

The start state is easy, it's just $q_{0,0,0,0,0,0}$ with the transitions $\delta(q_{0,0,0,0,0,0},0) = q_{0,0,0,1,1,0}$ and $\delta(q_{0,0,0,0,0,0},1) = q_{0,1,1,0,1,1}$. This uses the case where the current run length is the same as the best, and we see a one, so we update the best start and end to be the same as the current start and end etc.
Now let's try a state where the current run changes, but isn't better than the best. Imagine we're in state $q_{a,b,50,x,y,3}$, then the two transitions will be $\delta(q_{a,b,50,x,y,3},0) = q_{a,b,50,y+1,y+1,0}$ and $\delta(q_{a,b,50,x,y,3},1) = q_{a,b,50,x,y+1,4}$.

This actually pretty much covers all the cases (as there's really not much going on except the abuse of subscripts to count for us).

To boil that down to some rules for putting in the transitions:

$\delta(q_{a,b,n,x,y,m},0) = q_{a,b,n,y+1,y+1,0}$
If $m < n$, $\delta(q_{a,b,n,x,y,m},1) = q_{a,b,n,x,y+1,m+1}$
If $m = n$, $\delta(q_{a,b,n,x,y,n},1) = q_{x,y+1,n+1,x,y+1,n+1}$

You don't need any states where $m > n$, so you don't have to worry about that case (though you can include them and give them a rule like #3 if you want a complete infinite enumeration of all the subscripts.


Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?

A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint).
As an example, suppose you have two NP-complete problems and $A \le_p B$, the reduction blows up the instance size from $n$ to $n^2$, and $B$ admits an algorithm with running time $ 2^\sqrt{n}$. This only induces an algorithm for $A$ with a running time of $2^{\sqrt{n^2}}=2^n$.


How to uniquely encode a vector of non-increasing positive integers

Define $[b_1,\dots,b_n]$ by $b_i = a_i - a_{i-1}$ for $i>1$ and $b_1 = a_1-1$.  Then $[b_1,\dots,b_n]$ is a sequence of non-negative integers.

Pick any unique encoding of such sequences, call it $e^*$, with the property that the output of $e^*([b_1,\dots,b_n])$ is an integer in the range $0..M-1$ for some $M$.

Finally, define an encoding $e$ as follows:

$$e([a_1,\dots,a_n]) = M \times [a_1,\dots,a_n] \cdot [1,2,\dots,n] + e^*([b_1,\dots,b_n])$$

where $[b_1,\dots,b_n]$ is defined as above.  Then the encoding $e$ satisfies both of your conditions.  Encodings are unique (this follows from the uniqueness property of $e^*$).  Also it satisfies the ordering property (this follows since $0 \le e^*(\cdots) < M$).


Can every algorithm's running time be expressed as $\Theta(f(n))$?

The best case running time and the worst case running time on inputs of length $n$ can each be expressed in this way (as can any function of $n$), however, the two measures do not need to coincide. Details follow.

The running time of an algorithm is not a function only of input size $n$ but a function of the input and there are various running time measure that you can define as functions of $n$. You can define $f_A(n)$ as the worst case (=largest) running time over inputs of size $n$ and $g_A(n)$ as the best case (=smallest) running time over inputs of size $n$. Alex's argument is basically that $f_A(n) = \Theta(g_A(n))$ is not true for every algorithm $A$. The big-oh, big-omega and big-theta notations are used to denote the growth rate of a function as its argument goes to infinity - by itself $\Omega()$ doesn't say whether you are talking about worst case running time or best case running time, and neither does $O()$. So for the insertion sort you have:

$f_A(n) = \Theta(n^2)$ because you never need more than $O(n^2)$ steps to finish sorting and for each $n$ there is an input (reverse order) for which the algorithm takes at least $C n^2$ time for some constant $C$.
$g_A(n) = \Theta(n)$ because for each $n$ there is an input (sorted array) for which insertion sort runs in linear time and of course you need at least linear time to read the array.

And of course $f_A(n) = \Theta(f_A(n))$ and $g_A(n) = \Theta(g_A(n))$. However, $f_A$ and $g_A$ need not be monotonically increasing, they can oscillate infinitely often.

If you feel comfortable with all that you might check this discussion too: http://blog.computationalcomplexity.org/2005/01/big-omega.html


What happens if we add denormalized number and normalized number?

The result depends on the difference between the normal and denormal numbers you are adding.
 $1 + [denormal]$ is rounded to $1$.

But if the range difference between your numbers is inferior to $2^{52}$ for doubles, or $2^{23}$ for singles, you will get a real addition. There is nothing special about denormals here : $1 + 2^{-200}$ is rounded to $1$ as well.

To implement a floating point adder (as hardware or software), you shift right the smaller number to equalize the exponents before doing an integer addition to the aligned mantissas. If the range difference is too large, the smaller number is entirely shifted out.


How do you calculate the running time using Big-O notatation?

The while loop is executed $O(\log n)$ times (more precisely, $\Theta(\log n)$ times).

Yes. You account for every statement that is executed.

The line can $m \gets (m+j)/2$ can be executed in time $O(1)$, assuming that arithmetic operations take constant time. The overall time spent in one execution of the wile loop of the function doIt(n) is $O(\log n)$, since the number of its iterations is also $O(\log n)$ (and, more precisely, $\Theta(\log n)$).

This depends on the actual cost model you are using. Assuming that arithmetic operations take constant time, what you are probably thinking of is the number of divisions (resp. multiplications) by $2$ needed for $n$ to drop below (become larger than) some value $x < n$ (resp. $x>n$). If that's the case then the number of iterations is $O(\log n - \log x) \subseteq O(\log n)$ (resp. $O(\log x - \log n) \subseteq O(\log x)$.
Multiplying/dividing by any constant greater than $1$ does not change the asymptotic time complexity (recall that $\log_b a = \frac{\log_2 a}{\log_2 b}$, where $\log_2 b$ is a constant in this scenario).


Computability: Proving a predicate is not recursively enumerable

Show that your predicate is coRE-hard, that is, every coRE predicate reduces to it. If your predicate were RE, then it would follow that RE=coRE, which is known to be false.

The rest of the answer assumes that "comp(p,x) is defined" is the same as "program $p$ halts on input $x$".

In order to show that your predicate is coRE-hard, you need to show that for every coRE predicate $Q$ there is a computable function $f$ such that $Q(z)$ iff $P(f(z))$. A predicate $Q$ is coRE if there is a computable function $q$ such that $Q(z)$ iff for all $x$, $q(z,x)$. Hence we need

  for all $x$, $q(z,x)$ iff for all $x$, $f(z)$ halts on $x$.

You take it from here.

(In fact, your predicate is $\Pi_2$-complete.)


Can Breadth-First Search be Implemented Recursively without Data Structures?

You basically have two choices: "cheating" by embedding a queue in the nodes, and simulating BFS with higher complexity.

Embedded-Queue Cheating

If you look at virtually any description of BFS, e.g., this one on Wikipedia, then you can see that the algorithm adds attributes to nodes. E.g., the Wikipedia version adds to each node the attributes distance and parent.

So, even if you aren't allowed to use some clearly-cut external queue data structure, you can easily embed one using node attributes:

def BFS(G, root):
    for each node in G:
        n.distance = inf
        n.parent = None
        n.next = None

    root.distance = 0
    head = tail = root

    while head is not None:
         current = tail
         tail = tail.next

         for each node adjacent to current:
             if n.distance == inf:
                  n.distance = current.distance + 1
                  n.parent = parent
                  head.next = n
                  head = head.next
                  if tail is None:
                       tail = head

Note that the above code is iterative, but it's trivial to make it recursive.

Higher-Complexity Simulation

It's possible to run BFS recursively without any data structures, but with higher complexity. DFS, as opposed to BFS, uses a stack instead of a queue, and so it can be implemented recursively.

Suppose we modify DFS so that it takes a max_depth parameter:

 MaxDepthDFS(G, s, max_depth)

It should perform DFS until it reaches the first unvisited node at max_depth level, and returns whether it indeed found such a node. Then we could write the following variation of BFS:

 def BFS(G, s):

     depth = 0
     for i = 0, ..., |V|:
         if not DFS(G, s, depth)
             depth += 1

Again, note that the above code is iterative, but it's trivial to make it recursive.

Besides such (cheap) tricks, you cannot run BFS, as it uses a queue, and not a stack. Say, to the contrary, you have a recursive function

BFSVisit(G, s, current, more)

and consider the case where $s$ has $m$ neighbors. Then at the $m$th invocation, more needs to carry $\omega(1)$ information, and thus is already a data structure.


The English language is regular if you consider it as a set of single words. However, English is more than a set of words in a dictionary. English grammar is the non-regular part. Given a paragraph, there is no DFA deciding whether it is a well-written paragraph in the English language. Of course, it can say whether each word is an English word or not, but it can not judge whole paragraphs.


One must be careful about what the closure properties actually state.

If $A,B$ are regular languages, then $AB$ and $A \cup B$ are regular languages as well.

By induction, one can obtain that the concatenation / union of finitely many regular languages $A_1,\ldots,A_n$ is regular.

This however does not extend to infinite unions!

To understand why the extension would be wrong, consider a simpler case, first. Take the class of finite languages: sets containing finitely many words. Clearly this class is closed under union: if $A,B$ are finite languages, then $A\cup B$ is a finite language. However, taking the union of the infinitely many finite languages $\{1\},\{11\},\{111\},\ldots$ one gets an infinite language $\{1,11,111,\ldots\}$.

In the realm of regular languages, we met the same problem. Take any non-regular language $L$: it has to be infinite, since otherwise it would be regular. We can write $L=\{w_1,w_2,\ldots\}$ for some $w_1,w_2,\ldots$. But we also have $L=\{w_1\}\cup\{w_2\}\cup\ldots = \bigcup_{i\geq 1}\{w_i\}$, which is an infinite union of singleton-languages, which are regular. So, any non regular $L$ can be written as an infinite union of regular languages.

We conclude that the union of infinitely many regular languages is not necessarily a regular language.


Hardness of the Minimum Steiner Tree problem on grid

This problem is $NP$-complete as shown by a reduction from Rectilinear Steiner Minimum Tree (RSMT) problem. Consider the Hanan grid: https://en.m.wikipedia.org/wiki/Hanan_grid. Since Planar-3-SAT is strongly NP-complete, we can subdivide every segment of this grid into unit segments to obtain a grid graph.


Need help in a question regarding polynomial oracle reductions

Hint: Since $S_1$ runs in polynomial time, say $O(n^a)$, every input to the oracle has polynomial length $O(n^a)$. If $S_2 \in \mathsf{P}$, say can be decided in polynomial times $O(n^b)$, then we can simulate all the oracle calls in $O(O(n^a)^b)$.


How to show that Language is not Context Free?

There is a pumping lemma for context free languages too.

In you case, if $L$ was context free, then there would be some constant $n_0$ such that all words $a^{n!}$ with $n! \ge n_0$, $a^{n!}$ could be decomposed as:
$$
a^{n!} = a^x a^y  a^v a^w a^z
$$
such that $y+v+w \le n_0$, $y+v \ge 1$, and for all $i \ge 0$:
$$
a^x a^{yi}  a^v a^{wi} a^z \in L.
$$

Calling $\ell = y+w$ and simplifying, the above can be rewritten as:
$
a^{n!} = a^\ell a^{n! - \ell}
$
such that, for all $i \ge 0$, $a^{n!+(i-1)\ell} \in L$.

This cannot be true. To see this pick, e.g., $n=n_0+2$, and $i=0$.
Then $a^{n!+(i-1)\ell} = a^{(n_0+2)!-\ell}$, where
$
(n_0+2)! - \ell \le (n_0+2)! - 1 < (n_0+2)!
$
and
$
(n_0+2)! - \ell \ge (n_0+2)! - n_0 = (n_0+1) \cdot (n_0+1)! - n_0 > (n_0+1)!
$, showing that $n!-\ell \in ((n_0+1)!, (n_0+2)!)$ and hence it cannot be expressed as a factorial.


Showing the the language represented by a set is regular

See DFA for accepting all binary strings of form power of $n$ (not divisible by $n$) i.e. $n^k$ for given $n$.

The proof for $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n$ in binary for some $ n > 0 \}$ is not regular can be easily modified to prove that $L'=\{w \mid w \in \{0,1\}^*, w $ is $3^n - 1$ in binary for some $ n > 0\}$ is not regular.

However in ternary the same language is regular. It is similar to case of $2^n$ and $2^n-1$. So for some bases you might be able to prove these kind of languages regular but for others you may not.


Suppose that the original elements are $a_{ij}^{(1)}$. Their sum is $S^{(1)} = \sum_{ij} a_{ij}^{(1)}$, and the new elements are $a_{ij}^{(2)} = a_{ij}^{(1)} + S^{(1)}$. The new sum is $S^{(2)} = \sum_{ij} a_{ij}^{(1)} + nmS^{(1)} = (1+nm)S^{(1)}$, and the new elements are $a_{ij}^{(3)} = a_{ij}^{(1)} + (2+nm)S^{(1)}$. The new sum is $S^{(3)} = S^{(1)} + nm(2+nm)S^{(1)} = (1+nm)^2S^{(1)}$, and so on.

More generally, you can prove by induction that $S^{(t)} = (1+nm)^{t-1} S^{(1)}$ and $a_{ij}^{(t)} = a_{ij}^{(1)} + \frac{(1+nm)^{t-1}-1}{nm} S^{(1)}$. It remains to find a fast way to calculate expressions such as $S^{(k!)} = (1+nm)^{k!-1} S^{(1)}$ modulo the given prime $p = 10^9 + 7$. You do the rest.


How do you represent LISP as mathematical / logical model?

"Old" programming languages like Fortran, Cobol and LISP arose before serious mathematical theory of programming languages was developed. They inspired the development of such theory, but are full of idiosyncracies and features which from a mathematical point of view can best be described as "warts". However, each of the old languages in essence has a mathematical core. We can extract their cores and see what mathematical models those have.

For LISP the core would be a small subset of Scheme. Let us focus just on the list processing part, and forget about the fact that in LISP and Scheme one can change state with setq and the like.

A small core for LISP could contain the atoms, S-expressions and functions, by which we mean some basic functions, $\lambda$-abstractions, and recursive functions. There are several ways to model this much of LISP, but perhaps the neatest is by domain theory.

Consider the following simplified statement about (a core of) LISP. Every value is

either an atom (a literal),
or a cons,
or a function.

Let us try to express this idea mathematically. We should find a set $D$ of LISP values which

contains the set $A$ of all atoms (whatever they are)
contains $D \times D$ because every cons is a pair of values (car and cdr)
contains $D \to D$ because "functions are data"

We can express this idea as a requirement that
$$A + D \times D + (D \to D) \subseteq D.$$
Unfortunately, this is not possible because $D \to D$ is larger than $D$, unless $D$ contains just one element (but there are many atoms).

However, there is a way out: the set $D \to D$ of functions is larger than $D$ only if we take all functions -- but we only need to consider the computable functions, or some slightly larger set of them. Indeed, as was shown by Dana Scott a long time ago, we should look for a space $D$ (rather than a set) and then take $D \to D$ to be the space of continuous functions (because every computable map is continuous). As it turns out, there are several kinds of "spaces" that we could use, all of which have in common that they capture the idea of information content and information processing. I cannot go into technical details on how this is done, but you can read about domain theory to find out more.

Let us just think about what $D$ must contain. Of course, it contains various atoms, includnig an element corresponding to nil. Then, it contains all finite lists of elements, since a list (x1 ... xn) is just a lot of nested pairs (x1, (x2, ..., (xn, nil)). Next, it contains lot and lots of functions: anything that can be defined by a lambda, and with a bit of care also anything that can be defined by recursion.

In summary, the answer to your question is that the mathematical essence of LISP is a space $D$ which contains the atoms, its own product $D \times D$ and its own function space $D \to D$.

The stuff about logic and propositional connectives, you should forget that on the first round of studying mathematical models of LISP. Maybe come back to it later, and look up something like Curry-Howard correspondence and realizability.


Under what condition is P/poly equal to the class of languages having Turing machines running in polynomial length with polynomial advice?

Since $P/Poly$ talks about circuit families for languages (different circuit $C_n$ for length $n$ inputs), it is natural to talk about an advice which is a function of the input's length alone.
Different advice for each string will make the class too big. For any $L\subseteq \Sigma^*$, your advice for some $x\in\Sigma ^*$ can be 1 if $x\in L$ and 0 otherwise.


In a BOINC project, how are responses checked for accuracy?

Part of the checking that is performed by the BOINC platform to avoid cheating is to send the same work units to different users, and then verify that the results are the same.


Minimum path cover--- Disjointed paths with minimum total number of edges

A Trivial Algorithm

You can compute the lengths of all-pair shortest paths among $\mathcal{V}'$, and solve a minimum perfect matching in a complete graph on $\mathcal{V}'$ where the weight of an edge $(u,v)$ is the length of the shortest path from $u$ to $v$.

A Smarter Algorithm

Consider the connected component containing $\mathcal{V}'$, it must be a tree.

At each step we move the deepest nodes in $\mathcal{V}'$ to their fathers. If two nodes move to the same node, we decide to match them and do not consider them any more in following steps. If more than two nodes move to the same node, repeatedly match arbitrary two of them until no more than one node is left.

This algorithm runs in $O(|\mathcal{E}|)$.


Here's a derivation in your grammar, assuming that your 'e' denotes the empty string:
$$
S\Rightarrow AB\Rightarrow B\Rightarrow bbB\Rightarrow bb
$$
This is clearly not in $L=\{a^nb^{n+1}\mid n>0\}$. There is, however, a non-regular grammar for your language:
$$\begin{align}
S&\rightarrow AB\\
A&\rightarrow aAb\mid ab &\text{generates $a^nb^n$}\\
B&\rightarrow b &\text{generates the $b$ on the right}
\end{align}$$
There is no regular grammar that will generate $L$, since $L$ is not a regular language.

For your last question, "how can a language be regular and infinite?", you appear to be confused by your observation that any finite language is regular. This is true: logically we'd write this as "If a language is finite, then it is regular."

This does not, however, imply the converse: "If a language is regular, then it is finite." To see this, consider the true statement "If a number is a multiple of 6, then it is even". That's certainly true: 42 is a multiple of 6 and is also even. However, the converse, "If a number is even, then it is a multiple of 6" is certainly false sometimes, since 10 is even but not a multiple of 6. In logical notation, we have that the truth of $P\rightarrow Q$ does not guarantee that $Q\rightarrow P$.

The statement "If a language is finite, then it is regular" just says that the set consisting of finite languages are a subset of the set of regular languages, not that the two sets are the same. For example, the language $\{a^n\mid n\ge 0\}$ is regular (since that language is denoted by the regular expression $a^*$ and also generated by the grammar $S\rightarrow aS\mid \epsilon$) but is obviously not finite.


Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?

No, they are not in general - and focusing on the halting problem specifically makes the situation look more complicated than it actually is. The real point is the following:

There are lots of separation results which relativize to all oracles.

There's a slight technical issue here, actually: how exactly should we treat space-based complexity classes in the oracle context? See the bottom of page $5$ here. I'll only talk about time-based classes here to avoid having to think about this.

For example, the classical argument that $\mathsf{P}\subsetneq\mathsf{EXPTIME}$ in fact shows that $$\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$$ for every oracle $A$. In particular, we can take $A$ to be the Halting Problem. Another example of a separation which relativizes to all oracles - including the halting problem - is the time hierarchy theorem.

This topic is treated in chapter $3$ of Arora/Barak:

  "Any result about TMs or complexity classes that uses only Properties I and II above also holds for the set of all TMs with oracle $A$. Such results are called relativizing results.
  All of the results on universal Turing machines and the diagonalizations results in this chapter are of this type."

  (pg. 72; I've replaced their "$O$" with an "$A$" to avoid conflict with your use of "$O$" for the halting problem specifically.)

Of course not everything relativizes - and see in particular Baker-Gill-Solovay - but some things do relativize, and all relativizing separation results yield negative answers to the OP as special cases.

Just for completeness, here's one proof that $\mathsf{P}^A\not=\mathsf{EXPTIME}^A$ for any oracle $A$ goes; unsurprisingly, it's a direct diagonalization. Fix an oracle $A$; we want to show $\mathsf{P}^A\subsetneq\mathsf{EXPTIME}^A$. We'll use an exponential-time machine with oracle $A$ to diagonalize against polytime machines with oracle $A$. Fix appropriate enumerations $(\Phi_i)_{j\in\mathbb{N}}$ and $(p_j)_{j\in\mathbb{N}}$ of oracle machines and polynomials respectively and an appropriate pairing function $\langle\cdot,\cdot\rangle$, and let $$X=\{\langle a,b\rangle: \neg\Phi_a^A(\langle a,b\rangle)[p_b(\lfloor\log (\langle a,b\rangle)\rfloor)]\downarrow=1\}$$ (here "$[s]\downarrow=$" means "halts in $s$ steps and equals"). By construction we have that $X\not\in \mathsf{P}^A$ (suppose $\Phi_a^A$ decided it in time $p_b$ ...); however, the "brute force" calculation of $X$ from $A$ only takes exponential time, so $X\in \mathsf{EXPTIME}^A$.

Note that this is just the usual proof, with an "$A$" superscript added everywhere. The point is that diagonalization is such a "coarse" technique that - when it works at all - it tends to work for all objects like Turing machines. And this includes Turing machines relative to a fixed oracle.


Calculating fractions of accesses from various levels of memory? (L2 - Main)

The order of accesses is L1 → L2 (→ L3) → main memory. The chance of missing is $1 - p$ where $p$ is the hit chance.

In order for an access to hit L2 cache, it must have missed the L1 cache, and hit the L2 cache. So the chance is $(1 - 0.5) \cdot 0.7 = 0.35$.

In order for an access to hit main memory, it must have missed the L1 cache, missed L2 cache and hit main memory. So the chance is $(1 - 0.5)\cdot (1 - 0.7) \cdot 1 = 0.15$.


Hitting Set Problem with non-minimal Greedy Algorithm

The greedy algorithm always finds a minimal set (inclusion-wise). However, it does not necessarily find a minimum one.

So what does minimal and minimum mean, you might ask. Minimal set in a family of sets (say the set of all hitting sets), is a set that is not a superset of any other set in the family. That means, a minimal hitting set is a hitting set where if you exclude any element from it becomes a non-hitting set. On the other hand, a minimum hitting set is a hitting set of the smallest size. Even though a minimum hitting set might not be unique, all minimum hitting sets are minimal but minimal hitting sets do not have to be minimum.

An example, where the greedy algorithm does not yield a minimum hitting set is

$$U = \{1, 2, 3, 4, 5\}\\
\mathcal{F} = \{
\{1, 2, 3\}, \{1, 3, 4\}, \{1, 4, 5\}, \{1, 2, 5\}, \{2, 3\}, \{4, 5\}
\},$$
where $U$ is the universe and $\mathcal{F}$ is the family of sets to be hit. A minimum solution is hence $\{2, 4\}$. Any solution including $1$ is not minimum, since the set must hit $\{2, 3\}$ and $\{4, 5\}$ using at least one element of each resulting in a solution of size at least 3. However, the greedy algorithm includes $1$ in the first step and hence can not yield a minimum solution.


Why is compression ratio using bzip2 for a sequence of "a"s so jumpy?

Suppose a simple compression algorithm that represents a run of a by storing $(\text{header}, \mathtt{\text{"a"}}, n)$, i.e. some fixed header, the string a, and the number of repetitions $n$. This is a run-length encoding. Then the length of the compressed text would be close to $a + \lg n$ bits for some constants $a$. The corresponding compression ratio would be $\dfrac{a + \lg(n)}{n}$. This is roughly the shape of the curve as seen from a distance, if you neglect the local ups and downs. Asymptotically, the compression ratio is $\Theta(\lg(n)^p/n)$ with $p \ge 1$ (I haven't worked it out but I suspect there are other factors at play which make the size of the output superlinear in the length of the input string).

$\lg n$ bits aren't an integer number of bits, let alone bytes: the size of $n$ has to be at a minimum rounded up to an integer number of bytes. This explains a first threshold effect: for this simple compression algorithm, you would observe that the length of the output is $a$ when $n$ is sufficiently small, then $a+1$, then $a+2$, etc. The compression ratio therefore isn't a smooth curve but jumps from $\dfrac{a}{n}$ to $\dfrac{a+1}{n}$, then $\dfrac{a+2}{n}$, etc. This effect is barely visible in the realignment after jumps (but there are other effects at play which make the jumps different).

Since the compression ratio is too close to the inverse ratio of the length for visual observation, here is the data for small length in my implementation (this may be dependent on the version of the bzip2 library, as there are multiple ways to compress some inputs). The first column indicates the number of a's, the second column is the length of the compressed output.

1–3       37
4–99      39
100–115   37
116–258   39
259–354   45
355       43
356       40
357–370   41
371–498   43
499–513   41
514–609   45
610       43
611       41
613–625   42
626–753   44
754–764   42
765       40
766–767   41
768       42
769–864   45
…

Bzip2 is far more complex that a simple run-length encoding. It works in a series of steps, and the first step is a run-length encoding step, but with a fixed size limit. The first step works as follows: if a byte is repeated at least 4 times, then replace the bytes after the 4th by a byte indicating the repeat count of the erased bytes. For example, aaaaaaa is transformed to aaaa\d{3} (where \d{003} is the character with byte value 3); aaaa is transformed to aaaa\d{0}, and so on. Since there are only 256 distinct byte values, only sequences where the byte is repeated up to 259 times can be encoded this way; if there are more, a fresh sequence starts. Furthermore, the reference implementation stops at a repeat count of 252, which encodes a string of 256 bytes.

This step explains the first threshold and the threshold at 258: $\mathtt{a}^n$ compresses to 37 bytes for $1 \le n \le 3$ and to up to 39 bytes for $4 \le n \le 258$. The introduction of the repeat count results in 2 more bytes in the output of the subsequent steps, and that extra byte is able to represent all repeat counts up to 258. After 258 bytes, there is a second RLE string. There is a third one at 514 bytes, a fourth at 769 bytes, and so on. Extra RLE strings after the second one don't cost much if at all because that sequence aaaa\d{252} (assuming that \d{252} is the repeat count, I haven't checked) is itself repeated and therefore compressed by subsequent steps.

Why are the thresholds at 258, 516, 769, (none at 1024), 1279 rather than exact multiples of 256? I suspect it's because the Burrows-Wheeler transform followed by a move-to-front can transform something like aaaa\374aa (output of step 1 for $n=258$) by moving the a's together so that they can be encoded together, but I haven't checked.

The reduction in length at $n=100$ is interesting. For the input $\mathtt{a}^{101}$, the first RLE step produces aaaa\d{97} — but the byte value of a is 97, so this is aaaaa which has better potential for compression by subsequent steps. I suspect that the shrinking effect not only for $n=101$ but also for surrounding values is due to the delta encoding step which makes it easier to store bytes with nearby values. If you change a to A (65), you'll notice that the shorter output happens for $68 \le n \le 83$.

My analysis of this example is far from exhaustive. To understand other effects, you would have to study the other steps of the transformation: I mostly stopped after step 1 of 9. I hope this gives you an idea of why compression ratios get a little choppy and don't vary monotonically. If you really want to figure out every detail, I recommend taking an existing implementation and observing it with a debugger.

For the most part, such minute variations aren't the main focus when designing a compression algorithm: in many common scenarios, such as general-purpose or media compression algorithms, a difference of a few bytes is irrelevant. Compression tries to squeeze out every bit at the local level, and tries to chain transformations in such a way as to gain often while rarely losing and then not by much. There are nonetheless situations such as special-purpose communication protocols designed for low-bandwidth communication where every bit matters. Another situation where exact output length matters is when the compressed text is encrypted: when an adversary can submit part of the text to be compressed and encrypted, variations on the length of the ciphertext can reveal the part of the compressed-and-encrypted text to the adversary; this was recently publicized in the CRIME exploit on HTTPS.


Can someone give a generic definition of any Definite Language in set builder notation?

In set-builder notation, it's just $E\cup \{vw\mid v\in\Sigma^*\text{ and }w\in H\}$.

So, why is this the same thing as "Languages that can be recognized by the last $k$ characters of the string"

One direction is fairly simple. If $L$ can be recognized by looking at the last $k$ characters, then there must be some set $H$ of length-$k$ strings such that, if the last $k$ characters form a string in $H$, you accept the string, and if they form a string not in $H$, you reject. Furthermore, there may be some strings that you accept even though they have fewer than $k$ characters: this set is $E$.

The other direction is a little more complex.  Suppose that $L = E\cup\Sigma^*H$ for some finite $E$ and $H$. We need to show that there is some $k$ and sets $X\subseteq\Sigma^{<k}$ and $Y\subseteq \Sigma^k$ such that $L=X \cup\Sigma^*Y$. Note that this is different from the hypothesis that $L=E\cup\Sigma^*H$ because it's more specific: $E$ and $H$ can be any finite sets of strings, whereas $X$ contains only strings of length less than $k$ and $Y$ contains only strings of length exactly $k$.

The solution is to take $k$ to be whichever is the larger of:

the length of the longest string in $H$;
one plus the length of the longest string in $E$.

(Since both $E$ and $H$ are finite, each has a longest string, or several longest strings of the same length.)

We start by taking $X=E$, which we're allowed to do because every string in $E$ has length strictly less than $k$.  Now, consider some string $h=h_1\dots h_\ell\in H$.  We have $\ell\leq k$ by the choice of $k$.  If $\ell=k$, we're happy: just add $h$ to $Y$.  Now suppose that $\ell<k$. If a string ends with $h$, then either it has length less than $k$ or it has length at least $k$ and its last $k$ characters are $a_1\dots a_{k-\ell}h_1\dots h_\ell$ for some $a_1, \dots, a_{k-\ell}\in\Sigma$. Therefore, we add to $X$ all strings of length less than $k$ that end with $h$, and we add to $Y$ all strings of length exactly $k$ that end with $h$. And we repeat this for every $h\in H$.

I've explained how to construct $X$ and $Y$. I won't write out their formal definitions as sets because those definitions are so full of notation that they're not enlightening.


In the first sum, you know that k ≥ 0. In the second sum, you know k ≥ n/2. Therefore, adding k in the first sum is ≥ adding 0 in the first sum, and adding k in the second sum is ≥ adding n/2 in the second sum.

You can adapt this for example to show that the sum of $k^5$ for 1 ≤ k ≤ n is $O(n^6)$: You have n/2 terms each at least $n^5/32$, for a total of $n^6/64 = O(n^6)$. Or a lower bound for n!, where you have a product including n/2 terms each larger than n/2, so n! > $(n/2)^{n/2}$.


What happens under the hood when the process requests operating system to open a file?

I'll outline a fictional simplified filesystem for you. There are a few more details, but they are not needed to understand what's going on.

The operating system uses a module called a filesystem.
The filesystem is software that knows how the disk is organized.
It talks to the disk-driver which is software that tells the disk to read of write a particular sector on the disk.

The top down structure goes like this:

string s = ReadTextFileIntoString('c:\documents\test.txt');

//Translates to the following calls.
  Disk = GotoDisk('c:');
  //The root directory is always at sector 512.
  Dir = Disk.ReadDirectoryFromDisk(512);
  Sector = Dir.SearchForFileName('documents');
  if (Sector = -1) then StopWithError;
  Dir2 = Disk.ReadDirectoryFromDisk(Sector);
  Sector = Dir2.SearchForFileName('test.txt');
  if Sector = -1 then StopWithError;
  File = Disk.GetFile(Sector);
  s = File.ReadToString;  /see above.

A disk is made up of sectors, The first sector is 0 and the last is sector how ever many sectors there are on the disk. Say 1.999.999.999 for a 1 terabyte disk. Every sector is 512 bytes large. There are no missing numbers or gaps.
The very first sector, sector 0 holds the master boot record. Which is a small program in 512 bytes that starts up the operating system.
This tiny program knows how to read a sector from the disk and little else.

The disk driver is software that knows how to read and write a sector. That's it.
It has two methods.

ReadSector(sectornumber: integer, Buffer: 512bytes);
WriteSector(sectornumber: integer, Buffer: 512bytes);

Above the disk driver sits the filesystem,

It knows about:

Directories
File Allocation Table - FAT

A directory is a text file with the following structure:

filename1.1024.characters filesize starting-sector DirectoryYN
filename2....

As you can see we know where a file starts. The directory tells us.
But a sector is only 512 bytes. How do we know where the rest of the file is?
Files on disks are not continuous so if the first sector is 5 the rest of the file need not be on sectors 6,7,8 etc. In fact they can be anywhere at all.
To solve this problem there is the FAT The File allocation table.
This is structure to tell which sectors belong to a file.

It looks like this:

0 2 3 3 8 10 -1 -1 -1 -1

Every entry corresponds to a sector.
The 1 first entry is sector 0 (we start counting at 0 in computing).
The second entry is sector 1 etc.
Inside the entry is a reference to the next sector.
If a file has no next sector the entry references itself.
The first entry (in our fictional example) is the boot sector, which is a file 512 bytes long. It has no next sector, so the next sector is itself: 0.
The second entry is the FAT itself. It is a little larger, so it starts at sector 1->2->3->3 the entry for sector 3 points to itself, so there the file ends.
This is how the filesystem knows how to locate a file.
It knows where the file starts and it uses a little table to see where the different sectors after the first are located.

For those sectors that are empty it works the same way, but negative numbers are used. All the writer has to do is locate negative numbers in the file allocation table and write data into those sectors, then update the relevant entries in the FAT and the file is stored.
Note that there are two pieces of information stored a single entry in the table.
The first the the number of the entry, this corresponds with the sector, second it the data inside that entry, this corresponds with where the next sector in the chain is, or whether that sector is free.

An entry in the directory can be another directory (which is really a text file) or a normal file.
The filesystem will load one directory at a time, until it finds the entry for the file, then it will do whatever is requested (read, write, delete).


What is this approximation/error-reduction method called?

There is a high risk that you are "overfitting": you are fitting to noise, not to signal.  If that's indeed what is happening, your method won't actually be useful.

The way to find out whether your method is actually making any real improvements (or whether you're just fooling yourself) is to have a holdout set: a separate set of signals, that you haven't used during the error correction.  In other words, you have a training set (one set of signals) and a test set (a separate list of signals, with no overlap with the training set).  You do all of the correction, corrections to the corrections, etc., on the training set.  Then, once you've done that, you measure how effective your resulting corrected algorithm is on the test set.  This will give you a sense of how effective your approach is.


How do you solve a recurrence relation with multiple subproblems of different sizes?

You can find an upper bound like this:
$T(n)\leq 3T(n/2)+n$.

Solving using master theorem,
$T(n)=O(n^{log_23})$


As others have noted, books about (advanced) algorithms are best selected by topic. A good but heavy-weight general reference with rigorous analysis is probably The Art of Computer Programming by Knuth.

As for analysis techniques, you may be interested in An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, and Algorithmic Combinatorics by Flajolet and Sedgewick for more theory in the same direction.

For approaches on tackling hard problems, see Algorithmics for Hard Problems by Hromkovič.


Algorithm to split bipartite graph into subgraphs

It smells like it might be NP-hard.

One plausible approach is to use a SAT solver or ILP solver.  Suppose you decide you want to have at most $m$ subgraphs.  Then you can have boolean variables $x_{i,k},y_{j,k}$ indicating that customer $i$ goes into subgraph $k$ and service $j$ goes into subgraph $k$.  You can obtain a bunch of constraints (clauses) based on your requirements and then ask the SAT solver or ILP solver to find a feasible solution.  The worst-case running time is exponential.  This might or might not work well enough in your situation.


Your code is correct if the key of one node is never equal to the key of a different node.

Otherwise, you code fails to return the correct inorder-successor of the node at the bottom of the following graph.


In order to get valid paths in the free space from paths in the graph $G=(V,E)$ that is constructed via the trapezoidal decomposition, we require that all edges of $G$ lie inside the free space.
The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly smaller square with the same center as the obstacle. So, using only the nodes at the center of the trapezoid is not sufficient to find paths in the free space.
On the other hand, any segment between a pair of nodes centered at a vertical boundary of the same trapezoid is fully inside the free space, since trapezoids are convex. So, the graph $G'=(V',E')$ with as vertices the centers of the vertical boundaries with an edge between every pair of vertices that lies on the boundary of the same trapezoid lies fully within the free space.

So, why bother using the graph $G$ and not $G'$? One issue with $G'$ is that a trapezoid with $d$ adjacent trapezoids means $G'$ has the complete graph on $d$ nodes as a subgraph, which has $\Theta(d^2)$ edges. So in the worst case, finding a path in $G'$ takes at least $\Omega(n^2)$ time, where $n$ is the number of  in the decomposition. On the other hand, $G$ has at most $2$ edges for each vertical trapezoid boundary, so at most two per vertex of the obstacle boundary, which means it has $O(n)$ edges and we can find shortest paths in $O(n\log n)$ using Dijkstra.


Name of an Exact Cover by 3 sets variant

Gonzalez called this variant RXC3, for "Restricted Exact Cover by Three Sets."


Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$

Halting problem is generally unsolvable. The states don't have to repeat. But if you know that they will, see cycle detection.


Sorting a stack of cards with help of a computer

Setup an array of initially empty file folders (even better buy a mail sorter and you are in the pigeonhole sort case).
The computer, knowing the initial order of the cards, will tell you, one by one, where to put each card (you have a limited number of folders so instructions like "take the current card and place it on top / bottom of folder 3" are quite easy to follow).
Manually sort each non empty folder using insertion-sort.
Visit the folders in order and put all cards back onto the table.

(repeat n times and you're ready for the parcel delivery office, almost... a railway post clerk was required to sort 600 pieces of mail in an hour with 97% accuracy in order to keep his job :-)


What techniques could be used to support thread-local contexts and resources in a language?

One example of a language system built from bottom up to support this kind of situation is Erlang. It is well worth looking into.

It is built around the concept that you create a lot of tasks. The tasks never share variables and only communicates via messages. The task has a "thread-local" context which is maintained using a very specific construct of tail-recursion. It is not uncommon to have thousands or even millions of task in a Erlang system.

Erlang comes with a set of constructs and tools known as OTP which helps in handling a number of common situation in soft real time systems. I especially like how it allows you to update the programs in a running system on the fly.


The Post correspondence problem is undecidable, and in particular it is not in NP. The reason that your idea doesn't work is that the witness is not necessarily of polynomial size (in fact, you just proved it). That is, for your certifier to prove that the Post correspondence problem is in NP, it needs to run in polynomial time (in terms of the size of the PCP instance). It turns out that in this case there isn't always a polynomial size solution even when the problem is solvable. In fact, there is no computable bound on the size of a potential solution, since otherwise the problem would be decidable!


Is the image of a function the codomain of a function?

The image is the subset of the co-domain that the domain actually maps to. Take for instance the following function $$f: \mathbb{N} \rightarrow \mathbb{N}, \quad f(x) = 5.$$

It is simply the constant function that always "returns" 5, no matter what natural number is "passed in." The domain/co-domain defining $f$ is fine, but observe that the only value in the co-domain ever "used" is 5. In this case, the image of $f$ would just be the set $\{5\}.$

"The image of $S$ under $f$" is an explicit reference to the image of $f$ given $S$. That is to say, it is whatever each element in $S$ maps to as defined by $f$.


Why a separate ALU is needed, since any integer can be represented as floating point numbers?

Any 64 bit integer can be represented as an 80 bit IEEE 754 extended precision floating point numbers. Many processors (PowerPC and POWER, ARM) don't support extended precision floating point, so there is your first argument gone. They can't represent every integer number as a floating point number.

Most operations on integers can be done very cheaply with integers represented in an integer format, but are much more expensive if you try to implement them with numbers in a floating point format. That will reduce your clock speed and at the same time raise energy consumption, costing you battery life on any portable device.


Is set of all regular languages on a specific alphabet a regular language?

The language of regular expressions is context-free, but not regular.  It is given by the following grammar:

$$E ::= 0 | 1 | (E)^* | E E | (E|E)$$

Because of the parenthesis matching effect, it's not regular -- the language of matched parentheses is not regular.


I'm not sure why the answer of Karolis doesn't satisfy you. Let me chew it a bit more for you.
First, let's recall what the pumping lemma says (taken form the credible source of Wikipedia):

  If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as

  s = uvxyz

  with substrings u, v, x, y and z, such that

  |vxy| ≤ p,
  |vy| ≥ 1, and
  uv$^n$xy$^n$z is in L for all n ≥ 0.

Ok, so you say $L=\{a^nb^n \mid n \ge 0\}$ is CF, and thus we can run the Lemma on it.
Great. Here I'll show you that the lemma works for it. Say the pumping length is $p\ge2$.$^3$

The lemma says, that for any long enough $s$ string in $L$ (let's take $s=a^mb^m$ with $m\ge p$ as you suggest) we can write it as $uvxyz$ that satisfies some conditions.$^1$

Ok, let's give a try.
Let's  set $u=a^{m-1}$,  $vxy=ab$, $z=b^{m-1}$.

Sanity check: indeed, $uvxyz$ gives $s$. I don't know yet how to split the middle part into $vxy$, but see that condition (1) is satisfied, $|vxy|= 2 \le p$. Now for condition (2), i'll have to get the $vxy$ thing. Let's take $x=\epsilon$, thus $v=a$ and $y=b$. Do we satisfy condition (2)? Yes! $|vy|=2\ge1$. Yey.

Now, it says that no matter what $n$ I take, $uv^nxy^nz$ needs to be a word in the language $L$.
Let's see. By the way we picked the substrings,
$$ uv^nxy^nz = a^{m-1}a^n\epsilon b^{n}b^{m-1}$$
indeed! for any $n\ge 0$ we pick the word we get is $a^{m+n-1}b^{m+n-1}\in L$.

To conclude, we were able to take any word in $L$, and write it as $uvxyz$ so that the conditions of the lemma hold. This can be done for any language which is context-free (and for some that are not, as well) and we just saw how to do it for $L$.

more questions?

$^{1)}$ This should be emphasized: any word can be written in some way uvxyz etc. It doesn't mean that ALL the possible $uvxyz$ will work. Only one of them needs to work in order to satisfy the lemma.
$^{2)}$ when you want to prove that a language is not CF, then all the ways $uvxyz$ must be checked. This is because when you negate the lemma, the word "There exists ... that satisfies (1), (2), (3)" negates to "does not exist ... that satisfy" == "for all ... the condition is not satisfied". So to prove $L$ is not-CFG you need to check all possible ways. To show the lemma is satisfies for a CF $L$, you only need to find one.
$^{3)}$ What if $p=1$? Well, it is not. The lemma says that there exists some $p$. It doesn't say what this $p$ is. For our $L$, any $p \ge 2$ works, but $p=1$ doesn't. We need just one such $p$ (i.e., there exists), so taking $p=2$ is enough.


Regularity of language of words containing a square

Slightly more formally, for an alphabet $\Sigma$, the language of repetitive strings over $\Sigma$ is defined as follows.
$$ RR = \{w: w=uyyv \text{ for some }u, y, v \in \Sigma^*, y \text{ is not empty}\}$$ The question is, is RR a regular language?

There are three cases.

$\Sigma$ has one symbol.
WLOG, let $\Sigma=\{a\}$. Then $RR = aaa^*$ is a regular language.
$\Sigma$ has two symbols.
WLOG, let $\Sigma=\{a, b\}$. Suppose $w\in RR$ does not contain $aa$ or $bb$. That is, if an $a$ in $w$ is followed by another symbol, that symbol must be $b$; if a $b$ in $w$ is followed by another symbol, that symbol must be $a$. That means, if $w$ starts with $a$, it must contain $abab$; otherwise, it must contain $baba$. So any string in $RR$ must have one of $aa, bb, abab$ and $baba$ as its substring. Obviously, any string  that contain one of those four strings is a repetitive string. So we can write $RR = (a+b)^\ast(aa+bb+abab+baba)(a+b)^\ast$ as a regular expression. Hence, $RR$ is regular.
$\Sigma$ has 3 or more symbols. This is the most interesting case.
WLOG, let $\Sigma\supseteq\{a,b,c\}$. We know there is an infinite sequence $u$ of $a,b,c$'s that has no consecutive repeated substring. Let $u_k$ be the first $k$ symbols in $u$. For example, if $u=abcabacabcb\cdots$, then $u_1=a, u_2=ab, \cdots, u_6=abcaba, \cdots$.
Let $i<j$ be two positive integers. Then $u_j=u_iv$ for some non-empty string $v\in\Sigma^*$. Since $u_iv=u_j\notin RR$ and $u_jv=u_ivv\in RR$, $u_i$ and $u_j$ are in different Myhill–Nerode equivalent classes for $RR$. So we have infinitely many Myhill–Nerode equivalent classes that are represented by $u_1, u_2, \cdots$ respectively. According to the Myhill–Nerode theorem, $RR$ cannot be regular.

In the analysis for the last case, we have used one of Alex Thue's results on non-repetitive string over three symbols. He showed that there are many such strings of infinite length. One of them is given by the following procedure. Let $\Sigma = \{a,b,c\}$. Let $A_0 = a$ and $\phi : a \mapsto abcab, b\mapsto acabcb, c\mapsto acbcacb$. So
$$\begin{aligned}
A_0 = a& \\
\phi(A_0)= a&bcab\\
\phi^2(A_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\
\phi^3(A_0)= a&bcab\ acabcb\ acbcacb\ abcab\ acabcb \\
a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\
a&bcab\ acbcacb\ acabcb\ acbcacb\ abcab\ acbcacb\ acabcb\\
a&bcab\ acabcb\ acbcacb\ abcab\ acabcb\\
a&bcab\ acbcacb\ abcab\ acabcb\ acbcacb\ acabcb\\
\cdots\end{aligned}
$$
Note that $A_0$ is a prefix of $\phi(A_0)$. By a very easy mathematical induction, we can show that $\phi^n(A_0)$ is a prefix of $\phi(\phi^{n}(A_0))=\phi^{n+1}(A_0)$. (Thinking about this recurrence relation, I can feel the logic beauty of self reference. That is why I cannot help but writing down this example.) So we can specify a unique infinite string, $\omega$ whose prefix can be $\phi^n(A_0)$ for any $n$. $\omega$ is the wanted string. For a proof that $\omega$ is a string without consecutive repeated substrings, reader can check Axel Thue, Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen; Norske Vid. Skrifter
I Mat.-Nat. Kl.; Christiania; 1912 page 1–67.

In fact, as HendrikJan pointed out, the language of repetitive strings over three or more symbols is not context-free. This fact is proved in Repetitive strings are not context-free by R.Ross and K.Winklmann, RAIRO - Theoretical Informatics and Applications, 16 (1982) 191-199.

Since the complement of a regular language is also a regular language, the complement of the language of repetitive strings is also regular, too. In fact, if the alphabet has one or two symbols, they are finite languages. All non-repetitive strings over $\{a\}$ are $\{\epsilon, a\}$. All non-repetitive strings over $\{a,b\}$ are $\{\epsilon, a, b, ab, ba, aba, bab\}$.

Exercise. Show that an infinite language that does not contain a square is not context-free.

Question. Is the language of almost repetitive strings defined below regular? If no regular, is it context-free?
$$ RR = \{w: w=uyxyv \text{ for some }u, y, v \in \Sigma^*, y \text{ is not empty}, x\in\Sigma\}$$


Figuring out whether LL(1) grammar has an $\varepsilon$-free variant

The solution is to simply start in a slightly different starting state before starting the main recursion:

$$
\begin{array} \\
S & \rightarrow & (EP\\
P & \rightarrow & (EP \\
  & | & \varepsilon \\
E & \rightarrow &iE \\
  & | &sE \\
  & | &nE \\
  & | &(EE \\
  & | &)
\end{array}
$$


Can map-reduce speed up the count-min-sketch algorithm?

yes. section 3.2 from here.

  A key feature of the operations which manipulate the sketch is that
  they are largely oblivious to the current state of the data structure.
  That is, the updates to the sketch do not require inspection of the
  current state. This means that data structure is highly suitable for
  parallelization and distributed computation. Firstly, each row of the
  sketch is updated independently of others, so the sketch can be
  partitioned row-wise among threads on a single machine. But more than
  this, one can build sketches of different subsets of the data (after
  agreeing on the same parameters w, d and set of hash functions to
  use), and these sketches can be combined to give the sketch of the
  union of the data. Sketch combination is straightforward: given sketch
  arrays of size w × d, they are combined by summing them up,
  entry-wise. This implies that sketches can be a useful tool in large
  scale data analysis, within a distributed model such as MapReduce.
  Each machine can build and “emit” a sketch of its local data, and
  these can then be combined at a single machine (i.e. a single reducer
  simply sums up all the sketches, entry-wise) to generate the sketch of
  a potentially huge collection of data. This approach can be
  dramatically more efficient in terms of network communication (and
  hence time and other resources) than the solution of computing exact
  counts for each item, and filtering out the low counts.


How to check if a given point is inside a polygon with holes?

Yes, basically.

That algorithm is called ray casting algorithm, also known as the crossing number algorithm or the even–odd rule algorithm.

Why is it correct? "The algorithm is based on a simple observation that if a point moves along a ray from infinity to the probe point and if it crosses the boundary of a polygon, possibly several times, then it alternately goes from the outside to inside, then from the inside to the outside, etc. As a result, after every two 'border crossings' the moving point goes outside. This observation may be mathematically proved using the Jordan curve theorem." Note this reasoning works in all basic situations, whether the polygon is convex or not and whether the polygon has holes or not.

However, you should be aware of the degenerate cases as well as the case of a hole inside a hole. For an example of degenerate case, consider a degenerated polygon that are two triangles intersecting only on their only common vertex. Then the algorithm may fail when the ray goes through that common vertex. For the case of a hole inside a hole, you have to define the area inside the smaller area is inside the polygon so as to not invalidate the algorithm.

It is actually not easy to make a rigorous statement mathematically about the general situations when the ray casting algorithm works. For this particular question, let me just say the ray casting algorithm will work for a polygon with separate polygon holes inside it where all line segments of the outer polygon and inner polygons do not intersect each other.


Arden's lemma applicability on context free grammars

First of all, let me mention that Arden's lemma applies not only to regular expressions but to any equation among languages of the form $r = sr+t$, where $r,s,t$ are arbitrary languages. The smallest solution to this equation (also known as the least fixed point) is always $r = s^*t$. If $\epsilon \notin s$, then this is in fact the only solution. (Otherwise, $\Sigma^*$ is also a solution.)

The language generated by the rule $S\to aSa|a$ is not $a^*$ but rather $a(aa)^*$: only odd powers are allowed. So it seems that the student notes contain a mistake, though in this particular case the calculation yields the correct conclusion since $\epsilon \in L(A)$.

On the other hand, $S\to aSa|a$ and $S\to aaS|a$ do generate the same language.
More generally, if the only rules involving $S$ are $S \to ASA|A$, then replacing these rules by $S \to AAS|A$ or $S \to A|SAA$ result in the same language, $L(A)(L(A)^2)^*$; and if $\epsilon \in L(A)$, we can further simplify this to $L(S) = L(A)^*$.


Can the higher-order oracle Turing machines simulate the lower-order machines so that the current oracle does not contradict the simulated oracle?

The halting problem $\mathrm{Halt}_O$ for Turing machine with oracle access to $O$ is the language consisting of all oracle Turing machines $M$ that halt on the empty input when the oracle calls are interpreted as membership in $O$. A Turing machine with access to $\mathrm{Halt}_O$ can compute the busy beaver number for oracle Turing machines with oracle access to $O$.

Now to your other question. Let $O_0 := \emptyset$, and $O_{i+1} = \mathrm{Halt}_{O_i}$ (so $O_i = 0^{(i)}$ using the usual terminology). Let us show that given oracle access to $O_{i+1}$ you can simulate oracle access to $O_i$. Consider the following program:

  If $x \in O_i$ then halt, else run an infinite loop.

Using oracle access to $O_{i+1} = \mathrm{Halt}_{O_i}$ you can determine whether this program halts, which happens if and only if $x \in O_i$.

Applying this construction inductively, you can simulate access to $O_i$ given access to $O_j$ for all $j \geq i$. This shows that having an oracle for $O_j$ is indeed stronger than having an oracle for $O_i$ (when $i < j$).


Why integer division is of equal complexity as multiplication

The wikipedia page suggests using Newton-Raphson Division to get  $O(M(n))$.

The way Newton-Raphson Division works is by finding the solution $x$ of $\frac{1}{x}-b=0$ (so that $x=1/b$), and then returning $ax$.

A Newton-Raphson iteration in general is

$$ x_{i+1} = x_i - \frac{f(x_i)}{f'(x_i)}. $$

In this case $f(x)=\frac{1}{x}-b$ and $f'(x)=\frac{-1}{x^2}$, so the iteration works out to

$$ x_{i+1} = x_i(2-bx_i), $$
which takes 2 multiplications per iteration.

Given a good enough starting guess, $x_0$, Newton-Raphson is guaranteed to double the number of accurate bits per iteration, so needs to be run for $O(\log n)$ iterations for $n$ bits of accuracy.

All of the above is for real $x$.  To make it work for integers the trick is to actually calculate $x=\frac{2^n}{b}$ instead of $x=\frac{1}{b}$, which (with a little bit of "normalization") lets you do all the arithmetic with integer multiplies, subtracts, and shifts.

And now how you do it in the same time as multiplication:

Say you want a 1024 bit result, and you have 16 correct bits.

You do one iteration step with 32 bit precision, getting a 32 bit result. Then you do an iteration with 64 bit precision, then 128 bits, then 256 bits, then 512, then 1024.

So the cost isn’t M(n) every time, it’s M(n/64), M(n/32), ..., M(n/2), M(n). Adding up to 2M(n).


A word cannot be regular, only a language can be regular. So it's not clear what you mean by "$ab \in \Sigma^*$ which is regular", and even less what you mean by "$u$ must be regular for all $abu \in A$".

Given a DFA (or an NFA) $M$ for $A$, you can construct an NFA $M'$ for $A'$ as follows. Let $T$ be the set of states in which $M$ finds itself after reading some $ab \in \Sigma^*$ (so $1 \leq |T| \leq |\Sigma|^2$), in symbols $$T = \{ q(\sigma,ab) \mid a,b \in \Sigma \},$$ where $\sigma$ is the starting state of $M$ and $q$ is its transition function. Add to $M$ a new starting state $s$, and connect it to all sets in $T$ using $\epsilon$ productions. Hopefully you can see why the resulting automaton $M'$ accepts $A'$.

Here is a more difficult exercise for you to try. Show that if $A$ is regular then $\{u \mid abu \in A\text{ for a }\textit{unique}\text{ pair }a,b \in \Sigma\}$ is also regular.


CPUs are developed with typical code in mind. For example, indirect function calls are no problem - the destination of such a function call will be predicted, just as we do with branch prediction.

Remember that "hundreds of cycles" are only "tens of nanoseconds". Typically, 3,000 cycles is just one microsecond. So if a programming pattern wastes "hundreds of cycles", that's no big deal and no reason not to use that pattern. "Traversing big collections of subscribers" - there are efficient methods for doing so.


Since graph 2-coloring is in P and it is not the trivial language ($\emptyset$ or $\Sigma^*$), it is NP-complete if and only if P=NP.


Prove the existence of regular $C$ so that: $A \prec C \prec B $

Hint: Note that $B \setminus A$ is regular by closure properties of $\mathsf{REG}$.

   Since $B \setminus A$ is also infinite, you can find an infinite language $D \in \mathsf{REG}$ so that $D \prec B \setminus A$.


Are there any non-naive parallel sparse matrix multiplication algorithms?

This recent paper proposes a different approach, based on hypergraph partitioning.

Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. 2015. Brief Announcement: Hypergraph Partitioning for Parallel Sparse Matrix-Matrix Multiplication. In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures (SPAA '15). ACM, New York, NY, USA, 86-88. DOI=10.1145/2755573.2755613 http://doi.acm.org/10.1145/2755573.2755613


In this example of determinising an NFA, isn't there an edge missing in the result?

The standard definition of DFAs involves a transition function, that is total. That means that, from every state, there should be an arrow for each symbol. So, yes, there is a missing $b$ arrow from $q_4$ to $\emptyset$ and also, missing $a$ and $b$ arrows from $\emptyset$ to itself. While we're at it, the diagram also has no indicated start state.

Note, though, that some authors use the convention that, if there's no transition given for some symbol from some state then, when the automaton reads that symbol in that state, it goes to a "dead" state. The dead state is non-accepting and the automaton cannot leave it (reading any character keeps it in that state).  The author of your book might be using that convention inconsistently: the dead state is $\emptyset$ but they've only shown some of the transitions that lead to it.  I think that's bad style: in my opinion, it's clearest to either show all the transitions to the dead state, or none of them.


To union-by-size two trees, you have to find their roots first. Since union-by-size takes logarithmic time (your first bullet), then first must take logarithmic time as well.

Here is a more formal argument. Say you want to union-by-size two trees $T_1$ and $T_2$. Assume that their heights are logarithmic in their sizes:

$H(T_1)\le \log(n_1)$ and $H(T_2)\le \log(n_2)$

Where $H$ is the height function and $n_1$ (resp. $n_2$) is the number of nodes in tree $T_1$ (resp. tree $T_2$). There are two cases to consider: either one tree has fewer nodes than the other or both trees have the same number of nodes.

Case # 1

Say $n_1\lt n_2$. The resulting tree $T$ has height $H(T)=\max\{H(T_1)+1, H(T_2)\}$

Depending on the max we have:

$H(T)\le \log(n_1) + 1\le \log(2n_1)\le \log(n_1 + n_2)\le \log(n)$ (because $n_1\lt n_2$)

Or,

$H(T)\le \log(n_2)\le \log(n)$

Case # 2

In this case, $H(T)\le \max\{H(T_1),H(T_2)\}+1$.

Again depending on the max we have:

$H(T)\le \log(n_1)+1\le \log(2n_1)\le \log(n_1+n_2)\le \log(n)$ (because $n_1=n_2$) and likewise for the other one.

For the base case choose $n=1$ because $H(T)=0\le \log(1)=0$


Comparison using only bitwise operators (and return -1 or 0)

The first step is to take $c = a \text{ XOR } b$, this will return $0$ if the numbers were equal or some bits set to $1$ otherwise. Now to calculate the result the $c$ variable should be ORed with its circular shifts, to propagate $1$ on the whole variable.

$c = c \text{ OR }  (c \text{ ROL } 1)$
$c = c \text{ OR } (c \text{ ROL } 2)$
$c = c \text{ OR } (c \text{ ROL } 4)$
$\dots$
$c = c \text{ OR } (c \text{ ROL }(W / 2))$.

Using consecutive powers of two gives exactly $\log_2 n$ ROLs needed (credit for Extrarius, it works when you store the partial results back to $c$).


It seems you are trying to perform onion peeling(convex layers) from the inside out, which is not possible.
A convex hull of given points is a polygon that contains all given points either on itself or inside it.
To solve the problem you have described you must generate a convex hull using an algorithm of choice. Now that you have the outer layer, for the inner layer, use the same algorithm and only supply the points inside the convex hull.

The pseudo code would be:
 for given dataset:
   generate a convex hull
   remove the points that make the convex hull from the dataset
   loop until the dataset has no points or more than 2(since a convex hull requires at least 3 points).


Equivalence of two definitions of substitution

The following remark from definition 2.1.15 gives you a clue:

  In the third clause it is not needed to say "provided that $y \not \equiv x$ and $y \not \in \mathsf{FV}(N)$". By the variable convention this is the case.

Since you can't make substitutions, it means that there is some violation of the variable convention (§2.1.13):

  If $M_1, ..., M_n$ occur in a certain mathematical context (e.g. definition, proof), then in these terms all bound variables are chosen to be different from the free variables.

In the meta-level expression

$$((λx.x)\ [ x := y ])\ z,$$

let us denote $M_1 = (λx.x)$ and $M_2 = x$. Notice that $x$ is bound in $M_1$, but free in $M_2$. That violates the variable convention, so you can't use definition 2.1.15, because it relies on that convention.


The idea is to start generating the ones of the first addend from the axiom $S$, while simultaneously adding the corresponding number of ones at the end of the sentential form. Then you have a production from $S$ to non-terminal $A$ which takes care of generating the second added, while still appending ones at the end of the sentential form.

When you are done generating the second addend you can replace $A$ with $=$ in order to split all the ones from the two addends (on the left side) from the corresponding number of ones on the right size.

$$
\begin{align*}
S &\to 1S1 \mid +A \\
A &\to 1A1 \mid \,=
\end{align*}
$$


First, there is one special case of $k$, the powers of 10, which are 1, 10, 100, etc. Their positions at a lexicographically ordered sequence of positive integers are fixed.

1 is always at the 1st position.
10 is always at the 2nd position once it appears. Any number except 1 and itself will be sorted after it.
100 is always at the 3rd position once it appears. Any number except 1, 10 and itself will be sorted after it.
And so on.

We should process this peculiar case first.
The position of $k$ in the lexicographically sorted sequence is determined by the numbers that are before $k$ (lexicographically). These numbers fall into three categories.

the numbers that are smaller than $k$. If a permutation of 1, 2, ..., $n$ contains $k$, it must contain all these numbers as well.
$k$ itself.
the numbers that are bigger than $k$.

Let us compute how many numbers before $k$ are smaller than $k$. For example, take k $=$ 619. Any number smaller than $k$ has at most three digits.

All three-digit numbers before 619 constitute the interval [100, 619).
All two-digit numbers before 619 constitute the interval [10, 61].
All one-digit numbers before 619 constitute the interval [1, 6].

In total, there are 519 + 52 + 6 $=$ 577 numbers that are smaller than 619 and before 619. So if $m\le$ 577 + 1, where 1 stands for 619 itself, no $n$ can satisfy $Q(n,\,$619$)=m$. If $m=$ 578, the minimum $n$ is 619 itself.
Otherwise, the given $m$ is bigger than 1 plus the number of numbers smaller than $k$ and before $k$. We have to include numbers bigger than $k$ that are before $k$ to increase the position of $k$. For the same example, when $m\gt 578$, $n=$ 619 is not enough.

Try adding the number between 1000 inclusive and 6190 exclusive.
If that is not enough, try adding the number between 10000 inclusive and 61900 exclusive.
If that is not enough, try adding the number between 100000 inclusive and 618900 exclusive.
And so on.


How to estimate floating-point precision of function?

Assuming that you're rounding from the thousandths place, the code in your example will always be accurate. Floating point numbers remain useful because they keep their imprecisions quite small relative to the most significant digit.

For instance, using the 8-byte IEEE754 standard (doubles in Java), 10.0/3.0 becomes3.3333333333333335.

You also asked for a rule of thumb to quickly determine whether your math will be accurate. Assuming that you are using the 8-byte standard, you can reasonably guess whether the calculation you are doing will be inaccurate by remembering that inaccuracies begin roughly 15-16 digits beyond the largest digit.  If you're using the 4-byte standard (like you did in your example), you only get about 7-8 digits beyond the largest digit.

With that understanding, you can easily spot places you might run into trouble.  If you're going to use a loop to multiply your number repeatedly, and then check whether the 1s digit is even or odd, you will likely run into inaccuracies.

One slightly surprising way to find trouble is to check simple equality.  Consider the following Java code:

double x = 10.0;
double y = 3.0;
System.out.println( (1*x/(y*1)) == (10*x/(y*10)) );

It ultimately prints false, because it is really testing 3.3333333333333335 == 3.333333333333333. So, for equality testing, you will need to make some decisions about levels of precision, and run some rounding algorithm to obtain that.


How do I show that a DFA accepts only one word?

The case of 1-state DFA

Accepting one word is unrelated to having one state.

If there is only one state, it is necessarily starting and accepting
state, unless there is no accepting state which make the language empty.

An automaton that has only one state which is accepting is necessarily
accepting a language equal to $\Sigma_1^*$ for some subset $\Sigma_1$
of the input alphabet $\Sigma$.

Then the automaton accepts exactly one word if and only if it is the
empty word $\epsilon$, which is the case when $\Sigma_1=\emptyset$

Multi-state DFA

Now, assuming you can have more than one state (I would think that you
did not intend to have such a restriction).

You look at your DFA as a directed graph.

Acceptance of a word is equivalent to finding a path from initial
state to a final state. Since the automaton is deterministic there is
a bijection between such path and the words of the
language. Furthermore, the length of the word is equal to the length
of the path.

Finding one path between the initial state and a final state can be
done simply by tracing, starting with the initial state.
You start with a set $U$ (for untraced) containing only the initial
node, and a set $T$ (for traced once) initially empty.

Then for any state $q$ remaining in $U$, you add all nodes $q'$ with a
transition $q\to q'$ to $U$ unless they are already in $U\cup T$, and
you transfer $q$ from $U$ to $T$. You
terminate when $U$ is empty, and then all nodes in $T$ are reachable from
the initial state. Note that this is the gist of tracing garbage
collection algorithms. The complexity is linear if inclusion of a node
in a set is checkable in constant time (for example by marking the node).

Now, in order to check for multiple paths, you modify a bit the
algorithm, replacing $T$ by two sets $T_1$ (for traced once) and $T_2$
(for traced twice). You proceed as before, with the following changes, that depend on whether $q$ is in $T_1$ or not.

When $q\notin T_1$ ( $q$ was never traced, nor accessed from two paths), consider successively every transition $q\to q'$, making sure you process first a transition $q\to q$ if any exists:

if $q'$ is already in $T_2$, you ignore it
else, if it is in both $U$ and $T_1$, you ignore it
else, if it is in $T_1$, but not in $U$, you add it to $U$ (leaving it
in $T_1$ too).
else, if it is in $U$, but not in $T_1$, you add it to $T_1$ (leaving it
in $U$ too).
else, if $q'$ is in none of the sets, you add it to $U$.

Then you move the node/state $q$ to $T_1$ if it is not already in
$T_1$, or to $T_2$ if it is in $T_1$ (you may remove it from $T_1$ if
convenient for set encoding, but it does not matter). Note that $q$ may already be in $T_1$ if one of the transitions just processed is of the form $q\to q$.
When $q\in T_1$ (there are at least two paths to $q$), consider successively every transition $q\to q'$:

if $q'$ is already in $T_2$, you ignore it
else, put $q'$ in both in both $U$ and $T_1$ (it may be there already)

Then you move the node/state $q$ to $T_2$ (and you may remove it from $T_1$, if you wish).

When you terminate (with $U$ empty), you have at least two paths from
the initial state to a final state if and only if you have an
accepting state in $T_2$, or two accepting states in $T_1$.
You have at least one path if $T_1\cup T_2$ contains an accepting state, and no path it it does not.

So the necessary and sufficient condition for the existence of exactly a single word in the language is that there is a single accepting state in $T_1$ and none in $T_2$.

With proper encoding of the sets, this works in linear time (in the size of the DFA), and can be quite fast.

Note: the conditionals have been written for better readability. They can be better organized for efficiency.


Difference between "information" and "useful information" in algorithmic information theory

The central concept here is Kolmogorov complexity, and more specifically compressibility. To get a intuitive feeling of compressibility, consider two strings $A \in \mathbb{B}^*$ and $B \in \mathbb{B}^*$, where $\mathbb{B} = \{ 0,1 \}$. Let

$A = 1010$ $1010$ $1010$ $1010$, and
$B = 1011$ $0110$ $0111$ $1001$.

Note that $|A| = |B| = 16$. How could we quantify how much information $A$ or $B$ has? If we think about classical information theory, in general, transmitting a string of length $n$ takes $n$ bits on average. However we cannot say how many bits we need to transmit a specific string of length $n$.
Why is the information content of a random string not zero?
On a closer look, we can see that in fact $A = 10^8$. However, it is much harder to say if $B$ has any obvious patterns in its structure, at least it seems and feels more random than $A$. Because we can find a pattern in $A$, we can easily compress $A$ and represent it with less than $16$ bits. Likewise, since it is not easy to detect any patterns in $B$, we cannot compress it as much. Therefore we can say that $B$ has more information than $A$. Moreover, a random string of length $n$ has maximal information since there is no way we can compress it, and hence represent it with less than $n$ bits.
What is useful information, then?
For useful information, yes, there is a definition using a Turing machine $T$. The useful information in $x \in \mathbb{B}^*$ is
$$\min_T \space \{\space l(T) + C(x|T) : T \in \{ T_0, T_1, ... \} \},$$
where $l(T)$ denotes the length of a self-limiting encoding for a Turing machine $T$. The notation is usually such that $C(x)$ denotes the Kolmogorov complexity of $x$ and $C(x|y)$ the conditional Kolmogorov complexity of $x$ given $y$.
Here $T$ embodies the amount of useful information contained in $x$. What we could ask is which such $T$ to select among those that satisfy the requirement. The problem is to separate a shortest program $x^*$ into parts $x^* = pq$ s.t. $p$ represents an appropriate $T$. This is actually the very idea that spawned minimum description length (MDL).


Edge exchange property of two Minimum Spanning Trees

Here is a proof. Let $V$ be the vertices of $G$. $V$ are also the vertices of $T$ and the vertices of $T'$.
If $e$ is deleted from $T$, we will get two trees. Let the vertices of these two trees be $(V_1, V_2)$, which is a cut of $V$.
Since $T'$ is a tree, if we add $e$ to it, we will obtain a cycle. Since that cycle crosses $(V_1, V_2)$ at $e$, it must cross $(V_1, V_2)$ at another edge, say, $e'\in T'$.

Since $T \setminus \{e\}\cup \{e'\}$ is a spanning tree of $G$ and $T$ is an MST,  $\text{weight}(e) \le \text{weight}(e')$.
Since $T' \setminus \{e'\}\cup \{e\}$ is a spanning tree of $G$ and $T'$ is an MST,  $\text{weight}(e') \le \text{weight}(e)$.

So, $\text{weight}(e) = \text{weight}(e')$.
$T \setminus \{e\}\cup \{e'\}$, which is a spanning tree of the same weight as $T$,  must be an MST of $G$. $\quad\checkmark$


Correct term for “string consisting of words”

If definition (1) is intended for any sequence of characters, I would
simply call it string as you suggest, but I would call it word or
lexeme if it is intended to be words of a language.

Regarding definition (2), it depends again on what you are expecting
to consider. If it is any sequence of words, usually meaningless, with
a variety of separators, the name text would do fine, and I would
not worry too much about computational linguistic since the only
meaningless piece of text that matters in CL is "Colorless green ideas
sleep furiously".

If it is actually intended to be a sentence of a language, then you
might call it sentence. I feel that text would rather be used for
larger pieces of discourse. You should be careful though that is is
not confused with sentence meaning a string of words. Speech
processing people may speak of utterance, but it may be
inappropriate for your use. They use also sentence, which they
structure into word lattice when the separators are not clearly
identified, which amounts to a word sequence or word string if they
are clearly identified.

This disctinction may also depend on whether your separators are one or
many, and whether they have a role.

In other words, it is hard to give you a precise answer without more
details on what you are doing. I first tried, and then realized that
it led me to make unwarranted assumptions about what you are doing.

The one thing that is really important is that you are very clear
about your definitions. And if you can motivate your terminology
choices, that may help the reader. I am still wondering why the borogoves had to be so mimsy.


Is there a well-known algorithm for arranging inputs according to their category?

An algorithm can be seen as the steps needed to go from a well defined type of input to some well defined output. The input can therefore be everything that one can represent within a computer.

In the algorithm you are asking for it seems like the input has already been classified as specific good as in apples are already classified as apples, had it not been defined one could use clustering to find out what separates the types of goods from each other depending on the data of each entry of a good in the database.
That means that clustering is a way of data mining.

One way of solving your problem could use sorting like this:

1: def separate_goods(List S):
2:    sort S on the type of good
3:    A := a list
4:    B := a list
5:    current_type := S[0].type
6:    B.add(S[0])
7:    i := 1
8:    while(i < length(S)){
9:       if(current_type == S[i].type):
10:          B.add(S[i])
11:          i := i + 1
12:      else:
13:          A.add(B)
14:          B := a new list
15:          B.add(S[i]
16:          current_type := S[i].type
17:          i := i + 1
18:   }
19:   A.add(B)
19:   return A

The idea behind this algorithm is to first sort the input list such that all the apples are next to each, the oranges are next to each other and so on. From there we can go through the list and put all apples in a list together (the list B), then add that list to A, which simply just stores a list for each type of good.

When we go through the list (in the while loop) and sees that we go from a good of type say apples to another of type orange, then know that we finished collecting apples (since they are all together due to the sorting) and we can therefore add the list B of all the apples to list A. Then we make B contain a new list for all goods of type oranges and continuous through the list adding goods of type oranges until we either have categorized all goods or finds a new type of good.

This is not the most effective algorithm one could make, however it illustrates that sorting can be used to solve this problem.

 I'm not sure if this answers your question however feel free to reach out to me :)  This does not answer your question, here is another try:

Your problem is somewhat simple and can be solved in many ways, a particular fast way would be to use a hash table. Here you could hash each entry on the type of good, with this you can then access a list of all apples by using apple as key. I believe there is a chapter in Cormen et al about hashing that explains how this is done :)


What is a program in self-replicating programs?

The computer's operating system keeps track of which pieces of memory make up which program. The partition into programs is entirely arbitrary, and the only reason a section of memory counts as program is because there is a specially designated piece of memory that keeps a list of all "programs" and their memory locations.


DFA for at most two $b$'s and at least one $a$

Close your eyes. Tell yourself: I am an automaton.

What is my task? Check whether the number of $a$'s is at most $1$ and the number of $b$'s is at least $2$. So I will count $a$'s and $b$'s. My memory holds two numbers, the respective counts. I start with two zero's. When I see $a$ I add one to the first number, when I read $b$ I add one to the second number.

Ah. When the number of $a$'s reaches $2$ I can stop counting them: my test be be always false. When the number of $b$'s equals $2$ I can stop counting them, I have seen enough of them.

Now open your eyes and write down your state diagram: all possible states (=  memory contents) and actions upon reading a letter to another state. Mark the "good" states.

Done.


Heuristics vs meta-heuristics vs hyper-heuristics?

Defining meta-heuristics as "heuristics designed to find, generate, or select a heuristic" seems too broad. A meta-heuristic is commonly understood as an algorithmic template that defines how different low-level heuristic components (e.g. constructive procedures, local searches, solutions recombinations) interact in the search. After instantiating these components for a specific problem, you get a heuristic which searches in the solution space.

Gendreau, Potvin, Handbook of Metaheuristics define them as

  solution methods that orchestrate an interaction between local improvement strategies and higher-level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space

and chapter "Defining the term 'Metaheuristic'" of Zäpfl, Braune, Bögl, Metaheuristic Search Concepts summarizes

  A metaheuristic relies on a high-level strategy which builds upon a particular basic search principle
  The high-level strategy is problem-independent and can be seen as an abstract framework
  The high-level strategy has to properly realize a balance between the two forces intensification and diversification.

Thus, a short answer could be: in a meta-heuristic the designer instantiates low-level heuristics; a hyper-heuristic automates the selection or generation of the low-level heuristics.


Finding total valid strings of length N that could be formed using characters A,B and C which satisfies given criteria

Let $0 \leq i \leq n, 0 \leq c \leq 3, 0 \leq a \leq 2, 0 \leq b \leq 2$, and $DP[i][c][a][b]$, denote the number of good strings of length $i$, but which also have more restrictions:

It should have $\le c$ number of C's
At most $a$ of its ending characters are A
None of the last $b$ characters are B.

The final answer that we are looking for is $DP[n][3][2][0]$. Note that having 2 in the third parameter  adds nothing extra over the restriction that the string already be a good string. Similarly, the fourth parameter being 0 also adds no further restrictions.

To compute $DP[i][c][a][b]$, we look at the possibilities of the last character:

If $c > 0$, then the last character can be C, and the term that would be added is $DP[i-1][c-1][2][\text{max}\{0, b-1\}]$.

If $a > 0$, then the last character can be A, and the term that would be added is $DP[i-1][c][a-1][\text{max}\{0, b-1\}]$.

If $b = 0$, then the last character can be B, and the term that would be added is $DP[i-1][c][2][2]$.

The base case would be $DP[0][c][a][b] = 1$.

This Dynamic Programming can thus be solved in $\mathcal{O}(n)$ time and space.


Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

Dynamic programming is a strategy which avoids explicit enumeration of all possible solutions in the cutting stock problem.
Branch and bound  is a search based technique also based on pruning. However in branch and bound you might in the worst case need to search over all possible solutions.
Column generation is a variant of branch and bound where instead of creating all variables at once they are generated sequentially based on which ones are more "attractive".

In terms of implementation you can implement dynamic programming in any general purpose programming language like C or Java while for column generation  you will need to use specialised linear programming solvers as also for Linear programming based branch and bound.


Does a term being normalizable mean the same as the term has a normal form?

Yes, a term is normalizable if, and only if, it has a normal form.

It is well known that $\omega = (\lambda x . x x) (\lambda x . x x)$ is not typeable, nor is it normalizable. It is not normalizable because it has an evaluation step ($\beta$-reduction) which evaluates it to itself, so we get $\omega \mapsto \omega \mapsto \omega \cdots$.

To see that it is not typeable, observe that already its subexpression $\lambda x . x x$ is not typeable. For if $x$ has type $T$ then in order for $x x$ to have a type, $T$ must be of the form $T \equiv T \to S$ (because $x$ is applied to something, therefore by the typing rules it must have a function type). But there is no type $T$ such that $T \equiv T \to S$, because the type on the right-hand side is larger (as a syntactic expression) than the type on the left-hand side.


Partial order, total order, and version order in transaction histories

for what it concerns Question 1:

there is a theoretical result from 1930 [1] that states that

any partial order $S$ can be extended to a total order $S'$ which contains $S$.

This result is known as the "Order Extension Principle"; the proof of this result
uses the Axiom of Choice (I am not aware whether there is an alternative proof that does not use it). The paper is written in French, but you can find a proof at
https://www.proofwiki.org/wiki/Order-Extension_Principle.

When Adya states that he chooses the real-time order of events, the best guess
is that he assumes an implementation of the database; in this case, every history $H$
corresponds to an execution of the database, where events are totally ordered; such an order is the real-time order.
More specifically, by requiring that the partial order $<$ in a history $H$ is extended by the real-time (total) order, Adya imposes that whenever $e_1  < e_2$ in $H$, then the instant of time $t_1$ at which the event $e_1$ takes place (in the execution of the database that leads to $H$) is less than the instant of time $t_2$ at which $e_2$ takes place.
Choosing the real-time order of events to extend the partial order of a history $H$ is needed if one wants to prove the correctness of an abstract specification (i.e. set of properties that a history has to satisfy) with respect to a given specification.

Let's turn to Question 2:

in this case it seems to me that Adya wants to stress the fact that he allows the implementation of a database to access a version of an object which precedes (in the version order) the latest version installed. In practice, choosing an earlier version of an object could be either the result of the database not being able to access such a version (e.g. the lost update anomaly in causal consistency), or the user explicitly requesting to access an older version of an object (e.g. accessing an older version of a revision in a SVN repository).

Hope this helps,
Andrea Cerone.

[1] Edward Szpilrajn - sur l'extension de l'ordre partiel


Your grammar generates the following language:
$$
L = \{ w0^*1^*0^*1^*\bar{w}^R : w \in \{0,1\}^* \},
$$
where $\bar{w}$ is obtained from $w$ by switching 0s and 1s. Consider now $L' = L \cap 0^*1010101^*$. It is not hard to check that $L$ contains all words of the form $0^n1010101^n$ (take $w = 0^n1$ and $0101 \in 0^*1^*0^*1^*$). Conversely, if $0^n1010101^m \in L'$ and $n \neq m$, say $n > m$, then the decomposition $0^n1010101^m = wx\bar{w}^R$, where $x \in 0^*1^*0^*1^*$, must satisfy that $\bar{w}^R = 1^k$ for some $k \leq m$; but then $x = 0^{n-k}1010101^{m-k} \notin 0^*1^*0^*1^*$. We conclude that
$$
L' := L \cap 0^*1010101^* = \{ 0^n1010101^n : n \geq 0 \}.
$$
It is not hard to check that $L'$ is not regular (for example, the words $0^n$ are pairwise inequivalent), and so $L$ also isn't regular.


Answering your first question, whether you can tighten the analysis depends on the function $T$. If $T$ is constant, for example, then the analysis is tight; if $T$ is a polynomial, then the analysis is not tight, and in fact you can remove the logarithmic factor: the answer is simply $O(T(N))$.

Answering your second question, the best known time complexity for solving linear programming is given in Yin Tat Lee and Aaron Sidford's recent paper, top of page 43:
$$
\tilde{O}\left(\sqrt{\operatorname{rank}(A)}(\operatorname{nnz}(A)+\operatorname{rank}(A)^\omega)L\right).
$$
Here:

$\tilde{O}$ hides logarithmic factors.
$A$ is the constraint matrix.
$\operatorname{rank}(A)$ is the rank of $A$.
$\operatorname{nnz}(A)$ is the number of non-zero entries in $A$.
$\omega$ is the matrix multiplication constant. The best known value currently, due to Le Gall, is $\omega < 2.3728639$, but it is suspected that $\omega = 2$.
$L$ is the bit complexity of the LP, roughly the number of bits in the encoding of the LP (see footnote 2 on page 2 for the exact definition).

The smoothed complexity of the simplex algorithm might be better, but unless your instance is random, smoothed complexity isn't going to help you.


Algorithm for maximizing correspondence between 2 sets

This is known as the assignment problem.  There are polynomial-time algorithms for it.


No, not necessarily.

If $F$ is $(\neg X_1 \lor \neg Y_1) \land \dots \land (\neg X_n \lor \neg Y_n)$, then expressing $\neg F$ in CNF requires exponentially $2^n$ clauses.  See, e.g., https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF, Which CNF boolean formulas blow up exponentially at conversion to DNF?, and Formulas for which any equivalent CNF formula has exponential length.

However, if you allow introducing additional variables, then you can construct a formula $G$ that is equisatisfiable with $\neg F$ and such that $G$ can be represented in CNF with number of variables and clauses polynomial in $n$ and $m$.