An example of something you can formally verify with proofs in Software Development

Look into tools like Frama-C, SPARK, Astrée, etc...
They have their use in very specific cases, notably software verification of small to medium sized embedded safety critical software (e.g. inside aircrafts, per DO-178C, or nuclear power plants, etc...). Such software have a few dozen thousands lines (or perhaps two hundred thousands at most of C or Ada code), but a bug inside them could crash a plane. So the industry is ready (and required by external regulations) to spend a lot of money and efforts on such small critical software. There are also many severe coding rules (e.g. dynamic allocation, recursive functions, dead code are forbidden).
Proving software, even with these tools, is very costly. A typical safety-critical software costs about a hundred or a thousand times more to develop than a usual software (like your phone applet or some Unix command line tool) of equivalent size, because formal methods (but not only them) are involved. The teams developing them should have formal methods experts working together with aircraft software experts. Sometimes, a small routine has to be rewritten and annotated to be processable by code provers.
There are several research projects around such tools and their use. For a recent example look into VESSEDIA (but you could find many others). One of its results might include a simple proof of a small subpart of the Contiki OS. From an outside view, the results are related to simple subsystems of it (e.g. some simply-linked-list module). In practice the proof requires a lot of formal annotations (so the developer has to provide annotations in ACSL about half as long as the simple C code that is specified by these annotations).
The L4 microkernel has also a variant, called seL4, which uses formal methods (the code size which is formally proved is a few dozen thousands of C code). AFAIU that variant (with its proof) is open-source.
But formal methods don't scale well. It is very unlikely that they would scale -in the next 20 or 30 years- (for present-day programming languages and code) to software as big as the Qt toolkit or the Linux kernel (because formally specifying the intended behavior of Qt or of Linux kernel is practically impossible). For example, C heap allocation is easy to code (that is, a lot of C code uses malloc & free), but difficult to formalize and prove (because current shape analysis techniques don't scale well to large programs). That internal complexity and difficult of formal methods hinders its uses in real-world programs (whose size is growing a lot: a source code editor today is much more complex and bigger than what vi was in the 1980s).
I was part of several research grant submissions mixing more or less formal methods and other approaches (e.g. machine learning techniques on large amount of code, natural language processing techniques), but such funding is hard to get (e.g. there is probably no more any H2020 or FP9 calls dedicated to software engineering before my retirement; the last one was ICT-16 to which I was part of a submission -and waiting (in june 2018) for its evaluation; but only a few percents of submitted proposals get funding). See also this answer to another (but indirectly related) question. BTW, I might be interested in joining some European consortia in 2019 for HPC software tooling using such ideas.
To summarize: There is No silver bullet, so I agree with you:

there is no use in Hoare Logic or Operational Semantics in practical software development

(because even if you have proven your code w.r.t. some explicit formal specifications, there could be - and there still is some - "bugs" or incompleteness in the formal specifications; specifying "correctly" what a real-life software such as a word processor or some web application should do is practically impossible, since you want that specification to be "complete" and cover all the practical cases).
However, notice that recent practical programming languages (e.g. Rust, Ocaml, and also monsters like C++20 or C++17 which became so complex that only a dozen of people understands them fully) have been inspired by formal proof techniques. And academic curiosities like Agda uses even more them. Also, static source code analyzers like clang-analyzer (and even some optimization passes of GCC) use techniques related to formal proofs.
Regarding CompCert, you could download its source code (and proof) and study its code, but you are not allowed to use that source code for non-academic purposes (so CompCert is not free software but its source code is downloadable and you are allowed to study and experiment it. However the resulting binary has license restrictions).
See also this draft report (and the references there).


What does the term "Finite" stands for in Finite State Machines?

The number of states is finite in finite state machines (aka regular laguages).

In contrast, in a push-down machine (PDA) the number of states is potentialy infinite (more correctly unbounded, leaving out stack size limitations), but the machine itself does not bound the number of states (that is why a stack is used) (aka context-free languages)

To put it in another way, a finite state machine can store all its needed state (in the general sense, including transition rules, current symbol etc..) only in fixed finite storage, unlike push-down machine (or other automaton) which cannot do that.

A PDA, for example, by its design and definition, does not determine a fixed size needed for all its state (it is unbounded, aka infinite in this respect)

And to clear up the confusion, PDAs (and other automata) may have finite number of transition rules but not finite number of (potential) states (also refered as configurations) (see above).

update

note that a PDA does not necesarily need infinite storage, for example any given PDA can at any given time only need finite storage and even during its whole operation its storage size does not exceed an upper limit. However this is not fixed before-hand by the machine itself (like for FSMs) and thus is formaly unbounded. In fact for PDAs the storage size is determined by the input size itself and is a linear function of the length of the input (which are part of automata refered as LBAs, linear-bounded-automata, in which one end is always fixed, the bottom of the stack)


Partition an infinite regular language into 2 disjoint infinite regular languages

Every regular language is accepted by some minimal DFA. For an infinite regular language $L$, let's call such a DFA $M_L$. Consider any state $q$ which can be visited more than once while processing some string in $L$. If $q$ can be visited more than once, it follows that it can be visited any number of times. Define $$L_1 = \{w \in L \mid q\text{ is visited an odd number of times}\}$$ and $$L_0 = \{w \in L \mid q\text{ is visited an even number of times}\}$$
This is a DFA, so there's only one path. Any string in $L$ is accepted by the DFA, and must visit the state some number of times (maybe zero). The state can be visited an unlimited number of times; therefore, we know that there are infinitely many strings in $L_1$ (since there are words that cause the state to be visited 1 time, 3 times, etc.) and that there are infinitely many strings in $L_0$ (since there are words that cause the state to be visited 0 times, 2 times, etc.). Any given string is either in $L_1$ or $L_0$, and cannot be in both, so $L_0 \cap L_1 = \emptyset$. However, any word in $L$ is guaranteed to be in one of these two sets, so $L_0 \cup L_1 = L$.


Reducing optimization problem to its decision version

Use binary search on the target $A$, finding the maximal value for which an assignment of average compatibility $A$ exists.

I'll let you work out the resulting multiplicative overhead (which depends on the magnitude of the numbers involved).


How center the eyes of human face at specific pixels?

Assuming you can find the centers of the eyes...

Rotate - Find the difference of the angle between the actual eyes and your desired angle. Rotate image accordingly.
Scale - Find the distance between eyes. Scale according to the desired distance.
Translate - Move the image so that one eye lines up. If you've rotated and scaled properly, both should now be in the desired spot.


context free grammar not closed under relative complement using product construction of pda and dfa

If you forget about the product-part of this construction (or just consider $L_2=\Sigma^*$) then your proposal amounts to swapping the accepting states of the pushdown automaton. The new PDA has an accepting state iff the original one did not have one.

This is similar to the construction for deterministic finite state automata.
The problem here is that the original PDA is not deterministic. Thus for a single input there might be two computations, one which accepts and the other that does not accept. With your construction both the original and the new PDA will accept that input.

Moreover there might be inputs that do not have a full computation (the machine "blocks"). With your construction both of the PDA will not accept.

PS. In his comment Raphael observes complementation for nondeterministic automata in general has the same flaw when one swaps accepting and nonaccepting states. Many of his links relate to Turing machines, but perhaps especially look at his own answer where the problem relates to finite automata: "Language described by inverting accepting states of NFA"


Undecidability of the PCP problem with bounded width

If $w$ is bounded, and the alphabet size is bounded, then the number of possible words is bounded. Thus, there is only a finite number of possible instances, so the problem becomes a finite languages, and hence decidable.

If you don't bound the alphabet, then you can encode any width of $w$ by adding more letters, so the problem is the same as standard PCP, and hence undecidable.


Is there a formal way of defining a Zeno Machine?

Hamkins' survey Infinite time Turing machines, linked by Yuval Filmus, formally defines a computational model (Infinite time Turing machine) that meets the requirements of a Zeno machine.
The definition of ITTMs does not use the time based framing; instead it is an extension of classical binary TMs to be defined at transfinite ordinals.  A classical TM has a start status (empty tape, etc.) and a function to get the successive status; a ITTM just adds the status of the machine at limit ordinals.
Rather than taking the limit of the cells in the tape, as suggested and refuted in the question, we take the limit supremum.  Formally for
$$
T(\lambda)_k = \limsup_{n\rightarrow \lambda} T(n)_k
$$
where $\lambda$ is a limit ordinal, $k$ is the index of some cell, and $T$ is the function that gives the tape at some numbered step.
The $\limsup$ ensures that it will always be defined for any sequence (since the alphabet is bounded).  If the normal limit does not converge for some cell then (for a binary alphabet) the cell at time $\lambda$ will be $1$, since in order for it to not converge it must be $1$ at an infinite number of steps.
The state and the location of the read head are resolved much more simply.  Just as there is a start state, there is also a limit state.  At times corresponding to limit ordinals the machine is in the limit state, and the read head is set to the beginning of the tape.

The linked paper does not even mention "Zeno machine" (although it mentions Zeno) and ITTMs may not be the only formal model of a Zeno machine possible (beyond trivial modifications).  However it is a model of computation that allows a Turing machine to perform an infinite number of operations and then continue calculations, so if you are looking for a formal way to talk about Zeno Machines ITTMs work just fine.


Graphs, as usually defined, don't have parallel edges. Graphs with parallel edges are known as multigraphs.

However, like humpty dumpty, we can give a term whatever meaning we want. In some contexts, all graphs are multigraphs, and so the word graph denotes a multigraph. In other contexts, there are graphs and graphs with parallel edges. In yet other contexts, there are graphs and multigraphs. Only you know the conventions in your field.


Global relabeling heuristic: Push-relabel maxflow

Q1: The invariant goes the other way around: height[n1] <= height[n2] + 1 for all edges (n1,n2) in the residual graph.

As the sink (10) is not adjacent from (7) in the residual graph, the configuration height[7] == 14, height[10] == 0 is perfectly fine.

The other way around, (7) is adjacent from (10) in the residual graph, and indeed height[10] <= height[7] + 1.


What does the term "top-most" mean in the context of formal grammars?

In the context of context-free languages, "top-most" refers to the root of a parse tree. Your rules guarantee that a sum of the form $1+1+1$ is parsed as $1+(1+1)$ rather than the opposite, since the nonterminal Ntp ("not top-most") doesn't allow + to be the top-most operator (you should imagine a parse tree in which + labels the root).
Consider the following two parse trees: (generated using Syntax Tree Generator)

On the left, the left child of the root has + as the top-most operator.
On the right, the right child of the root has + as the top-most operator.
Your grammar only allows the second parse tree, since the left child of + must not have + as the top-most operator.


Is the language $0^n 1^n 0^n$ recursive?

Explaining intuitively why this language is recursive is easy: it's almost trivial to write a computer program in a high-level programming language (e.g. Java, C) that decides this language. Since TMs can simulate high-level languages, you get the result.

If you need a concrete TM that decides this language, try the following:

First, erase a 0 and go right until you encounter 1. Replace this 1 with some new symbol $X$.
Go back left, and repeat the process until you are out of 0s on the left.
Then go back right and do the same thing with the $X$s and 0s on the right.

If, at any point, something "unexpected" happens, (e.g. you run out of 1s, or have too many 1s), then reject. Otherwise you will end up with an empty tape, at which point you can accept.


Complexity of GF(2) and applications to cryptography

The (meta) algorithm you're looking for is the Gröbner basis algorithm. In the last decade, the approach that you mention, called algebraic attacks, has gained momentum in the cryptological community. One person who has been developing efficient Gröbner basis algorithms in the context of cryptography is Faugère. He has some links to relevant papers on his web page, including applications.

Since SAT can also be written as a (small) system of polynomial equations, you shouldn't expect a general algorithm to work always, or even on average. The hope is that some systems of polynomial equations are easier. You have to find these "easy" systems in order to apply this method in cryptology.


Difference between Data point, attribute, feature?

An attribute is usually synonymous with feature, both of which refer to a single dimension. A data point probably refers to a complete record. That is, a data point is a collection of features.

For example, imagine we have a bunch of data on people and we want to classify each one as being male or female. Specifically, for each person (record), we have the following attributes (features): height, weight, and eye color. A data point would be one person's 3-dimensional record (e.g. [74in, 200lbs, brown] or [61, 125, blue]).


Find an invariant in the minimum algorithm

The invariant is good (once you fix lots of imprecise things, like the 1..k which is obvious nonsense, and wouldn’t proof correctness. Precision is important. ) The code is broken, so your proof should fail - because it would be an invariant of a correct algorithm, but not your code posted here.


Is it decidable if there exists some input such that the TM makes at least five moves?

It's 9 because it doesn't matter what symbol we land on after move 5.
It's finite because the number of cells is 9, yes. The significance is because otherwise the algorithm in point 3 wouldn't finish.
All strings of length 9, with the starting point in the middle. "Five or fewer" is an error, I believe.


Data hazard or forward in MIPS SW after LW in this case?

It is unclear to me if you ask about the "real" MIPS chips, or about the simplified educational version one sees in class.

If you mean the former, then I would guess it does. Well, the CPU probably has way more steps in its pipeline, caches, and tons of other fancy machinery, but I think it is safe to assume that any valid code will run correctly on it.

As for the simplified 5-step pipelined MIPS: again, it depends on which version you refer to. Certain books have load-hazard circuits which are supposed to take care of most situations. But if you have a drawing of the circuits I guess you will be able to tell by yourself if forwarding units exist or not.

The moral is - the MIPS must run correctly any piece of code. If the code you present causes a hazard, then the MIPS hardware must$^*$ deal with it somehow. In most classes that teach MIPS they leave some parts off so maybe you saw a partial design that doesn't take care of it. If you have a specific version in hand, you can check.

$^*$Well, if the MIPS hardware doesn't take care of this, then the programmer (i.e., the compiler) must take care of it. This is less desirable.


Understanding connection between length of codeword and hamming distance in Hamming code

The answer to both questions is the sphere-packing bound.

Consider a binary code on $n$ bits with minimum distance $2d+1$ and $M$ codewords. Imagine surrounding each point of the code with a ball of radius $d$, consisting of all points at distance at most $d$ from the point. These balls must be disjoint: if the balls corresponding to $x,y$ contain some point $z$ in common (note that $z$ need not be in the code), then $d(x,y) \leq d(x,z) + d(y,z) \leq 2d$, contradicting the stated minimum distance. Each ball contains $\binom{n}{\leq d} := \sum_{r=0}^{d} \binom{n}{r}$ points, and so
$$ M \times \binom{n}{\leq d} \leq 2^n. $$
This is because there are $M$ disjoint balls, each containing $\binom{n}{\leq d}$ points, while in total there are $2^n$ binary strings of length $n$.


When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

No, you can't.

First, as a technical point, it never makes sense to say "If this simulation halts", since that would require doing the whole simulation and, if it doesn't halt, you'd never finish simulating it. You can, in certain circumstances, ask whether a particular Turing machine halts on a particular input, but that's something subtly different.

But the main point is that your reduction looks backwards. You're supposed to be using the argument "$S$ must be undecidable because I could use the ability to decide $S$ to let me decide the halting problem, which is impossible." But, by basing decisions on whether some Turing machine halts or not, you're assuming that you can determine this, i.e., assuming that you can already decide the halting problem.


Minimum spanning tree - Prim's algorithm

Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here.

Your second solution: $v_0,v_1,v_3,v_2,v_7,v_8,v_6,v_4,v_5$ is incorrect. After adding $v_0,v_1,v_3,v_2$ you add $v_7$. But the minimum distance between $v_7$ and any existing vertex in the tree is $6$. Vertex $v_6$ however has a distance of only $4$, and should thereby be added first.

You could continue this, and end up with a solution that is indeed different from your solution 1, but has the same weight. For example, $v_0,v_1,v_3,v_2, v_6, v_7,v_8,v_4,v_5$, which gives an MST of weight $37$, as expected.


What is the signature of a formal language?

In my experience a "signature" is something that puts additional constraints on a language made of syntactic terms. I'll try to provide an example.

Consider the alphabet $\Sigma = \{f,g,a,b,(,),;\}$. From this we can build the set of all the words $\Sigma^*$. This contains any word, including gibberish like "$)g;;f(($".

Then, we can craft the set of syntactic terms $T \subseteq \Sigma^*$ through an inductive definition.

We start by defining a subset $F \subseteq \Sigma$ as $F = \{f,g,a,b\}$, and we call this the set of function symbols. Then, inductively, we state that if $t_1,\ldots,t_n$ (with $n\geq 0$ are terms and $s\in F$, the word $s(t_1;\ldots;t_n)$ is a term.

Note that $n=0$ above gives the "base case" of the induction. We then have that $f()$ is a term, $a()$ is a term, $f(a();b())$ is a term, $f(f(a();b();a();a(b())))$ is a term, and so on.

Now, we might want to put more constraints on those terms. For instance, we might want to associate to each $s \in F$ a fixed nubmer of arguments, and consider only those terms respecting that. For instance, if we decide that $f$ has arity two (f is binary), then we allow $f(a();b())$ but not $f(a())$ nor $f(a();f())$. This restriction essentially defines a subset language $L\subseteq T$.

This is sometimes done by specifying a signature. E.g. something like
$$
\begin{array}{l}
f : A \times A \to A \\
g : A \to A \\
a : 1 \to A \\
b : 1 \to A \\
\end{array}
$$
The above is a fancy way to state that $f$ is binary, $g$ is unary, and $a,b$ are both constants (= zero-arity function symbols). $1$ is used to mean no-arguments.

A possible term here is $f(g(a());b())$.

The name $A$ above is called a "sort", and has no deep meaning on its own. The above is called a single-sorted signature since it uses only one sort. By contrast
$$
\begin{array}{l}
f : A \times B \to A \\
g : A \to B \\
a : 1 \to A \\
b : 1 \to A \\
\end{array}
$$
uses two sorts. This now forbids $f(g(a());b())$ since $g(a)$ has not sort $A$ as required. Instead, $f(b();g(a()))$ is still allowed.

When terms are logical formulae, it is common to use signatures to keep our words meaningful. For instance

$$
\begin{array}{l}
\land : P \times P \to P \\
{\sf prime} : \mathbb N \to P \\
0 : 1 \to \mathbb N \\
s : \mathbb N \to \mathbb N \\
\end{array}
$$
allows $\land({\sf prime}(0());{\sf prime}(s(0())))$ (i.e. ${\sf prime}(0) \land {\sf prime}(s(0))$, in more casual notation), but disallows nonsense such as
$\land({\sf prime}(0());0())$ (i.e. ${\sf prime}(0) \land 0$) which tries to use term $0()$ as if it were a proposition (a term of sort $P$).


In your example the assignment $f_1\wedge f_2$ is $(f_1\wedge f_2)(A)=f_1(A)\wedge f_2(A)=\text{True} \land \text{False} = \text{False}$.
similarly: $(f_1\wedge f_2)(B)=(f_1\wedge f_2)(C)=\text{False}$ so actually $f_1\wedge f_2 \equiv f_2$.

As they define, AND is preserving $X$ if for every two assignments $f_1, f_2$ that satisfy $X$, the assignment $f_1 \wedge f_2$ (defined by $(f_1\wedge f_2)(v)=f_1(v)\wedge f_2(v)$) also satisfies $X$.


Order a list of whole numbers so that no two numbers have the average of them sitting between them

Here's a simple recursive construction for the more restrictive version of the problem.  First of all, note that the average of an odd number and an even number is never a whole number; if $a=2i-1$ and $b=2j$, then $\frac12(a+b)=i+j-1+\frac12$.  This means that if we put the $\lceil N/2\rceil$ odd numbers $a_i$ first (in some as-yet-to-be-determined order) and then the $\lfloor N/2\rfloor$ even numbers $b_j$ (likewise, in some as-yet-to-be-determined order), then we can be guaranteed that the average of a $a_i$ and a $b_j$ can never be between them (because it'll never be a whole number), so we've split the problem into two subproblems: one for the set of odd numbers $a_i$ and one for the set of even numbers $b_j$.

But note now that if we have two odd numbers $a_m=2m-1$ and $a_n=2n-1$, then their average is $2\left(\frac{m+n}2\right)-1$, and so the subproblem of 'sorting' the $a_i$ correctly is exactly the same as sorting the numbers $c_i\in 1\ldots n$, where $c_i=\frac{a_i+1}{2}$ and $n=\lceil N/2\rceil$; a similar result holds true for the even numbers $b_j$.  This means that we can keep applying the same procedure to both of these groups recursively.  For instance, when $N=8$ this construction produces the ordering $15372648$.  Note that if we subtract one from these values and look at the numbers $0\ldots(N-1)$, then this ordering is $04261537$; looking at the bit patterns for these numbers ($000, 100, 010, 110, 001, 101, 011, 111$) shows that they're just the bit patterns of the numbers $0\ldots 7$, reversed!  This 'bit reversal' shuffle is used by Fast Fourier Transform (FFT) algorithms to correct the output ordering of their data (see, for instance, http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html ).

In fact, this construction shows that there are at least $O(2^{N/2})$ such orderings, since at each of the $N/2$ 'internal' nodes we can choose to either put the odd or the even numbers first without spoiling the result.  These don't exhaust all of the orderings, though; for instance, we can exchange $2$ and $7$  in the constructed $N=8$ ordering to get the ordering $15327648$ which also clearly satisfies the constraint but can never be constructed by this procedure (since odd and even numbers are 'intermingled').  I don't know how many of the $N!$ orderings of $1\ldots N$ actually satisfy the problem.


Question is about a paper "A Block-sorting Lossless Data Compression Algorithm" by M. Burrows and D.J. Wheeler

F.e. string "abc" becomes "bca" after BWT. This means that "abcabc" will transform into "bbccaa", i.e. "external repetition" of entire string will lead to "internal repetition" of each char in transformed string.


Why should small o notation has to satisfy the equation for all values of the constant

Consider this also (more?) common definition:

$\qquad\displaystyle f \in o(g) \quad\mathbin{:\!\!\iff}\quad \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Do you see now why we need to get below all factors $c$ in your definition? If not, we would have $f \in \Omega(g)$.


Nondeterministic PDA for the following language with Kleene star

I figured out the answer and hope this will help anyone with similar confusion in the future.

Since a pushdown automaton is essentially a finite automaton with an extra component called the stack which is used for storage, if we are presented with a regular language like the one given above, we simply need to create a PDA that does not use the stack. This concept confused me at first, but here's what I mean:

$$L = (aaa^*bab)$$

$\space$

$$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$
$$Q = \{q_0,\ q_1,\ q_2,\ q_3,\ q_4,\ q_5\}$$
$$\Sigma = \{a,\ b\}$$
$$\Gamma = \{$\}$$
$$z = \$$$
$$F = \{q_5\}$$

$\space$

$$\delta(q_0, a, $) = \{(q_1,\ $)\}$$
$$\delta(q_1, a, $) = \{(q_2,\ $)\}$$
$$\delta(q_2, a, $) = \{(q_2,\ $)\}$$
$$\delta(q_2, b, $) = \{(q_3,\ $)\}$$
$$\delta(q_3, a, $) = \{(q_4,\ $)\}$$
$$\delta(q_4, b, $) = \{(q_5,\ $)\}$$

$\space$

I'm not completely certain about the stack start symbol, because I've noticed some resources use it regardless, while others assume that at the beginning the stack is empty ($\lambda$) and push the start symbol at the first step.

Anyway, I hope this answer helps anyone else.


Are these examples of unification problems?

Yes, the variables can occur more than once in a term.  Either way you end up with a system of equations.  For plain unification, you can always have the unification variables be distinct and then add equations to unify them separately.  That is, you can turn $\mathtt{p}(X,X) = \mathtt{q}(\mathtt{a},\mathtt{b})$ into $\mathtt{p}(X,Y) = \mathtt{q}(\mathtt{a},\mathtt{b})$ and $X = Y$.

Comparing predicates with duplicate variables comes up all the time in Prolog.  For example, one of the most iconic Prolog programs is list append, usually written as:

append([], Ys, Ys).
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).

If you want to be very pedantic and say these programs don't illustrate terms with duplicate variables, then you can consider another iconic Prolog technique: difference lists. The most general difference list representation of a list $[1,2,3]$ is $[1,2,3|X]\setminus X$.


Why is it that Btrees most of the times have a degree that is odd? What happens if they are even?

One thing that distinguishes real-world B-trees from "lecture B-trees" is that real B-trees tend to have nodes and leaves where the size in bytes is fixed. So the "degree" of a B-tree is determined by the number of keys that will fit on a page.

So if the keys vary in size (e.g. strings), the "degree" of different nodes may be different. Roughly 50% of them will have even degree.


How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation?

A famous example: a PCRE that finds primes. I couldn’t find Abigail’s original, but there have been many iterations on this.

In JavaScript, for example, you can pass a function to the matcher to do arbitrary computation with the results.


Are today's massive parallel processing units able to run cellular automata efficiently?

Excellent question. I believe the answer is yes.

Evolving a cellular automaton is essentially equivalent to performing a stencil computation. On some 1D, 2D, or 3D grid, successive values of points (or cells) are computed based on the last value of point's neighborhood. In a simple 1D CA, this neighborhood might be the cell and the two cells to the left and right. There are lots of examples of stencil computations being performed on GPUs; ORNL's SHOC benchmark suite for OpenCL/CUDA contains a 2D stencil example, for instance.

The basic idea is to have each thread get a local copy of the neighborhood for several points, then compute the next values for points determined by that neighborhood. By appropriately using the memory hierarchy in e.g. CUDA (registers, shared, constant, texture, and global memories) and the SIMT processing model (e.g., by appropriately computing the transition function without introducing excessive warp divergence), good performance can be achieved.

This answer would be a lot better if I were to give an example, but I am too busy to write any code right now... But in theory, I think it should be feasible to efficiently simulate CAs on GPUs by modeling them after stencil computations. Lots of considerations go into writing a good stencil computation for GPUs, though.


Are there regular languages between every two non-regular languages?

Hint. Given any sets $A, B, C$ we have $A \cap C \subset C \subset B \cup C$.


Finding short readable representation of words

Given a string $S$ of length $n$, one can find the minimal representation in $O(n^3)$ time using dynamic programming.

Let's consider a representation as a binary tree.  Each node of the tree generates a string (a substring of $S$).  Each leaf generates to a single letter.  The tree has two types of internal nodes: a concatenation node, which generates the concatenation of the strings generated by its two children; and a repetition node, which takes the string generated by its only child and repeats it $r$ times, where $r$ is an integer stored in the node.  Your diagrams can all be represented in this form.

Now given a string $S$, we can find the minimal binary tree that generates it, using dynamic programming.  We'll let $A[i,j]$ denote the minimal binary tree that generates the substring $S[i..j-1]$.

We can derive a recursive expression for $A[i,k]$.  In particular, consider all of the following trees:

a tree with a concatenation node at the root, and a left child $A[i,j]$ and a right child $A[j,k]$ (one such tree for each $j$)
a tree with a repetition node at the root, holding the integer $r$, and a single child $A[i,i+(j-i)/r]$ (one such tree for each divisor $r$ of $j-i$)

We will find the smallest of these trees, and store the result in $A[i,k]$.

By evaluating this recursive relation in a bottom-up fashion (i.e., fill in entries of $A[i,j]$ in order of increasing value of $j-i$), we can fill in the entire table.  There are $O(n^2)$ entries in the table, and each entry takes $O(n)$ time to fill in, so the total running time is $O(n^3)$.

As far as related concepts, your idea is similar to a context-free grammar, augmented with the notion of repetition (e.g., we add a production $A \to r \otimes B$, which means that if a word $w$ that can be produced by $B$, then $w^r$ can be produced by $A$).  I haven't seen that particular notion explored, but context-free grammars are well-explored.

If you want heuristics to find a relatively small representation, but not necessarily the minimal one, you might be interested in the Sequitur algorithm and other uses of context-free grammars for data compression.  I think that the Sequitur algorithm can be modified to work in your setting: i.e., given a string, find a (hopefully small) representation of that string.


How to structure device driver software?

That very, very much depends on the kernel for which you are writing your driver. I'm (a bit) familiar with Linux. There are structures defined into which your drver has to hook. Those structures define most of the structure you are looking for, the driver itself just hooks into the kernel's structures on startup, gets its marching orders through a structure to be filled with function pointers for the relevant operations on the hardware. See Corbet, Rubini, Kroah-Harman "Linux Device Drivers" (3rd edition, get it here). It is somewhat dated, but the fundamentals haven't changed that much. The Linux Drivers Project gathers people trying to write drivers.

For a graphics card, the picture is quite different, I believe you'll find the above split between the kernel and X.org.

(The above general picture, with the kernel defining the overall architecture and the driver filling in the details of what object-oriented programming fans would call an "object" in an operating system defined device type "class" is the only reasonable way of structuring a non-toy, non-one-machine-only operating system. Most of the time written in C, not C++ or ($deity forbid) Java, but OO all the same.)


Framework or tools to generate theorem prover/solver/reasoner for new logic

There are many related ways  you can mechanise your logic.

Deep embedding into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is (almost) always possible, but makes using the embedded logic awkward.
Shallow embedding into one of the well-developed provers such as Isabelle/HOL, Coq or Agda. This is only possible when the embedded and embedding logics are sufficiently similar, but when it works it tends to work well.
Embedding into Isabelle. Note that Isabelle is a meta-tool for embedding logics, and Isabelle/HOL is but an implementation of HOL using the Isabelle tool. This is probably a lot of work, and moreover, most of the proof automation available for Isabelle/HOL is targetxing the logic HOL, so is unlikely to work for your specific logics.
Roll your own. It's quite easy to build a proof checker, should be just a few lines of code, especially if you take the LCF approach. More advanced tools are rather difficult, a modern SAT solver is probably > 10k LOC and that's for propositional logic, which is the simplest logic.
Logical frameworks. Some $\lambda$-calculi have been built particularly to enable the embedding of logics. Most well-known might be the Edinburgh Logical Framework and Pure Type Systems. Some mechanismation of those is available, but whether that is usable for you I don't know.


Yes you missed something ,
Lets review how your PDA works :

we push  a for each a we read
we pop 2as for each b we read , then when stack is empty we push b for each b we read
we pop b for each 2cs we read

Your PDA will accept strings of form a2nbn+mc2m
for ex , a4b5c6 , here n = 2 , m = 3
You push 4 as , then for each 2as you pop b , you pop 2bs , and 3 bs remain which are pushed to stack !!!
Hopefully you can see the problem here , no one told you that you are half way bs when you finished popping as
You continue , for each of the 6 cs you pop a b then you accept
You expect the string in the form a2nbn+mc2m , you compare  a2nbn then  bmc2m , of course if n = m you are correct , but there is no way to ensure this


Garey, Johnson and Stockmeyer ("Some simplified NP-complete graph problems") came up (already in 1974!) with a gadget reduction from MAX3SAT to MAX2SAT. Given a 3SAT clause $C = x \lor y \lor z$, they come up with a gadget $G(C)$ consisting of 2SAT clauses on the variables $x,y,z$ as well as some additional variables $V(C)$, satisfying the following property. Given an assignment to $x,y,z$, the maximal number of clauses in $G(C)$ which can be satisfied by an assignment to $V(C)$ is $M_1$ if $C$ is satisfied and $M_2<M_1$ if $C$ is not satisfied.

Try to understand how the existence of this gadget allows us to reduce MAX3SAT to MAX2SAT. Then either try to construct such a gadget, or look it up.


What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

Regular languages can be accepted in linear time and constant space.

Valiant's algorithm parses arbitrary context-free languages in time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. Deterministic context-free languages (which are those used in practice) can be parsed in linear time.

Context-sensitive languages are identical to the class $\mathsf{NSPACE}(n)$. I'm not aware of any non-trivial time upper bound.

Recursively enumerable languages cannot be parsed in general, since $\mathsf{R} \neq \mathsf{RE}$.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question is completely unrelated. Unfortunately, the undergraduate curriculum usually spends much more time on the old-fashioned Chomsky hierarchy compared to more modern hierarchies afforded by computational complexity theory.


Prim's algorithm on graph with weights of only $1$ and $2$ on each edge

The running time depends on how you implement the queue data structure.

Hint: Can you think of any way to implement the queue data structures, so that ExtractMin, Remove, and Insert operations are much faster, if you're given the knowledge that every edge has weight either 1 or 2?


Complexity of finding binomial coefficient which equals to a number

It is not true that $(n-k)^k<{n\choose k}$. For example ${9\choose 2} = 36 < 49 = (9-2)^2$.

I haven't (yet) found a subtle solution using arithmetic properties of the binomial coefficients, however I can suggest a somewhat bruteforce one if that helps :-)

You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt[k]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.

The complexity of a Newton-Raphson search only depends on the complexity of computing the function and its derivative, and the number of digits required for the solution (in our case we just need the closest integer).

So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.


Are there programs that never halt and have no non-termination proof?

There are indeed programs like this. To prove this, let's suppose to the contrary that for every machine that doesn't halt, there is a proof it doesn't halt.

These proofs are strings of finite length, so we can enumerate all proofs of length less than $s$ for some integer $s$.

We can then use this to solve the halting problem as follows:
Given a Turing Machine $M$ and an input $x$, we use the following algorithm:

s := 0
while (True)
    test if machine M halts on input x in s steps
    look at all proofs of length s and see if they prove M doesn't halt on input x
    set s := s + 1

If $M$ halts on input $x$, then it halts in some finite number of steps $s$, so our algorithm terminates.

If $M$ doesn't halt on input $x$, then by our assumption, there's some proof length $s$ where there's a proof that $M$ doesn't halt. So in this case, our algorithm always terminates.

Thus, we have an algorithm deciding the Halting problem which always terminates. But we know this cannot exist, so our assumption that there's always a proof of non-halting must be false.


Binary to ASCII using logical operations

By looking at a ASCII table you can see that the $4$ least significant bits of all characters between $0$ and $9$ correspond to the respective integer representations of the numbers between $0$ and $9$, while the 4 most significant bits are always $0011$ (leading zeroes are not shown in the table, so keep in mind you need to pad binary numbers to 8 bits).

If $x$ is the binary representation of a number between $0$ and $9$, you can then obtain the ASCII representation of the corresponding character as
$$
x \;| \;00110000,
$$

where $|$ denotes a bitwise logical or and the second operand is in binary.


How To Merge Together Two Circular Doubly-Linked Lists In O(1) Time?

There is no need to use temporary variables. See the following picture and the associated pseudocode below. You want to reassign the gray pointers to their colored counterpart. You just have to be careful with the order of the instructions.

one.right.left = two.left;  //red
two.left.right = one.right; //blue

one.right = two; //green
two.left = one;  //purple


Why is this function computable in $O(n^{1.5})$ time?

Denote by $|x|$ the length of a number $x$, i.e. $\lfloor \log_2 x \rfloor + 1$ (for $x > 0$). Calculating $2^x$ requires time $O(x)$ in the RAM model, and so calculating $f(i+1)$ from $f(i)$ takes time $O(f(i)^{1.2}) = O(|f(i+1)|)$. Since $f(i)$ is growing faster than geometrically, the overall time to calculate $f(i+1)$ is $O(|f(i+1)|)$. As you point out, you need to do so until $f(i+1) \geq n$, which means that $f(i) < n$. Therefore the total running time is $O(|f(i+1)|) = O(f(i)^{1.2}) = O(n^{1.2})$.

In the Turing machine model with a single tape, calculating $2^x$ takes time $O(x\log x)$, and so the total running time is $O(n^{1.2} \log n) = O(n^{1.5})$. The algorithm for computing $2^x$ replaces $[x]$ by $1[[x]]$ (here $[x]$ is the binary representation of $x$, and $[[x]]$ is the binary representation using different digits $0',1'$), and then repeatedly runs the transformation $[[x]] \longrightarrow 0[[x-1]]$, which takes time $O(|x|) = O(\log x)$.


A function $f(n)$ is time-constructible if there is a Turing machine that runs in time exactly $f(n)$, where $n$ is the input size (in bits). Kobayashi, in his paper On proving time constructibility of functions, showed that if $f(n)$ can be computed in time $O(f(n))$ then $f(n)$ is time-constructible. In particular, functions like $n^{\lfloor \log_2 n \rfloor}$ are time-constructible, even though they lie strictly between polynomial time and exponential time.

In fact, the time hierarchy theorem even shows that there are some decision problems which can be computed in time $O(n^{\log n})$ but not in polynomial time. This shows that there are problem not in $\mathsf{P}$ which can be computed in faster than exponential time.


Resources for implementing dependent type theory

This paper is my go-to for implementing dependent types. It starts from the basics, uses bidirectional types, and has accompanying code in Haskell.
If you're at all interested in type inference, this paper is great, and also has accompanying Haskell code.
David Christiansen has a tutorial on dependent type checking with bidirectional types, with a Haskell and Racket. More generally, I've heard great things about his book The Little Typer, though I haven't had a chance to read it myself.
I've heard great things about  smaltt  by András Kovács, particularly for it being an efficient implementation.


Find total number of assignment in the worst case?

Likely the question is asking you to focus on line 4, in which you assign a value to A[i]. You can also focus on the for-loop with and its control variable to get a complete answer, but the only way to know for sure is to ask the person responsible for the problem.

Anyway, more precisely, the question is how many assignments do you do in the worst case as a function of the array length $n$. As you can see, this number is determined by the number of times the preceding if-branch evaluates to true. Your task is to argue how many times that can happen in the worst case.


smaller size approximation to minimum vertex cover

Do you want a set whose size is a lower bound? Or do you want a lower bound on the size?

If you want a set, does it need to be a subset of a minimum vertex cover, or just a smaller set (in the latter case, any set of the appropriate cardinality would do)?

Since there is a well-known approximation algorithm that is a factor of two over-approximation, you can divide the result by two to get a factor of two under-approximation. In fact, these notes use a lower bound to prove the over-approximation factor.


Is there a mistake in the expression for clean behavior in Pnueli's article from 81'?

It would seem that in (1) (still page 9) he refers to a sequential program, so there is no concurrency. I think this assumption holds for the rest of the articles. So the "the" is ok there.


Can someone help me come up with a formula for calculating the difference in time?

The solution I originally provided here is wrong, the comments on why the question itself is out of scope are interesting though.

      int hours = Math.abs(a - b)/ 100;

    int minutes1 = Math.min(a,b) % 100;
    int minutes2 = Math.max(a,b) % 100;

    int mdifference = ((Math.min(a,b) / 100) == (Math.max(a,b) / 100)) ? minutes2 - minutes1 : (60 - minutes1) + minutes2;

    System.out.print("\nDifference: " + hours + " hours and " + mdifference + " minutes");


Pumping lemma with multiple of prime number + a constant

Your error is that you assume that you must find one $i$ to satisfy all the subdivisions $uvwxy$ of the lemma. The lemma is actually much weaker in that you need to find any $i$ for every subdivision $uvwxy$ of a string $s$ in $L$ longer than $h$. Without loss of generality, I will assume that any given $h$ is prime, because if it were not, I would just substitude all next occurances with any higher prime number and everything would still work the same way (I never needed the condition $|vwx|\le h$).

That said you can take your second try from the question and then fork it into two cases where:

$v \neq \epsilon$ (where $\epsilon$ means empty string, I don't know if that's international notaion. It can be otherwise written as $|v|\neq0$ )
From your first equation $$h + |v|(i-1) = m, m \text{ prime}$$ with $i = h + 1$ you get $$h + |v|h = (1+|v|)h$$ which is composite number because of our assumption $v \ne \epsilon$, meaning the string is not from $L$.
$|v|=0$ where we can pick another $i$ because it is different division of the string $s$. Here we get $$|v|=0 \land |vx| \ge 1 \implies |x|\ge 1$$
And we can trivially chose $i=0$, because now we actually subtract from the second string of zeroes, which was originally $2h+1$ long. The new length will be shorter than that, meaning we'll get a string $0^{h}10^{g}$ where $g<2h+1$ thus the string is not from the language $L$.

On final note, if you were to use this as a rigorous proof, you would need to address all the other options including those, where the $1$ is part of either of the pumped strings, it is part of either $u$ or $y$ and so on. I covered only the two interesting options and the others should now be trivial to you (I assume that is why you never mentioned them in your question and assumed that 1 is part of the $w$ string).


This is provably impossible. The proof of Shannon's theorem goes through as usual.

As a simple example, suppose that are looking for an algorithm that compresses all $n$-bit strings to smaller strings. This is impossible since there are $2^n$ possible inputs, but only $2^n-1$ possible outputs. The proof of Shannon's theorem is very similar. Note how $Q$ makes absolutely no difference.

What happens if you choose a random 1 MiB window of $Q$ as your file? This can easily be compressed to 30 bits, by sending the location of the window. However, in this case the entropy of $Q$ is indeed at most 30 bits, since there are at most $2^{30}$ different windows.


Clarification on "clause learning" in DPLL algorithm

All the literals in a conflict clause are set false by definition, else there would be no conflict.  So if the clause $\overline{b_1}\lor\overline{b_2}$ existed, one of those false literals would have caused that clause to go unit before we reached the current level, which in turn would have forced one of the $\overline{b_1}$ or $\overline{b_2}$ literals true.  But we already know that those literals must be false, so we have a contradiction.  This contradiction shows that the clause $\overline{b_1}\lor\overline{b_2}$ cannot exist.  The reasoning is the same for all clauses that are subsets of the conflict clause.


Converting Decimal Numbers between 0 and 1 to Binary

You are not doing arithmetic on arbitrary infinitely precise numbers. You are doing arithmetic on the subset of number representable in your computer's native floating point format. Moreover, the values you see printed out are not infinitely precise representations of the actual values encoded in the computer. They are decimal numbers (of a maximum precision) which approximate the internal value. This makes it a little difficult to see what's really going on. At the very least, it is confusing.
Although some programming languages (and even some computers) natively support decimal arithmetic, most of the time the internal representations you will be working with are fixed-precision binary representation. By fixed precision, I mean that the number represented is a fraction $n/2^i$ where $i$ is an integer in a limited range and $n < 2^p$ for some fixed $p$, the precision. Typical CPUs have settled on a precision of 53 bits, so $n < 2^{53}$.
When you supply $.002992$ -- that is, $2992/10^6$ -- the programming language needs to find an internally representable number that is as close as possible to that value in order to minimise calculation errors. At least on my machine, the value selected is $1724770570891843/2^{59}$. That number is extremely close to $2992/10^6$ -- so close that if you round it off at the 18th decimal point you will still see $0.002992$ -- but it's not equal. So your calculation starts with a small inaccuracy.
However, if you just run your algorithm (multiply by 2; subtract 1 if the result is not less than 1), you will not increase the inaccuracy. Multiplying by 2 is exact (unless you exceed the exponent limits), since it only requires changing the exponent to the next integer. And 1 can be represented exactly. In fact, every integer up to $2^{53}$ can be represented exactly, as well as quite a few other integers (but not $2^{53}+1$). So your algorithm will reveal the binary representation of the number actually being used by your computer instead of $0.002992$. That number has no more than 53 binary digits of precision, but it is slightly longer than 53 binary digits because of the 9 leading 0s (in binary). There is no repeating part at all.
Trying to "correct" this computation by introducing additional round-off errors at each step is not going to help.
If you want to find the exact binary representation of $0.002992$, you can use integer arithmetic to work with successive rational numbers. Start with $2992/1000000$ and repeatedly double the numerator and, if necessary, subtract the denominator [Note 1]. (You don't need any extended precision for that. If you start with $0 \le n \lt d$, then $n$ will never exceed $2d$. In the case of $2992/1000000$, that's well within the range of a normal 32-bit integer.)
That will indeed show that the repeating fraction has a period of 12500. It's straightforward to show that the period of the repeating fraction of $n/d$ is less than $d$ in any base. The above algorithm only depends on the value of $n$ and never changes the value of $d$, so the second time you hit a particular value for $n$, your output will start repeating. The period must be less than $d$ because if $n$ is 0, you have an exact fraction, and there are only $d-1$ other possible values of $n$, so it must repeat before $d$ steps.

Notes:

Base 2 makes this particularly easy. If you want to do the computation for a base other than 2, you'll need to do the following
 n = n * b          # Note: n < d
 f = floor(n / d)   # Thus: f < b
 Output f as the next digit
 n = n - d * f      # Or: n = n mod d

The simpler base 2 case is just what happens if you plug $b=2$ into the above calculation.


Determining the number of iterations needed to find the number of bits in an integer

The number of bits is always an integer, so you have to solve for that equation over the integers.  Thus, use $\lceil \lg (n+1) \rceil$.


Being a functor requires two properties:

fmap id = id
fmap (f . g) = fmap f . fmap g

The definition fmap fails the first condition:

fmap id = map id . reverse = reverse != id

So that's not a functor at all!

And it even fails the second condition:

fmap (f . g) = map (f . g) . reverse
             = map f . map g . reverse
             = map f . fmap g
             = reverse . map f . reverse . fmap g
             = reverse . fmap f . fmap g
             != fmap f . fmap g

Which is quite clear if you think about it:

fmap (f . g) reverses the list once and then maps its elements via f . g
fmap f . fmap g reverse the list, maps via g, then reverses the list again and then maps via f!


Remove minimum number of vertices to disconnect the graph

(This answer was originally given as part of the question, with the goal of it being verified.)

My intuition tells me that we can use max-flow, min-cut algorithm to solve this problem:

Replace each of the undirected edges with a pair of directed edges.
Replace each vertex $v$ with two vertices $v_\text{in}$ and $v_\text{out}$ connected by an edge. all the incoming edges of $v$ will be connected with $v_\text{in}$, all the outgoing edges of $v$ will be connected with $v_\text{out}$.
Try to find a minimum cut $M$. The edges of $M$ refer to the vertices that we need to remove.


What is the difference between $AC^2$ and $FO (\log \log n)$ complexity classes?

The functions $\log \log n$ and $\log^2 n = (\log n)^2$ are quite different. The latter grows much faster than the former: $\log \log n = o(\log^2 n)$. This shows that FOLL is a subset of AC2 (and even of the smaller class AC1).

Uniformity is a different aspect in which the two classes differ: FOLL is a class of uniform circuits, whereas the AC hierarchy captures non-uniform circuits. As such, even AC0 circuits can compute uncomputable functions, something that FOLL cannot do.


Why are Chess, Mario, and Go not NP-complete?

It's a common misconception that chess is NP-hard. Generalized chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces. The question is, given a certain position on an nxn board, will white win if both players play perfectly? There may be a "yes" answer and the certificate for NP might be a list of perfect moves for both players, but it's intractable to check if those moves by black are actually perfect. Maybe black has better moves so that white doesn't win. You can't check such a certificate in polynomial time.

Also, it may even be the case that a game takes an exponential number of moves, so that such a certificate is of exponential length.


The standard definition you'll usually find is the second one, but it makes no difference since they're indeed equivalent, and you can prove both arrows, I'll give a sketch of proof:

To see that (1) $\Rightarrow$ (2), consider a machine that non-deterministically guesses a certificate and then acts as a poly-time certifier.

On the other hand, to see (2) $\Rightarrow$ (1), observe that if a nondeterministic Turing machine decides $x \in L$ in polynomial time, then the set of nondeterministic choices it made in the path towards the accepting state is a certificate for $x$, and it must have polynomial size because by hypothesis every branch of the computation must terminate in polynomial time.

As for your second question, it is not true that a nondeterministic Turing machine can only guess out of polynomially many options (if it were the case, it could be simulated by a polynomially related deterministic machine). The limitation is that every computational branch must terminate in polynomial time. For instance, consider a nondeterministic machine for $\textsf{SAT}$: the number of valuations is exponential in the number of variables.

The reason why we give the characterization you cite in (1) is that we want to prove that $\textsf{NP}$ is the class of problems for which you can "guess" a solution and verify it in polynomial time, but a certificate that is more than polynomial in size cannot be "guessed" in polynomial time.


Is Q-Learning ever better than Brute Force?

Reinforcement Learning (RL) algorithms are useful in a setting when the structure of the environment is unknown and/or stochastic. The environment is normally formalized as a Markov Decision Process (MDP) or Partially Observable Markov Decision Process (POMDP) and the goal of an RL agent is then to maximize its cumulative reward (or minimize its regret with respect to the best alternate policy) while behaving in the environment.

As such it isn't clear how a brute force algorithm would efficiently deal with the stochastic nature of the environment or the fact that this procedure is almost universally assumed to be done online. For more information and a modern overview of RL I recommend this excellent reference by Csaba Szepesvari.


Suppose that $T(n) = n^{\omega(1)}$, and consider the complexity class $\mathsf{E}^{\mathsf{DTIME}(T(n))}$. Given a Turing machine $M$ and an input $x$ of length $n$, an $\mathsf{E}^{\mathsf{DTIME}(T(n))}$ machine can write $1^{2^n}$ and then ask the oracle whether $M$ halts on $x$ within $T(2^n)/\log T(2^n) = 2^{\omega(n)}$ steps. This cannot be done in $\mathsf{E}$ according to the time-hierarchy theorem.


Proving that directed graph diagnosis is NP-hard

Reduce from NP-complete SET-COVER instead.

Let $S_1,\dots,S_m \subseteq\{1,\dots,n\}$ with $k\in\mathbb{N}$ an instance of set cover. Define an instance $(V,E,k')$ of DGD like this:

$V= \{s_1,\dots,s_m,o_1,\dots,o_m,e_1,\dots,e_n,o\}$
$E= \{(s_i,o_i) \mid i = 1,\dots,n \} \cup \{(s_i,e_j)\mid j \in S_i\} \cup\{(e_j,o)\mid j=1,\dots,n\}$
$k' = m + k$

It is easy to see that the constructed DGD instance has a positive answer if and only if the given set cover instance has a positive answer. In particular, all $m$ pairs $(s_i,o_i)$ have to be chosen no matter what in order to cover all $o_i$; then $k$ of the $m$ pairs $(s_i,o)$ have to cover all the $e_j$, and the first components of those chosen are the solution of the SET-COVER instance. If no such choice is possible the SET-COVER instance has no solution as well.

As the construction is possible in polynomial time, this proves SET-COVER $\leq_p$ DGD.

As an example,consider the example set cover instance given on Wikipedia, namely $\{1,2,3,4,5\}$ and sets $S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}$. This translates to the following graph:

[source]


Here is the description of a desired algorithm in Python style pseudocode.

Generate a spanning tree T of G
Put all remaining edges that are not in T in a list L
For each edge e in L:
  Find the cycle C in the graph that is T plus edge e.
  If e is lighter than the heaviest edge e' in C:
    add e to T and remove e' from T

It requires $O(n)$ operations to generate a spanning tree. It requires $O(n)$ operations to find a cycle when you add an edge to a tree and $O(n)$ operations to find the heaviest edge in a cycle. Since there were total $c+1$ edges remaining, where $c+1$ is a constant, the for loop requires $O(n)$ operations. Adding up other operations of small time, we find that the time-complexity of the algorithm is $O(n)$.

The correctness of the above algorithm has been proved in my answer to turn MST of G to MST of G with one new edge. Note that initially T is its own MST.


Can one increment an $n$ bit integer using fewer than $2 - 2^{1-n}$ bit inspections on average?

We can prove a tight lower bound of $2 - 2^{1-n}$ as follows. Informally speaking, we will argue inductively that whenever a bit is read during the increment procedure, that one of the two possible outcomes (a $0$ or a $1$ can be read) will cause the algorithm to stop reading additional bits. This will show that if we require the average number of reads to be strictly smaller than $2$, then we required a code isomorphic to the standard binary code.

Suppose that the first bit read by the increment algorithm is bit $i_1 \in [n]$. Now we have three cases to consider. In the first case (A), the algorithm will stop reading additional bits regardless of the value of $i_1$. This means that after reading $i_1$, the algorithm must decide which bits must be flipped right away, and clearly this will not yield a valid increment algorithm for $n > 1$. In the second case (B), the algorithm will adaptively read another bit, regardless of the value of $i_1$. We note that the algorithm may choose to read a different bit depending on the value of $i_1$. In this case, however, we are already reading at least $2$ bits no matter what, so the average number of bits read will exceed $2-2^{1-n}$. Finally, in the third case (C), the algorithm will only read another bit for a single value of $i_1$ (say $1$ for convenience). That is, when $i_1$ is $0$, the algorithm will determine which bits need to be flipped, and when $i_1$ is $1$, the algorithm will probe a second bit. In such a case, the expected number of bit reads is at least $1/2 \cdot 1 + 1/2 \cdot 2 = 3/2$. This is the only case where we can hope to beat the standard binary code.

Now we can apply this argument inductively. Suppose now that the algorithm is adaptively reading bit $i_k$, with $k \leq n-1$. Then in case (A), at most $n-1$ of the bits are ever read by the algorithm. This means that there is a bit that is never read and thus never written to, so the increment algorithm cannot be correct. Here we assume that the only bits that can be flipped are the ones read during that particular increment operation. In case (B), we can verify that the expected number of reads is at least $$\sum_{j=1}^{k-1} j/2^j + 2^{1-k}\cdot(k+1) = 2$$ which is again too many. In case (C), however, the expected number of reads can be verified to be at least $$\sum_{j=1}^{k-1} j/2^j + 2^{-k}\cdot k + 2^{-k} \cdot (k+1) = 2 - 2^{-k}\cdot(2k+3)$$ which is again the only case which might lead us to a better performance than the standard binary code.

When performing the $n$-th bit read, there are no other bits that the algorithm can read (since the other $n-1$ bits have already been read), so only case (A) becomes valid. Computing the expected number of reads then gives exactly $2 - 2^{1-n}$, as required.

I find that it helps to view this as a binary decision tree, where the internal nodes are labelled by the bit read, and the leaves are labelled by the bits that are flipped. So you begin by reading the bit labelled at the root of the tree (in our case $i_1$), then you go left if you've read a $0$ and right if you've read a $1$. With this picture in mind, it becomes clear that there are only three cases to consider at each step of the proof.


Proving a factor 2 performance guarantee for a greedy minimum cardinality vertex cover algorithm (Exercise)

In this exercise, we think of the DFS tree (in fact, DFS forest) as a rooted tree (in fact, forest). We define leaf and nonleaf accordingly. In particular, the root of the tree is not a leaf vertex unless it is an isolated vertex.

In order to prove that the set of nonleaf vertices is a vertex cover, you have to notice that no edge can connect two leaves $x,y$ of the tree, since if $x$ is the vertex reached first, then $y$ will be a descendant of $x$.


In which environment we use NFA(Non Deterministic Finite Automata)?

The NFA is simpler to construct and manipulate.

The equivalent DFA of a n-state NFA can have up to 2^n states in the worst case.

For these two reasons the NFA is the preferred state machine for most real implementations dealing with regular languages.

The non-determinism is dealt with using either backtracking or or simulating multiple states at the same time (this last one can be seen as constructing the states of the equivalent DFA on the fly).


Sub-Graph Isomorphism for graphs with multiple edge types and multiple node types

You can replace each edge $(u,v)$ with two edges $(u,t_0)$ and $(t_0,v)$ where $t_0$ is a new vertex (a different one for each edge you replace), and then color the vertex $t_0$ based on the type of the edge $(u,v)$.


All superlinear runtime algorithms are asymptotically equivalent to convex function?

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

No. A simple example is
$$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\
n^2 & \text{ when } n \text{ is even.}
\end{cases}$$

What if we also require $T(n)$ be strictly increasing?

The answer is still no. A simple example is

$$T(n)=\begin{cases}2^{(n+1)^2} & \text{ when } n \text{ is odd,}\\
 2^{n^2}+1 & \text{ when } n\text{ is even.}
\end{cases}$$

Since $\displaystyle\lim_{k\to\infty}\frac{T(2k)}{T(2k-1)}=1$ and $\displaystyle\lim_{k\to\infty}\frac{T(2k+1)}{T(2k)}=\infty,$
there is no convex function $f$ such that $T(n)=\Theta(f(n))$.

Exercise 1. What if we also require both $T(n)$ be strictly increasing and $T(n+1)/T(n)$ be bounded?

Exercise 2. Let $T_1$ and $T_2$ be two increasing functions such that $T_2(n)\not=O(T_1(n))$. Show that there is a function $T(n)$ that is bounded between $f_1$ and $f_2$ such that there is no convex function $f(n)$ such that $T(n)=\Theta(f(n))$.


"Insensitive" CNF/DNF SAT always satisfying same number of clauses

Consider a DNF $C_1 \lor \cdots \lor C_m$.

For any clause $C_i$, we can compute the probability that a random assignment satisfies $C_i$: it is 0 if $C_i$ contains both a variable and its negation, and otherwise it is $2^{-|C_i|}$, where $|C_i|$ is the number of literals in $C_i$.

For any two clauses $C_i,C_j$, we can compute the probability that a random assignment satisfies both $C_i$ and $C_j$: it is just the probability that a random assignment satisfies $C_i \land C_j$.

Given this data, it is routine to compute the variance of the number of satisfied clauses under a random assignment. The DNF is insensitive iff the variance is zero. The corresponding algorithm runs in polynomial time, and so the problem is in $\mathsf{P}$.

If we have a CNF, we can negate it to obtain a DNF which is insensitive iff the original CNF is.


It depends on what "memory" you are talking about. Basically, nothing in a computer can contain data forever. Random Access Memory in a computer loses its data after it is no longer powered, a hard drive has a data retention of approximatively 10 years (this may be different now because of SSDs/SSHD/etc, but you get the idea). There are also several cases where a memory becomes amnesic, but knowing that there are many types of technology for memory, it can vary greatly. It is sometimes possible de retrieve lost data, but again, it depends on the technology.


Can we use domains other than the naturals in computability theory?

The domain is finite strings of symbols from some alphabet – i.e., initial contents of Turing machine tapes. The natural numbers can be easily coded as finite strings: either in unary using length or in some higher base using symbols from the tape alphabet as digits. Other countable sets (e.g., integers and rationals) can be coded if, and only if, there is a computable bijection between that set and the naturals. However, you can't let your domain be any countable set: for example, if you want your domain to be the set of Turing machines that halt on every input, you couldn't even tell which Turing machine a given finite string codes.

There's no way to use an uncountable domain because the initial contents of the tape must be finite and there are only countably many finite strings over any finite alphabet.


This can be expressed as a weighted maximum matching problem.

Suppose we want the average team strength to be $x$.  If the actual team strength is $s$, we apply a penalty of $(x-s)^2$.  In this way, for any proposed partitioning of the players into teams, we obtain a total penalty (the sum of the penalties for each of the teams).  The goal is to find an assignment of teams that minimize the total penalty.  I think this is what you are asking for.

So, here is how we express this as a maximum matching problem.  If you have $n$ players, form a graph with $n$ vertices, one vertex per player.  For each pair of players $v,w$, add an edge from $v$ to $w$ whose weight is $-(x-s_{v,w})^2$, where $s_{v,w}$ is the strength of the team obtained by putting $v$ and $w$ onto the same team.  Now any division of the people into $n/2$ teams is a matching in this graph.  By maximizing the total weight of the matching, we are minimizing the total penalty of the corresponding teams, so the maximum matching gives us a solution to your problem.  Finally, there are polynomial-time algorithms for finding a maximum matching in a weighted graph, so you can just use one of them.

How do we find $x$?  I initially interpreted your comments to imply that $x$ should be the optimal team strength, by which I assume you mean the average strength of the teams in the assignment that maximizes this average (without trying to make the team strengths as similar as possible).  This too can be computed by solving a maximum matching problem, where now the weight on the edge from $v$ to $w$ is simply $s_{v,w}$.  So, the total algorithm is: first find $x$, using an algorithm for maximum matching, then find the best partitioning of teams according to your original matching, by applying the maximum matching algorithm a second time.

However, after reading megas' comments, I now suspect that interpretation was incorrect.  As megas correctly explains, a more reasonable interpretation would be to make $x$ be the average strength of the teams in the partitioning selected to make team strength as close as possible.  That's a harder problem.

However, here's an approach that might work reasonably well in practice.  Sweep $x$ over a range of candidate values, say, over 100 candidate values.  (You can probably get some reasonable guess for a range $[\ell,u]$ that is likely to contain the optimal value for $x$; now try a bunch of different values of $x$ in that range, say the values $\ell, \ell+0.01(u-\ell), \ell+0.02(u-\ell), \dots,u$.)  For each such hypothesized value of $x$, solve the maximum matching problem (with weights $-(x-s_{v,w})^2$ on the edges) to get an assignment of players to teams.  In this way, we get 100 candidate assignments.  Now for each we can calculate the average team strength and the total penalty, and see which assignment is best.

Why do I expect this will give close to an optimal answer?  Well, there is some real optimum.  Let $x_\text{opt}$ be the average team strength for this actual optimum.  When we use a candidate value for $x$ that is sufficiently close to $x_\text{opt}$, we can expect to get an assignment that matches the optimum (or is close to it).  So, if the step size for the candidate values of $x$ is small enough, this procedure seems like it should find the optimum.  In practice, this is only a heuristic, and it might or might not find the actual optimum, but I suspect it will enable you to find an assignment that's pretty close to optimal, even if it's not exactly the optimum.


How was the σ function chosen to extend the perceptron?

Answer to first part
The function in the question is called the logistic function. Sometimes it is also called "the" sigmoid function, but some authors use sigmoid to just mean any s-shaped function.
There are a wide variety of activation functions used in practice in neural networks, sigmoid and otherwise. The logistic function is one of the more common ones, because both the logistic function and its derivative are defined for all real inputs, can be written as short expressions in terms of elementary functions, and can be computed efficiently using standard library functions in most programming languages. (This is unlike the step function used as the activation function for a classic perceptron—the derivative of the step function is undefined at the discontinuity.) Another widely-used activation function that has these properties is $\tanh$. There is really no strong reason to prefer one over the other when initially presenting sigmoid neurons. You can pretty much pick any function you learn how to differentiate in a Calculus 1 class and that has a sigmoid shape with asymptotes at $\pm\infty$. They have slightly different performance characteristics in training, but that is not very relevant for an initial explanation.
It is unfortunately very difficult to explain backpropagation without understanding partial derivatives, since backpropagation is literally just gradient descent where the gradient is computed by automatic differentiation. I would recommend watching 3Blue1Brown's excellent series of YouTube videos on how backpropagation works: part 1, part 2, and especially part 3 and part 4.
You mention an audience in the question. If you are going to be presenting this material, I would seriously consider referring your audience to the 4 videos linked above, at least as references. They certainly provide a better explanation than I could give in a lecture.
Answer to second part
The reason for not using a linear function is that a neural network with all linear activation functions is a linear combination of linear functions, and is therefore itself a linear function. So using a linear activation function misses the entire point of training a neural network; you could get the same result faster by doing a least-squares fit of a linear function to the data.
To oversimplify only slightly: a neural network with a linear activation function is just the "fit trendline" feature in Excel.
By contrast, there is a universal approximation theorem that says that, for sufficiently nice nonlinear activation functions, any function can be approximated well by using enough neurons.
The universal approximation theorem was not discovered for many years after when neural networks were first invented, so it was not a motivating factor in their invention. Early neural network research was mainly inspired by biological neurons (the kind in your brain) and control theory.
While the universal approximation theorem says that a sufficently large neural network has the potential to approximate any function well, the actual reason why the standard method of training neural networks (stochastic gradient descent backpropagation) performs so well in practice is still poorly understood and an active area of research.


The trick here is to get rid of the sum. Note that the sum is up and down, it can be replaced by twice up:
$$
\begin{align*}
  (n + 1) T(n + 1) &= 2 \sum_{1 \le k \le n} T(k) + c (n + 1)^2 \\
  n T(n)           &= 2 \sum_{1 \le k \le n - 1} T(k) + c n^2 \\
  (n + 1) T(n + 1) - n T(n) &= 2 T(n) + c (2 n + 1)
\end{align*}
$$
This is a linear, first order, non-homogeneous recurrence.

Update: Solution to the recurrence.

The recurrence can be written:
$$
\frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1} = c \frac{2 n + 1}{(n + 1)(n + 2)}
$$
This reduces to a sum:
$$
\begin{align*}
\frac{T(n)}{n + 1} &= T(0) + c \sum_{0 \le k \le n - 1}
                                 \frac{2 k + 1}{(k + 1) (k + 2)} \\
                   &= T(0) + c \sum_{0 \le k \le n - 1}
                                 \left(
                                   \frac{3}{k + 2} - \frac{1}{k + 1}
                                 \right) \\
                   &= T(0) + 3 c (H_{n + 1} - 1 - \frac{1}{2}) - c (H_n - 1) \\
                   &= 2 c H_n + (T(0) - 2 c) + \frac{3c}{n + 1} \\
T(n)               &= 2 c (n + 1) H_n + (T(0) - \frac{7 c}{2}) (n + 1) + 3 c \\
                   &\sim 2 c n \ln n
\end{align*}
$$
Here $H_n$ is the $n$-th harmonic number:
$$
H_n = \sum_{1 \le k \le n} \frac{1}{k}
    = \ln n + \gamma + O(1/n)
$$

The recurrence $x_{n + 1} - a_n x_n = f_n$ can always be reduced to a telescoping sum at the left side by multiplying by the summing factor:
$$
(a_n a_{n - 1} \ldots a_0)^{-1}
$$
$$
\frac{x_{n + 1}}{a_n a_{n - 1} \ldots a_0} - \frac{x_n}{a_{n - 1} \ldots a_0}
   = \frac{f_n}{a_{n + 1} a_n \ldots a_0}
$$


Proving the security of Nisan-Wigderson pseudo-random number generator

Here is Ran G.'s answer mentioned in the comments: Google gives quite nice results: 1, 2.


The term "true concurrency" arises in the theoretical study of concurrent and parallel computation. It is in contrast to interleaving concurrency. True concurrency is concurrency that cannot be reduced to interleaving. Concurrency is interleaved if at each step in the computation, only one atomic computing action (e.g. an exchange of messages between sender and receiver) can take place. Concurrency is true if more than one such atomic action take place in a step.

The simplest way of distinguishing both is to look at the rule for parallel composition. In an interleaving based setting, it would look something like this:

$$\frac{P \rightarrow P'}{P|Q \rightarrow P'|Q}$$

This rule enforces that only one process in a parallel composition can execute an atomic action. For true concurrency, a rule like the following would be more appropriate.

$$\frac{P \rightarrow P'\quad Q \rightarrow Q'}{P|Q \rightarrow P'|Q'}$$

This rule allows both participants in a parallel composition to execute atomic actions.

Why would one be interested in interleaved concurrency, when concurrency theory is really the study of systems that execute computation steps in parallel? The answer is, and that's a great insight, that for simple forms of message passing concurrency, true concurrency and interleaving based concurrency are not contextually distinguishable. In other words, interleaved concurrency behaves like true concurrency as far as observers can see. Interleaving is a good decomposition of true concurrency. Since interleaving is easier to handle in proofs, people often only study the simpler interleaving based concurrency (e.g. CCS and $\pi$-calculi). However, this simplicity disappears for concurrent computation with richer forms of observation (e.g. timed computation): the difference between true concurrency and interleaved concurrency becomes observable.

Standard equivalences like bisimulations and traces have the same definitions for true and interleaving based concurrency. But they may or may not equate different processes, depending on the underlying calculus.

Let me give an informal explanation of why interleaving and truly concurrent interaction are indistinguishable in simple process calculi. The setting is
a CCS or $\pi$-like calculus. Say we have a program

$$
   P \quad=\quad \overline{x} \ |\  \overline{y} \ |\  x.y.\overline{a} \ |\  y.\overline{b}
$$
Then we have the following truly concurrent reduction:
\begin{eqnarray*}
  P &\rightarrow& y.\overline{a} \ |\  \overline{b}
\end{eqnarray*}
This reduction step can be matched by the following interleaved steps:
\begin{eqnarray*}
  P &\rightarrow & \overline{x} \ |\  x.y.\overline{a} \ |\  \overline{b} \\
    &\rightarrow & y.\overline{a} \ |\  \overline{b}
\end{eqnarray*}
The only difference between both is that the former takes one step, while the
latter two. But simple calculi cannot detect the number of steps used to reach
a process.

At the same time, $P$ has the following second interleaved reduction sequence:
\begin{eqnarray*}
  P &\rightarrow & \overline{y} \ |\  y.\overline{a} \ |\  y.\overline{b} \\
    &\rightarrow & \overline{a} \ |\  y.\overline{b}
\end{eqnarray*}
But this is also a reduction sequence in a truly concurrent setting, as long
as true concurrency is not forced (i.e. interleaved executions are allowed even
when there is potential for more than one interaction at a time).


Finding the two largest of five small integers as quickly as possible

In my other answer I suggest that
conditional jumps might be the main impediment to efficiency. As a consequence,
sorting networks come to mind:
they are data agnostic, that is the same sequence of comparisons is executed no
matter the input, with only the swaps being conditional.

Of course, sorting may be too much work; we only need the biggest two numbers.
Lucky for us, selection networks have also been studied. Knuth tells us
that finding the two smallest numbers out of five² can be done with
$\hat{U}_2(5) = 6$ comparisons [1, 5.3.4 ex 19] (and at most as many swaps).

The network he gives in the solutions (rewritten to zero-based arrays) is

$\qquad\displaystyle [0:4]\,[1:4]\,[0:3]\,[1:3]\,[0:2]\,[1:2]$

which implements -- after adjusting the direction of the comparisons -- in
pseudocode as

def selMax2(a : int[])
  a.swap(0,4) if a[0] < a[4]
  a.swap(1,4) if a[1] < a[4]
  a.swap(0,3) if a[0] < a[3]
  a.swap(1,3) if a[1] < a[3]
  a.swap(0,2) if a[0] < a[2]
  a.swap(1,2) if a[1] < a[2]
  return (a[0], a[1])
end

Now, naive implementations still have conditional jumps (across the swap code).
Depending on your machine you can cirumvent them with conditional instructions,
though. x86 seems to be its usual mudpit self; ARM looks more promising since
apparently most operations are conditional
in themselves. If I understand the instructions
correctly, the first swap translates to this, assuming our array values have been
loaded to registers R0 through R4:

CMP     R0,R4
MOVLT   R5 = R0
MOVLT   R0 = R4
MOVLT   R4 = R6

Yes, yes, of course you can use XOR swapping
     with EOR.

I just hope your processor has this, or something similar. Of course, if you build the thing for this purpose, maybe you can get the network hard-wired on there?

This is probably (provably?) the best you can do in the classical realm, i.e.
without making use of the limited domain and performing wicked intra-word magicks.

Sorting and Searching
by Donald E. Knuth; The Art of Computer Programming Vol. 3 (2nd ed, 1998)
Note that this leaves the two selected elements unordered. Ordering them requires an extra comparison, that is $\hat{W}_2(5) = 7$ many in total [1, p234 Table 1].


What is the best solving algorithm for a game with stacks?

Denote the current state of the stacks as a $k$-vector $t=(t_1,\dots,t_k)$, where $k$ counts the number of stacks, $t_i$ is the number on the top of the $i$th stack, and I assume you have sorted the $t_i$ so that $t_1 < t_2 < \dots < t_k$.

Define a total order on state vectors as follows: $(t_1,\dots,t_k) \prec (u_1,\dots,u_\ell)$ if $k<\ell$, and $(t_1,\dots,t_k) \prec (t_1, \dots, t_j, u_{j+1}, \dots, u_k)$ if $t_{j+1} < u_{j+1}$.  Basically, this is comparing state vectors first by length (i.e., number of stacks), and comparing equal-length vectors by lexicographic order.

Now I suggest that you use the "greedy stays ahead" proof strategy, to try to prove by induction that if $A^i$ is the state of the stacks after $i$ steps of your algorithm and $O^i$ is the state after $i$ steps of the optimal algorithm, then $A^i \preceq O^i$.  I will let you work out the details of this proof to see whether you can prove it.  If you can do that, you will be done.  Letting $A$ be the final state after running your algorithm and $O$ the final state after running the optimal algorithm, it follows that $A \preceq O$.  Therefore, by the definition of $\prec$, $f(A) \le f(O)$.  This shows that your algorithm is as good as the optimal algorithm.

In other words, use "greedy stays ahead" to try to prove your algorithm correct, but you'll need to keep track of more information than just the number of stacks used so far; you need a more fine-grained measure of what it means to be "ahead" than just the number of stacks.


Find pairs of integers (a, b) in an array such that a = b + k in linear time - elements are not unique

If you must write out all of the pairs individually, then the overall problem takes quadratic time because the running time of this last post-processing step is $O(n^2)$.

If you are allowed to represent the output in a different way, then you can simply keep track of distinct pairs and associate them with a counter (see run-length encoding). Thus, you can compute the solution in $O(n)$ time using the following algorithm:

Initialize an auxiliary array (or hash map) $Aux$.
Perform a first linear scan of the input array $Arr$ and use the auxiliary array to keep track of how many times each of the elements appears. For example, $Aux[2]=3$ indicates that $2$ appears $3$ times in $Arr$.
Perform a second linear scan of the input array $Arr$. During the $i$th iteration, $a=Arr[i]$ and you must look for the element $b =a-k$, which appears $c =Aux[b]$ times in $Arr$. If $c \gt 0$, then you will add the pair $(a,b)$ to your solution, associated with the count $c$. Two special cases that must be considered at step 3:

If the pair already exists in your solution, you can simply increment the existing counter by $c$.
If $k=0$, you must add the pair $(a,b)$ only if $c \gt 1$. The counter associated with this pair will not be set to (or incremented by) $c$, but, rather, by $c-x-1$, where $x$ stores how many times we have seen $a$ before.


You can use the top-tree data structure.
It maintains a forest $F$ on $n$ nodes and supports (among others) each of the following operations in $O(\log n)$ time per operation:

Given an unmarked vertex $v$ mark $v$.
Given a marked vertex $v$ unmark $v$.
Given two vertices $u,v$ that belong to two different trees in $F$, add the edge $(u,v)$ to $F$ (thus merging two trees into one).
Given an edge $(u,v)$ of a tree in $F$, delete $(u,v)$ from $F$ (thus splitting the three into two).
Given a vertex $v$, report the distance to the marked vertex that belongs to the tree of $v$ and is closest to $v$.

This allows you to preprocess your tree in time $O(n \log n)$: build the forest $F$ on $n$ nodes by adding the edges of the tree one by one (so that, at the end, $F$ contains the input tree), then mark each hotspot.

To answer a query $(a,b,c)$ in time $O(\log n)$ proceed as follows:

Delete $(a,b)$ from $F$ in time $O(\log n)$.
Find the distance $d$ to the marked vertex that is closest to $c$. This takes $O(\log n)$ time and is exactly the answer to the query.
Re-add $(a,b)$ to $F$ in time $O(\log n)$.
Return $d$.


right and left derivatives of a cfg from parse tree?

What you wrote are not derivations, they are grammars.

The leftmost derivation in your case is $A \to BC \to 0DC \to 0DDE \to 0D0E \to 0D01$. I'll leave you to figure out the rightmost derivation.


Online and parallizeable set intersection algorithm

Apparently this is a distributed systems problem.  You have ~ 10 stacks, each with up to 10 million items at a time, and each stack living on a different machine.

Here is one simple candidate solution.  Have a separate "monitor" machine, whose sole purpose is to continually compute the intersection.  Any time one of the stacks is modified, the machine storing that stack should send a message to the monitor message describing the change.  (These diffs can be batched, depending upon your latency requirements.)

Now you have all the data on a single machine, the monitor machine.  When running on a single machine, you can completely avoid all of the concurrency issues associated with multithreading or distributed systems -- e.g., the need for synchronization, locks, etc.

Moreover, the amount of data is small enough that it could easily be stored in the available RAM on that monitor machine.  (Why?  If each entry is large, hash it first using a good hash function and a large enough hash output that you won't see collisions.  If each hash value is 128 bits, then storing all 100 million hashed items takes 1.6GB.  If you use SHA256 truncated to 128 bits as your hash function, by the birthday paradox, the chances of encountering a hash collision are incredibly small.)

Once all of the data is living in RAM on a single machine, the problem becomes much easier.  For example, one approach would be to build an index data structure: a hashmap that maps each key to a 10-bit bitmap that indicates which of the stacks it is stored on.  You can easily update this hashmap as the individual stacks change.

You can also easily use this hashmap to compute the intersection: just have a doubly linked list threaded through the entries of this hashmap where the bitmap is equal to 11111111111 (all 1's).  Any time a bitmap changes from 11111111111 to something else, you remove it from the doubly linked list.  Any time a bitmap changes from something else to 11111111111, you insert it into the doubly linked list.

The amount of data you need to transfer from other machines to the monitor machine is very small, especially since you only need to send the hashed items to the monitor, not the original items.  If each of the 10 machines will do at most 4k push/pop's per second (taken from your question), then that's 64 KB of hashed data per second per machine.  If we add another 32 bytes or so of overhead (packet headers), that's about 200 KB/s of data out of each machine, or about 2 MB/s of data into the monitor machine -- a very manageable amount.  On a 1 Gbps Ethernet link you won't notice this, and you might not notice it even on a 100 Mbps link.  You can reduce the amount of traffic by a factor of 2-5x by batching such messages and/or by using a shorter hash.

This should provide an efficient algorithm to compute the intersection, and keep it updated on the fly as each of the stacks change.


Count bridging edges in a family of two component forests

I have an idea that will efficiently get you "halfway there". Hopefully you or someone else can think of a way to extend this to get the "other half" efficiently.

For a given edge $uv$ in $T$, let me rename the two subtrees that deleting $uv$ would create as $F_u^{uv}$ (this is the subtree containing $u$) and $F_v^{uv}$ (the one containing $v$). Denote by $E_u^{uv}$ the subset of $E$ for which both vertices belong to the vertex set of $F_u^{uv}$ (i.e., the graph edges that are "completely within" the $u$-subtree of $F$), and similarly for $E_v^{uv}$.

For each edge $uv$ in $T$, if we can efficiently compute both $|E_u^{uv}|$ and $|E_v^{uv}|$ , then we can compute $c(uv)$ simply by subtracting these two counts from the total number $|E|$ of edges.

Half of the necessary counts can be computed in $O(|E|)$ time as follows:

Root $T$ arbitrarily and consider all edges to be directed "down", away from the root.
Preprocess $T$ for fast lowest common ancestor (LCA) queries.
For each graph edge $uv$:

Increment a counter $\Delta_x$, where $x$ is the LCA of $u$ and $v$ in $T$.

Compute $|E_v^{uv}|$ as $\Delta_v + \sum_{c:vc\in T}|E_c^{vc}|$ for each $T$-edge $uv$ using a single postorder DFS traversal (here $u$ is the unique parent of $v$ in $T$).

Since LCA can be computed in constant time after linear preprocessing, the above takes only $O(|E|)$ time and space to compute all $n-1$ of the $|E_v^{uv}|$ values. (I think of $|E_v^{uv}|$ as the number of edges "completely below" $uv$.) But it does not compute any of the $n-1$ $|E_u^{uv}|$ values -- the numbers of edges "completely above" $uv$ -- and I can't think of an efficient way to do so.

You can of course reroot $T$ at a different vertex and repeat the exercise: The directions of some edges will be reversed, and the $|E_v^{uv}|$ values computed for each of them can be used for the $|E_u^{uv}|$ values in the original rooting. You could repeat this until all edges have been covered in both directions -- if you were lucky enough to be given a $T$ that is a Hamiltonian path, just 2 rootings would suffice, but in general "covering" all edges this way could require as many as $n-1$ rootings (think of a star tree), which leaves us no better off than the original method.

Ideas anyone?


Get nodes that are participating in any cycle in a graph

First use Tarjan algorithm to find all of the bridges in the graph. Then remove all of them. Remaining graph should be made of some cycles, such that all of them have at least one common vertex, otherwise we can return false for all vertices. Is possible to check this with DFS, further reasoning is easy, total running time is $O(|V|+|E|)$.


$T(n)$ is number of comparisons done when quicksort sorts an array of length $n$.

To sort an array of length $n$, we must split it into two halves and sort the halves.  To split the array, we must compare each element of the array against the pivot, which is $n$ comparisons.  (Perhaps $n-1$ if the pivot is an actual array value rather than, say, an estimate of the median.) Then, we must recursively sort the two halves, which requires $T(n/2)$ comparisons each.


give potential function - binary heap - extract-min in amortized const time and insert in log amortized time

Let's review the potential function method. Suppose that the $i$th operation costs $c_i$ and the value of the potential function at time $i$ is $\Phi_i \geq 0$, and that $\Phi_0 = 0$ (the potential at the beginning). Define the amortized operation costs by $a_i = c_i + \Phi_i - \Phi_{i-1}$. Then
$$
\sum_{i=1}^n a_i = \sum_{i=1}^n (c_i + \Phi_i - \Phi_{i-1}) = \sum_{i=1}^n c_i + \Phi_n - \Phi_0 \geq \sum_{i=1}^n c_i.
$$
This means that the total amortized cost $\sum_{i=1}^n a_i$ is an upper bound on the actual cost $\sum_{i=1}^n c_i$, which is what we want.

In this argument there is no need to assume that the amortized costs are non-negative – the argument works even if they can be negative. However, if some amortized costs are negative, then you can probably improve the amortized analysis.

Back to your case. Suppose that inserting the $n$ element costs $\log n$, and extracting the minimum when there are $n$ elements also costs $\log n$. This suggests a charging argument in which we charge the insertion of the $n$th element by $2\log n$, and discharge the extra $\log n$ when extracting the minimum the next time that there are exactly $n$ elements. This gives an amortized time of $O(\log n)$ for insertion, and $0$ for extract-min.

We can give a similar argument using a potential function. We choose a potential function of the form $\sum_{i=1}^n \log i$, where $n$ is the current number of elements. Under this potential function, insertion costs $2\log n$ and extract-min costs $0$.

Note that $\sum_{i=1}^n \log i = \log n! \approx n\log n$, so this differs from your suggestion (appearing in the comments) of using $n$ as a potential function; your suggestion doesn't work, since under it extract-min costs
$$
\log n + n - (n-1) = \log n - 1.
$$
Taking a closer look at your question, you are actually using the potential function $n\log n$, which is very similar to what I suggest. This potential function does work.


Is FACTORIZATION or PRIMES known to be in LOGSPACE

Factoring is not known to be even in $\mathsf{P}$.

Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).


Metrics for measuring the tradeoff between efficiency and effectiveness in Information Retrieval

I assume that your question is being put in the context of boolean retrieval. It seems that there is not a single metric that takes into account both efficiency and effectiveness and provide a theoretical framework for IR evaluation.

This is mainly because these two issues can sometimes be quite independent between each other. We use certain methods to build inverted indexes in order to mitigate memory issues that arise when we try to index large collections of documents. Some of these methods (such as hash tables) provide fast access to the dictionary (in $O(1)$ time) but fail to accomodate proximity queries (the sort of "find documents that have the word "Beatles" near the word "Animals"). Moreover there are implications arising if we are to index a collection that might change in size and content. Usage of B-trees can overcome these issues as these structures permit an ordering of their contents.

On the other hand some other methods (such as k-gram auxiliary indexes) charge us with additional processing time but offer a more broad range of queries that can be computed (complex wildcard queries such "co*ter*ed"). In general this results in a more powerful IR system in the sense of a wider capability in answering queries.

There is of course the "user happines" measure that takes into account the extent to which the user's information need is satisfied by the system but this is not always the case as users tend to take into consideration several other factors like the user interface which is independent of the system's performance.

In my humble opinion the issue of the relation between effectiveness and efficiency is something that can be examined more thoroughly in the "real" context of an implemented IR system. It is in this setting that more concrete conclusions can be extracted about the effect that different indexing methods have on the performance of the IR system.

An excellent resource in these topics is the following book by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze
http://nlp.stanford.edu/IR-book/information-retrieval-book.html


"Any problem whose domain is finite is always Decidable", is true or false?

It's not so clear what is "a problem whose domain is finite". Let me assume that what is meant by this is a finite language. Every finite language is decidable. The Turing machine compares the input to each word in the language, accepts if it finds a match, and rejects otherwise.

This answers your first question. Your second question is a special case of the first one.


Trying to tag parts of a word and keep track of any changes that happen to those parts

You can use sequence alignments with a suitable score. You then get something like this:

$\qquad\displaystyle
\begin{array}{cccccc}
  r & e & p & e & a & t & e & d \\
  r & - & p & e & - & t & e & -
\end{array}$

Now, if you have marked the original word, you can read off that -- according to your alignment score -- only "r" is left from the prefix, "pet" from the stem and "e" from the suffix.

The score makes a difference when parts may be assigned to e.g. prefix or stem. Levenstein/edit distance and Damerau-Levenstein distance may be good starting points. Play around with the penalties a bit; note that you can assign costs depending on whether you match against prefix, stem or suffix (if you have marked the original words) and use things like affine gap costs.