Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?

The reduction is possible.

I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d_{i}$, we make $d_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation.

Say the graph we want to solve minimum feedback arc set in is (V, E). We'll build a graph (V', E') such that (V', E') has a feedback arc set of size k or less if and only if (V, E) has a feedback arc set of size k or less, and the maximum outdegree of any node in (V', E') is two.

Let $d_{i}$ be the outdegree of node $v_{i}$ in $(V, E)$. Corresponding to node $v_{i}$ in $V$ we'll have nodes $v'_{i, 1} \dots v'_{i, d_{i}}$ in $V'$. For every node $v'_{i, j}$ we'll also have $d_{i}$ nodes $x'_{i, j, 1}, \dots, x'_{i, j, d_{i}}$.

Corresponding to edge $e_{i} = (s_{i}, t_{i})$ from node indexed $s_{i}$ to the one indexed $t_{i}$ in $E$, we'll have the node $e'_{i}$ and nodes $y'_{i, 1}, \dots, y'_{i, d_{t_{i}}}$ in $V'$.

For all vertices $v_{i} \in V$, let $id_{i, k}$ be the index of the $k$th edge leaving node $i$. In $E'$, for every $1 \leq j \leq d_{i}$ we'll have the edge $(v'_{i, j}, x'_{i, j, 1})$ and further for $1 \leq k < d_{i}$ the edge $(x'_{i, j, k}, x'_{i, j, k+1})$ and for $1 \leq k \leq d_{i}$ the edge $(x'_{i, j, k}, e_{id_{i, k}})$.

For all edges $e_{i} = (s_{i}, t_{i})$ in $E$, we have the edges $(e'_{i}, y'_{i, 1})$, for $1 \leq j < d_{t_{i}}$ the edge $(y'_{i, j}, y'_{i, j+1})$, and for $1 \leq j \leq d_{t_{i}}$ the edges $(y'_{i, j}, v'_{t_{i}, j})$.

By the way we defined the nodes, clearly every node has outdegree at most two.

I'll embed an image of an example of the reduction at the bottom of the proof.

Now we'll prove the main claim.

Clearly if $(V, E)$ has a feedback arc set of size $k$, so does $(V', E')$ (cut edge $(e'_{i}, y_{i, 1})$ for every edge $e_{i})$ cut in the original graph).

For the other direction, Take any feedback arc set of size $k'$ in $(V', E')$. We'll build a feedback arc set of cost $k \leq k'$ for $(V, E)$, by cutting edge $e_{i}$ if and only if one or both of the following hold:

One of the edges corresponding to $e_{i}$ in $E'$ is cut in $(V', E')$
For all of $v'_{s_{i}, 1}, \dots, v'_{s_{i}, d_{s_{i}}}$, at least one edge corresponding to them has been cut.

Note that the second case only happens if we make at least $d_{s_{i}}$ cuts in the copies corresponding to node $v_{s_{i}}$, so $k \leq k'$. Now assume that with these cuts $(V, E)$ has a directed cycle $v_{p_{1}}, \dots, v_{p_{m}}$. Then for the copies corresponding to $v_{p_{j}}$, at least one, say $v'_{p_{j}, h_{j}, 1}$ has has none of its or its $x'$s edges touched, otherwise by condition 2 for cutting an edge we would have no edges leaving $v_{p_{j}}$ in our solution in $(V, E)$.

But then $(V', E')$ also has a directed cycle: the cycle goes through $v'_{p_{j}, h_{j}}$ to $x'_{p_{j}, h_{j}, 1}$ to $\dots$ to $x'_{p_{j}, h_{j}, out_{p_{j}, p_{j+1}}}$ (where $out_{a, b}$ is the index in the edges out of $a$ of the edge to $b$) to $e'_{edi_{p_{j}, p_{j+1}}}$ (where $edi_{a, b}$ is the index of the edge from $a$ to $b$) to $y_{edi_{p_{j}, p_{j+1}}, 1}$ to $\dots$ to $y_{edi_{p_{j}, p_{j+1}}, h_{j+1}}$ to $v'_{p_{j+1}, h_{j+1}}$.

Since a contradiction followed, we must have that the cuts in $(V, E)$ form a feedback arc set, completing the proof.

Here's an image of the reduction graph for $V = \{1, 2, 3, 4, 5\}$, $E = \{(1, 2), (1, 3), (2, 4), (2, 5), (4, 1), (3, 1)\}$. Sorry for the massive size. The rectangles at the top-right show the graph $(V, E)$.


Trick/insight to I implement given boolean function with minimum numbers of given gate

There is no trick.  There is no efficient method.  The circuit minimization problem is NP-hard (in fact $\Sigma_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-hard, too.  That should tell you that there is no systematic approach that always works and is reasonably efficient.  Instead, you will have to use heuristics and trial-and-error.  For instance, you might have to try multiple methods and take the best circuit you can find among all of them.


What is the intuition behind the way of reading off a dual optimal solution from simplex primal tabular in CLRS?

Answer My Own Question:

I found that the interpretation in Section 8.3 of the textbook "Introduction to Linear Algebra; 4th Edition" by Gilbert Strang is quite intuitive and much easier to understand than that in CLRS.

Note: The textbook of Gilbert Strang takes the "min" program as the primal and the max program as the dual. I follow this convention. Besides, it adopts the matrix form of linear programs, which, in my opinion, helps a lot in understanding the simplex method and the duality theory.

Quoted from the textbook:

  The $m$ inequalities $Ax \ge b$ were changed to equations by introducing the slack variables $w = Ax - b$:
  $$\begin{bmatrix} A & -I \end{bmatrix} \begin{bmatrix} x \\ w \end{bmatrix} = b$$ and
  $$\begin{bmatrix} x \\ w \end{bmatrix} \ge 0.$$
  Every simplex step picked $m$ columns of the long matrix $\begin{bmatrix} A & -I \end{bmatrix}$ to be basic, and shifted them (theoretically) to the front. This produce $\begin{bmatrix} B & N \end{bmatrix}$. The same shift reordered the long cost vector $\begin{bmatrix} c & 0 \end{bmatrix}$ into $\begin{bmatrix} c_{B} & c_{N} \end{bmatrix}$. The stopping condition, which brought the simplex method to an end, was $r = c_N - c_B B^{-1} N \ge 0$. At the stopping moment, the cost was as low as possible:
  $$cx^{\ast} = \begin{bmatrix} c_{B} & c_{N} \end{bmatrix} \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix} = c_B B^{-1} b.$$
  If we can choose $y^{\ast} = c_B B^{-1}$ in the dual, we certainly have $y^{\ast}b = cx^{\ast}$. The minimum and maximum will be equal.

It turns out that $y^{\ast} = c_B B^{-1}$ is exactly the one read off in the final slack form of the primal program in the way CLRS describes. Its feasibility in the dual is due to the stopping condition $r = c_N - c_B B^{-1} N \ge 0$.


Adding a node between two others, minimizing its maximum distance to any other node

Introduction

This answer is in two parts.

The first is an analysis of the problem mixed with a sketch of the
algorithm to solve it. As it is my first version, it is detailed, but
results in an algorithm that is a bit more complex than needed.

It is followed by a pseudo-code version of the algorithm, written sometime later, as the algorithm was clearer. This pseudo-code is more
direct, and somewhat simpler, but probably easier to understand after
reading the first part.

In retrospect, the more important ideas are:

to see that the maximum distance of a node to the new node C, as a
function of the length of $(A,C)$, is given by the superposition of
roof shaped (inverted V) curves, characterized by their top,
associated to nodes of the graph.
to see that irrelevant curves can be eliminated efficiently by a
scan in monotonic order of abscissa of tops (with minimum backtrack).
then minimal points can be enumerated simply by intersecting the remaining
curves two by two, again in monotonic order of abscissa of tops.

Sketch of an algorithm

NOTE: I changed the initial presentation of the question to get a more
standard view of graphs, by considering that the edge $(A,B)$ is
replaced by a new node $C$ and two edges $(A,C)$ and $(C,B)$ with the
same total length as $(A,B)$.

Let $(A,B)$ be the distinguished edge, and let $l$ be its length. Let
$e$ and $n$ be respectively the number of edges and the number of
nodes in the graph.

First you remove the edge $(A,B)$. Then, for every node $U$ of the
graph, you compute the distance $\alpha(U)$ between $A$ and $U$, and
the distance $\beta(U)$ between $B$ and $U$. This can be done with
Dijkstra's shortest path algorithm, in time $O(e+n\log n)$.

Then you add a new node $C$ with an edge $(A,C)$ and an edge $(C,B)$,
of length respectively $a$ and $b$, such that $a+b=l$. The
length $a$ is not known, and is to be found so as to minimize the
distance of the most remote node to node $C$. The distance of $C$ to
$A$ or $B$ may be 0.

The difficulty of the problem is that the node most distant from $C$
via $A$ may be close to $C$ via $B$, and thus does not matter. Also, a
node closer to $C$ via $A$ than via $B$ may inverse that situation as
$C$ moves between $A$ and $B$, i.e. as $a$ varies in $[0,l]$.

We consider three sets of nodes in the graph, forming a partition of
all nodes:

the set $N_A$ of nodes that are always closer to $C$ via $A$
independently of the value of $a$:
$N_A=\{U|\alpha(U)+l\leq\beta(U)\}$
the set $N_B$ of nodes that are always closer to $C$ via $B$ independently
of the value of $a$:
$N_B=\{U|\beta(U)+l\leq\alpha(U)\}$
and $N_{AB}$ the set of nodes that can be closer to $C$ via $A$ or
via $B$, depending on the value of $a$, actually closer via $A$ for
smaller values of $a$, and closer via $B$ for larger values of $a$ in $[0,l]$:
$N_{AB}=\{U\mid\alpha(U)+l>\beta(U) \wedge \beta(U)+l>\alpha(U)\}$

Let $U_A$ the node in $N_A$ most remote from $A$, and $U_B$ the node
in $N_B$ most remote from $B$.

No other node in $N_A\cup N_B$ is ever more distant from $C$ than the
more distant of these two nodes, whatever the distance $a$ of $(A,C)$.
Hence all other nodes in $N_A\cup N_B$ can be discarded for the
computation of the optimal value of $a$.

Note that it may happen that $N_A$, or $N_B$, or both, are empty. In
which case, the corresponding nodes $U_A$ and/or $U_B$ do not exist.

We will build a distance curve on a plane with coordinate $(x,y)$, which will
ultimately represent the longest distance $y$ of a node from $C$ as a
function of the distance $x=a$ of $C$ from $A$. Hence $x=a\in[0,l]$

This distance curve is actually a zig-zag composed of segments angled $\pm
45^\circ$. Once it is built, the point minimizing the longest distance
is to be found in the minimal points of the curve. There may be
several such points. All these points have to be computed, and then
compared.

We describe below how to compute them.

Actually, we consider a collection of simpler distance curves, with only one or
two segments in the interval $[0,l]$, such that the longest distance of
a node from $C$ is always on or above the curve. The final curve is
obtained by taking for every value of $x$ the maximum value of $y$
given by one of the distance curves. This can be done formally by computing the
intersection of the segments in an ordered fashion.

First we have (at most) two distance curves composed of only one segment. These
are the curves corresponding to the distance of $U_A$ and $U_B$ to
$C$. The first is upward at a $45^\circ$ angle, and the second is
downward at a $45^\circ$ angle.

Assuming no other node is ever more distant from $C$, the optimal
value of $a$ is the abcissa of their intersection. At that abscissa,
that value for $a$, the nodes $U_A$ and $U_B$ are at the same distance
from $C$. Hence the distance is minimum when $a$ satisfies the
equation $\alpha(U_A)+a=\beta(U_B)+b$. Since $a+b=l$, this gives
$\alpha(U_A)+a=\beta(U_B)+l-a$, and finally
$a=(\beta(U_B)-\alpha(U_A)+l)/2$. This corresponds to a distance
$y=(\alpha(U_A)+\beta(U_B)+l)/2$ of both nodes to $C$.

Together, the two curves give a V shaped curve, with a minimum at the
point just computed.

But we also have to account for all the nodes in $N_{AB}$. The
distance of a node $U\in N_{AB}$ to $C$ first increases with $x$ while
the shortest path goes through $A$, them it decreases with $x$ when
the shortest path goes through $B$. Hence, the corresponding distance curve is
formed of two segments, roof shaped, with a maximum at an abscissa
such that the distance to $C$ is the same through $A$ or through $B$.
This gives the equation $\alpha(U)+a=\beta(U)+b$. Resolving it as
above, we get $x=a=(\beta(U)-\alpha(U)+l)/2$, and
$y=\alpha(U)+\beta(U)+l)/2$. We note $T_U$ (for Top of $U$) the point
with these coordinate. The top $T_U$ characterizes the roof shaped distance
curve for node $U$ since the slope of both side is $\pm 45^\circ$.

Now all the difficulty of the problem is that several nodes $U\in
N_{AB}$ may be such that $T_U$ is above our first V-shaped curve,
which will lead to the final zig-zag line.

But, we first can eliminate all nodes $U\in N_{AB}$ such that $T_U$ is
below the V-shaped distance curve, as they will not ever contribute to the
longest distance. This is easily done and is skipped here for clarity.

Then we want also to eliminates all nodes $U\in N_{AB}$ such that
their roof-shaped curve is always below the curve of another node
$V\in N_{AB}$. This is determined by the position of their tops, and
we say that $T_V$ dominates $T_U$, or that $V$ dominates $U$. Actually
$T_V$ and $T_U$ are in a domination relation iff the absolute value
of the abcissa difference is less than the absolute value of the
ordinate difference. The dominating node/top is the one with the
highest ordinate.

For this purpose, we first sort all tops of the remanining nodes of
$N_{AB}$ in ascending order of increasing abscissa. This is done in
time $O(n\log n)$.

Then we remark that if top $T_U$ dominate a non adjacent top $T_V$,
then any intermediary top $T_W$ dominate $T_V$, or is dominated by
$T_U$, or both. Hence, to eliminate all nodes/tops that are dominated,
on can simply proceed from left to right (by increasing abscissa),
comparing only adjacent nodes, and removing any that is dominated.  If
the node on the right is dominated, it is removed and the node on the
left is compared again to the next right. If the node on the left is
dominated, it is removed and the node on the right is then compared
with the previous one on its left. If none dominates the other, then the node on left
is kept, and the node on right
is then compared with the next right. This is repeated until the
rightmost node/top has been thus processed, in time $O(n)$.

Whatever nodes have been kept do contribute to the final curve, in
left to right order of their tops, with the line for $U_A$ at the left
and the line for $U_B$ at the right, if they exist. The minima are
easy to compute by considering the intersections of the contributing
curves from left to right, in time $O(n)$.

Finally, the abcissa for the smallest distance of all nodes to $C$ may be
found by a linear scan of all minima for the lowest ones. They may
actually be several such abscissa, i.e. values for the length $a$ of
edge $(A,C)$.

If the distances have to be integers, the abscissa of the minima can be
rounded up or down.

The time complexity of the algorithm is: $O(e+n\log n)$.

With thanks to user3153970 who remarked that my initial solution was
not quite correct.

Pseudo-code version

The procedure described in the analysis of the problem is modified or
improved in some ways.

the length l is changed to d to avoid confusion with the number 1.
for simplification, the V curve is replaced by two tops of roof curves placed on
both end of the interval [0,d].
the sets $N_A$ and $N_B$ need not be created. Only $d_A$ and $d_B$
are needed, briefly, to crate the two extra tops.
the set $N_AB$ is not created either, only the corresponding set
(actually a multiset, or bag, that may be implemented as a list) of tops, as two distinct nodes may
produce the same top, if at the same distance of A and B.

(bugs are provided free of charge)

d := distance (A,B)
none := -1     % programming trick - none is for distances to be ignored %
Remove the edge (A,B) from the graph.
Using Dijkstra's shortest path algorithm, for every node $U$ compute its shortest
    distances α(U) and β(U) to respectively A and B.
d_A := none
d_B := none
  % We use lists of pairs, representing the [x,y] coordinate of points, where the %
  % abcissa x stands for the choice of length (A,C), and the ordinate y stands is the %
  % distance of some node to C. %
  % The call first(L) returns a pointer to the first pair of list L. %
  % Given a pointer t to a pair, t.x and t.y give the two components of the pair, %
  % and the functions prev and next return a pointer to the previous or the next pair, or %
  % NIL if it does not exist. The call add([a, b], L) adds the pair [a, b] to the list L. %
  % The call remove(t) removes the element pointed by t from its list. %
For every node U do
T := []     % T is the list of tops of curves for individual nodes %
    if    α(U)+d ≤ β(U) then d_A := max(d_A, α(U))
    elsif β(U)+d ≤ α(U) then d_B := max(d_B, β(U))
    else add( [(β(U)-α(U)+d)/2, (β(U)+α(U)+d)/2], T)
% Instead of V curve, create dummy tops at ends of [0,d] interval %
if d_A ≠none then add( [d, d_A+d], T)
if d_B ≠none then add( [0, d_B+d], T)
Sort T in increasng order of abscissa
% Remove from T all tops that are dominated by another top %
t1 := first(T)
t2 := next(t1)
Repeat
    if abs(t1.x-t2.x) ≤abs(t1.y-t2.y)
    then  % one top dominates the other %
        if t1.y≥t2.y
            then  % t1 dominates %
            remove(t2)
            t2 := next(t1)
            if t2=NIL then exit loop
        else % t2 dominates %
            remove(t1)
            t1 := pred(t2)
            if t1=NIL then
                t1 := t2;
                t2 := next(t1)
                if t2=NIL then exit loop
     else % neither top dominate the other %
         t1 := t2
         t2 := next(t1)
         if t2=NIL then exit loop
% Compute all local minima %
M := []  % M is the list of minima, where roof shaped curves intersect, %
         % or intersect the boundaries of the interval [0.d]. %
t2 := first(T);
if t2.x≠0 then add( [0, t2.y-t2.x], M)
repeat
    t1 := t2
    t2 := next(t1)
    if t2=NIL then exit loop
    add( [(t1.y-t2.y+t1.x+t2.x)/2, (t1.y+t2.y+t1.x-t2.x)/2], M)
if t2.x≠d then add( [d, t2.y-d+t2.x], M)
Select in M the pairs with the smallest ordinates. Their abcissas are all
    the possible answers to the problem.

If the solutions must be in integer values, it is possible to round
the coordinates of the points in M to the nearest integer(s), before
selecting the pairs with smallest ordinates. However some more
analysis is needed to check whether it can involve passing over a top,
and whether abcissas and ordinates are always integer simultaneously.
This is left to the reader as an exercise.

All bug reports are welcome.


What are good counter-examples when training an apple classifier?

A standard approach is to pick a standard image bank of other images that you might run into that aren't apples, and use that as your other class.  The way you figure out what kind of images you need is: figure out what kind of images your classifier might be run on, and try to make the training set as similar as possible to the kinds of images that it will be run on in production.


Describing explicitly the MyHill-Nerode classes created by a language

Your classes are correct, and one can also describe them in words: words containing no $a$, words containing a single $a$, words containing at least two $a$s. When described in this fashion, it is clear that the every word belongs to exactly one class.

However, there is no reason to use the Myhill–Nerode criterion to prove that a language is regular. Instead, you can use its vast generalization and give a DFA or NFA for the language. In the other direction, there is no need to describe all classes, only infinitely many; this already shows the language is not regular.


The method you propose in your answer is mostly correct. $L_2$ is, indeed, decidable because it's regular. But you can't argue that $L_1\cap L_2$ is decidale because it is a subset of the decidable language $L_2$: every language is a subset of the decidable language $\Sigma^*$ but that doesn't mean that every langauge is decidable.

Hint. You chose the tag closure-properties, which shows you're on the right lines. $L_1$ is either decidable or recognizable; $L_2$ is both. What do you know about the intersection of two decidable/recognizable languages?


Reframing decision, counting, enumeration, and search as optimization

Search problems are in NP if you can verify a solution in polynomial time.

Counting problems are ♯P if you're counting the number of solutions to an NP search problem.

Enumeration problems are not particularly special.

See https://en.wikipedia.org/wiki/Computational_problem.


Why, intuitively, does the Ackermann function require $\mu$-minimisation?

Roughly speaking, a function is primitive recursive if it can be computed by a program in which all loops are bounded ahead of time. Concretely, we can consider the LOOP programming language, which has the following instructions:

Set $x$ to zero.
Increment $x$.
Run a piece of code $x$ times.

We can use LOOP to compute one-argument functions using some input/output convention, say the input is in $x$ and the output is in $y$.
If the program has no loops, then $y \leq x + C$ for some constant $C$. If the program has no nested loops, then $y = O(x)$. If it has nesting depth 2 (a loop can appear within another loop, but that's it), then $y = O(x^C)$ for some constant $C$. More generally, if the program has nesting depth $d$, then $y$ can be bounded by a function on level $d$ on the Ackermann hierarchy.
The Ackermann function is constructed in such a way that it doesn't belong to the Ackermann hierarchy, and so cannot be computed by a LOOP program. In brief, it grows too fast.

Growing too fast isn't the only reason for not being primitive recursive. Indeed, using diagonalization we can construct Boolean recursive functions which are not primitive recursive. Let $f_i$ be an effective enumeration of all primitive recursive functions, and define
$$
f(n) = \begin{cases}
1 & \text{if } f_n(n) = 0, \\
0 & \text{otherwise}.
\end{cases}
$$
The function $f$ is recursive but, by construction, not primitive recursive.


There are no natural problems that I am aware of that have that property. There are two problems which are "close", however.

The Minimum Circuit Size Problem is, given a truth table of a boolean function $f$ and an integer $k$, is $f$ computed by a circuit of size at most $k$? Note $MCSP \in NP$, and it is widely expected that $MCSP$ is "hard"; however, it is not known that $MCSP$ is $NP$-complete, and while it is easy to conjecture that it might be, there is also some evidence that it is not.

The Unique Games Conjecture states that approximating the value of a certain combinatoric problem is $NP$-hard. This problem is not strictly in $NP$ because its decision version is a "promise problem". Nevertheless, the UGC is one of the premier open questions of computer science today and there is little consensus on whether it is true or not.


Is the memory usage of total languages deterministic?

Because total programs cannot run forever they cannot use infinite memory. You can know maximum, and best case cost from looking at what algorithm is implemented. Checkout these wikipedia pages to see the relationship between different grammars, algorithms, and machines:

"https://en.wikipedia.org/wiki/Complexity_class"
"https://en.wikipedia.org/wiki/Computational_complexity_theory"
"https://en.wikipedia.org/wiki/Chomsky_hierarchy"


All languages are regular, as unions of singleton languages

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.


Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?


Disjoint Set - Tree Implementation with Union-By-Rank and Path Compression

I assume you are talking about Union Find data structure. When you do UNION($x,y$), you just change the parent pointer of one of $x$ and $y$ to root of the other. The depth of resulting tree is not exactly equal to larger depth of two trees because, initially if the depth of two trees are equal, then the depth of new tree formed will be $1$ plus the old depth.

Coming to the original question, path compression takes place when we do FIND operations and not during UNION operations. When we do FIND($x$), we first find root $p$ of $x$ and for all ancestors of $x$ and also for $x$, we change the root pointer to $p$. You can see that this can reduce the height of tree drastically. After some FIND operations, next FIND operations will take time close to $O(1)$. This is formalised by saying that $n$ FIND operations take time $O(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function.


Algorithm to find smallest number divisible by N with sum of digits as N

Assuming that "number" means "positive integer", every number divisible by $N$ must be at least $N$. Conversely, $N$ has the same digit sum as itself. Therefore the answer is simply $N$, as your two examples demonstrate.


Push-down automaton for a language with number of 1s double than 0s

Consider this algorithm:

Initialize a variable $x := 0$.
Scan the string, left to right. If you see $1$, set $x := x + 1$, if you see $0$, set $x := x - 2$.
When you are done, accept iff $x = 0$.

It should be obvious that it recognizes your language. Can you figure out a way to implement it replacing the counter with the stack?


Hash table collisions: why use a linked list if we can use a hash set?

An hash set is an hash table.  Using an hash set to handle collisions in an hash table is equivalent to using a bigger hash table, with an hashing function which is a combination of the hashing functions of both level.

In other words, you'd probably be better with a bigger initial table (for instance there is no risk of resonance between the two hash functions which could lead to an higher collision rate than expected at the second level).


Sphere packing inequality for error-correcting codes

For a codeword $x$, let $B_k(x)$, the ball of radius $k$ around $x$, consist of all words at distance at most $k$ from $x$. Notice that
$$|B_k(x)| = \sum_{i=0}^k \binom{m+r}{i}. $$
If the code supports correcting up to $k$ errors, then the sets $\{ B_k(x) : x \in C \}$ must be disjoint. The code contains $2^m$ many different codewords, hence we get
$$
2^m \sum_{i=0}^k \binom{m+r}{i} \leq 2^{m+r},
$$
which is the same as your inequality. Here $m+r$ is the length of each codeword, and $2^{m+r}$ is the number of possible vectors.

If your code is $q$-ary rather than binary, then the same calculation shows that
$$
\sum_{i=0}^k (q-1)^i \binom{m+r}{i} \leq q^r.
$$


Store the window in a balanced binary search tree.  Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it.  Each of those operations can be done in $O(\log k)$ time, so the total running time to process $n$ items will be $O(n \log k)$.


$\newcommand{\I}{\mathbb{I}}\newcommand{\E}{\mathbb{E}}$Given our observed variables $x = \{x_i\}$, hidden variables $z = \{z_i\}$ and distribution parameters $\theta = \{(\mu_j, \sigma_j)\}$, let's define the complete-data log-likelihood as
$$
\begin{align*}
\ell_c(\theta) &= \sum_{i=1}^n \log \Pr[x_i, z_i|\theta] = \sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log (\Pr[x_i|\theta_j] \Pr[z_i=j|\theta])
\end{align*}
$$ where $\I[\cdot]$ is the indicator function, $\Pr[x_i|\theta_j]$ is the probability of observing $x_i$ given the $j$th Gaussian and $\Pr[z_i=j|\theta]$ is the mixing weight of the $j$th distribution (i.e., the probability of observing the $j$th hidden variable). This is the model we have if we somehow knew which Gaussian generated a given data-point. We obviously don't know, so we would like to compute the expected value of this complete-data log-likelihood. That is, what is the expected outcome of this full-knowledge formulation? To do that let us define the $Q(\theta^t|\theta^{t-1})$ function as
$$
\begin{align*}
Q(\theta^t|\theta^{t-1}) &= \E\left[\sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log \Pr[x_i, z_i = j| \theta]\right]\\
 &= \sum_{i=1}^n \sum_{j=1}^k \E[\I[z_i = j]] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \Pr[z_i = j | x_i] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \underbrace{\Pr[z_i = j | x_i]}_{r_{ij}} \log (\Pr[x_i|\theta_j]\underbrace{\Pr[z_i = j| \theta]}_{\pi_j}).\\
&= \sum_{i=1}^n \sum_{j=1}^k r_{ij} \log \Pr[x_i|\theta_j] + \sum_{i=1}^n \sum_{j=1}^k r_{ij} \log \pi_j.
\end{align*}
$$
Computing $r_{ij}$ for the E-step is done by simple Bayes theorem,
$$ r_{ij} = \frac{\pi_j \Pr[x_i|\theta_j^{t-1}]}{\sum_{j'=1}^k \pi_{j'} \Pr[x_i|\theta_{j'}^{t-1}]}.$$
Now for the M-step we would like to compute the mixing weights $\pi$ and parameters $\theta$ that maximize $Q$. Luckily for us, we can optimize for each independently as seen by the final formulation! By taking the derivative of $Q$ wrt $\pi$ with the Lagrange constraint that $\sum_j \pi_j = 1$ we have
$$
\pi_j = \frac{\sum_{i=1}^n r_{ij}}{n}.
$$

In order to optimize $Q$ wrt $(\mu_j, \sigma_j)$ lets look at the part only dependent on them (ignoring some constants).
$$
\sum_{i=1}^n r_{ij} \log \Pr[x_i|\theta_j] =
-\frac{1}{2}\sum_{i=1}^n r_{ij} \left(\log \sigma_j + \frac{(x_i - \mu_j)^2}{\sigma_j}\right)
$$
Using this information helps when taking the derivative of $Q$ wrt to each parameter. Finally we have,
$$
\begin{align*}
\mu_j &= \frac{\sum_{i=1}^n r_{ij} x_i}{\sum_{i=1}^n r_{ij}},
&\sigma_j &= \frac{\sum_{i=1}^n r_{ij} x_i^2}{\sum_{i=1}^n r_{ij}} - \mu_j^2.
\end{align*}
$$

In your case, $x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)$, $z = (z_1,\dotsc, z_{13})$, $k=2$, and $\theta = ((\mu_1, \sigma_1),(\mu_2, \sigma_2))$. EM begins by randomly initializing $\pi = (\pi_1, \pi_2)$ and $\theta$ and then alternating between E-step and M-step. Once the parameters haven't changed much (or better the observed-data log-likelihood hasn't changed much) you can stop and output your current values $\theta^t$ and $\pi$.

One benefit from using $|\ell(\theta^t) - \ell(\theta^{t-1})|$ over $||\theta^t - \theta^{t-1}||$ as a stopping condition is for bug checking. EM guarantees that the likelihood will always monotonically increase; therefore, you can simply check the values each iteration to much sure that your likelihood is greater than or equal to last iteration's. If it isn't, then something is wrong.

Finally one important thing to note is that computing a MLE for a mixture of Gaussians will tend to overfit. One way to overcome this is by incorporating priors for $\pi$ and $\theta$ and then computing the MAP estimate instead. This would only change the M-step; however, its derivation is dependent on which prior you choose.

EDIT: Since it is clear you are more interested in just a working example than really understanding any of this here is Python code that will run EM for a basic GMM. Running this in ipython gives:

In [1]: import em

In [2]: x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

In [3]: em.em(x, 2)
Out[3]:
(array([ 0.49645528,  0.50354472]),
 array([ 15.89753149,   5.10207907]),
 array([ 3.8611819 ,  2.65861623]))

where the final output are the mixing weights, means for each Gaussian, and stdevs for each Gaussian.


Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function?

Suppose $M$ is a Turing machine which halts for all inputs $x\in\Sigma^*$, then we can define the corresponding function $f_M$ in the following way:

$$
f_M(x) = \begin{cases}
             1,  & \text{M accepts x} \\
             0,  & \text{otherwise}
       \end{cases} \quad
$$

$f_M(x)$ is a legitimate mathematical function from $\Sigma^*$ to $\left\{0,1\right\}$, it does not care about concepts such as "machine" or "algorithm" or any implementation you have in mind. Obviously the function $f_M$ was tailored for the machine $M$, but this does not make it illegitimate in any way.

You could ask whether i can describe the output of $M$ using a simple function? Perhaps using only the four basic arithmetical operations (we can treat the input strings as numbers represented in binary). The term you should look up in this regard is expressibility, what functions can your model express? For example, when talking about neural nets, the more neurons we use, the bigger our expressive power gets (we can implement more functions).

Note that the converse is not true, not every function can be described by a Turing machine (look up the arithmetical hierarchy, a famous example is the halting problem, but we got a whole hierarchy of even "harder" functions).


Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

The time complexity for both versions is exactly the same. It is linear in terms of the distance between $p$ and the $root$.

Space complexity is a little different.
It's easy to see that the iterative version will use constant space.
The recursive function will use linear space on paper (each recursive call must store some information about the current function call, for instance in a call stack via stack pointer).

This might give problems, if the distance between $p$ and $root$ is very long. Image a tree with $id[0] = 0$ and $id[p] = p - 1$ for $p > 0$. Then finding the root for a large element $p$ might exceed the allocated stack and crash the program.

However in practice the situation might look a bit different. Depending on the programming language, the compiler/interpreter, configuration this linear space can be optimized to constant space. The concept that allows such an optimization is called tail recursion. E.g. gcc -O3 will generate exactly the same assembler code for both versions: example. But be careful, not all languages, compiler / interpreter have these optimizations implemented.


Calculating speedup for a two-way superscalar cpu

The speedup is the ratio of the time when using your superscalar CPU, divided by the time if you used a simple sequential CPU.  For the sequential CPU, imagine that at each step you can execute either pipeline U or pipeline V, but not both at the same time.  Simulate the workload on that kind of sequential CPU, and see what the execution time would be.


(This is edited after the conversation in the Comments below)
This is similar to degree-constrained subgraph problems. That is one direction to search in.

You can drop your 'spanning' requirement since you enforce a minimum degree of 1, which means every vertex has to be included in order to satisfy your degree constraints. It feels like it should be polytime with a max flow solution.


I suspect this clustering algorithm is going to give a poor quality clustering.  The cluster heads are chosen just about arbitrarily (randomly, essentially) and then points are assigned to a cluster if they are near a cluster head or near some other randomly chosen points in the cluster.  The whole algorithm looks unprincipled and I have serious doubts about the quality of the clustering it will produce.

Of course, if the clustering is of low quality, then it just doesn't matter what the running time is.  I can suggest an extremely fast algorithm if you don't care about the quality of its output....

As far as running time, it will depend upon the distribution of the input points.  If the input points are distributed uniformly across the input space, then I would expect that each iteration of the inner loop will remove roughly a $0.15^d$ fraction of the input points.  This suggests that you'll need to do about $1/0.15^d \approx 2^{2.7 d}$ iterations.  Each iteration takes about $O(n)$ distance computations, and each distance computation takes $O(d)$ steps, so I'd expect the running time to be something like $O(n d 2^{2.7d})$.  That's dominated by the exponential factor, so the worst-case running time estimate is very bad, in high dimensions (e.g., $d \approx 100$).  Welcome to the curse of dimensionality.

This algorithm does not look promising to me.  Of course, before drawing any serious conclusions, you'd need to do a serious evaluation of both its running time and the quality of its clustering, on relevant input distributions, as compared to other standard clustering algorithms.  So, if you want to seriously pursue this direction, you need to start studying the state of the art and work on performing such a careful evaluation.  But personally, I think your time would be better spent by starting to look at what's available in the literature and seeing if you can make any standard algorithm work for your application.


Computational complexity of finding a spanning tree in planar hybergraphs

The answer is in this paper "Tree-Residue Vertex-Breaking: a new tool for proving hardness"

  The Hypergraph Spanning Tree problem in $k$-uniform $2$-regular
  hypergraphs is $NP$-complete for any $k≥4$, even when the incidence graph
  of the hypergraph is planar.

Basically, they define a new problem:

  Tree-Residue Vertex-Breaking (TRVB): given a multigraph $G$ some of
  whose vertices are marked "breakable," is it possible to convert $G$
  into a tree via a sequence of "vertex-breaking" operations (replacing
  a degree-$k$ breakable vertex by $k$ degree-$1$ vertices, disconnecting the
  k incident edges)?

Proving this:

  For any k≥4, TRVB is NP-complete when the given multigraph is
  restricted to be planar and consists entirely of degree-k breakable
  vertices.

You can see that solving TRVB for the incidence graph of a hypergraph corresponds to solving SPANING TREE in hypergraphs. Where the incidence graph of a hypergraph is isomorphic to the bipartite representation of the hypergraph described above.


Determine shortest path in a 4x5 grid graph

Since your graph is a DAG you can topologically sort $V$ and solve your problem via dynamic programming by considering the vertices in reverse topological order.

For each vertex $v$, let $d(v)$ be the distance from $v$ to $v_{n,m}$.
Clearly, if $v = v_{n,m}$, then $d(v)=0$.

For $v \neq  v_{n,m}$, you have:
$$
d(v) = \min_{(v,u) \in E} \{ w(v,u) + d(u) \},
$$

where $w(v,u) \in \mathbb{R}$ is the weight of edge $(v,u)$ in $G$.

Both the topological order of $V$ and all the quantities $d(v)$ can be found in $O(|E|)$ time. Therefore the overall time required is $O(|E|) = O(|V|) = O(nm)$.


Decidability of "Is this regular expression prefix-free?"

Let $L$ be a language on the alphabet $A$. Then $L$ is prefix-free if $L \cap LA^+$ is empty. If $L$ is regular and given by a regular expression, then $L \cap LA^+$ is also regular (and one can effectively compute a regular expression for it). Now testing whether a given regular language is empty is decidable.
For context-free languages, the situation is different. Above proof does not work because the context-free languages are not closed against intersection. In fact, there is no algorithm to decide whether a given context-free grammar generates a prefix-free language.
Here is a proof of this claim [Luc Boasson, personal communication].
Let $(u_1, v_1), \dotsm, (u_n,v_n)$ be two finite lists of words of $A^*$ defining an instance of the Post Correspondence Problem (PCP) and let $X = \{x_1, \ldots, x_n\}$ be an alphabet of $n$ letters. Assume that $A$ and $X$ are disjoint and consider the homomorphims $u, v: X^* \to A^*$ defined by $u(x_i) = u_i$ and $v(x_i) = v_i$. Consider the languages
\begin{align}
 U &= \{x^Ru(x) \mid x \in X^+ \} \\
 V &= \{x^Rv(x) \mid x \in X^+ \}
\end{align}
Let $\sharp$ be a new letter. Then $U \cup V\sharp$ is a context-free language. It is prefix-free if and only if $U$ and $V$ are disjoint if and only if the Post Correspondence Problem has no solution. Thus deciding whether a given context-free language is prefix-free is undecidable.


Finding the shortest path in a grid which has walls

Let $w$ be the width of the grid and $h$ be its height. Let $n = w \cdot h$.
The following solution requires $O(n k)$ time and works regardless of whether there are restrictions on the direction of movement. If the movement is allowed only downwards and rightwards then there is a solution with a running time of $O(n)$, which is better whenever $k$ is not a constant (see Nir Shahar's answer).

Assume that there is no wall on the upper-left cell (otherwise remove it, and decrease $k$ by $1$).

Construct a directed graph $G$ as follows: the vertex set $V=\{1,\dots,h\} \times \{1, \dots, w\}$ consists of $n$ nodes. A generic node $(i,j) \in V$ represent the cell in the $i$-th row and $j$-th column of the grid.

There is an edge between vertex $u$ to vertex $v$ iff it is possible to move (in one step) from cell $u$ to cell $v$ without breaking a wall on $v$.
If all directions of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is no wall on $v$.

Create a directed graph $H$ consisting of $k+1$ copies $G_0, G_1, \dots, G_k$ of $G$.
Intuitively the $i$-th copy represents the situation in which exactly $i$ walls have been broken.

Augment $H$ as follows: for each $i=0, \dots, k-1$ add an edge from vertex $u$ of the $i$-th copy to vertex $v$ of the $(i+1)$-th copy iff it is possible to move (in one step) from cell $u$ to cell $v$ but this requires breaking a wall on $v$.
Again, if all direction of movement are allowed this is equivalent to saying that $u$ and $v$ are adjacent and there is a wall on $v$.

Finally, add a new vertex $t$ and all the edges from vertices $(\ell, \ell)$ in all of the $k+1$ copies of $G$ to $t$.
Notice that the number of vertices is $O(nk)$ and that the number of edges is linear in the number of vertices.

It now suffices to find a shortest path $P = \langle v_0, v_1, \dots, v_h \rangle$ from vertex $(0,0)$ in $G_0$ to $t$.  This can be done in time $O(nk)$ using, e.g., a breadth first search from $(0, 0)$ in $G_0$.
The sought shortest path on the grid has length $h$ and is obtained by traversing the cells corresponding to vertices $v_0$ to $v_{h-1}$.


$M\gets\emptyset$
While $E\neq\emptyset$ do

select $(u,v)\in E$
$M \gets M \cup \{(u,v)\}$
delete all edges incident to $u$ and $v$

Return $M$

The above algorithm runs in $O(m+n)$ time if we store $G=(V,E)$ using adjacency list.

Now we prove this algorithm is 2-approximation. Let OPT be the maximum matching. For each edge $e\in$ OPT, there must exist $e'\in M$ s.t. $|e\cap e'|\in\{1,2\}$, i.e. $e$ and $e'$ share one or two common vertex. Moreover, at most two different edges of OPT are incident to the same edge of $M$.

Now we divide OPT into two disjoint subsets OPT$_1$ and OPT$_2$. In OPT$_1$, no two edges are incident to the same edge in $M$. In other words, $M$ has a subset $M_1$ s.t. OPT$_1$ and $M_1$ are one-to-one, which implies $|OPT_1|=|M_1|$. We can pair all edges in OPT$_2$ s.t. different pairt of edges in $OPT_2$ are mapped to different edges in $M_2\subseteq M$. It's easy to show that $M_1\cap M_2=\emptyset$ and $M_1\cup M_2 = M$.

We have $|M|=|M_1|+|M_2|$ and $|OPT|=|OPT_1|+|OPT_2|=|M_1|+2|M_2|$. Therefore, $2|M|\geq|OPT|$.

Edited on Jan. 15, 2020:

The following is a simpler argument. For every matching $M$, we have $2\#edges(M)=\#vertices(M)$. For each $e=(u,v)$ in the maximum matching $M^*$, at least one of $u$ and $v$ appears in a maximal matching $M$. Otherwise, $M$ isn't maximal. Hence,
$2\#edges(M)=\#vertices(M)\geq\#edges(M^*)$.


Does graph connectivity being NP-complete imply NL=P?

If NP completeness of connectivity implies $\mathsf{NL}=\mathsf{P}=\mathsf{NP}$, then $\mathsf{P}\neq\mathsf{PSPACE}$. To see why, suppose $\mathsf{P}=\mathsf{PSPACE}$, then connectivity (and any other non trivial language in P) is NP complete, thus $\mathsf{NL}=\mathsf{P}=\mathsf{PSPACE}$ (by our original assumption), which contradicts the space hierarchy theorem.

This means such implication is not yet known. For completeness, I'll add that a negative answer would imply the existence of an NP complete problem which is not complete under logspace reductions (if all NP complete problems were also complete under logspace reductions, then NP completeness of connectivity implies $\mathsf{NL}=\mathsf{NP})$.


Reduction to complement of Accept Problem

When reducing $L_1$ to $L_2$, we need to come up with a computable mapping $f$ such that $x \in L_1$ iff $f(x) \in L_2$. We don't start with a Turing machine deciding $L_2$ and then construct one for deciding $L_1$, although this construction can easily be accomplished using the mapping $f$. The reason we refrain from doing so is that sometimes we already know that $L_2$ is undecidable, and yet there is merit in saying that $L_1$ reduces to $L_2$, since $L_1$ might have an even strong guarantee of "hardness"; this sort of thinking leads to classical recursion theory.

Regarding your construction, there are two problems: (1) it doesn't involve $w$, (2) when you write "if $x \in L(M)$", you actually mean "simulate $M$ on $x$"; this simulation could halt, or it could never halt. Generally speaking, when a Turing machine never halts, then we say that it rejects. See if this fits with what you were trying to accomplish.


Graph find all vertices that are part of a cycle

There is a duplicate question in StackOverflow. I quote the highest voted answer from Craig Gidney here.

  What you want to do is remove all of the Bridges (i.e. edges that disconnect a component when removed). The Wikipedia article gives a linear time algorithm for finding all of the bridges.

  Once all the bridges are gone, each node is either isolated (has degree 0) or is part of a cycle. Throw out the lonely nodes, and what's left is the nodes you want.


Implement data structure with efficient insert/findKthSmallest operations

Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree.  This data structure is known as order statistic tree.

If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the search path).

Also finding the k-th element is logarithmic time. Let $n$ be the number of nodes in the left subtree of the root. If $k=n+1$ we return the root. If $k\le n$ we continue in the left subtree. If $k>n$ we return the $k-(n+1)$-st node in the right subtree.


Is there an algorithm to overapproximate a context free grammar by a regular expression?

One classical answer to this question is Parikh's theorem. Parikh's theorem states that the histograms of all words in a context-free language form a semilinear set. Conversely, the language of all words whose histogram belongs to a semilinear set is regular. Since the proof of Parikh's theorem is constructive, you can in principle take a context-free grammar and come up with a regular over-approximation.

Another classical answer is the Chomsky–Schützenberger theorem, which states that every context-free language can be written in the form $h(D \cap R)$, where $h$ is a homomorphism, $D$ is a Dyck language, and $R$ is a regular language. You can over-approximate your language by $h(R)$, which is regular. Once again, the proof is constructive, so the over-approximation is algorithmic.

Another option is to take all parse trees of your language of a given depth $d$, and replace all nonterminal leaves with $\Sigma^*$. This generalizes your approach. However, generally speaking it won't be the case that the languages $L_d$ produced in this way will converge to the original language, even if you only consider parse trees corresponding to leftmost derivations.

A similar option is to convert your context-free grammar to a PDA, and take the language of all  words whose length-$n$ prefix has some corresponding partial computation. The language $L_n$ do converge to the original language, for trivial reasons.

Even simpler, you can take all words of length up to $n$ in your language, together with $\Sigma^n\Sigma^+$.

These methods can of course be combined. For example, starting with the Chomsky–Schützenberger theorem, you can consider more intelligent over-approximations for the Dyck language $D$, for example taking all parse trees of length $d$ corresponding to the grammar containing the rules $S \to \epsilon$ and $S \to (_i S )_i S$.


How to find time complexity of this pseudocode

It sounds like your pseudocode is equivalent to the following:

Do search for low in the BST. Find this value or the next largest value. (assuming that the BST is somewhat balanced, this is $O(lg(n))$)
In-order traverse until we reach an element that is greater than high, adding all values that we traverse to some running sum. (in order traversal of $m$ elements in a BST is time $O(m)$ since each element is visited at most twice.)
The running sum gives us our answer. The total runtime of this is $O(lg(n) + m)$

This is equivalent to what you write in your psuedocode I believe. The ignoring of subtrees that are not in the range of interest is what is done in a search.

Hope this helps!

For a proof:
First you should show that this algorithm is complete, i.e. show that it gets you the answer you want.

Then all you need to do is argue the asymptotic bounds. These arguments should be based on the fact that this is a BST, e.g. a search in a BST is in the worst case $O(h)$ where $h = O(lg(n))$ is the height of the tree because at each step in the search, you go up one level in the tree.


How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1.

Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0);
Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] && (board[x2][y] == 0), where x2>x1.
Compute the case when the table can be on a single row, dp[x][y1][x][y2] = dp[x][y1][x][y2-1] && (board[x][y2] == 0), where y2>y1.

For brevity, those boundary cases are not mentioned explicitly in the editorial. Once those cases are included, the algorithm will be fully correct.


Is it decidable "Given a TM M, whether M ever writes a non blank symbol when started on the empty tape."

Q1: A state can get repeated. The point is that if a state gets repeated and no non-empty symbol has even been written, then you known the that the Turing machine will never halt as it is necessarily stuck cycling through some of the states encountered so far. Since none of the states of the cycle caused the TM to write a non-blank symbol, the TM will never write a non-blank symbol.

After $2q$ steps, either a non-blank symbol has been written, and you can answer "yes", or all the written symbols were blank and (at least) one state must have been encountered two or more times, meaning that you can answer "no".

Q2: My guess is that $w$ is defined somewhere to be the empty string.
If the TM can be started with some arbitrary string $w$, then a variation of the above solution still works.
Suppose that the head of the TM starts at the beginning of $w$.
The number of states increases by a factor of at most $1+|w|$ in order to take into account all possible states of the tape (if only blank symbols are written, then the tape always contains one of the $1+|w|$ suffixes of $w$). If the head can start anywhere then this factor will be at most $1+|w|^2$.


Do comparison sorts have to start at the beginning of the input?

You can make the comparisons in any order you want. If there was only one possible sequence of comparisons, there'd be only one possible sorting algorithm!

But note that, to specify an algorithm, you have to specify it in terms of operations that your model of computation supports. For example, althouh you as an intelligent human can say "compare 1 with 3", to specify an algorithm, you'd need to be able to describe how to choose the elements to be compared next. Of course, you could try to say "compare the smallest with the second-smallest" but, then, you'd have to give an algorithm for finding those two elements which would, itself, probably use further comparisons.  And, of course, if you already knew which were the smallest two, you wouldn't need to compare them anyway.


If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]

Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is:

  Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has exactly $\ell$ elements smaller than it (i.e., it is the $(\ell+1)$st element).

Why is this enough? (The following is somewhat informal. See below for a more formal proof.) Suppose that your comparison algorithm outputs an element $x$ but knows only $j < i-1$ elements smaller than it, that is, in the corresponding partial order, only $j$ elements are smaller than $x$. Then there is some total order in which element $x$ is in position $j+1 < i$, and in particular, you cannot be sure that $x$ is the $i$th element. Similarly, if the algorithm knows only $j < n-i$ elements larger than $x$, then there is some total order in which $x$ is in position $n-j > i$ (using the dual version of the observation). Therefore the only way in which a comparison algorithm can be sure that $x$ is the $i$th element is if in the corresponding partial order, $x$ has exactly $i-1$ elements smaller than it and $n-i$ elements larger than it.

It remains to prove the observation. Given a partial order, we can generate a total order extending it by repeatedly performing the following operation:

  Choose a source (a minimal element) $y$, output it, and remove it from the partial order.

This (non-deterministic) algorithm outputs the elements in a certain order which is a total order extending the given partial order.

In order to apply this algorithm to prove the observation, consider the set of elements $P = \{ y : y \leq x \}$ which are at most $x$. In the first $\ell+1$ steps, we always choose a source from $P$ (this is always possible, though this requires an inductive argument). Then it continues in some arbitrary fashion. The resulting total order has $x$ as the $(\ell+1)$st element.

Our argument above, showing how the key observation implies the result, was somewhat informal. Here is a more formal treatment. We will actually show a slightly weaker result, that if a comparison algorithm finds the $i$th element correctly on all inputs with distinct elements, then it "knows" which elements are smaller than the $i$th element (can output them without further comparisons). The stronger result is left as an exercise to the reader.

We can think of the algorithm, when restricted to inputs with distinct elements, as a binary tree: each non-leaf compares two elements and has two children corresponding to the result of the comparison, and each leaf contains the output of the algorithm. We can furthermore assume that each vertex is reachable (we can always prune the tree to ensure this).

We can annotate each vertex with the partial order on the input elements, representing the algorithm's knowledge given the results of the preceding comparisons. We will show that at each leaf with output $x$, the corresponding partial order has exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

The proof is by contradiction. Suppose that there is some leaf with output $x$ at which there are $j < i$ elements smaller than $x$ (the other case, of having less than $n-i$ elements larger than $x$, is handled symmetrically). The key observation shows that there is some linear order $L$ extending the partial order in which $x$ is not the $i$th element. If we had input this linear order to the algorithm, it would have reached the same leaf, and so would have answered incorrectly – contradicting our assumption that the algorithm is valid.

We conclude that at each leaf with output $x$ there are exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.


Finding first/last intersection in a set of lines

Notice that you want to maximize

$$x' = - {\frac{b_j - b_i}{a_j - a_i}}$$

over all possible pairs of indices $i,j$. If you interpret the lines as points in the plane, so that the line $y=ax+b$ corresponds to the point $(a,b)$, then the above expression corresponds exactly to the negative slope, so you want to look for the minimum slope that occurs between any two points in the set.  You can prove that this slope always occurs between two points that are adjacent after sorting by $b$.  Similarly, to minimize $x'$, it suffices to consider only points that are adjacent after sorting by $a$.

This yields a $O(n \lg n)$ time algorithm for your problem.

Also, here's a somewhat less efficient solution.  It doesn't achieve $O(n \log n)$ runtime (the running time also depends on coordinate magnitude and required precision), but it may be what you're looking for.

Label the lines. Let  $\mathrm{sortedPermutation}(x) = (\mathrm{label}_1, \mathrm{label}_2, ..., \mathrm{label}_n)$ be a function of $x$ that returns the permutation of labels which corresponds to the sorted order of $y$ values at point $x$. Notice that $\mathrm{sortedPermutation}$ becomes constant after $x'$ (the lines never change order again). Let's call this final permutation $P_{\mathrm{final}}$. We've never seen $P_{\mathrm{final}}$ for any $x < x'$. If we had, it means some lines swapped order more than once and, well, lines tend not to do that. $P_{\mathrm{final}}$ is easy to compute in $O(n \log n)$ time.

You can now use $\mathrm{sortedPermutation}()$ to evaluate candidates for $x'$ and decide if they're too small or too big compared to the real value, and use binary search to find $x'$.


Does finding a cycle with $\log n$ length in $\text{P}$?

You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.


The MMIO is read into instruction cache, and the code executes as normal. The instruction cache assumes that the contents of memory underneath it do not change unless the cache is explicitly flushed.

Not only does this work, it's common practice to execute code directly from flash devices in very small embedded applications.


Data structure for finding the sum of edge weights on a path

Static case. Suppose the tree is static.  Let $d$ denote the average depth of the nodes of the tree, taken over all nodes.  Then you can solve this problem with $O(nd)$ preprocessing, a data structure of size $O(nd)$, and query time of $O(1)$.  As a consequence, if the tree is balanced or of height $O(\lg n)$, the preprocessing and data structure size are $O(n \lg n)$ and the query time is $O(1)$.

Here's how.  My solution is inspired by Yuval's, but takes into account that we do not have an inverse.  Basically, you just build a map that stores mappings $(u,v) \mapsto f(u,v)$, where $u,v$ range over all pairs of tree nodes such that $u$ is an ancestor of $v$.   This has $O(nd)$ entries and can be computed in $O(nd)$ time during preprocessing.  Also, precompute a data structure to help you solve the least common ancestor problem.  Now, to compute $f(u,v)$ where $u,v$ are an arbitrary pair of nodes (not necessarily an ancestor of the other), find their least common ancestor $p$ and compute $f(u,v) = f(p,u) + f(p,v)$ (with the convention that $f(v,v)=0$ for all $v$).  Thus, queries can be solved in $O(1)$ time, using a sufficiently good algorithm for LCA.

It's also possible to get slightly better efficiency for the above scenario.  Instead of storing all mappings $(u,v) \mapsto f(u,v)$ where $u$ is an ancestor of $v$, we'll store just a subset of them.

Let $r$ denote the root.  Focusing on a single leaf $\ell$, we have a path from $r$ to $\ell$; if the leaf is at depth $d$, this path has length $d$.  So, we can build a balanced binary tree $T_\ell$ (akin to a Fenwick tree) over this path, where each node of $T_\ell$ corresponds to a mapping $(u,v) \mapsto f(u,v)$ (where $u$ is an ancestor of $v$ in the original tree $T$).  The root of $T_\ell$ is the mapping $(r,\ell) \mapsto f(r,\ell)$, corresponding to a path of length $d$.  It has two children, $(r,m) \mapsto f(r,m)$ and $f(m,\ell) \mapsto f(m,\ell)$, corresponding to two paths of length about $d/2$ (here $m$ is a node halfway along the path from $r$ to $\ell$).  Each leaf of $T_\ell$ represents a single edge in  the path from $r$ to $\ell$.  In this way, we get a tree $T_\ell$ of size $O(d)$, where $d$ is the depth of $\ell$ in the original tree $T$.

Now take the union of the $T_\ell$, over all leaves $\ell$ of the original tree $T$ (sharing common nodes in these trees).  This gives us a map that stores mappings $(u,v) \mapsto f(u,v)$, but now with a smaller subset of entries in the mapping than before.  Given any pair of nodes $p,v$ where $p$ is an ancestor of $v$, we can compute $f(p,v)$ in time $O(\lg d)$, where $d$ is the depth of $v$.  Therefore, we can compute $f(u,v)$ for arbitrary $u,v$ in time $O(\lg d)$, where $d$ is the depth of the deeper of $u,v$.

With this "forest of trees" scheme, the time to answer a single query is slightly more, but the size of the data structure is slightly less.  I don't know if this will be a win in practice, but it might be.  This scheme also has the advantage that, if the weight on an edge of $T$ is updated, you can fairly efficiently update the data structure.

There might be a smarter way to choose what subset of entries $(u,v)\mapsto f(u,v)$ to store in your data structure -- I'm not sure.

It's possible to extend these to the case of a static DAG, if you are promised that the length of the longest path  in the DAG is not too large  (if it is short and bushy/wide rather than long and narrow).


Why do reductions to NP-complete problems in NTIME(n) not break the nondeterministic time hierarchy?

The reduction takes time to perform. You know that time is polynomial but you don't know it's linear so you can't conclude that $L\in \mathrm{NTIME}(n)$. You can only conclude that $L\in\mathrm{NTIME}(n^k)$ for some $k$ which, of course, you already knew from the assumption that $L\in\mathrm{NTIME}(n^3)$.


How to find the minimal description for an array?

The phenomenon you're describing is Kolmogorov complexity.  Essentially, if you fix a programming language (or, more formally, a coding of Turing machines) then the Kolmogorov complexity $K(s)$ of a string $s$ is the length of the shortest program that outputs $s$ when started with no input. It turns out that, within reason, it doesn't matter what programming language you use, since using a different language makes at most a constant additive difference to $K(s)$. If you want to define Kolmogorov complexity with respect to some whacko language, I can just use that language to write an interpreter for a sensible language, so the Kolmogorov complexity of a string with respect to your language cannot be worse than the complexity in my language plus the fixed, constant overhead of the interpreter.

Like all interesting properties of Turing machines, the Kolmogorov complexity of a string is undecidable. However, this doesn't stop it being a useful concept and there's been a large amount of research on the subject.


Showing the following sequents are not valid

First, $\phi \models \psi $ means that $\psi$ is a consequence of $\phi$. In other words, if $M$ is a structure and if $M \models \phi$ ($M$ models $\phi$) then $M \models \psi$ ($M$ also models $\psi$).

Now, regarding your statement $$\lnot \forall x P(x) \models \forall x \lnot P(x)$$
clearly $\forall x \lnot P(x)$ is not a consequence of $\lnot \forall x P(x)$. To show it consider the set of natural numbers as a structure $M$ and $P(x)$ as the predicate "$x$ is divisible by $2$". Then
$$\lnot \forall x P(x)$$
means "Not for all $x$, $x$ is divisible by $2$ which is a true sentence (since in fact odd numbers are not divisible by 2), while
$$ \forall x \lnot P(x)$$
means "For all $x$, $x$ is not divisible by $2$" which is not a true sentence (since in fact even numbers are divisible by $2$).

So, the structure $M$ (the set of natural numbers) is an example showing that $M \models \lnot \forall x P(x)$, but $M \nvDash  \forall x \lnot P(x)$ and your statement
$$\lnot \forall x P(x) \models \forall x \lnot P(x)$$
is not true.


At step $k$, draw a random number $q$ uniformly between $1$, $2$, and $3$.

  if $q = 1$, walk $2^{k-1}$, wait $2^{k+1}$, walk $2^{k-1}$
  if $q = 2$, wait $2^{k-1}$, walk $2^{k-1}$, wait $2^{k}$, walk $2^{k-1}$, wait $2^{k-1}$
  if $q = 3$, wait $2^k$, walk $2^k$, wait $2^k$

At each step $k$, both friends will walk $2^k$ steps. If $k < \log_2(x) + 1$, they won't meet during that step, however if $k >= \log_2(x) + 1$, they will meet if and only if they don't draw the same number. The probability that this doesn't happen is only $1/3$ at each step.

Hence the expected walking distance is (bounded above by):

$$2\left(\sum_{k=0}^{\lceil\log_2(x)\rceil}2^k+3^{\lceil\log_2(x)\rceil}\sum_{k=\lceil\log_2(x)\rceil+1}^{\infty}\left(\frac{2}{3}\right)^k\right)$$

Which is finite, and equal, if my napkin maths are to be trusted, to $2^{\lceil\log_2(x)\rceil+3}-2 \le 16x$.

By the way, if $d$ is the random variable representing the distance walked, we still have that $\forall D>0, \mathrm{P}(d>D) > 0$, i.e. the distance is unbounded and can end up being arbitrarily high. Luckily this probability vanishes fast enough to ensure that the infinite sum $\sum_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}[d]$ converges. Having a finite upper bound for $d$ is a much stronger property and I reckon it's not possible to find a solution satisfying it.


Why does this pumping lemma proof not cover every division of xyz?

For reference, the pumping lemma is (from Introduction to the Theory of Computation by Michael Sipser)

  If $A$ is a regular language, then there is a number $p$ (the
  pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  for each $i ≥ 0, xy^i z \in A$,
  $|y| > 0$, and
  $|xy| \le p$.

When you want to prove that a language is not regular using the pumping lemma, you use a proof by contradiction. You first assume that the given language is regular.

As per the pumping lemma, given a regular language, there exists a number $p$ such that for all $s$ with length at least $p$, there exists a way to partition it in the form $x,y,z$ such that all the three conditions hold.

The contrapositive is

For all $p\ge1$, there exists a string $s$ with length at least $p$, such that for all ways to partition $s$ in the form $x,y,z$, at least one of the three conditions are false, implies that the language is not regular.

So, to show that $L$ is not regular, you need to show that the appropriate quantifier (existential or universal) for each entity is used correctly.

Initially, you have taken a value $p$, with no assumption. This is in accordance with for all $p$.

Then, you have chosen a string $s$ with length at least $p$. This is in accordance with there exists a string $s$, i.e., a single instance of a string satisfying the rest of the statement is sufficient.

Now, you need to consider all ways of partitioning $s$ in the form $x,y,z$, and show that always, at least one of the three statements of the lemma is false.

So, you have partitioned it into $x=a^l, y=a^k, z=a^{{2^p}-l-k}$. As of now, there are no assumptions on the values $l$ and $k$ can take, except that they are non negative, which is as required. To force a contradiction, you need to try to show that all the statements of the lemma do hold. Statement 2 states that $|y|\gt0$. So, if it were true, we must have $k\gt0$. Statement 3 states that $|yz|\le p$. If it were true, we must have $k+l\le p$.

Finally, Statement 1 must be true if $L$ is regular, so $xy^iz\in L$ for all $i\ge0$ must be true. It is sufficient thus to show that it is false for any one value of $i$. I choose $i=2$. So, we must have $a^la^{2k}a^{{2^p}-l-k}=a^{{2^p}+k}\in L$ for all possible values of $l$ and $k$ except as per the previously imposed restrictions.

Now, we have
$$k\gt0\implies k\ge1$$
$$2^p+k\ge 2^p+1\gt 2^p\tag1$$

$$k+l\le p$$
But $l\ge 0$, so we have
$$k\le p$$
$$2^p+k\le 2^p+p\tag2$$

But we have $$p\lt 2^p$$

for all $p\ge 1$, which is the set of all allowed values of $p$. So, $(2)$ becomes,
$$2^p+k\le 2^p+p\lt 2^p+2^p=2^{p+1}\tag3$$

From $(1)$ and $(3)$,

$$2^p\lt 2^p+k \lt2^{p+1}$$

As $2^p+k$ lies strictly between consecutive powers of $2$, it cannot be a power of $2$ itself. So, $a^{2^p+k}\notin L$, and we have a contradiction as desired.

Thus, $L$ is not regular.

In your proof, the initial steps are all correct, all you need to do is to show why the string cannot lie in the language, using an appropriate value of $i$, as shown in this answer. Moreover, choosing $i=0$ is not straightforward. For $i=2$, I argued that $2^p\gt p$. For $i=0$, you will need to use $2^{p-1}\gt p$, which is not true if $p=1$.


How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"?

The $x$ in $\forall x . P(x)$ is not an argument. It is a bound variable indicating which variable the quantifer is ranging over.
Let us compare the situation to the definite integral, for concretness just from $0$ to $1$. Here is an example:
$$\int_0^1 x^2 + 3 x \, dx$$
This is a very archaic way of writing mathematical expressions that mathematicians like to stick to. In general (and ignoring details about non-integrable functions) the definite integral is itself a function: it takes a function $f$ as an argument, such as $f(x) = x^2 + 3x$ and returns a number (the area under the curve). So we could simply write $I$ for "integrate from $0$ to $1$" and then the integral of $f$ is simply
$$I(f)$$
(Or if you want to keep the integration bounds visible write $I_0^1(f)$, but I won't).
The argument $f$ need not be a symbol, it can be a complex expression:
$$I(x \mapsto x^2 + 3 x)$$
Notice how "$dx$" above changed to "$x \mapsto$". In $\lambda$-calculus notation we would write this as
$$I(\lambda x . x^2 + 3 x).$$
In archaic notation people sometimes feel uneasy about writing
$$\int_0^1 f$$
and so they end up always displaying $dx$ by writing
$$\int_0^1 f(x) \, dx$$
even though there really is no need to do so, because $\int_0^1$ is a higher-order function which maps real-valued functions to real numbers.
If you want to make traditional mathematician feel uneasy you should write
$$\int_0^1 (x \mapsto x^2 + 3 x)$$
on their whiteboards
If this much is clear, then it should be easy to see that the universal quantifier $\forall$ is like integration, except that it takes a propositional function (one mapping into truth values instead of numbers) and returns a truth value.
The archaic notation
$$\forall x . (x^2 + 3 x > -3)$$
can be changed, just like for integrals, to
$$A(f).$$
Here $A$ is the universal quantifier, and $f$ its argument, which is a function mapping from a set to the truth values. An example of such a function is $f(x) = (x^2 + 3 x > -3)$. And again, we can inline the complex expression to get
$$A(\lambda x . (x^2 + 3 x > -3))$$
Now just replace $A$ with $\forall$ for good old times sake:
$$\forall(\lambda x . (x^2 + 3 x > -3)).$$
This his how computers like it. The notation is general, so we can write just $\forall f$ instead of $\forall x . f(x)$, and it exposes $\forall$ for what it is: a higher-order function that maps propositional function to truth values.


What is pass-by-value-result and its advantage and disadvantage?

Note: parameter passing by xxx is sometimes called "pass by xxx" and
sometimes "call by xxx".  I will use both expressions indifferently.

Parameter passing by value-result consists in passing by value when the
subprogram (whatever it is) is called, and then, when it terminates,
assign the current value of the formal parameter in the subprogram
back to the actual parameter if it is a mutable entity, such as a
variable or an array entry. Of course, no such assignment may occur if
the actual parameter is a non mutable value providing entity such as
an expression, a function call, a constant (though some old versions
of Fortran have been known to assign values to constants, so that
printing 3 could actually print 5).

Afaik, fortran was first to use this mechanism (I do not know for
Cobol). It is also available in Ada. Actually, Ada has call by value
(IN parameter) and call by result (OUT parameter). OUT parameters are
not initialized at call, but assign current value of formal parameter
to the actual parameter upon return. Parameter passing by value-result
(IN OUT) is the combination of both. Actually, the case of Ada is more
complicated (at least in its initial versions) because it was
explicitly allowed to implement these parameter passing mechanism with
a call by reference. I am not sure of the current status of the
language. This of course muddles the discussion below.

Comparing parameters passing mechanisms is dependent on the language
considered.

Issues you may want to consider are cost in time or space, readability
and maintenance, compiling issues such as efficiency and optimization,
and also semantics such as determinacy of programs, and also programming
convenience. (I may have forgotten some).

Many of these issue are stongly impacted by aliasing
phenomena. Whenever the same mutable entity (possibly a simple
variable) can be accessed in different ways, it becomes harder to
analyse the program, determine what parts of the computation may
interfere with other parts. When there are several threads of
computation, this may cause race conditions making the computation
dependent on timing. When compiling program, aliasing may make it harder
to get a reliable definition-use relation for performing some
otpimizations.

Hence,I would consider aliasing problems a major issue when comparing
computing mechanisms.

Since you need ways to communicate in programs, assessing a parameter
passing mechanism can only by comparing to alternatives.

Regarding pass-by-value-result, the are only two that I see:

Doing nothing on exit.
Then you can pass information back to the caller only as function
result, or by assigning a global variable visible from both callee
and caller.
Using pass by reference.
Then the formal parameter becomes just
another name, an alias, for the actual parameter, so that the actual
parameter has the value of the formal one upon exit (as well as
before exit).

Issues

Time and space cost

One advantage of call by reference over call by value-result is that
it is often cheaper, especially if the data to be passed is large
(time/space costs of copying). Call by reference may have a time cost
because of indirect addressing, though that can sometimes be optimized
out.

Aliasing

The major drawback of call by reference is all I said about
aliasing. So that may be considered a very good point for
pass-by-value-result.

Side effects and evaluation order

Then call by value-return has a problem when returning the values, as
in your example. If two formal parameters (x and y in the example)
actually get the same actual parameter (b in the example) then the
actual parameter will take on return a value that depends on the order
chosen for returning values. Hence, it is essential to define it.  In
any case, such a situation is a sure indicator of bad programming
practice.

This problem does not exists with call by reference. But call by
reference is a completely different kind of computation, as shown by
executing your example in call by reference.

Returning values is a side-effect on the actual
parameters. Computations with side-effects always raise issues of
order dependence. If the evaluation of actuall parameters entails some
side-effects (for example by calling a function with side-effects),
then the order of evaluation of arguments may have an impact on the
computation. That is why side-effect are to be avoided, or at least
carefully managed.

Objects identity

If you have a language that allows to distinguish identity and
egality, the call by reference wil preserve identity, while call by
value will not.  For example, when you copy an integer (for example by
assignment), there is no way you can distinguish the new copy from the
old one.  But Object-Oriented (OO) languages could let you make a
difference, and have a test for equality (same value) and a test for
identity (same reference).

Well definedness of call by value (irrespective of result)

Another problem is that call by value may not be well defined. You
have to determine what a value is. How deep do you copy an object
implemented with references (pointers) when doing call by value.
When a reference is not followed for copying, it is an open door for
aliasing problems.

I am not saying these issues are untractable, but only that you have
to deal with them consistently throughout the language (consistency
with assigment in particular). And that does not make for a clearcut
answer, independently of the rest of the language, and the style of
programming it supports.

Running the example in call by value-result and call by reference

Notation

    a<==b  a becomes aliased to b
    a==b   a is alias of b  (reminder)
    a<-3   a is assigned the value 3

Call by value-result:

    Call of fun(b,b): x<-1 y<-1 b<-2 x<-3 y<-5 return print 2 (3 or 5)

unpon returning, b ends up with 3 or 5 depending on the order of argument return.

Call by reference:

    Call of fun(b,b) x<==b y<==b b==b<-2 b==x<-4 b==y<-8 return print 2 8


Compare each array $i$ member to all array $j$ member where $(i > j)$ , in time less than $O(n^2)$

Create a binary tree containing the points, either each node also containing the number of elements in each sub tree . For each candidate, determine the number of candidates arriving earlier, and having same or higher score using the tree, then add the candidates score to the tree.

Should work in O(n log n). I doubt O(n) is possible.

PS chi’s answer is a lot easier, and you probably have a library for the sorting, which is the hard part.


This post shows that the answer to your initial question is yes (even if P = NP).

On the other hand, I suspect there is no known proof that
if
unambiguousGC(polylog, NC) ⊈ coNP/poly then there is a superpolynomial time-constructible function $T$ and a superlogarithmic space-constructible function $S$ such that

DTIME(T(n)) ∩ DSPACE(S(n)) ⊆ NP/poly.


Average codeword length in Huffman encoding at most log n

Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).

Let us notice now that there is a code in which each codeword has length $\lceil \log n \rceil$, and in particular the average codeword length is $\lceil \log n \rceil$ (with respect to any distribution). Hence Huffman's algorithm produces a code in which the average codeword length (with respect to the input distribution) is at most $\lceil \log n \rceil$.

Here are two comments. First, we cannot replace $\lceil \log n \rceil$ with $\log n$. For example, if $n = 3$ and you consider the uniform input distribution, then the optimal average codeword length is $5/3 > \log 3$.

Second, the average codeword length is only guaranteed to be small with respect to the input distribution. For example, if the input distribution is $1/2, 1/4, 1/8, \ldots, 1/2^{n-1}, 1/2^{n-1}$ then the optimal code has codeword lengths $1,2,3,\ldots,n-1,n-1$, and so the average codeword length with respect to the uniform distribution is roughly $n/2$. The average codeword length with respect to the input distribution, however, is constant (tends to 2).


The system has 32.000 bytes and each byte must have its own unique address:

32.000 unique addresses

How many bits to represent these?

$2^{15} = 32768$, so if we let addresses be 15 bit we have the address space $[0,32767]$.


Handling epsilon productions in recursive descent parsing

You need to know FOLLOW(APPLICATION'), and it has to be disjoint to FIRST (ATOM).

Actually, you only have to know that the sets are disjoint, in which case the epsilon action becomes the default.

Personally, I wouldn't bother with two functions:

Application:
    v := Atom()
    if lookahead token in FIRST(ATOM):
        return ApplyNode(v, Application())
    else:  (* default case *)
        return v

That corresponds with your grammar, but it might not correspond with your intended language. Normally, lambda application is left-associative, not right-associative, but of course it is impossible to express left-associative expressions with an LL(k) grammar. Fortunately, it is easy to write a recursive descent parser which left-associates. That's usually done with a local variable and a while loop: (Technically, the parser is doing a tree-rewrite in order to fix the associativity, but the mechanism is so simple that hardly anyone sees that it is even there.)

  Application:
     v := Atom()
     while lookahead token is in FIRST(Atom):
         v := ApplyNode(v, Atom())
     return v


Why isn't there just one "keystone" activation function in Neural Networks?

Those are old articles.  Tinkering with activation functions probably isn't your best use of time, in most cases.  Today, the standard engineering practice is (to a first order of approximation): use ReLU and don't stress over it.  ReLU is clearly superior to sigmoid and tanh for most cases, so if you read older articles they'll talk about sigmoid and tanh, but today, ReLU has replaced them.  There are fancier newer activation functions that in some cases are slightly better than ReLU and in some cases are slightly worse but the short version is ReLU is good enough and don't worry about the others at this stage in your learning and knowledge; just use ReLU and call it a day.
This is a crude simplification and there are absolutely exceptions but I'm giving you a rule of thumb that will be pretty reasonable in practice.
Why?  My main answer is that you will need to get used to the fact that when working with neural networks, we don't really know the answer to most "why" questions.  Sometimes we have intuition and theories but at its heart this is an empirical science: we don't really understand why neural networks work well.  There are papers that give some explanation of why ReLU seems to do better than sigmoid/tanh -- in particular, sigmoid/tanh suffer from vanishing gradients when their inputs are in the tails of the sigmoid/tanh (as then their output is exponentially small, so the gradient is essentially zero), and then training gets stuck or proceeds very slowly -- but don't expect great theory that is going to tell you what to do.  Instead, this is largely an empirical science, and if we're lucky, we have experiments and theory that helps us understand the empirical data we see.
I don't see any reason to expect there to be a single activation function that is optimal for all tasks, so I'm not bothered if that isn't true and don't feel that we need a "reason" for it to be false.


When is the concatenation of a language $L$ with $\Sigma^*$ regular?

In the first case, $n$ can be 0, and the concatenation will produce $\Sigma^*$. So any other value of $n$ is irrelevant; no other strings could be added. If the restriction were $n>1$, then the concatenation would not be regular.


Lower bound the difference between distinct values of a function over a discrete domain?

You can certainly do better than $N(N-1)$: you can achieve $O(N \lg N)$ running time.  Evaluate $f$ on every possible element of $x$, then sort the resulting values, and look at the gap between consecutive values.  The smallest such gap is exactly the value of $\min |f(x_1)-f(x_2)|$.

As Raphael says, without any information about $f$, it seems unlikely that you can do any better than to evaluate $f$ on every possible input.  Indeed, it seems possible to prove this using an adversarial argument, in a black-box setting: if there is a single value $x^*$ where you haven't evaluated $f(x^*)$, then any answer your algorithm outputs can be made to be wrong by choosing the value of $f(x^*)$ appropriately.

Since the notion of "monotonically non-decreasing" is not defined when the domain is not totally ordered (as in your example for $X$), and the notion of continuous is not defined when the domain is discrete (i.e., not continuous, as in your example for $X$), your second question isn't well-formed and can't be answered in its current state.


Choose the best classifier to predict the label of strings of a regular language

My bet would go to a Recurrent Neural Network, as it closely models some (fuzzy, non-discrete) state machine as each character is output. A decent start to read up on RNNs for this purpose is to read the article The Unreasonable Effectiveness of Recurrent Neural Networks which describes character-level RNNs used to predict text.


Complexity of list coloring $K_n$ with $n$ colors

Consider list coloring the complete graph, where the available colors for vertex $v$ are $L(v)$.

Form a bipartite graph in which the left-hand side corresponds to vertices and the right-hand side corresponds to colors. Connect $v$ on the left-hand side to all colors in $L(v)$ in the right-hand side.

There is a list coloring iff there is a matching saturating the left-hand side. You can decide whether this is the case by running an algorithm for bipartite perfect matching.


Boruvka MST algorithm using doubly linked lists

I came across your question in pursuit of the same answer. Anyway this comment gives a hint, I would say, why a detailed algorithm is not there or easily searchable:

"It is possible to remove the lg*E factor to lower the theoretical bound on the running time of Boruvka’s algorithm to be proportional to E lg V, by representing MST subtrees with doubly-linked lists instead of using the union and find operations. However, this improvement is sufficiently more complicated to implement and the potential performance improvement sufficiently marginal that it is not likely to be worth considering for use in practice (see Exercises 20.66 and 20.67)."

(from: http://apprize.info/c/algorithms_2/36.html)


Algorithm analysis question in growth of functions

Formally, there is absolutely no way to tell.  O( ) notation is about the limiting behavior of a function (in this case, the running time of an algorithm) as its argument (in this case, the input size) grows to infinity.  Without more information, it is absolutely impossible, even in principle, to predict behavior in the limit from a finite number of function values.


Algorithm to find path with max sum of degrees in a tree structure

In a tree, there is exactly one path from the root to any vertex. So just do depth- or breadth-first search on the tree and label each vertex with the sum of the degrees on the path from the root to there. Then pick the leaf with the smallest value.

An optimization could be to use greedy best-first search, where you maintain a queue of vertices in increasing order of their weight (sum of degrees on the path from the root). The first leaf you find would then be guaranteed to be the one of minimal weight. This would reduce the number of vertices that you look at but it's possible that the additional overhead of maintaining the priority queue would negate that benefit.


Finding strings that are matched by a given regular expression

Let's break down the regular expression $(c \cup ab \cup b)^*bb(c \cup ab)$. It has three parts $(c \cup ab \cup b)^*$, $bb$, and $(c \cup ab)$. The first part means "zero or more repetitions of $(c \cup ab \cup b)$", the second part matches two $b$, and the third part matches $c$ or $ab$.

As you already mentioned in your question bbc and bbab are strings that are matched. In both we choose zero repetition of the first part then the obligatory bb and then c, respectively ab, to match the third part. To make this easier to see I'll separate the parts of the string that are matched by the different parts of the expression with a - like so: -bb-c and -bb-ab.

We can generate more strings by choosing more than zero repetitions of the first part. For example we can choose one repetition of c to get c-bb-c. c-bb-ab would also be ok. We could also choose more repetitions of c or a c followed by ab for the first part. So cc-bb-c and cab-bb-c would also be acceptable strings.


Is it possible that the subtraction between two undecidable languages is regular?

Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.

Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define
$$L_2 = \lbrace b w \mid w \in H\rbrace$$
and
$$L_1 = L_2 \cup \lbrace a \rbrace.$$
Now it is obvious that $a \not\in L_2$ because all words in $L_2$ start with $b$. Also, $L_2$ and $L_1$ are undecidable because there are easy reductions from $H$ to them, and back. And of course we have
$$L_1 \setminus L_2 = \{a\},$$
which is decidable. You can make the example more complicated by taking any decidable langauge $D$ and define $L_2$ as before, but change $L_1$ to
$$L_1 = L_2 \cup \{a w \mid w \in D\}.$$
This way $L_1 \setminus L_2$ is computably isomorphic to $D$.


What do we mean by running time of algorithms?

Depends on who is talking. It can mean everything from actual time in seconds to execution count of some asymptotically dominant instruction.
Things get muddied further by widespread overuse of Landau notation.

Also, one typically distinguishes at least worst, average and best case.

  when we say running time of bubble sort is $O(n^2)$, what are we implying?

Here we use that the actual running time is in $\Theta$ of the execution count of an asymptotically dominant operation. We can rigorously show that Bubblesort takes $\Theta(n^2)$ comparisons (in fact, we can get the exact number for worst-, best- and average case), that all other operations happen only $O(n^2)$ often, and thus the real running-time has to be in $\Theta(n^2)$ as well.

That assumes that our machine model (usually RAM) and the real machine differ only by constant factors (unknown to us). If you analyzed formally on the TM model, you could not carry over Landau bounds as easily. In general, converting between (reasonable) models can add a polynomial factor.

  Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm?

No, not at all. Assuming that by "asymptotic complexity" you mean a Landau bound on the runtime function $T$,

you only know the behaviour of T for $n \geq n_0$ for some $n_0$ that may be larger than anything you ever see in inputs;
you only know the behaviour up to a constant factor $c$;
you only know the type/degree of the leading terms but lower terms can be significant (i.e. the absolute error of your bound can tend to infinity, even if you have a tight estimate of the constant factor of the leading term).

Even if you knew $n_0$, lower-order terms and all constant factors,

these bounds are usually not tight and
the analysis gives you the execution of some operations, not actual time.

The only way to use formal analysis for predicting actual running times is

analysing the execution counts for all statements,
analysing up up to small error terms, and
know how many (nano)seconds each statement takes.

Sometimes we can do 1. and 2. but 3. is very, very tough for real machines -- which is why everybody in TCS analyses on clean machine models.


Generally, to prove a greedy algorithm is optimal what you do is come up with a theorem that captures the idea of “moving away from” the greedy strategy and show that that decreases the optimal value. It’s important that you phrase the theorem in a way that can be iteratively applied, as otherwise it might be that the objective function goes down immediately after departing from the greedy algorithm, and then goes back up. In this case, you want

  Theorem: If $a\geq b$ and $c\geq d$ then $ac+ bd\geq ad+bc$

Given any way of pairing numbers, this theorem says that if you swap two numbers so that you move closer to the greedy algorithm then the value cannot go down, and if you swap two numbers so that you move further from the greedy algorithm the value cannot go up. So prove this, and the correctness of the greedy algorithm follows.

It’s sufficient to consider only vectors of length two because any permutation of the vectors can be generated from exchanging two numbers. Equivalently, $S_n$ is generated by its two-cycles for every $n>1$


How is a JIT compiler different from an ordinary compiler?

JIT compilers compiles the code on the fly, right before their execution or even when they are already executing. This way, the VM where the code is running can check for patterns in the code execution to allow optimizations that would be possible only with run-time information. Further, if the VM decide that the compiled version is not good enough for whatever reason (e.g, too many cache misses, or code frequently throwing a particular exception), it may decide to recompile it in a different way, leading to a much smarter compilation.

On the other side, C and C++ compilers are traditionally not JIT. They compile in a single-shot only once on developer's machine and then an executable is produced.


Unification Algorithm without Occur Check

Say you tried to solve $f(A, g(A)) = f(B, B)$ after applying $A \to B$ you'd then have $f(A, g(A)) = f(A, A)$ and you'd have to unify $A = g(A)$ as a sub problem.


Complexity of Subset Sum where the size of the subset is specified

There are $\binom{n}{k}$ $k$-subsets of an $n$ set, and $\binom{n}{k} = n (n - 1) \dotsm (n - k + 1) / k!$, which is $O(n^k)$, as you observe. The brute force complexity is a bit more (need to add up the numbers too and check), but that is ballpark.
This is polynomial for any fixed $k$, but not polynomial in $n$ if e.g. $k = n / 2$ (that is the Partition problem, known NP-complete).


In the preface of his book “Mathematical Discovery, On Understanding, Learning, and Teaching Problems Solving” George Pólya writes:

  Solving problems is a practical art, like swimming, or skiing, or
  playing the piano: you can learn it only be imitation and practice.
  This book cannot offer you a magic key that opens all the doors and
  solves all the problems, but it offers you good examples for imitation
  and many opportunities for practice: if you wish to learn swimming you
  have to go into the water, and if you wish to become a problem solver
  you have to solve problems.

I think there is no short path, especially for reaching the state of writing papers. It requires practice, a lot of it.

Some pointers:

If “limited background in mathematics and the formal aspects” means “has never conceived a proof and written it down” then something like this might be a start.

If something on the Theoretical Computer Science Cheat Sheet makes the student feel uneasy, then a refresher course of the according branch of mathematics would be advisable.

There are many  sources for mathematical writing: The lecture notes of the 1978 Stanford University CS209 course perhaps. Or this article by Paul Halmos.


change the info part of each node in binary tree

In my point of view, since you want to use the next info in the inorder traversal, you have to do a function that traverse you tree backward for this order.

    int change(node* n,int next){
     int k;
     k=next;
     if(n){
      if(n->right) k = change(n->right,next);
      if(n->left) change(n->left,n->info);
      n->info += k;
     }
    }

That way, calling

     change(root,0)

You have next that is the info of the next node in your order.

I hope I didn't made a mistake and that it help.


What are the limitations of symbolic model checking?

The primary limitation is that it can be more complicated to use.


Automatic translation between formal languages

I think you are asking this from a stand point of specific tools so let me answer this in two parts.

Theory Part (ideal view):

There is a notion of languages and a notion of computational systems that except these different classes of languages. Finite Automata can accept regular languages, Pushdown Automata can accept context-free languages. If we go all the way up in the Chomsky hierarchy we get recursively enumerable languages which are accepted by turing machines.

As long as the class of languages define by a certain syntax is less than or equal in power to the target syntax's class of languages then this is possible (at least in principal). Parser generators typically compile context-free grammars to turing machines (or turing complete systems rather) which is just jumping rather far in Chomsky hierarchy. Nicely however this allows us to use context-free grammars in settings where we need recursive enumerability like interpreters. I could in principal compile a context-free grammar to a context-free grammar but defined using a different syntax; this is just an issue of the syntax being used to define context-free grammars. What I could not however do is compile a context-free grammar to a regular expression. No semantic rules need apply in this ideal view.

Practical part:

Real parser generators don't just generate code that accepts a given context free language however. They add in bits of your code to produce abstract syntax trees for your programs to use. I think the details of translating something like Antlr 3 (LL grammars) to Bison (LR grammars which are more general) or some other parser generator would be a bit tricky; I wouldn't want to try it. They probably use slightly different template systems for your code for starters. It could be that they execute your code in different orders so unless your code was pure there would really be no hope of translating the code properly.

So I think the answer to "would semantic rules for the grammars also have to formally specified" would be yes. The code that generates the ASTs would need to be functional and pure or something like that. The substitution principal needs to apply I think which is not something that generally applies except in languages like Haskell where even their effectual code has the substitution property.

My bet is that something like this is possible between the right tools but I think it is a very tricky thing.


Hint: Your problem looks a lot like minimum $(s,t)$-cut.