How to modify Floyd-Warshall algorithm with space $O(V^2)$ with tracking actual path?

For each $i,j$ keep track of the last $k$ for which the value $d_{ij}^{(k)}$ was changed. That must be the highest value on the shortest path from $i$ to $j$. The actual path can be retrieved recursively.

Added. A simpler solution. Keep track of array $n_{ij}$ of vertices, giving the next vertex on the shortest path from $i$ to $j$. Whenever $d_{ij}^{(k)}$ changes, $n_{ij}$ is set to $n_{ik}$.


Minimizing a multiple output circuit with K-maps - and without

Good job on $f_a = \overline acd \lor bc \lor bd$.
With $f_b$, I'd denote it as $b\overline d\lor b\overline cd$ - you missed overlap with $\overline d$: $f_b = b\overline c \lor b\overline d$.
I'd tally that as and inputs: 11 complemented: 3 ands: 5 gates/ors: 2

In the combined implementation, groups are still allowed to overlap: both blue ones can be twice as large, use one input less.
One can share either $bc\overline d$:
$f_a = b\overline cd \lor \overline acd \lor bc$
$f_b = b\overline cd \lor b\overline d$
or $b\overline cd$:
$f_a = bc\overline d \lor \overline acd \lor bd$
$f_b = bc\overline d \lor b\overline c$
and inputs: 10 complemented: 3 ands: 4 gates/ors: 2


Rearranging function in 'Theorems for free'

It can, as good evidence for it define m as something like

m f = map f . drop 2

And everything still typechecks. Here "rearranging" is supposed to refer to structural operation on the list without regards to the specific values of each element. This is captured by the free theorem at this type,

m (\x -> x) . map f = map f . m (\x -> x)

m (\x -> x) performs all the structural changes to the list and map f actually alters this element. This theorem implies that they are independent of each other.


Prove correctness for computing the nth Fibonacci number for the pseudo code

The idea is that at the end of the $i$th iteration, $a = F_i$ and $b = F_{i-1}$. This is something that you can easily prove by induction. (Usually this sort of condition is called a loop invariant.)


Transformation Function: Gonzalez and Woods

Those ${\sum}\text{-signs}$ specify sigma notation.  They're basically like for loops where you keep summing up the value specified in the body.

The equation,
$$
T \left(u, v\right)
=
\sum_{x=0}^{M-1}
{
  \sum_{y=0}^{N-1}
  {
    f \left(x, y\right)
    \,
    r \left(x, y, u, v\right)
  }
}
\,,
$$

translates into:

public double T(double u, double v)
{
    var sum = 0.0;

    for (int x=0; x <= M-1; ++x)
    {
        for (int y=0; y <= N-1; ++y)
        {
            sum = sum + (f(x, y) * r(x, y, u, v));
        }
    }

    return sum;
}

In other words, it defines some function, $T \left(u, v\right) ,$ that takes two input variables: $u$ and $v .$  You also need to know two other functions: $f \left(x, y\right)$ and $r\left(x, y, u, v\right) ,$ which means you'll need at least 2 more equations.

Then:

Start with a starting total value of $0 .$
Set $x$ to $0 .$
Set $y$ to $0 .$
Calculate $f\left(x, y\right) r\left(x, y, u, v\right) ,$ then add this value to the total.

On the first evaluation, $x=0$ and $y=0 ,$ so that's $f\left(0, 0\right) r\left(0, 0, u, v\right) .$

Increment $y .$

If it's still less-than-or-equal-to $N - 1 ,$ then go back to Step (4).

Increment $x .$

If it's still less-than-or-equal-to $M - 1 ,$ then go back to Step (3).

The final total is the calculated value for $T \left(u, v\right) .$


Extremal related question regarding Intersection of neighbourhood of vertices

This problem has been solved in the undirected case by Füredi, New asymptotics for bipartite Turán numbers, who showed that for constant $k$, the optimal bound is
$$
\frac{1}{2} \sqrt{k} n^{3/2} + O(n^{4/3}),
$$
when counting undirected edges. When counting directed edges, you have to double the number. The lower bound also holds in the directed case — it is given by an explicit construction based on finite fields.

Following Füredi's footsteps, we can generalize the upper bound to the directed case. Denote by $P_2$ a path consisting of two directed edges pointing at the central cases. The number of copies of $P_2$ in your graph is at most $k \binom{n}{2}$, since for every choice of the outer vertices there are at most $k$ choices of the inner vertex. On the other hand, the number of copies of $P_2$ is also $\sum_v \binom{d_{in}(v)}{2}$, where $d_{in}$ is the in-degree of $v$, since for every $v$, we can choose any two vertices in its incoming neighborhood to create a copy of $P_2$. Convexity now shows that $\sum_v \binom{d_{in}(v)}{2}$ is minimized when all in-degrees are the same. If the graph contains $m$ edges, then the total in-degree is $m$, and so
$$
k \binom{n}{2} \geq n \binom{m/n}{2},
$$
from which we can deduce $m < \sqrt{k} n^{3/2} + n/2$.


Is the extension of every undecidable theory undecidable?

No. A theory is a set of theorems. The set of all formulas is a decidable theory and it is an extension of all theories, including undecidable ones. It is also very inconsistent and thus useless in practice, but it is a counter-example to your claim.


Understanding the algorithm behind day of week calculation

As mentioned in a comment, this program is a variant on Zeller's congruence.

Here are the steps:

It's good to know that the Gregorian calendar (which is what we are using) repeats every 400 years. In the 400 year cycle, every fourth year is a leap year except for the centuries other than the one at the start of the cycle. In other words, in the 400-year cycle starting 2000 and ending 2399, there are 97 leap years: all the years divisible by 4 except 2100, 2200 and 2300.

There are 365 days in a normal year, which is 52 weeks and one day. A leap year has an extra day. So the 400-year cycle, which has 303 normal years and 97 leap years, is 52*400 weeks plus (303 + 97*2 = 497) days. 497 days is exactly 71 weeks, so the cycle is an exact number of weeks, which means the weekday for a given date is the same for the "same date" in every cycle. (The same date meaning the same day, month and year mod 400.)

Since we're only interested in which weekday a date is, and not the total number of days since some determined starting point, we can do all computations mod 7. So if we know the weekday for some particular date, we can find the weekday for the same day/month in another year by adding the number of years and then the number of intervening leap days.

int x = y0 + y0/4 - y0/100 + y0/400;

y0 is explained below; if you think of it as the number of years from the beginning of (some) 400 year-cycle, then x is just the number of years plus the number of leap years: y0/4 (every fourth year) - y0/100 (except for centuries) + y0/400 (other than the centuries which start a cycle). If we had computed y0 as years into the current cycle, we could have avoided the y0/400 term.
The fact that a leap day falls into the middle of a year complicates that computation. To make it simpler, we start the cycle at March 1 instead of January 1, effectively moving January and February to the previous year. That puts the leap day at the end of the year, so we can evaluate the number of leap days by counting the number of leap years, as above. As we'll see below, this also has the advantage of making the alternation of month lengths more regular; aside from February, months more or less alternate between 31 and 30 days.

int y0 = year - (14 - month) / 12;
int m0 = month + 12*((14 - month)/12) - 2;

Those lines are trying to way too hard to be clever, and end up being terrible because of the slowness of division (even though division by 12 can be performed with multiplies, and even though the compiler can figure out that it's only necessary to do it once. The code would be clearer and faster if it were written in the obvious way:

int y0 = year, m0 = month - 2;
if (m0 < 1) { ++y0; m0 += 12; }

Essentially, we now have a weekday offset of March 1 in the specified year from the March 1 which starts the cycle. Now we just need to figure out the adjustment for the months between March and the specified month. Each of these months will move the weekday by either two (30 mod 7) or three (31 mod 7) days. Months mostly alternate between 31 and 30 days, except although sometimes there are two 31-day months in a row. (As mentioned above, we can ignore February here because we're only counting months which come before the specified date, and with February shifted to the end of the year, it is never before any date in the year.)

int d0 = (date + x + (31*m0)/12)%7;

(31 * m0) / 12 for m0 in the range [1, 12] produces the sequence {2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31}. The adjacent differences in that sequence are {3, 2, 3, 2, 3, 3, 2, 3, 2, 3, 3} which happen to correspond to the lengths of the months (mod 7) starting at March. (The pairs of consecutive 3s correspond to July/August and December/January.) So adding this to the year adjustment x and the date in the month date and then reducing the sum mod 7 gives us the day in the week with the week starting three days before March 1 of (every) cycle. (Three days before because (1) the magic formula (31 * m0) / 12 starts with 2, not 0, and (2) the day of the month starts with 1, not 0. So the formula is off by 3.)

This is not the only way of performing this calculation. As it happens, exactly the same sequence is produced with (13 * m0 - 1) / 5. Either way, the cleverness is not justified by efficiency; division is a lot slower than a simple table lookup:

/* Not optimal but it corresponds to the above computation */
static const char month_adjust[] = {
    2, 5, 7, 10, 12, 15, 18, 20, 23, 25, 28, 31
};
int d0 = (date + x + month_adjust[m0]) % 7;

The above table could be reduced to three bits per month, since only the value mod 7 is important. That means that the lookup table could be replaced with a magic integer constant and a bit-shift, but the potential gain is probably insignificant. I'll leave the details as an exercise for would-be code golfers.
March 1 of every cycle is a Wednesday, and that needs to correspond to the value 3 of that computation. The mapping between modulo and day of the week is provided by the switch statement:

switch (d0) {
    case 1: return "Monday";
    case 2: return "Tuesday";
    case 3: return "Wednesday";
    case 4: return "Thursday";
    case 5: return "Friday";
    case 6: return "Saturday";
    case 0: return "Sunday";
}

I would have used a lookup table instead of a switch, which leads to more direct code:

static const char* weekdays = {
    "Sunday", "Monday", "Tuesday",
    "Wednesday", "Thursday",
    "Friday", "Saturday"
};
return weekdays[d0];


Many people cringe at the notation $n^2=O(n^3)$, since, strictly speaking, $O(n^3)$ is a set of functions, defined by
$$
O(n^3)=\{f\mid \exists k>0, N\ge 0\, [f(n)\le kn^3\text{ for all }n\ge N\}
$$
In other words,
$$
O(n^3)=\{1, n, n^2, n^2\log n, n^3, 3n^3+15n^2,\dotsc\}
$$
which is to say $O(n^3)$ consists of all functions $f(n)$ that are eventually less than a constant multiple of $n^3$.

With this understanding, to be precise we should write $n^2\in O(n^3)$, rather than the sloppier $n^2=O(n^3)$. This means that it is indeed notationally correct to ask whether $O(n^2)=o(n^3)$, since they are both sets of functions.

[Note, by the way, I'm not asserting that $O(n^2)=o(n^3)$. I'll leave that to you to prove or disprove.]


proof that BFS remains total after adding edge to graph

Let us assume that $G$ is a connected undirected finite graph.

Instead of by induction, a direct proof by contradiction as the following is probably easier and clearer.

Suppose we have just finished a BFS starting at vertex $s$. For the sake of contradiction, let us assume that there is a vertex $u$ of $G$ that is unvisited. Because $G$ is connected, there is a path from $s$ to $u$. Select the first unvisited vertex on that path and name it $u'$ (which may or may not be $u$). Let $s'$ be the vertex right before $u'$ on that path (which may or may not be $s$). Then $s'$ must be visited.

Now take a moment to reflect on BFS. Whenever a vertex is visited, each of it adjacent vertices must have been visited earlier or later; I will let you prove this proposition rigorously. However, this contradicts that $s'$, a visited vertex is adjacent to $u'$, an unvisited vertex. Our proof is done.

Here is the summary of the proof strategy. A subset of vertices of a connected graph that is closed under adjacency must contain all vertices. This also holds for infinite graphs.


How does an image classifier select relevant features?

There is no single answer.  A cascade is a very simple idea: it basically represents a bunch of classifiers, applied sequentially.

You are free to decide how each individual cascade will work.  You could design the cascade so that every classifier uses the same set of features.  Or, you could design the cascade so that each classifier has a different subset of features.  They're both considered cascades.

In the standard cascades I've seen used in computer vision, there is one set of features.  Each stage in the cascade is a single classifier which is trained on the entire feature vector.  Part of the training involves selecting a subset of the features (perhaps only a few features) to use at that stage of the cascade.  The training process is responsible for that, and there are many different algorithms for training out there.  One example is ADAboost, with decision stumps as the weak classifier; you could take a look at that to see how it works.


Build PDA for a language with unknown input alphabet

You might reason like this: If $L_1, L_2$ are regular, then $L_2^R$ is regular ($L^R$: reverse words). You can build regular grammars $G_1 = (N_1, \Sigma_1, P_1, S_1)$ and $G_2 = (N_2, \Sigma_2, P_2, S_2)$ that generate $L_1$ and $L_2^R$. The crucial point is that the regular grammars have the lonely non-terminal always at the end (or beginning!) of the sentential form. Build a CFG with nonterminals $Q = N_1 \times N_2$, and productions that build up $L_1$ to the left (using the first part of the nonterminal) and $L_2^R$ to the right (using the second part of the nonterminal, building from the end). From the resulting grammar you can build a PDA.
The basic idea is similar to the construction for $\{ w w^R \colon w \in \Sigma^*\}$ with $S \to x S x$ for all $x \in \Sigma$ and $S \to \varepsilon$ (or $S \to xx$ for purists).


Which law is this expression X+ X’.Y=X+Y

One way of looking at this is as a consequence of distributivity, where $P+QR\equiv (P+Q)(P+R)$. Then you'll have
$$\begin{align}
X+(X'Y) &\equiv (X+X')(X+Y)&\text{distributivity}\\
&\equiv T(X+Y)&\text{inverse}\\
&\equiv X+Y&\text{domination}
\end{align}$$


Efficient data structure for storing integers in a range?

Since you know you're going to have to deal with all $2^{32}$ values eventually, you're going to need at least $2^{32}$ bits of memory, one for each value. The pigeonhole principle means that there's no possible way to store all the information you need with fewer bits than this.

So I recommend a straightforward bitmap. In other words, a simple array of bits. When a new value comes in, see if the corresponding bit is on or not; if it's off, flip it on. This takes the minimum possible amount of space, and is extremely fast (since all you have to do is index into an array).

P.S. You need $2^{32}$ bits specifically because the numbers could appear in any order. This means that there are $2^{2^{32}}$ possible states the program could be in, one for every possible combination of seen and not-seen values. Representing this many states will always take at least $2^{32}$ bits. If you knew the numbers would always come in increasing order, on the other hand, there'd only be $2^{32}$ states to distinguish between (since all you care about is the highest value seen so far), so you'd need a minimum of $32$ bits.


Name for class of algorithms preserving accuracy/confidence

I'm not familiar with any standard name for this type of algorithm.  Go ahead and write your research paper and define a class with a name of your own choice (confidence-preserving seems like a quite good name to me).


State Machine and State transition Table - Explanation and Creation Of

The state transition function just says "If you're in state $X$ and receive input $Y$, go to state $A_{X,Y}$", for every possible $X$ and $Y$.

Designing the transition function is a matter of programming; implementing it is just a case of

state := start_state
while state is not a terminating state do
    input := read_input ();
    state := A[state, input];
done


Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

You can partially compute $f^{-1}(y)$ as follows:

  for $x$ from $0$ to $\infty$:

    if $f(x) = y$ then return $x$

If you don't like for loops, you can use the following implementation:

  $x \gets 0$
  if $f(x) = y$ then return $x$
  $x \gets x + 1$
  goto step 2


How can I prove that if $\chi(G) > k \wedge \vert\{ad(H): H\ is\ an\ induced\ subgraph\ of\ G\}\vert$ then $G$ has a $k-regular$ induced subgraph?

Hint: It's better to prove that if $mad(G) \leq k$ and no induced subgraph of $G$ is $k$-regular then $\chi(G) \leq k$. Here is the idea of the proof:

Show that $G$ has a vertex $v$ of degree smaller than $k$.
Color $G - v$ using $k$ colors (by induction).
Complete this to a $k$-coloring of $G$.


What properties of a programming language make compilation impossible?

The distinction between interpreted and compiled code is probably a
fiction, as underlined by Raphael's comment:

the claim seems to be trivially wrong without further assumptions: if there is
an interpreter, I can always bundle interpreter and code in one executable ...

The fact is that code is always interpreted, by software, by hardware
or a combination of both, and the compiling process cannot tell which
it will be.

What you perceive as compilation is a translation process from one
language $S$ (for source) to another language $T$ (for target). And, the
interpreter for $S$ is usually different from the interpreter for $T$.

The compiled program is translated from one syntactic form $P_S$ to
another syntactic form $P_T$, such that, given the intended semantics
of the languages $S$ and $T$, $P_S$ and $P_T$ have the same
computational behavior, up to a few things that you are usually trying
to change, possibly to optimize, such as complexity or simple efficiency (time, space,
surface, energy consumption). I am trying not to talk of functional equivalence, as it would require precise definitions.

Some compilers have been actually used simply to reduce the size of
the code, not to "improve" execution. This was the case for language used in the Plato system (though they did not call it compiling).

You may consider your code fully compiled if, after the compiling
process, you no longer need the interpreter for $S$. At least, that is
the only way I can read your question, as an engineering rather than
theoretical question (since, theoretically, I can always rebuild the
interpreter).

One thing that may raise problem, afaik, is meta-circularity. That
is when a program will manipulate syntactic structures in its own source
language $S$, creating program fragment that are then intepreted as if
they had been part of the original program. Since you can produce
arbitrary program fragments in the language $S$ as the result of arbitrary computation manipulating meaningless syntactic fragments, I would guess you can
make it nearly impossible (from an engineering point of view) to
compile the program into the language $T$, so that it now generate
fragments of $T$. Hence the interpreter for $S$ will be needed, or at
least the compiler from $S$ to $T$ for on-the-fly compiling of
generated fragments in $S$ (see also this document).

But I am not sure how this can be formalized properly (and do not have
time right now for it). And impossible is a big word for an issue that is not formalized.

Futher remarks

Added after 36 hours. You may want to skip this very long sequel.

The many comments to this question show two views of the problem: a
theoretical view that see it as meaningless, and an engineering view
that is unfortunately not so easily formalized.

There are many ways to look at interpretation and compilation, and I
will try to sketch a few. I will attempt to be as informal as I can manage

The Tombstone Diagram

One of the early formalization (early 1960s to late 1990) is the T or
Tombstone diagrams. These diagrams presented in composable graphical
elements the implementation language of the interpreter or compiler,
the source language being interpreted or compiled, and the target
language in the case of compilers. More elaborate versions can add
attributes. These graphic representations can be seen as axioms,
inference rules, usable to mechanically derive processor generation
from a proof of their existence from the axioms, à la Curry-Howard
(though I am not sure that was done in the sixties :).

Partial evaluation

Another interesting view is the partial evaluation paradigm. I am
taking a simple view of programs as a kind of function implementation
that computes an answer given some input data. Then an interpreter
$I_S$ for the language $S$ is a program that take a program $p_S$
written in $S$ and data $d$ for that program, and computes the result
according to the semantics of $S$. Partial evaluation is a technique
for specializing a program of two arguments $a_1$ and $a_2$, when only
one argument, say $a_1$, is known. The intent is to have a faster
evaluation when you finally get the second argument $a_2$. It is
especially useful if $a_2$ changes more often than $a_1$ as the cost
of partial evaluation with $a_1$ can be amortized on all the
computations where only $a_2$ is changing.

This is a frequent situation in algorithm design (often the topic of
the first comment on SE-CS), when some more static part of the data is
pre-processed, so that the cost of the pre-processing can be amortized
on all applications of the algorithm with more variable parts of the
input data.

This is also the very situation of interpreters, as the first argument
is the program to be executed, and is usually executed many times with
different data (or has subparts executed many times with different
data). Hence it become a natural idea to specialize an interpreter for
faster evaluation of a given program by partially evaluating it on
this program as first argument.  This may be seen as a way of
compiling the program, and there has been significant
research work on compiling by partial evaluation of a interpreter on
its first (program) argument.

The Smn theorem

The nice point about the partial evaluation approach is that it does
take its roots in theory (though theory can be a liar), notably in
Kleene's Smn theorem.  I am trying here to give an intuitive
presentation of it, hoping it will not upset pure theoreticians.

Given a Gödel numbering $\varphi$ of recursive functions, you can
view $\varphi$ as your hardware, so that given the Gödel number $p$
(read object code) of a program $\varphi_p$ is the function defined
by $p$ (i.e. computed by the object code on your hardware).

In its simplest form, the theorem is stated in wikipedia as follows
(up to a small change in notation):

  Given a Gödel numbering $\varphi$ of recursive functions, there is a primitive recursive function $\sigma$ of two arguments with the following property: for every Gödel number $q$ of a partial computable function $f$ with two arguments, the expressions $\varphi_{\sigma(q,x)}(y)$ and $f(x,y)$ are defined for the same combinations of natural numbers $x$ and $y$, and their values are equal for any such combination. In other words, the following extensional equality of functions holds for every $x$:
      $\;\;\varphi_{\sigma(q,x)} \simeq \lambda y.\varphi_q(x,y).\,$

Now, taking $q$ as the interpreter $I_S$, $x$ as the source code of a
program $p_S$, and $y$ as the data $d$ for that program, we can write:
   $\;\;\varphi_{\sigma(I_S,p_S)} \simeq \lambda d.\varphi_{I_S}(p_S,d).\,$

$\varphi_{I_S}$ may be seen as the execution of the interpreter $I_S$
on the hardware, i.e., as a black-box ready to interpret programs
written in language $S$.

The function $\sigma$ may be seen as a function that specializes the
interpreter $I_S$ for the program $P_S$, as in partial evaluation.
Thus the Gödel number $\sigma(I_S,p_S)$ may be seen has object code that is
the compiled version of program $p_S$.

So the function $\;C_S = \lambda q_S.\sigma((I_S,q_S)$ may be seen as
a function that take as argument the source code of a program $q_S$
written in language $S$, and return the object code version for that
program. So $C_S$ is what is usually called a compiler.

Some conclusions

However, as I said: "theory can be a liar", or actually seem to be one. The problem is that we
know nothing of the function $\sigma$. There are actually many such
functions, and my guess is that the proof of the theorem may use a
very simple definition for it, which might be no better, from an
engineering point of view, than the solution proposed by Raphael: to
simply bundle the source code $q_S$ with the interpreter $I_S$. This
can always be done, so that we can say: compiling is always
possible.

Formalizing a more restrictive notion of what is a compiler would
require a more subtle theoretical approach. I do not know what may
have been done in that direction. The very real work done on partial
evaluation is more realistic from an engineering point of view. And
there are of course other techniques for writing compilers, including
extraction of programs from the proof of their specification, as
developed in the context of type-theory, based on the Curry-Howard
isomorphism (but I am getting outside my domain of competence).

My purpose here has been to show that Raphael's remark is not "crazy",
but a sane reminder that things are not obvious, and not even
simple. Saying that something is impossible is a strong statement
that does require precise definitions and a proof, if only to have a
precise understanding of how and why it is impossible. But building
a proper formalization to express such a proof may be quite difficult.

This said, even if a specific feature is not compilable, in the sense
understood by engineers, standard compiling techniques can always be
applied to parts of the programs that do not use such a feature, as is
remarked by Gilles' answer.

To follow on Gilles' key remarks that, depending on the language, some
thing may be done at compile-time, while other have to be done at
run-time, thus requiring specific code, we can see that the concept of
compilation is actually ill-defined, and is probably not definable in
any satisfactory way. Compilation is only an optimization process, as
I tried to show in the partial evaluation section, when I compared
it with static data preprocessing in some algorithms.

As a complex optimization process, the concept of compilation actually
belongs to a continuum. Depending on the characteristic of the
language, or of the program, some information may be available
statically and allow for better optimization. Others things have to be
postponed to run-time. When things get really bad, everything has to
be done at run-time at least for some parts of the program, and
bundling  source-code with the interpreter is all you can do. So this
bundling is just the low end of this compiling continuum. Much of the research on compilers is about finding ways to do statically what used to be done dynamically. Compile-time garbage collection seems a good example.

Note that saying that the compilation process should produce machine
code is no help. That is precisely what the bundling can do as the
interpreter is machine code (well, thing can get a bit more complex
with cross-compilation).


Computing the error bound of floating-point expression

IEEE 754 gives you the maximum relative error of each operation. You have three differences with a maximum relative error each. Multiplication and division adds the maximum relative error of each operand, plus the maximum relative error of the multiplication and division.

Then you have a final addition. If the right hand side is very close to the negative of the left hand side of the "+" then the relative error is unlimited. You'd need to analyse how close to -a.y the right hand side can be.

For absolute error, you convert the relative error of the right hand side into an absolute error.


There might be some more clever trick in the analysis to get rid of the $V$, but at the very least, I can provide some intuition as to why you can get rid of it.

With Ford-Fulkerson, it is generally assumed that you are working with connected graphs.

For any connected graph with $V$ nodes, there are at least $V-1$ edges, since each node needs at least one edge (except the "last" one in a sense) to be connected.

This means that, either there are $O(V)$ edges, in which case $O(V + E) = O(E)$, or the number of edges dominates the number of vertices (for example, when there are $O(V^2)$ edges), in which case the $V$ gets dominated and we can just write $O(E)$.

When you learn breadth-first search and depth-first search, one of the main applications is testing for connectedness and finding connected components. Here, you could be dealing with a graph with thousands of components, so it makes sense to not assume that there is one component.


What computational model supports arbitrarily sized integers?

I suspect you're looking for either the RAM model or the transdichotomous model.  They differ primarily in how they take into account the size of integers and their effect on the time of various operations.  See What's the difference between transdichotomous model and RAM?.

If you want your results to have any applicability at all, the main thing is to pick a model that avoids treating the time to do arithmetic on exponential-length integers as polynomial, otherwise you can end up with absurd results.  If you count each arithmetic operation as $O(1)$ time, no matter how large the numbers are, then you end up with absurd results like polynomial-time algorithms for factoring and indeed all of #PSPACE.  See https://cs.stackexchange.com/a/53885/755.

Note that proving a problem is in P is not the same as proving it runs in polynomial time on some strange model of computation.  P is defined as problems that have an algorithm that run in polynomial time on a Turing machine.  As mentioned in the previous paragraph, if you change "on a Turing machine" to some other model of computation, that statement might no longer hold.

It's a famous open problem with factorization is in P or not. The problem is likely to be very difficult, with our current state of understanding.  I would not recommend taking on such an ambitious goal.


Decision problem such that any algorithm admits an exponentially faster algorithm

It seems to be a simple case of Blum's Speedup Theorem:

  Given a Blum complexity measure $(\varphi, \Phi)$ and a total computable function $f$ with two parameters, then there exists a total computable predicate $g$ (a Boolean valued computable function) so that for every program $i$ for $g$, there exists a program $j$ for $g$ so that for almost all $x$
  $$f(x,\Phi_j(x)) \leq \Phi_i(x)$$

Just let the the complexity measure be the time complexity measure (i.e. $\Phi_e(x)$ is the time complexity of the Turing machine with code $e$) and let $f(x,y) = 2^y$.


Is no language with the non-primes property context-free?

You can use Parikh's theorem to prove this claim.

Indeed, if such a language was context-free, then its Parikh image would be regular. But the Parikh image would also satisfy the condition (as it only talks about length of words). It's very easy to prove that no regular language can satisfy this condition (e.g. by complementing it and using the pumping lemma).


Is it possible to find the nodes larger than k in a min-max heap in O(m) time?

You can use a max-heap and a min-heap containing the same elements, with pointers joining pairs of identical elements in both heaps. This allows supporting all the usual operations in logarithmic time, and the new operation (finding all nodes larger or smaller than a given value) in time linear in the output size.


What do you mean by "solve"?

Do you want to provide an algorithm for the problem? Then you reduce $X$ to $Y$ and use a supposedly known algorithm $A_Y$ to solve it. That is, if you have an instance $x$ of $X$ , you use the reduction $f$ to convert it to some instance $y=f(x)$ of $Y$ and then use the algorithm that solves $Y$ on instance $y$. In that way, you have an algorithm with running time $T_f + T_{A_Y}$ for $X$.
What if by solve you mean to find out the complexity of $X$, in this case prove that $X$ is $\mathbb{NP}$-hard?

Instead of providing a one-time answer, I would like to show you why this answer holds. As it is common in mathematics and science in general, the level of abstraction you are working on might be helpful, yet it covers some fine details. For example, the intuitive measurement of the resources spent, most notably time, has its basis on a complicated scheme with the purpose to define reductions with some desirable properties.

For polynomial-time reductions, like the ones we use to prove $\mathbb{NP}$-completeness, you can treat reductions as the $\leq$ operator (in mathematical terms, polynomial-time reductions define a partial order. In general, reductions define a preorder). That is, the right hand side is always at least as hard as the left hand. At this point of the discussion, I beg you to remember that we compare problems, so in the extreme case that a single instance is hard and the rest easy, this single instance determines the complexity of the entire problem.

Now, we can answer your question. We know that $Y$ is a $\mathbb{NP}$-hard problem and we want to prove that $X$ is at least as hard as $Y$. Therefore, thinking in terms of the $\leq$ operator, it is suffices to reduce $Y$ to $X$, that is $Y \leq _{p} X$. Provided you have that reduction, $X$ is at least as hard as $Y$. And $Y$ is $\mathbb{NP}$-hard, so $X$ must be $\mathbb{NP}$-hard too. By definition, if you can prove that $X \in \mathbb{NP}$, then $X$ is $\mathbb{NP}$-complete.

At the end of this discussion, you might have noticed a problem. The satisfiability problem $SAT$ is $\mathbb{NP}$-complete, yet there exists a simple $O(n)$ nondeterministic time algorithm for it. How can it be as least as hard as any problem in $\mathbb{NP}$? The answer is simple: Polynomial-time differences are not of an interest to us, as we have defined our model. So, the polynomial-time reduction behaves like the $\leq$ operator, though it allows the complexity of the left hand side to be larger up to a polynomial than the running time of the harder problem. This is why we don't use exponential time reductions, since the error margin would be larger than the complexity of the problems themselves (and the definition of the respective classes), making them useless.


Choosing an independent hash function, given hash function value

From what I have understand from your question, I think you are looking for a way to transform a probability distribution to another probability distribution. For example, if your first hash function distributes your data into a gaussian/normal form into the buckets, then you need a function that takes the index of this bucket as input and gives you another bucket which must be chosen uniformally. This post may be helpful if I ve understand correctly what you are trying to achieve: https://stats.stackexchange.com/questions/223317/how-to-transform-one-pdf-into-another-graphically
My personal opinion is that a successful transformation depends a lot in your data. A hash function tries to distribute the data uniformally in the first place. But, even if you have a function G that distributes your data in a "weird" way then you can make a transformation T: G -> F so that F is whatever distribution you like.

[EDIT]
I don't think that this is achievable without using randomization. For example, if you have a hash function that maps all your data into one bin (for example the bin 0) then this function is constant. So, you are trying to create a function that takes a constant value and maps it uniformally, which cannot be done if you don't use any randomness or internal memory. By internal memory, I mean that your function "should remember" what kind of inputs has already "seen", and map them in a different value each time.


Java, strong typing, covariance and contra-variance

"Structurally typed" means that you don't need to write implements I: if your type has all the methods I has, with compatible signatures, it's automatically a subtype of I. However, in this case, C.equals(C) does not implement I.equals(I) (due to variance) and so C isn't a subtype of I.

EDIT:

  I'll explain: For C to be structurally equivalent to I we need to know the type hierarchy for the arguments of equals.

Yes, here you have recursive structural types, which complicate the issue quite a bit.

  The equals method in C changes the paramater in a covariant way and so it doesn't match the equals method in I.

This is strictly speaking incorrect, this isn't covariant (again, since C isn't a subtype of I). It should instead say e.g. "if we assume C is a subtype of I, then the equals method in C changes the parameter in a covariant way and we get a contradiction". You could claim C and I should be treated as equivalent (i.e. both subtypes of each other), and then there is no contradiction.

Another problem is that definition of C depends on C itself, so you have recursive structural types, which complicate the language quite a bit.


Why do some search trees store all the elements in leaves, while others don't?

The point is that often data is bulky and moreover of variable size (i.e., a full student record) while the keys needed to locate the data (name, enrollment number) is small and fixed size. Different requirements, keep them separate.


The product is the monoid product. A monoid is a set equipped with an operation (which we can call product) satisfying certain axioms. The classical monoid we use in formal languages is $\Sigma^*$ (for some alphabet $\Sigma$), in which case the monoid product is indeed concatenation. But this is not the only possibility: for example, every group is a monoid, since the monoid axioms are a subset of the group axioms.


3-Hitting Set problem is known in parameterized complexity theory. The requirement $\cup S_i=R$ can always be assumed without loss of generality. See e.g. An efficient fixed-parameter algorithm for 3-Hitting Set. According to this link it is NP-hard in its usual (not parameterized) form. Proving NP-completeness of your problem we give reduction FROM 3-Hitting Set to your problem not vica versa. Therefore your problem is NP-complete (in its decision form).


Policy dependent on initial state distribution in finite horizon MDPs

On an MDP the main assumption is that states are independent (Markov Decision Process). Any policy in such environments will decide an action on a given state independently of previous visited states, taken actions and received rewards.
This means that the optimal policy doesn't depend at all on the initial distribution. However the initial distribution might affect the expected reward but it won't affect the optimal policy.
To be clear on your second question, the condition that allow us to rule out this dependency is the markov property: The future is independent from the past given the current state. So the optimal policy will have a distribution of actions to take depending only in the state, without caring about the weight of such state in the initial distribution.


Is matrix multiplication cheaper than inverse?

Matrix multiplication and matrix inverse have the same asymptotic running time. If we denote the running time of multiplying two $n \times n$ matrices by $T_1(n)$, and that of inverting an $n \times n$ matrix by $T_2(n)$, then this means that there exist constants $A,B$ such that
$$ T_1(n) \leq AT_2(n) \\ T_2(n) \leq BT_1(n). $$
However, the constants $A,B$ can be significant. (Also, numerical stability might be an issue.)

Checking your claim is, however, very easy in practice. Choose your favorite matrix library (e.g. LAPACK), and you can determine empirically $T_1(n),T_2(n)$ for the values of $n$ that you are interested in, on the hardware platform that you are interested in.


What is the chance that this code terminates?

This is an example of a branching process. The behavior of a branching process depends on the expected number of children, which in your case is $1.25 > 1$. When this number is at most 1, the process gets extinct with probability 1. When the number is more than 1, it has a chance of surviving forever; the extinction probability is just what you calculated — you need to select the root which is smaller than 1.


O(1) space, O(N) complexity algorithm for buy and sell stock twice interview question

Here's an O(1) space, O(n) time algorithm with Java code.
Logic:

Let $P_i$ denote the price of the stock on day $i$.

Calculate maximum profit for $1^{st}$ transaction by $selling$ at or before day $i$ the usual way i.e. by calculating $Max(P_i - min[P_0...P_{i-1}])$. Call this $MaxProfit1_i$.
If you had sold before day $i$ you can buy again at day $i$. If you do so, you'll need to deduct day $i$'s price from the 1st transaction's profit. Then, the maximum leftover profit at day $i$ is $Max(P_i - MaxProfit1_i)$. Call this $MaxLeftOver_i$.
In the same vein, if you had bought the 2nd stock before day $i$, you can sell it at day $i$. If you do so, you add
day $i$'s price to the previous leftover profit to arrive at your profit at day $i$ with 2 transactions. Then, the maximum profit at day $i$ with 2 transactions is $Max(P_i + MaxLeftOver_i)$ - which is the final answer.

public int maxProfitWith2Transactions(int[] prices) {
    if (prices.length == 0) return 0;

    int minPrice                      = prices[0];
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int i = 1; i < prices.length; i++) {
        final int p = prices[i];
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        minPrice                    = Math.min(p, minPrice);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

The below modified (slightly faster) variant of the above beats every solution in both space and time on LeetCode.
public int maxProfitWith2Transactions(int[] prices) {
    int minPrice                      = Integer.MAX_VALUE;
    int maxProfitAfterFirstSell       = 0;
    int maxProfitLeftAfterSecondBuy   = Integer.MIN_VALUE;
    int maxProfitAfterSecondSell      = 0;

    for(int p : prices) {
        minPrice                    = Math.min(p, minPrice);
        maxProfitAfterFirstSell     = Math.max(p - minPrice, maxProfitAfterFirstSell);
        maxProfitLeftAfterSecondBuy = Math.max(maxProfitAfterFirstSell - p, maxProfitLeftAfterSecondBuy);
        maxProfitAfterSecondSell    = Math.max(p + maxProfitLeftAfterSecondBuy, maxProfitAfterSecondSell);
    }
    return maxProfitAfterSecondSell;
}

Here's the values that the above code calculates for prices 8, 10, 3, 7, 4, 9, 2, 3.
Clearly, the max profit after 1 transaction is 6 (Buy at 3, sell at 9). After 2 transactions, the max profit is 9 (Buy at 3, Sell at 7, Buy again at 4, sell at 9).
$$\begin{array}{l|r r r r r r r r}
\text{$i$} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} \\ \hline
\text{Price} & \text{8} & \text{10} & \text{3} & \text{7} & \text{4} & \text{9} & \text{2} & \text{3} \\ \\ \hline
\text{Lowest price seen} & \text{8} & \text{8} & \text{3} & \text{3} & \text{3} & \text{3} & \text{2} & \text{2} \\
\text{till day $i$} \\  \hline
\text{Max Profit if} & \text{x} & \text{2} & \text{2} & \text{4} & \text{4} & \text{6} & \text{6} & \text{6} \\
\text{bought at lowest} \\
\text{price before day $i$}  \\
\text{and sold before}  \\
\text{or on day $i$}  \\ \hline
\text{Max Profit left if} & \text{x} & \text{-8} &  \text{-1} & \text{-3} & \text{0} & \text{0} & \text{4} & \text{4} \\
\text{2nd buy is done on} \\
\text{day $i$.} \\
\text{= Max(PreviousRow$_i$ - $P_i$)} \\ \hline
\text{Max Profit if 2nd} &  \text{x} & \text{2} & \text{2} & \text{4} & \text{6} & \text{9} & \text{9} & \text{9} \\
\text{stock is sold before} \\
\text{or on $P_i$} \\
\text{= Max(PreviousRow$_i$ + $P_i$)} \\ \hline
\end{array}$$


For example, the running time $O(2^{1/\varepsilon} \cdot n^2)$ corresponds to a PTAS, since the running time depends polynomialy on $n$, but not on $1/\varepsilon$ since it is in the exponent. The running time $O(1/\varepsilon \cdot n \log{n})$ depends polynomialy on $n$ and $1/\varepsilon$, so it corresponds to a FPTAS.

NB, you also need to show that your algorithm has an approximation ratio of $(1 + \varepsilon)$ (or -) to show the algorithm is in fact a (F)PTAS.


Can Von Neumann bit extraction be made more efficient?

Suppose you are going to throw a 6-sided die N times.  You can convert that to an integer in the range $[0,6^N-1]$, by viewing the sequence of N outcomes as a base-6 representation of an integer.  This gives you a random number chosenly uniformly at random from $[0,6^N-1]$.

Now pick a value of $k$ such that $2^k < 6^N$.  Let $Y = \lfloor 6^N/2^k \rfloor \times 2^k$.  You can now use the following algorithm to output a $k$-bit number (much of the time):

Generate a random number from the range $[0,6^N-1]$ by tossing a 6-sided die $N$ times.  Suppose the number you get is $x$.  If $x < Y$, then output the value $x \bmod 2^k$ (which can be viewed as $k$ bits).  Otherwise, output nothing -- you will have to re-roll.

This produces a uniform random distribution on $k$-bit values.  It produces output on any given attempt with probability $Y/6^N$; on average, the expected number of times you'll have to repeat this procedure is $6^N/Y$, which is a bit more than $1$ (but not much more than $1$, as long as you're not too greedy and don't pick $k$ too large).

It's possible to do a bit better, by saving information about the value of $x-Y$ when you repeat the process, but this might not make a big difference in practice.

See also Generating uniformly distributed random numbers using a coin and Is rejection sampling the only way to get a truly uniform distribution of random numbers? and How to simulate a die given a fair coin and Isn't std::bernoulli_distribution inefficient? Designing a bit-parallel Bernoulli generator.


SMO, Random forest and Bayes net algorithms: why does Random forest perform better?

In machine learning, there's often no clear "why" or "reason" we can point to.  These are different methods, which implicitly embed different biases or different priors or different assumptions, and thus will work better in different situations.


Looping and branching with Algorithmic Differentiation

AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the contents of variables whose derivatives are to be calculated (or variables depending on them).  Here is an example:

if x = 3 then 9 else x * x

At close inspection you will recognize that the above is really just an inefficient way of implementing $x*x$.  If you evaluate this program at $x = 3$, then the result is the constant $9$.  But the derivative of constants is zero, which is obviously not the right answer, which should be $6$.

The reason is that AD will typically only look at the executed branch of your program.  It is perfectly ok to have branches on conditions that don't involve numbers, or conditions involving number variables not part of the computational graph for derivative calculations.  It's also ok to look at fixed properties of derivative values (e.g. the dimension of a vector).  But as soon as you "look" at the contents of a variable that depends on one of the inputs to determine what calculation to perform next, you will "break the chain".  AD does basically just that: apply the chain rule.

Users of AD should view programs as "configuring" a fixed computational graph.  If running the program with different inputs for which derivatives are requested gives you different computational graphs, AD may not always give the correct result.


Why is first-order logic (without arithmetic) VALIDITY only recursively enumerable, and not recursive?

However, I am not seeing why VALIDITY is not recursive as well, because given a formula $\phi$, one could run two Turing Machines for THEOREMHOOD, one on $\phi$ and the other on $\neg \phi$, concurrently. Since at least one of them is valid, it is always possible to decide whether $\phi$ is valid, or not valid. What am I missing?

This is wrong. A formula $\phi$ is valid iff it holds in all models.

It is not true that at least one of $\phi$ and $\lnot\phi$ must be valid: both might hold in some models, but not all of them.

Trivial example: take FOL with two constant symbols ${\sf a}, {\sf b}$, and the formula $\phi \equiv {\sf a}={\sf b}$. Then $\phi$ holds in some models (those which interpret $\sf a$ and $\sf b$ with the same point), but not all of them (a model can map them to distinct points). And indeed, FOL can not prove ${\sf a} = {\sf b}$ nor ${\sf a} \neq {\sf b}$.


Every decidable language $L$ has an infinite decidable subset $S \subset L$ such that $L \setminus S$ is infinite

If $L$ has a finite alphabet, then $L$ is recursively enumerable.
Then, from such an enumeration $w_0,w_1,w_2,...$ of the words of $L$ you can take $S=\{w_0,w_2,w_4,...\}$, which will also be decidable. To check if a word $w$ is in $S$ check if it is in $L$. If it is then use the enumeration of $L$ to check if its position is even or not.


Given L is a regular language, prove that Perm(L) is Context-Free

For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter:
$$
(\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) -
(\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)),
$$
and only accepts if this equals zero at the end. Since
$$
\#_a(\sigma_1 \ldots \sigma_i) + \#_b(\sigma_1 \ldots \sigma_i) =
\#_a(\tau_1 \ldots \tau_i) + \#_b(\tau_1 \ldots \tau_i),
$$
the counter equals zero iff $\tau_1 \ldots \tau_i$ is a permutation of $\sigma_1 \ldots \sigma_i$ (this only works because the alphabet is binary).
To see that this approach doesn't work for a ternary alphabet, it suffices to consider
$$
\operatorname{Perm}((abc)^*) \cap a^*b^*c^* = \{ a^nb^nc^n : n \geq 0 \}.
$$


Find subsequence of maximal length simultaneously satisfying two ordering constraints

A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers).
First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending).
Now, define $M[f, v]$ to be the maximal number of fruits in a sublist, containing only the last $f$ fruits (of the sorted list), having a vitamin content of at most $v$. $M[0, *] = 0$ and
$$M[f, v] = \begin{cases}
 \mathrm{max} \{M[f-1, v], 1 + M[f-1, V_f]\} & \text{if \(V_f <= v\)} \\
 M[f-1, v] & \text{otherwise} \\
\end{cases}$$
Using dynamic programming gives you a solution that runs in $O(\text{number of fruit} \times \text{possible vitamin values})$.


The (non)halting condition for PDAs doesn't make much sense; "non-halting" for a PDA means that there are one or more $\epsilon$-moves (not input read) that can cause a "loop" or an infinite stack expansion.

In order to test if a PDA accepts a string $x$, a Turing machine should not "barely simulate" it  (i.e. recusively enumerate all reachable (partial input,stack content,state) configurations of the PDA. Otherwise such machine could never end if the PDA doesn't accept the string and it contains $\epsilon$-moves.

In order to test if a PDA accepts $x$ it you should build the equivalent CFG anc check if the CFG generates the string $x$.

Also note that for any PDA $A$ there is an equivalent (costructible) PDA $A'$ with no $\epsilon$-moves (real-time PDA, i.e. the PDA reads a letter from its input every step) and even there is an equivalent $A''$ with no $\epsilon$-moves and only one state (simple real-time PDA). See Greibach normal form.

A TM once constructed $A'$ (or $A''$) can barely simulate it, enumerating all the possible nondeterministic choices, but in this case it will surely halt.


Number of finite strings over a countably infinite alphabet

It's countable.  The set $S_\ell$ of strings of length $\ell$ is $\Sigma\times\dots\times\Sigma$, which is a finite product of countable sets, so is countable. Now, the set of all finite strings is $\bigcup_{\ell\geq 0}S_\ell$, which is a countable union of countable sets, which is countable.

Usually, you can only get an uncountable set from countable ones by taking the power set.


Knapsack problem 0/1 with even number of items

For the base case, the value is often decided manually based on the context of the problem. What should be the base value?

It is easy to see that $DP_{even}[0,0]$ should be $0$, and $DP_{even}[0,j]$ for $j>0$ should be $-\infty$. This is because the highest value you can get with considering none of the items and cost nothing is trivially 0, but the case where you consider none them but still cost something is impossible, hence we can safely assign it $-\infty$.

Now let's look at $DP_{odd}$. You might think that $DP_{odd}[0,0]$ is $0$, but following your definition, $DP_{odd}[0,0]$ means the highest value you can get with considering none of the items, and take an odd number of items and costs nothing. Notice the contradiction in this statement? You don't consider any items, then obviously you couldn't have taken an odd number of items! The same argument holds for all $DP_{odd}[0,j]$ for $j\geq 0$. Hence, they are all assigned $-\infty$.

To summarize, the base case is very similar. Both $DP_{even}[0,j]$ and $DP_{odd}[0,j]$ are mostly $-\infty$, except $DP_{even}[0,0]$ which is $0$. Now, you can safely run your recurrence relations on top of the base cases.


Minimum space needed to sort a stream of integers

Ok, it's way past my bedtime, but this won't let me go, so here's a second try (deleted my first)...

Before going into the specifics of how to sort the numbers, I will start by representing them not as a sequence of integers $i_1, i_2, \dots , i_n$, but as a sequence of their differences, i.e. $\delta_k = i_k - i_{k-1}$ where, by convention, $i_0 = 0$.

Then, in order to represent these values, I will first group them into buckets depending on the number of bits needed for their representation, with the assumption that I need one bit to represent 0. Since the numbers are between 0 and 99'999'999, I will need 27 buckets.

For each bucket, I will choose a prefix from the set 1, 01, 001, 0001, etc... Up to 000000000000000000000000001. Obviously, I will choose the shortest prefix for the largest bucket, the second-shortest for the second largest, etc...

The sequence of $\delta_k$ can then be written as pairs of prefixes and values, whereby for the values $>1$, the leading bit can be omitted.

For any random set of numbers, then, how many bits do I need to represent the sequence of $\delta_k$?

For a constant sequence, e.g. $0, 0, 0, 0, \dots , 0$, I only have to store one million representations of the number $0$, or with the above encoding, 10, hence 2 million bits. For any other constant, it would be 2 million bits plus the number of bits of that value for the initial $\delta_1$.

The same computation goes for an increasing sequence, e.g. $0, 1, 2, 3, \dots , n$, where $\delta_k=1$ and the sequence is represented as a million copies of 11.

Now what is the worst-case, i.e. what sequence of $\delta_k$ will give the longest sequence of bits? The worst we can do is make sure that each bucket has one entry less than the previous one, choosing the smallest $\delta_k$ possible, thus assigning the largest prefix to the longest sequences. For simplicity, I'll assume that $K$ buckets have the same amount of entries, with the shortest prefix assigned to the shortest sequence. This means that we have $n$ ones, $n$ twos, $n$ fours, etc... To represent the $j$th bucket, we need $2j-1$ bits, except for the first bucket, that needs $2$ bits.

So if we put $m$ $\delta_k$s into each of the $K$ buckets, we need $m\left(2 + \sum_{j=2}^{K}2j-1\right) = m(K^2 + 1)$ bits. However, the sum of all the $\delta_k$ must not exceed 99'999'999. This sum, assuming we've kept the $\delta_k$ as small as possible, is $m\sum_{j=2}^{K}2^{j-1} = m(2^K-2)$.

So here's the question: is there a combination of $K$ and $m$ such that

$m(2^K-2) < 100'000'000$, e.g. the largest value is $<100\,000\,000$,
$Km < 1'000'000$, e.g. there are at most a million values, and
$m(K^2+1) > 8'000'000$, e.g. we use more than $8\,000\,000$ bits?

Unfortunately, this does happen. Here's a plot of the number of bits as computed in Maple with plot( min( 100000000/(2^K-2) , 1000000/K ) * (K^2 + 1) , K=2..27 ):

So we can represent any sequence of up to one million numbers in $[0,99\,999\,999]$ using roughly 10 million bits. This is, unfortunately, still above the specification.

But how can we sort numbers like this? Well, remember that the numbers come in one by one, so as each number comes in, we update its bucket count ($\mathcal O(1)$) and compute the new optimal prefixes for each bucket ($\mathcal O(\log\log(i_\mathsf{max}))$ if the buckets are indexed in a heap). We then run through our encoded $\delta_k$, reading each entry, computing the respective $i_k$ from the cumulative sum, and comparing it to the new value. If the computed $i_k$ exceeds the new value, we encode the new value and write it back, along with the adjusted $\delta_k$, using the new encoding. Otherwise, we just write back the $\delta_k$ with the new encoding.

But write-back where? Well, if we treat our eight million bits as one large ring buffer, we can append the new, re-coded sequence of $\delta_k$ to the old sequence, re-writing the old values as we go along. We've got almost 1 million extra bits from the worse-case scenario, and I don't think the re-coding can cause that amount of stretching to make this not work.

All in all, this leaves us with a $\mathcal O(n)$ cost for inserting the $n$th number, which gives us an average-case cost of $\mathcal O(N^2)$ for a total of $N$ elements. This isn't really good, but speed did not seem to be a criteria.


Why Cook-Levin thorem's proof can mean SAT's NP-Hardness

Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.


Is persistence a property of a database?

The databases I've seen are persistent.  But rather than trying to figure out the "one true meaning" of the word database, if this aspect matters in a specific context, then I suggest you just be explicit about how you are using the word.  That's probably best in any case if this is critical.
A rose by any other name would smell as sweet.  (Shakespeare)


Regular expression for binary words with few zeros

@SamM's answer isn't completely right. Yes, it is $(01^m)^*$ for "each zero is followed by exactly $m$ ones", but this can't just be combined with "at least $n$ ones before". And a string of only ones complies always. So consider the ones between two zeroes:

If $m < n$, you can't comply with both conditions, so the language is just $1^n 1^* 0 1^m \mid 1^*$
If $m \ge n$, the only way to comply in between zeroes is to have $m$ ones there, so the language is $1^n 1^* (0 1^m)^+ \mid 1^*$


defining the operational semantics of a concurrent language

Coinductive Big-Step Semantics for Concurrency by Tarmo Uustalu writes:

  Second, contrary to what is so often stated, concurrency is
  not inherently small-step, or at least not more inherently
  than any kind of effect produced incrementally during a
  program’s run (e.g.,  interactive output).  Big-step semantics
  for concurrency can be built by borrowing the suitable
  denotational machinery, except that we do not want to use
  domains and fixpoints to deal with partiality, but
  coinductively defined sets and corecursion.

So the answer is that it is stated throughout the literature, but it is not true.


The difference between compiler and interpreter

In basic terms the difference between an interpreter and a compiler is the point at which a source text is actually executed.

An interpreter interprets a language by reading the text or source code and then performing computations as it processes the text to execute the text. So as the interpreter is reading the source of the program, the program runs or executes as the interpreter reads lines of code and performs those actions.

A compiler compiles a language by reading the text or source and transforms the source code into another form which is typically machine code.

To make things a bit more complicated you will see that some interpreters have a Just In Time (JIT) compiler component to them. So the process then is the interpreter reads the source code and converts it to an intermediate, more machine friendly, form which is then fed to a JIT compiler which creates a machine code which is then executed by the target hardware. Most interpreters of this form have a Virtual Machine which is hardware independent that uses a JIT compiler to target the actual hardware when the program is executing. The Virtual Machine is hardware independent but the JIT compiler must be tailored to the particular hardware. The JIT compiler compiles the Virtual Machine code or instructions into the target hardware machine code which is then executed by the hardware.

And by the way this kind of Virtual Machine is different from the virtual machine used with Docker and other types of containers which has hardware virtual machine support. The Virtual Machine used by these interpreters is an application which emulates some abstract hardware.

For examples of this kind of Virtual Machine look to the Java Virtual Machine. Or the Python Virtual Machine.  See Java “Virtual Machine” vs. Python “Interpreter” parlance?
.

And this document, Python (2.5) Virtual Machine: a guided tour has some of the gritty details about the Python Virtual Machine though an older version of Python.

A compiler will normally compile the source text to actual hardware machine language. So the output of a compiler depends on the actual target hardware. The machine code of a compiler that targets an x86 architecture is different from one that targets an ARM architecture.

Using a compiler will require additional software tools as the process for a compiler is generally something like the following:

create the source code file or files
compile the source code file or files to generate one or more object code files
link the object code files with various libraries to generate an executable
run the executable application

Using an interpreter will be a simpler procedure something like the following:

create the source code file or files
execute the interpreter program, specifying the source code file

The C programming language is normally a compiled language using a compiler. The python programming language is normally an interpreted language using an interpreter.

However there is nothing to stop someone from writing a compiler for what is normally an interpreted language nor writing an interpreter for what is normally a compiled language. And you can see examples of this all over the internet.

To make things even a bit more complicated in the naming of things, there are applications called compilers that translates one programming language into another.

A classic example is the first C++ compilers which would transform C++ source code into C source code and then compile the C source code into machine language. It's not done like that anymore and the C++ language was a subset of modern C++ (C++11/17) but it worked for a proof of concept.

I have also seen a translator that would transform C source code into JavaScript.


Is λx. a valid Lamda Calculus abstraction?

No, $\lambda x.$ is not a syntactically valid expression. By the definition of the syntax of lamda terms,

  $\lambda x.M$ is a term if $x$ is a variable and $M$ is a term.

You need a term $M$ to abstract over, and there are no empty terms. (This also means that there can be no application that reduces to "nothing". Any lambda term must consist of at least an atom (= a variable or a constant)). So $\lambda x.$ is not a term.


Upper bound for size of minimal covers of a set

The trivial bounds are that $|c| \le |X|=n$ and $|c| \le |S|=p$.

Knowing bounds on the sizes of the sets $s_i$ doesn't help much.  For instance, consider the family of sets $s_1,\dots,s_{n-k+1}$ given by $s_i=\{i,n-k+2,\dots,n-1,n\}$.  These sets are all of size $k$, and yet the largest inclusion-minimal cover has size $n-k+1$, i.e., exactly equal to the trivial bound of $|S|$ and fairly close to the trivial bound of $|X|$.  So, knowing only the sizes of the sets does not help to provide upper bounds that are much better than the trivial ones.


Random permutations by probability matrix

Your problem is not well-defined. As David Eisenstat notes in his comment, your matrix actually has to be bistochastic rather than just stochastic, since every convex combination of permutation matrices is bistochastic. Also, there could be many ways of representing a given bistochastic matrix as a convex combination of permutation matrices. As a simple example, the matrix $$\begin{bmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{bmatrix}$$ can be obtained by taking all permutations or just $123,231,312$.

The Birkhoff–von Neumann theorem states that every bistochastic matrix is a convex combination of permutation matrices. Its algorithmic proof gives a polynomial time algorithm that gives such a combination with at most $n^2$ matrices, which is probably optimal or close to optimal. In the literature you might be able to find faster algorithms; if you do, please let us know.


When to use Djikstra or Bellman-Kallaba algorithm?

Dijkstra's algorithm is faster (more efficient) than Bellman-Ford for graphs where it is applicable, i.e., for graphs where all edge weights are non-negative.  This is one such graph, as the cost of a bookshelf can never be negative.  Therefore, for this graph, Dijkstra's algorithm is better than Bellman-Ford.

(Incidentally, that answer is the accepted answer because you accepted that one.)


Simple algorithm for listing all 6-cycles in a directed graph

The easiest-to-program method will probably be a straightforward for-loop.  In particular, for each combination of six vertices $v_1,v_2,\dots,v_6 \in V$, check whether the following conditions all hold:

the $v_1,v_2,\dots,v_6$ are all distinct
$(v_1,v_2) \in E$ and $(v_2,v_3) \in E$ and ... and $(v_5,v_6) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, then you've found a cycle.  Output it.  Repeat for each possible combination of vertices.

The running time of this method is $\Theta(|V|^6)$.  It is easy to see that in the worst case there can be $\Theta(|V|^6)$ different cycles (consider a complete graph), so any algorithm will have to take at least this long on some graphs.

You can also get a very easy-to-program algorithm with running time $\Theta(|E|^3)$.  Enumerate all triples of edges $(v_1,v_2), (v_3,v_4), (v_5,v_6) \in E$, and then check the following conditions:

the $v_1,v_2,\dots,v_6$ are all distinct
$(v_2,v_3) \in E$ and $(v_4,v_5) \in E$ and $(v_6,v_1) \in E$.

If all the conditions hold, you've found a cycle; output it

This algorithm has $\Theta(|E|^3)$ running time.  Again, it's easy to see that there exist graphs where there are $\Theta(|E|^3)$ cycles and thus any algorithm will need to take at least $\Theta(|E|^3)$ time.

Both of those algorithms are easy to program.  That doesn't mean they are necessarily optimal in running time.  One could hope for an output-sensitive algorithm whose running time is a function of the number of 6-cycles as well as of $|V|,|E|$.  I suspect there are more complex algorithms that might have better asymptotic running time, for some graphs, when considering all three of those parameters.  However, they will be much more complex to program.  Therefore, by your stated goal of "easiest-to-program", I recommend one of the two algorithms listed above.


Not convincing claim for Master Theorem Case 3

Yes, this holds since $\log n = O(n^\epsilon)$ for any $\epsilon > 0$. You can prove this formally as follows. We will show that $\log n = o(n^{1/k})$ for all $k > 0$, or equivalently, that $\log^k n = o(n)$ for all $k \geq 0$. The proof is by induction. The base case $k = 0$, is clear. For the induction step, L'Hôpital's rule gives
$$
\lim_{n\to\infty} \frac{\log^k n}{n} = \lim_{n\to\infty} \frac{k\log^{k-1} n}{n} = 0.
$$


Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

This is the problem of finding a Steiner tree in the graph. It's one of the NP-complete problems in Karp's original paper; the reduction there is from Exact cover by 3-sets.


How do you prove the Natarajan's Lemma intuitively?

You can check Natarajan, On learning sets and functions or Haussler and Long, A generalization of Sauer's lemma.


Testing whether an arbitrary proof is circular?

The vast majority of proof systems don't allow for infinite, circular proofs, but they do so by making their langauges non-Turing complete.

In a normal functional language, the only way to make a program go on forever is with recursion, and in terms of theory, usually we look at recursion as the $Y$ combinator, a program of type $\forall a \ldotp (a \to a) \to a$: that is, it takes a function which makes calls to some other "self" argument, and turns it into a single recursive function.

Now, apply the Curry-Howard isomorphism to this: we now have a proof that, for any proposition $a$, if $a$ implies itself, then we can prove $a$. We can prove anything this way!

The key here is that the Y-combinator is built-in to a language, it's taken as an axiom. So if you want it not to cause you problems, just get rid of it as an axiom!

Most formal proof systems, because of this, require your recursion to be well founded. They only accept functions that they can prove will halt. And as a result, they reject some programs that do halt, but which they can't prove it for.

Coq does this in a fairly limited way: it just requires that any recursive functions have an argument where any recursive calls only use strictly smaller versions of that argument. Agda does something similar, but with a little more fancy checking to accept a few more programs.


Is the language of TMs that decide some language Turing-recognizable?

Of course, this depends on what you exactly mean.

Do you mean, all the machines that decides a specific language? e.g.,
$$ L = \{ \langle M \rangle \mid M \text{ decides the language } A\}$$

then, it depends on the language $A$. For instance, if $A=HP$, the halting problem, then $L$ is clearly decidable (i.e., it is empty).

But if you mean, any language, i.e., that $M$ is a decider,
 $$ L = \{ \langle M \rangle \mid M \text{ halts on all inputs } \}$$
then $L$ is not recognizable, see Yuval's answer.


first order logic to normal form order of operations

You always remove quantifiers in the order in which they appear in the prefix, from left to right, that is, you first eliminate $\exists y$ and then $\forall x$.
But the variables to apply the skolem function to are just the variables occurring free in the expression, no bound ones. Since $x$ is bound by $\forall x$, and $y$ is being skolemized away, the skolem function for $\exists y$ becomes a zero-place function symbol, or constant, S():
∃y∀x [¬A(x) v ¬B(y) v C(x,y)]
>>
∀x [¬A(x) v ¬B(S()) v C(x,S())]
In the next step, eliminate the the universal quantifier:
∀x [¬A(x) v ¬B(S()) v C(x,S())]
>>
¬A(x) v ¬B(S()) v C(x,S()).


This is not a full answer, but I think it is very useful.

Euclid's formula generates all primitive triples in a fairly linear fashion. Using all integers $m, n$ with $m > n$, $m, n$ coprime and $m-n$ is odd, all primitive triples can be generated as

$$a=m^2-n^2, b=2mn, c=m^2 + n^2$$

I don't have any knowledge on complexity, but hopefully this will help


How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers?

Question a):

Here is the output from python console.

>>> import math
>>> math.log(3,10) * (3**(3**3))
3638334640024.0996
>>> math.pow(10, 0.0996)
1.2577664324512539

The first 5 most significant digits are almost the same of that of Wolfram, 12577 vs 12580.

If we try the following at my favorite online arbitrary precision calculator,

pow(3.0000000000000000000000000000000, pow(3, pow(3, 3)))

we get

1.2580142906274913178603906982032e3638334640024

which is completely consistent with Wolfram. So Wolfram can be fully trusted on this particular result.

You might be wondering why "$3.000000$$000000$$000000$$000000$$0000000$" is entered instead of a simple "$3$". Had "$3$" been used, that calculator would have performed integer calculations without loss of precision, which will run out of 30-second time limit in our case. "$3.0$" would be enough to instruct that calculator to use floating numbers, which, however, would have only 2 digits of precision. That long string of 0s is used to specify 32 digits of precision of floating-point numbers.

Question b):

The computation above showed there are 3638334640025 digits if we express $3^{3^{3^3}}$ as a decimal integer. It we store 2 digits in one 8-bit byte, we need 1.82 terabyte storage.

However, if we ask that online calculator to compute $4^{4^{4^4}}$,

pow(4.0000000000000000000000000000000, pow(4, pow(4, 4)))

it say,

Complete loss of accurate digits

That is not a surprise since the exponent $4^{4^4}$ $=$ $1340780792994259$$7099574024998205$$8461274793658205$$9239337772356144$$3721764030073546$$9768018742981669$$0342769003185818$$6486050853753882$$8119465699464336$$49006084096$ $\approx$ $1.34×10^{154}.$
We can work around this out-of-limit error by computing directly the exponent of 10 in $4^{4^{4^4}}$ by using $\log$ with base 10.

log(4.0000000000000000000000000000000,10) * pow(4, pow(4, 4))

The answer is

8.0723047260282253793826303970853e153

That number of digits, about $8\times10^{153}$ is much more than vigintillion in long scale. To store $4^{4^{4^4}}$ as a decimal integer, it is not enough even if all atoms in the known universe are used, assuming each of them can store more digits than all available computer storage on earth.

However, not a lot of memory is needed for the calculations above to obtain the result above. It is possible that a few megabyte or just several kilobytes of extra memory could support the calculations above.


What's the difference between a stream and a queue?

A queue is an abstract data type with two operations: enqueue() and dequeue() (or sometimes push() and pop()) that have first-in-first-out semantics.

A C stream is hard (for me) to describe abstractly.  My best cut at it is that it is an abstraction representing a buffered file (where "file" is understood in the Unix sense of the word as something that is usually (but not always) a sequence of bytes and a current file position.)

At it's most general a stream is like a sequence of bytes numbered from 0, that can be arbitrarily extended at the end, but that has some additional state (the current position).  There are some basic operations (fread() and fwrite()) that read or write an arbitrary number of bytes starting at the current position, and then reset the current position to point just after the most recently read or written byte.  The current position can also be changed with fseek() and queried with ftell().

Now here's where it gets "icky."  At the time a stream is opened a variety of factors determine which of the above operations are enabled or disabled.  If you open your stream only for read then calling fwrite() will cause an error.  If you open your stream only for write then calling fread() will cause an error.  If your stream is actually a pipe or a socket, or is opened in mode append then you are not allowed to fseek().   You are only allowed to read or write from the current file position.  stdin, stdout, and stderr are pipes so you can't fseek() them.  You can't fwrite() stdin and you can't fread() stdout or stderr.

C++ fixed most of that mess by giving us a hierarchy of types (for example: http://www.cplusplus.com/reference/istream/basic_iostream/), so that we can do error recovery with RAII and can also tell whether the file is readable or writable by looking at the type (although I don't know offhand whether they fixed the seeking mess.)

But then there's the whole other question of formatted output.  C has fprintf() which formats some stuff and puts some bytes into a writable stream (starting at the current file position).  C++ replaced fprintf() with the (IMHO) really-much-too-cute operator<<().  operator<<() has the advantage of being strongly typed, but the extreme disadvantage of requiring the use of manipulators.  So operator<<() puts some bytes to the output stream starting at the current file position, but formatted based on a whole bunch of state that is mutated by manipulators.  So a C++ stream actually has a bunch of extra state that you need to know about.  (Whether integers are going to get formatted hex or decimal from now on, how much precision floats are printed with, etc.)

So: a queue inserts and removes individual items of a well defined type from its front or its back.  A stream is random access extendable array of bytes where you can read and write arbitrary numbers of bytes from the current file position (except when it isn't random access and except when you either can't read or can't write).


Why doesn't relu cause back propegation to get stuck

Normally, any ReLU unit will return 0 for some samples and not for other samples (in particular, it'll probably return 0 for about half of the samples).  Because of how SGD works, it won't get stuck: the former samples will yield a contribution to the gradient of 0, but the latter samples will have a non-zero gradient, so the weights and bias will be updated for the latter samples.  So it's not a problem; the weights and bias still get updated for many of the samples.
That said, there can be cases where this problem can occur.  If the ReLU unit outputs 0 for all (or most) samples, then SGD won't update the weights, and learning for that neuron will get stuck.  This is sometimes called the "dying ReLU" problem.  See, e.g., https://datascience.stackexchange.com/q/5706/8560 and https://en.wikipedia.org/wiki/Rectifier_(neural_networks)#Potential_problems.   Typically we're able to avoid this problem by appropriate initialization of the weights and by suitable choice of learning rate for SGD, so it's usually not a big deal in practice if you choose those appropriately, but it can happen.


Why does the state remain unchanged in the small-step operational semantics of a while loop?

The state can change in subsequent reduction steps because on the right hand side of

$$
   \langle while\ B\ do\ S, \sigma \rangle
\quad\rightarrow\quad
 \langle if\ B\ then\ ( {\color{red}{S}};\  while\ B\ do\ S )\ else\ skip, \sigma\rangle
$$

the $while$-loop is guarded (preceeded) by $S$. The computation of $S$ may change the state so that the condition $B$ can evaluate to $\mathsf{false}$.


Semantic natural language processing - from texts to logical expressions? Universal knowledge base?

There are several implementations of semantic parsers that convert natural-language texts into formal logical representations of their meanings. Natural language understanding systems can also be based on discourse representation theories that represent the meanings of English texts using first-order logical predicates.

I have found at least one system that is able to generate a knowlege base from statements that are given in a natural language. The ACE Wiki is based on Attempto Controlled English, which is a semantically unambiguous subset of the English language.


On efficiency analysis of randomized divide-and-conquer median find

There's no need to do any calculation. There is absolutely nothing special about the numbers 25 and 75.
If $0 < \alpha < \beta < 1$ and you are promised that the median is between the $\alpha$'th percentile and the $\beta$'th percentile, then the running time of the algorithm will be linear. Indeed, if $\gamma = \min(\alpha,1-\beta)$, the length reduces by a factor of at least $1-\gamma$ in each recursive call, so the total running time will be proportional to at most
$$ n \sum_{i=0}^\infty (1-\gamma)^i. $$
Even without computing the sum, we can tell that in converges, so we get a bound of $O(n)$. If we compute the sum, we get the dependence on $\gamma$:
$$ \frac{n}{\gamma}. $$
This sort of behavior always occurs when we reduce a problem to a subproblem which is smaller by a constant factor bounded away from 1. Once you know that, you don't need to do any calculations.


It is definitely not a classic graph problem such as the shortest path, maximum-flow, or graph coloring problem. But your problem, in its general form, seems to solve the Independent set problem, which is $NP$-complete.

Assume that you have a polynomial time algorithm $A(G,m,p)$ solving this problem. Then take $m=1$ and call $A(G,1,p)$ for $p=N,N-1,...,2,1$ (at most $N$ times) until you find a solution. When $m=1$, each subgraph has only one node and so its weight is 0, which is maximum for a single node graph. Furthermore, these nodes are not connected by an edge, and so they are not adjacent, i.e. they are independent.

If this procedure finds a solution for the maximum $p$ less than $N$, then this means we have a maximal independent set, since
we have exactly $n$ nodes (subgraphs) with no edges between them, i.e. independent.

Once your problem is $NP$-complete, you could try any approximation algorithm including Linear or Integer programming.


Hint: A string with exactly one $a$ would look like this:
$$
(any\ number\ of b's)\,a\,(any\ number\ of b's)
$$
and a grammar to generate the language of these strings is $S\rightarrow AaA,\ \  A\rightarrow aA\mid \epsilon$.

Generalize.


OK, it sounds like your problem is the following:

  You have an undirected graph.  Each vertex is either a consumer or a producer.  Say that a consumer $c$ is connected to a producer $p$ if there is a path from $c$ to $p$ where all intermediate nodes are consumer nodes.  You want to output a list of pairs $(c,p)$ where $c$ is connected to $p$.

This problem can be solved in a straightforward, clean, and efficient manner, using an algorithm for connected components.  Here is the algorithm:

Remove all of the producer nodes, keeping only the consumer nodes and the edges from a consumer node to a consumer node.
Compute connected components on this smaller graph.  Let the connected components be $C_1,\dots,C_k$.
Now, back in the original graph, shrink all of the consumer nodes in the same connected component into a single node.  Thus, we get an edge from connected component $C_i$ to producer $p$ if there is any consumer $c$ in $C_i$ that has an edge to $p$.
This resulting graph now describes the connectivity relationship.  In particular, for each consumer $c$ and each producer $p$, $c$ is connected to $p$ if and only $C_i$ has an edge to $p$, where $C_i$ is the connected component containing $c$.

For instance, to output the list of all pairs $(c,p)$ that are connected, you can do the following:

For each connected component $C_i$, for each provider $p$ that has an edge from $C_i$ to $p$, for each consumer $c$ in $C_i$, output the pair $(c,p)$.

This algorithm runs in linear time.  The running time to compute the connectivity graph (produced in steps 1-3) is $O(m+n)$, where $n$ is the number of nodes and $m$ is the number of edges (interconnections) in the original graph.  The running time in step 4 could be as large as $\Theta(n^2)$, since there might be as many as $\Theta(n^2)$ such pairs.  However, here's what we can say.  If the correct output has length $\ell$ (i.e., there are $\ell$ pairs $(p,c)$ that are connected), then step 4 will have running time $O(\ell)$.

Therefore, the total running time is $O(m+n+\ell)$, i.e., linear in the sum of the size of the input and the size of the output.  This is as fast as you could possibly hope for.

If you don't need to output the set of all pairs $(c,p)$ explicitly, but you just want a compact representation of this connectivity information, you can use the graph computed in steps 1-3 as that compact representation.  Then the running time is $O(m+n)$.


Are there two kinds of polynomial hierarchy collapses?

Suppose that $\Sigma_i^p = \Sigma_{i+1}^p$ (and so $\Pi_i^p = \Pi_{i+1}^p$). Then every statement of the form $(\exists y_1) \cdots (Q y_{i+1}) f(x,\vec{y})$ for polytime $f$ is equivalent to another statement $(\exists y_1) \cdots (Q y_i) g(x,\vec{y})$ for polytime $g$.

Now suppose you have a predicate in $\Sigma_{i+2}^p$, say $(\exists y) (\forall z_1) \cdots (Q z_{i+1}) f(x,y,\vec{z})$. The inner $i+1$ quantifiers are a $\Pi_{i+1}^p$ predicate, and so they are equivalent to a $\Pi_i^p$ predicate $(\forall z_1) \cdots (Q z_i) g(x,y,\vec{z})$. Adding back the outer quantifier $(\exists y)$, we find that the original predicate is equivalent to a $\Sigma_{i+1}^p$ predicate, and so $\Sigma_{i+2}^p = \Sigma_{i+1}^p = \Sigma_i^p$.

In the same way, we show that $\Sigma_i^p = \Sigma_{i+1}^p$ implies $\Sigma_i^p = \Sigma_{i+j}^p$ for all $j$, so that $\mathsf{PH} = \Sigma_i^p$.

Note that $\Pi_i^p \subseteq \Sigma_{i+1}^p$. Indeed, if $(\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Pi_i^p$ predicate, then the equivalent $(\exists w) (\forall y_1) \cdots (Q y_i) f(x,\vec{y})$ is a $\Sigma_{i+1}^p$ predicate.

Since $\Pi_i^p \subseteq \Sigma_{i+1}^p$, we see that $\Sigma_i^p = \Sigma_{i+1}^p$ implies that $\Pi_i^p \subseteq \Sigma_i^p$ and so $\Pi_i^p = \Sigma_i^p$.

Now for the other direction. Suppose that $\Pi_i^p = \Sigma_i^p$, and consider some $\Sigma_{i+1}^p$ predicate $(\exists y_1) (\forall y_2) \cdots (Q y_{i+1}) f(x,\vec{y})$. The inner $i$ quantifiers are a $\Pi_i^p$ predicate, and so they are equivalent to some $\Sigma_i^p$ predicate $(\exists z_2) \cdots (Q z_{i+1}) g(x,\vec{y})$. Adding back the outer quantifier $(\exists y_1)$ and folding $y_1,z_2$, we obtain a $\Sigma_i^p$ predicate equivalent to our original $\Sigma_{i+1}^p$ predicate.

Summarizing, if $\Pi_i^p = \Sigma_i^p$ then $\Sigma_i^p = \Sigma_{i+1}^p$, and so (as we have seen above) $\mathsf{PH} = \Sigma_i^p$.


Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$

By the basic equivalence of PCPs and MaxCSP problems, there exists a conjunction $C$ of polynomially many boolean literals, s.t.

  $\exists \text{ proof } \pi$ which makes the verifier $V$ accept with probability $\geq p$ $\Leftrightarrow$ $\exists$ an assignment that satisfies at least a $p$ fraction of the literals in $C$.

So you just need to show that the following problem is polytime solvable: given a conjunction $C$ of boolean literals, what is the largest number of literals that can be simultaneously satisfied. That's a very easy problem.

The idea here is that a PCP with query complexity $q$ corresponds to some MaxCSP problem with arity $q$. If the PCP has completeness $c$ and soundness $s$, then the language accepted by the PCP is reducible to a promise version of an arrity $q$ MaxCSP problem where in a 'no' instance at most an $s$ fraction of the constraints can be satisfied, and in a 'yes' instance at least a $c$ fraction of the constraints can be satisfied. These reductions are standard, look up any reference on PCPs.


Operating system maintains copy of page table for each process

why does it keep copy of instruction counter and register contents?

It's because of process scheduling.

Let's say a process comes in execution first time and executes some lines of instruction. The registers contain values as per the instructions executed till now. Now if the process switches from running state to waiting state (due to I/O or preemption) and then comes back to the running state, it must have the same register values for further execution. So OS stores a copy of each register in the program control block(PCB).

  I don't understand why OS would copy the page table, isn't it the one
  creating and maintaining it?

Again, if the process goes out of execution, OS must save the information regarding frames of memory allocated to the process.


Determine endpoint of a graph given as a list of nodes + direct successors and predecessors

It appears this is an instance of "incremental graph connectivity".  There are very efficient algorithms for this.

First, let's identify the weakly connected graph components and keep track of them as the graph changes.  In undirected graphs, it's easy to keep track of connected components as you add vertices and/or edges, using a union-find data structure.  In particular, each time you add a vertex, you use the MakeSet function to put it in a component of its own, and each time you add an edge, you use the Union function to merge the two associated components.  You can use this to keep track of the weakly connected components in your directed graph.

This can be done $O(\alpha(n))$ time per operation (i.e., per vertex or edge added).

Your "ends" are normally called "sink vertices".  You can keep track of the "ends" of each weakly connected component by associating a doubly linked list with each component; that list contains all of the sink vertices in that component.  Also, each sink vertex should have a pointer to the placed in the doubly-linked list where it appears.  When you merge two components, you can concatenate their lists in $O(1)$ time.  Also, when you add an edge, you check if this turns a sink vertex into a non-sink; if so, you follow the pointer from that vertex to find its place in the doubly-linked list, and remove it from the doubly linked list.  This too can be done in $O(1)$ time.  In all, this takes an additional $O(1)$ time per vertex or edge added, which is dominated by the cost of the union-find data structure.


Independent sets into which all the vertices of the graph can be split

This is Mirsky's theorem, a sort of dual of Dilworth's theorem. Dilworth's theorem is a standard result in the combinatorics of posets.


No.  As you have defined it, $t$ is only in the language if it is every prefix, except $\varepsilon$, of $s$.  That definition describes $\emptyset$ if $|s|$ is not 1, or $\{s\}$ if $s$ is a single symbol.  If you change ∀n∈{1,…, length(s)},  to $\text{s.t.}$ $1 \leq n \leq |s|$, then it would be almost equivalent.  However the first language includes the empty string.

Also "first n part of" is not a very good way to describe a prefix of length n.  It could be ambiguous.  And you should define what $t$ is, i.e. $t \in \Sigma^*$.


Why Deterministic PDA accepts $\epsilon$ input but DFA not

There are definitely definitions of DFA that allow $\varepsilon$-transitions. Arguably, they are not very useful for three reasons.

They don't add computational power.
If you have them, you have to require (for DFA) that every $\varepsilon$-transition is the only transition leaving its source state.
Everything you might want to do with them (say, prove closure of regular languages against concatenation) can be done by using NFA and determinising.

Because they do have use in proofs, they are usually included in the definition of NFA, though. For example, consider translating regular expressions into NFA.

In PDAs, $\varepsilon$-transitions can be used to deal with stack content without consuming any input. Even in DPDA there can be multiple choices in any given state, depending on stack content. So they are useful here for constructing PDA and are thus usually included in the definition.


Analysis of Algorithms: Applying Concepts

Typically, when presented with a piece of code, your first step is to come up with a formula which gives the running time $T$ of your code as a function of the input size. In your example, the function takes an array, so a natural way to represent the input size is the number of elements in the array, values.length, which we can call $n$.

So, we now want an expression for $T(n)$. To get this, we should assign a "cost" to each statement, and then determine how many times each statement is executed. The costs are somewhat arbitrary and may vary across real computer hardware, but some assumptions can reasonably be made; in particular, we usually assume simple statements have a constant cost with respect to the input size. In your example, we might assign costs like this:

int summation(int[] values)
{
  int sum = 0;                       // cost = A, executed once
  for(int i = 0;                     // cost = B, executed once
      i < values.length);            // cost = C, executed n + 1 times
      i++)                           // cost = D, executed n times
  {
    sum += values[i];                // cost = E, executed n times
  }
}

Now, to get the expression for $T(n)$, multiply each statement's cost by the number of times it's executed. Here, we get $T(n) = A \times 1 + B \times 1 + C \times (n + 1) + D \times n + E \times n$. This comes out to $T(n) = (A + B + C) + (C + D + E) \times n = c_0 + c_1n$ for constants $c_0, c_1$.

In this example, happily, we have a closed-form expression for $T(n)$. As such, we can make an educated guess that this function is $\Theta(n)$, since $T(n)$ is a linear function. To prove this is true, we can try to prove it's both $\Omega(n)$ and $O(n)$.

By definition, $T(n) = \Omega(n) \iff \exists c > 0, n_0 \ge 0 \mid n \ge n_0 \rightarrow T(n) \ge cn$. Our job now is to demonstrate that there is an $n_0$ and $c$ such that $T(n) \ge cn$ for all $n \ge n_0$. We have $c_0 + c_1n \ge cn$ for fixed constants $c_0, c_1$. We can solve this for $c$: $c \le c_0/n + c_1$. As long as we choose $c$ less than $c_0/n + c_1$, we have a valid choice for $c$; in particular, if we choose $c = c_1$, we satisfy the inequality for all natural numbers, and can choose $n_0 = 0$.

You can make a very similar argument for $O$; try choosing $c = c_0 + c_1$ in this case and complete the argument yourself. Once you know it's both $\Omega(n)$ and $O(n)$, you can conclude that it's $\Theta(n)$.

Of course, you don't really need to find the constants every time, but it can make an argument pretty convincing. If your $T(n)$ comes out to a expression which is the sum of powers of $n$, then you will always have that $T(n) = \Theta(n^x)$, where $x$ is the highest power to which $n$ is raised.

This gets significantly harder when $T(n)$ is recursive, i.e., when the expression for $T(n)$ involves $T$ itself; to solve problems like that, you'll often need to avail yourself of the Master Theorem or inductive proofs on the input size. Cross that bridge when you come to it, though.


Is TSP a more detailed form of the "Set Inclusion" question?

As far as I can see, your model is that the edges of the graph are represented by cards and the edges on the optimal TSP tour are cards with blue backs. You're asking if TSP corresponds to the problem of identifying the cards with the blue backs.  If that is the case, the answer is "yes".

However, there is a huge caveat. In the set inclusion problem, we can tell in constant time if the back of a card is blue: you just turn over that one card and look at it. You assume that we can do the same in TSP: in constant time, we can tell whether any single edge is in the optimal tour. This is a completely unrealistic assumption because it's impossible to tell if an edge is on the optimal tour without examining at least one edge from every vertex.

I think that what you've observed is basically that, if somebody has somehow solved a TSP instance, you can find the solution by asking them whether each individual edge is in the optimal tour. This is obviously true, but it's not very interesting.


If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language?

First, note that CFL is not closed under intersection, contrary to what you've mentioned.
For example:
$$ L_1 = \{a^ib^ic^j|i,j \geq 0\}, \quad L_2 = \{a^ib^jc^j|i,j\geq 0\}. $$
We see that $L_1 \cap L_2 = \{a^ib^ic^i|i\geq0\}$,
which is not CFL.

For your question,
Take two languages $L_1, L_2$ which are not CFL.
Let
$$
\begin{align*}
L'_1 &= \{0x|x \in L_1 \} \cup \{1x|x \in \Sigma^*\}, \\
L'_2 &= \{1x|x \in L_2 \} \cup \{0x|x \in \Sigma^*\}, \\
\end{align*}
$$
which are both not CFL. It's easy to see that $L'_1 \cup L'_2 = \Sigma^*$, which is CFL (as it is a regular language).


I'll present an algorithm by example. Initialize a list of lists containing a list containing all of the players.

[[1, 2, 3, 4, 5, 6]]

For the first team, TEAM_A, replace each list by two lists, where the first list contains TEAM_A and the players on TEAM_A and the second list contains the players not on TEAM_A. Duplicate all of the existing team entries in both lists (none here).

[[TEAM_A, 1, 2, 4, 5], [3, 6]]

Discard all lists with no players (none here). For the second team, TEAM_B, replace each list by two lists, where the first list contains TEAM_B and the players on TEAM_B and the second list contains the players not on TEAM_B. Duplicate all of the existing team entries in both lists.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6], []]

Discard all lists with no players.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6]]

Well implemented, this should run in time proportional to the product of the number of teams and the number of players.


Finding the minimum vertex cover of planar graph given the planar representation

Given a planar graph, one can always compute a combinatorial embedding for it.


Strassen algorithm for matrix multiplication complexity analysis

It's true that the parameter $n$ usually denotes the size of the input, but this is not always the case. For square matrix multiplication, $n$ denotes the number of rows (or columns). For graphs, $n$ often denotes the number of vertices, and $m$ the number of edges. For algorithms on Boolean functions, $n$ denotes the number of inputs, though the truth table itself has size $2^n$. There are many other examples.