It is a direct consequence of the time hierarchy theorem:

Time Hierarchy Theorem: if f and g are time-constructible functions and $f(n) \log f(n) =
o(g(n))$ (e.g. $f(n) = n^2, g(n) = n^3$), then $DTIME(f(n)) \subsetneq DTIME(g(n))$


Probability that all indices divisible by 100 in a hash table with linear probing are occupied

This problem may be reduced to the following simple probability problem with concrete numbers.

Assume you have an urn with 8 black and 12 white balls, total 20 balls. You randomly draw 15 balls from the urn one by one without replacement. What is the probability that all black balls are selected?

How does it relate to the original problem? Occupying slots one by one is equivalent to drawing balls without replacement. Both number of slots and balls decrease. "Drawing a ball" corresponds to "eventually occupying a slot" after linear probing (searching).

We have address space of $10^6$ slots equivalent to having $10^6$ balls in an urn. Then you have positions with indices divisible by 100 equivalent to having $10000$ $(=10^6/100)$ black balls. $500000$ positions are occupied means that you draw $500000$ balls. Finally, the requirement "all positions with indices divisible by 100 $(=10^6/100)$ are occupied" means "all $10000$ black balls must be selected".

Thus it is the hypergeometric distribution that describes the probability of $k$ successes in $n$ draws, without replacement, from a finite population of size $N$ that contains exactly $K$ successes, wherein each draw is either a success or a failure (black or white).
The probability is equal to

$$ P(k \text{ successes})= \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$$

So, if we take urn-balls model then we have
$$ P(8 \text{ black balls})= \frac{\binom{8}{8}\binom{20-8}{15-8}}{\binom{20}{15}}$$

As for the original problem then we have
$$ P(10000 \text{ occupied slots})= \frac{\binom{10000}{10000}\binom{10^6-10000}{500000-10000}}{\binom{10^6}{500000}}$$

Now, our numbers in the original problem is too large to compute the binomial coefficients. You could get around the problem using Stirling's approximation.


Are consensus (and atomic broadcast) protocols limited by single node's resources?

Your argument for "no" is flawed, for two reasons:

When we say that X reduces to Y, we mean that a solution to Y is one way to solve X.  But there might be other ways to solve X that don't rely on solving Y.
Some protocols for consensus elect a leader, but that doesn't necessarily imply that all approaches to solve consensus require electing a leader.  (For example: consider Bitcoin.  No leader, but it arguably solves a consensus kind of problem.)


Running time for Breadth-First-Search vs Depth-First-Search

The running time of both BFS and DFS are $\Theta(V+E)$ since both of them are guaranteed to visit every vertex and every edge at least once. Note that we are talking about the situation when the input graph is a connected graph whose edges are given by adjacency-list, the most common situation (in the course of your study).

It is not surprising that the CLRS book presents the running time of BFS as $O(V+E)$ even though $\Theta(V+E)$ is the optimal asymptotic bound for its running time. It is actually a general practice that the running time of an algorithm is described in term of big $O$ even though it might be possible to describe in term of big $\Theta$. The reason is that how tight we can bound the  running time of an algorithm from above is the major concern for many situations.


I would start by finding a CFG that generates the balanced version $\{a^ib^jc^k\mid i=j+k\}$ from nonterminal $C$.

   $C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$

Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+\mid b^*c^+)$ on the right. To deal with the former possibility, you simply add the following rules.

$
S\rightarrow aL\\
L\rightarrow aL\mid C
$

You can deal with the other two possibilities in similar manner.

   $ S\rightarrow R_bb\mid R_cc\\R_c\rightarrow R_cc\mid R_b\mid C\\R_b\rightarrow R_bb\mid B$


Oracle that can only definitively say if an instance is unsatisfiable

Edit: I wrongly read the question, therefore the following answer is incorrect. It would be correct if the oracle worked as followed: "if the instance is unsatisfiable, then the oracle always says it is unsatisfiable otherwise, there is a 57% chance the answer is that the instance is satisfiable, and a 43% chance that it is not".
The key here is to repeat the process of asking your oracle to improve the probability of getting the right answer. You know that the way it is constructed, if the oracle states that a formula is satisfiable, then IT IS satisfiable (since it never makes mistakes on non-satisfiable formulas).
For example, with your percentages, if you ask 6 times your oracle if a formula $\varphi$ is satisfiable, it will always give the right answer if $\varphi$ is not satisfiable, and there will be over 99% chance to say that $\varphi$ is satisfiable if $\varphi$ is satisfiable, because it has $0.43^6 < 1\%$ chances to say that $\varphi$ is not satisfiable even if it is.
You will never be able to guarantee 100% in both cases, but you can be as close as you want by repeating the question to the oracle.


Detecting coplanarity by given pairwise distances

I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

Random Greedy

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the expected running time is, but I would wild-guess it at $O(n \, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

Prioritized Greedy

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.


You can implement this in O(klogk + n) time complexity.

Maintain an external min-heap while iterating the queue. The min-heap shall have at most k elements at a time.

Insert the first k elements in the min-heap. Thereafter compare the present queue element with the top of the heap. If the top is less than present value then delete the top element from the heap and insert this new present element.

At the end the heap shall contain top k elements in the queue.


You could continue with
\begin{align*}
    \log n + \log (n^{n-1}+1)
        &\leq \log n + \log(2n^{n-1})\\
        &= \log n + (n-1)\log 2n\\
        &= \log n + (n-1)\log 2 + (n-1)\log n\\
        &= O(n\log n)\,.
\end{align*}
(Leaving out whatever steps you feel are obvious.)


What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?

You've misunderstood the algorithm and it doesn't have the behaviour you suggest.

Let the pivot value be $p$. The algorithm searches from the left for a value $\ell\geq p$ and from the right for a value $r\leq p$. It then only swaps them if they're in the wrong order relative to each other, i.e., if $\ell>r$, so it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.


I don't have a dynamic programming solution but this problem can be efficiently reduced to a minimum weight max-flow problem.
Let $G$ denote your original graph. We will create an instance $(s,t,G')$ of the minimum weight max-flow problem as follows:

Let $W$ denote the sum of all weights in $G$ plus one.
For every vertex $u$ in $G$, we create two vertices $u_{in}$ and $u_{out}$ in $G'$ and add a directed edge from $u_{in}$ to $u_{out}$ with weight $-W$ and capacity $1$.
For every directed edge $e=(u,v)$ in $G$, we add a directed edge from $u_{out}$ to $v_{in}$ in $G'$ with weight $w(e)$ and capacity $1$.
We create a vertex $s'$ and we connect the source $s$ to $s'$ with a directed edge of weight $0$ and capacity $2$.
We connect $s'$ to every "in" vertex with a directed edge of weight $0$ and capacity $1$. We  connect every "out" vertex to the sink $t$ with a directed edge of weight $0$ and capacity $1$.

Let $n$ denote the number of vertices in $G$. Then the vertices in $G$ can be partitioned into two vertex-disjoint paths of total weight $k$ (which is what you want) if and only if there is a max-flow in $(s,t,G')$ with total weight $k-nW$. Moreover, this flow is the union of two paths in $G'$ (which are disjoint except at $s$, $s'$ and $t$) , from which you can easily retrieve the two vertex-disjoint paths in $G$.
Note that by changing the capacity of the $(s,s')$ edge from $2$ to whatever integer we like, we can generalize this approach to partitioning into arbitrary number of vertex disjoint paths with minimum total weight.


The space used by a Turing machine is the total number of cells that the head (or heads, if a multitape machine) of the Turing machine has ever visited. A function $f(n)$ is space-constructible if there is a Turing machine that on input $1^n$ outputs the binary representation of $f(n)$, and while doing so only visits $O(f(n))$ cells. Note that $O(f(n))$ is an upper bound on the visited cells, not on the length of the representation.

Whether constant functions are space-constructible or not according to this definition depends on the Turing machine model. If the input and output are on the same tape, then a Turing machine space-constructing $c$ should first erase the input $1^n$ and then write the binary representation of $c$. Unfortunately, this takes $n$ space rather than $O(c) = O(1)$ space. If, in contrast, the input is on a special read-only tape and the output is on a special write-only tape (as is the case for log-space machines), then there is absolutely no problem to (fully) space-construct $c$.


Why and how is a quantum computer faster than a regular computer?

A quantum computer by itself isn't faster. Instead, it has a different model of computation. In this model, there are algorithms for certain (not all!) problems, which are asymptotically faster than the fastest possible (or fastest known, for some problems) classical algorithms.

I recommend reading The Limits of Quantum by Scott Aaronson: it's a short popular article explaining just what we can expect from quantum computers.


What if block sizes are not equal among caches?

To begin with, block sizes are usually equal across all levels of the cache hierarchy. I would like to see if someone has an example of a commercial architecture where is is not true. There are multiple reasons for this, all of which involve circuit complexity

Now, to answer your question, one could do either. When the processor requests a SP float (4 bytes), only 4 of the 16 (in your example) bytes from the block of the L1 are sent towards the pipeline. The same logic that selects this subset of bytes can be used to select the subset of 16 bytes (in your example) from the incoming block of 32 bytes.

Alternatively, you could over-write the neighboring block in L1 with data from the block of 32 bytes because spatial locality would imply you are likely to require this data soon.


Can you explain this exercise solution to me?

According to this article: F. J. Corbató, M. M. Daggett, R. C. Daley, An Experimental Time-Sharing System (IFIPS 1962), CTSS uses a "multi-level scheduling algorithm":

  The basis of the multi-level scheduling algorithm is to assign each user program as it enters the system to be run (or completes a response to a user) to an $\text{ell}$-th level priority queue. The process starts with the time-sharing supervisor operating the program at the head of the lowest level occupied queue, $\text{ell}$, for up to $2^\text{ell}$ quanta of time and then if the program is not completed (i.e. has not made a response to the user) placing it at the end of the $\text{ell}+1$ level queue. Programs are initially entered into a level $\text{ell} = 0$.

A program at the ell-th level is assigned $2^{\text{ell}}$ quanta.

Now you know how to solve your exercise.


Independent set poly reducible to Strongly independent set?

Assume that the integer $k$ of the (decision version of the) independent set instance $G$ you are reducing from is larger than $1$ (the case $k \le 1$ is trivial).
Let $G'$ be the graph of the corresponding instance of strongly independent set.

As it is written in your solution notes, all the additional vertices are connected to one another with a clique. If you select any of them, say $w_e$, then you cannot select any other vertex $v$ in $G'$ since the distance in $G'$ between $v$ and $w_e$ is at most $2$. This implies that the size of a maximum strongly independent set of $G'$ is $1$. Therefore, if there is a strongly independent set of $G'$ of size $k$, it must not include any vertex $w_e$.

The correctness of the reduction is then easy to see:

If $S$ is an independent set for $G$, then $S$ is also a strongly independent set for $G'$ since all pairs vertices in $S$ are at a distance of at least $2$ in $G$ and hence they are at distance of at least $4$ in $G'$.
If $S$ is a strongly independent set for $G'$ with $|S| \ge k$, then $S$ cannot include any vertex $w_e$, and is therefore a subset of the vertices of $G$. The distance between any two distinct vertices in $S$ is larger than $2$ in $G'$, and hence it is larger than $1$ in $G$.


Language of all words accepted by a TM by at most $t$ steps is regular

The language $L$ only depends on the first $t$ letters of the input (since the Turing machine never gets to any of the other letters). This implies that it is regular, since
$$
L = (L \cap \Sigma^{<t}) \cup (L \cap \Sigma^t) \Sigma^*,
$$
where $\Sigma^{<t} = \bigcup_{i=0}^{t-1} \Sigma^i$. The right-hand side is regular since $L \cap \Sigma^{<t}$ and $L \cap \Sigma^t$ are both finite, and so, regular.


Does Gale-Shapley work when the number of men and women are not equal?

First thing is algorithm will definitely terminate in the case even when number of men are not equal to women. Now at the end of Gale-Shapley algorithm for the case when number of men$(m)$ and women$(w)$ are equal.

  Each man can have the best partner that he can have in any stable matching.

If you only care about men then there are two cases:

If $m > w$ then algorithm will terminate but at the end there are going to be some men left out without matching
If $m < w$ then algorithm will terminate then at the end, each man can have the best partner that he can have in any stable matching.


Differences and relations between high-performance/throughput computing and parallel computing?

As noted by @JukkaSuomela, you can do parallel computing on low-end resources such as your laptop and even on your mobile phone (if they are equipped with a multicore processor). However, HPC (High Performance Computing) is, roughly stated, parallel computing on high-end resources, such as small to medium sized clusters (ten to hundreds of nodes) up to supercomputers (thousands of nodes) costing millions of dollars. Therefore, the difference is mainly in the hardware used.

Finally, HTC (High Throughput Computing) refers to executing the maximum number of tasks (or jobs if you prefer) per time unit. A classical example of HTC computation is the so called parameter sweep, in which you must run the same executable, but varying in each execution a set of parameters (thus the sweep spans the whole parameter space).


Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs

The problem is that a Hamiltonian cycle has to pass through all vertices: if the cycle in the original graph does not take some edge $e$, then the vertex you split $e$ with will not be taken if you take the same route. This means that the resulting cycle is not Hamiltonian.


How does one prove that Big Step semantics and Small Step semantics are equivalent for IMP?

Don't proceed by induction on $P$, i.e. by structural induction on the syntax of programs. This is because structural induction is quite weak, and is likely to fail on while loops.

Look at the inference rules for the big step semantics for while, in particular at the while-true rule which handles the case where the guard is true. In such case, you'll see that in one of the premises we have the same while loop. Roughly, the rule defines the behaviour of while in terms of itself.

(I didn't check your own rule, and used mine instead, but it should be simple to adapt the reasoning to yours.)

$$
\dfrac{
\sigma\models \phi \quad
\langle c, \sigma \rangle \to_b \sigma'
\quad
\langle while\ \phi\ do\ c, \sigma' \rangle \to_b \sigma''
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma''}
$$

If we proceed by structural induction, when we handle such case, we only get an induction hypothesis for $c$, wince it is a subterm of $while\ \phi\ do\ c$. That however provides no help in coping with he last premise involving the $while$ itself.

The solution is to use the induction principle generated by the rules for $\to_b$, instead. Doing that, when handling the rule above, we have two induction hypotheses, namely that the small step semantics

reduces $\langle c, \sigma \rangle$ to some $\sigma'$ state in some $N$ steps
reduces $\langle while\ \phi\ do\ c, \sigma' \rangle$ to some $\sigma''$ state in some $M$ steps

Exploiting those properties, it is possible to show that, using (something like) $N+M+1$ steps, we can reduce $\langle while\ \phi\ do\ c, \sigma \rangle$ to $\sigma''$ using small steps.

The other rules can be handled in a similar way.

When you write such proofs, I strongly suggest to always check the while-true case first, since that's the "hardest". Checking it first helps avoiding wasting effort on other simpler (but long) cases, only to discover that the proof can not be completed and all the work done has to be thrown away.

Assume we have these as the inference rules for the big step semantics. (If rules omitted)
$$
\begin{array}{c}
\dfrac{
}{\langle skip, \sigma \rangle \to_b \sigma}
\qquad
\dfrac{
\langle e, \sigma \rangle \to_e v
}{\langle x:=e, \sigma \rangle \to_b \sigma[x\mapsto v]}
\\
\dfrac{
\langle c_1, \sigma \rangle \to_b \sigma'
\qquad
\langle c_2, \sigma' \rangle \to_b \sigma''
}{\langle c_1;c_2, \sigma \rangle \to_b \sigma''}
\\
\dfrac{
\sigma\models \lnot\phi \quad
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma}
\qquad
\dfrac{
\sigma\models \phi \quad
\langle c, \sigma \rangle \to_b \sigma'
\quad
\langle while\ \phi\ do\ c, \sigma' \rangle \to_b \sigma''
}{\langle while\ \phi\ do\ c, \sigma \rangle \to_b \sigma''}
\end{array}
$$

We immediately get the following induction principle.

Let $p(c,\sigma,\sigma')$ be any property of a command and two states.
To prove that
$$
\forall c,\sigma,\sigma'.\ \langle c \sigma \rangle \to_b \sigma' \implies p(c,\sigma,\sigma')
$$
it suffices to check all of the following:

$\forall \sigma.\ p(skip,\sigma,\sigma)$
$\forall x,e,\sigma,v.\ \langle e, \sigma \rangle \to_e v \implies
p(x:=e, \sigma, \sigma[x\mapsto v])$
$\forall \sigma,\sigma',\sigma''.\
p(c_1, \sigma, \sigma') \land p(c_2, \sigma', \sigma'')
\implies p(c_1;c_2, \sigma, \sigma'')$
$\forall \phi,c,\sigma.\ \sigma\models \lnot\phi \implies
p(while\ \phi\ do\ c, \sigma, \sigma)$
$\forall c,\phi,\sigma,\sigma',\sigma''.\
\sigma\models \phi \land
p(c, \sigma, \sigma') \land
p(while\ \phi\ do\ c, \sigma', \sigma'') \implies
p(while\ \phi\ do\ c, \sigma, \sigma'')$

Note that in item 4 we get the induction hypotheses on the subterms, very much like what would happen using structural induction.

In step 5, instead, we get both an induction hypothesis on the subterm $c$, and (crucial!) another induction hypothesis on the $while$ itself (on different states).

For your case, choose a suitable property $p(c,\sigma,\sigma')$ such as "there is some natural $N$ for which $c,\sigma$ terminates in $N$ small steps in stale $\sigma'$".


Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?

You can get a $\Sigma_2$ sentence for $\mathsf{P}=\mathsf{PSPACE}$, using the same technique as in the blog post, only replace $SAT$ by $QBF$. I doubt there is a known sentence of lower complexity.


Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

You shouldn't need to keep track of state. This can all be handled with capacity constraints over the nodes. The network can be structured as follows:

Start with the graph where one partition consists only of the "men" nodes and the other partition consists of the "women" nodes. Now, add a node for each broker $b$ and for each marriage pair $(m, w)$ on $b$'s list create two edges $(m, b)$ and $(b, w)$. Finally add a source node connected to all men and a sink node connected to all women (you can add another arc between those to simplify constraint cases if you want, but it's not necessary).

So now we have a graph, but to have a proper flow-network we need capacity constraints. For each man and women node we have a capacity constraint of 1, since they can each only marry at most one person. For the $i$th broker node, add a capacity constraint of $b_i$. This way the total number of flows (marriages) going through the broker is at most $b_i$.

Compute maximum flow over this graph and you should be good to go.


Numbers of ways of expressing the sum of a number between [a,b]

What you want is the number of integer partitions restricted to the interval $[a,b]$. I suggest you take a look at the approaches to count all partitions (check references and external links of the article) and adapt it to your needs.


Is the complexity of this algorithm O($\sqrt{n}$) or linear?

No, it would not make the algorithm linear. The worst-case scenario would be $n = m^2 + 1$, where $m$ is some positive integer. In this case, you have an additional $(m+1)^2 - m^2 = 2m + 1$ many tries (since the next square after $m^2$ is $(m+1)^2$ and $n < (m+1)^2$), which is roughly equal to $2\sqrt{n} \in \Theta(\sqrt{n})$.


What is the complexity class of arranging $1,\ldots, n$ so that all neighbors sum to a perfect square?

Whether this problem is in NP or not (or rather, in NP or not known to be in NP) depends on how you encode the input. If you encode the input in binary (or in decimal), then the input "$N$" has length $n = O(\log N)$, whereas the obvious witness has length $\Theta(N\log N)$, which is exponential in $n$ (of course, there could be a more compact witness), giving a complexity upper bound of only NEXP. In contrast, if you encode the input in unary (that is, as $1^N$, i.e., $N$ times the symbol $1$), then the input length is $N$ as well, and so the witness has polynomial length, putting the problem in NP.

Even if you use the second encoding, it seems unlikely that the problem is NP-complete. Most NP-complete problems involve a lot of data, and even the few problems which have a constant number of integers as input have more than one integer as input. Of course, formally, speaking, you can think of the input to any problem as a single integer. But semantically, there is a big difference.

What is the complexity of the problem, then? If there is a nice characterization of the values of $N$ for which such an arrangement exists, then it is likely that implementing the characterization would put the problem in P (even using binary encoding). As an extreme example, if such an arrangement exists for all large enough $N$, or doesn't exist for all large enough $N$, then the problem can be solved in linear time. If there is no simple characterization, then the problem might indeed be difficult, but probably not NP-complete or NEXP-complete.


Algorithm for optimal spacing in intervals

Sure.  A simple approach is to use binary search on the separation distance $d$: given $d$, it is easy test whether there is a way to space out $k$ points so that all are at least $d$ apart (I'll let you figure out how; if you can do it for one interval, you should be be able to do it for multiple intervals).  Then use binary search on $d$.


Selecting a subtree in an array representation of a binary tree

If you change the layout to following:

1 is the root
The left child of i is L(i) = 2*i.
The right child of i is R(i) = 2*i+1.

then formula is simple: binary index of the node is prefix of binary index of any its descendant, f.e. node with index 0b101 is ancestor of any node with index 0b101...

In order to check this property, you need to find index of highest set bit in both numbers hsbit(x) and perform the check descendant >> (hsbit(descendant) - hsbit(ancestor)) == ancestor.

Moreover, it seems that your layout is just the same as mine, but with all indexes decremented by 1.


We use the following notation:

$M$ is the set of men, $W$ the set of women.
For a man $m$ and a set $W'$ of women, $\max_m W'$ is the woman which $m$ prefers the most among those in $W'$, or $\bot$ if $W'$ is empty. We similarly define $\max_w M'$ for a woman $w$ and a set $M'$ of men.

One way to view the Gale–Shapley algorithm is as maintaining a graph $G$ of possible matches. Here is pseudo-code for the Gale–Shapley algorithm from this point of view:

Create a complete bipartite graph $G$ with the men on one side and the women on the other side. The initial set of edges is thus $\{(m,w) : m \in M, w \in W\}$.
For each man $m \in M$, let $\operatorname{top}(m) = \max \{w : (m,w) \in G\}$ be the woman $m$ most prefers among his possible matches at this point; $m$ proposes to $\operatorname{top}(m)$.
For each woman $w \in W$, let $\operatorname{best}(w) = \max \{m : \operatorname{top}(m) = w\}$ be the man $w$ most prefers among those who propose to her; $w$ chooses $\operatorname{best}(w)$ (if different from $\bot$).
Remove $(m,\operatorname{top}(m))$ from $G$ whenever $\operatorname{best}(\operatorname{top}(m)) \neq m$, that is, remove $m$'s top choice as a possibility if she rejects him.
If any edge was removed from $G$ in Step 4, go back to Step 2.
Return the matching in which each man $m \in M$ is married to $\operatorname{top}(m)$, and each woman $w \in W$ is married to $\operatorname{best}(w)$.

The idea of the algorithm is that at each point, in every stable marriage, every match $(m,w)$ is an edge in $G$. The reason is as follows. Suppose that in Step 4, $\operatorname{best}(\operatorname{top}(m)) \neq m$ for some man $m \in M$, and consider any marriage in which $m$ is married to $w = \mathrm{top}(m)$. Let $m' = \mathrm{best}(w)$, so that $w = \mathrm{top}(m')$. Obviously $w$ by definition prefers $m'$ to $m$. Since $w$ was $m'$'s top possible choice, $m'$ must be married to someone he prefers $w$ over. Therefore $(m',w)$ is an unstable pair. This shows that no stable marriage can contain $(m,w)$, and so we can safely remove it from $G$ in Step 4.

Throughout the algorithm, no man $m \in M$ is ever left alone, i.e. there is always some $w \in W$ such that $(m,w) \in G$; this is important, since otherwise the algorithm isn't well-defined. This property holds due to the following list of observations:

Once $\operatorname{best}(w) = m \neq \bot$ at some stage for some woman $w \in W$, $\operatorname{best}(w) \neq \bot$ from that point on, and never becomes less desirable than $m$ from the point of view of $w$. This is because at the next iteration, $\operatorname{top}(m) = w$, so $\operatorname{best}(w)$ is at least as good as $m$.
If $\operatorname{best}(w_1),\operatorname{best}(w_2) \neq \bot$ at some iteration for $w_1 \neq w_2 \in W$, then $\operatorname{best}(w_1) \neq \operatorname{best}(w_2)$ at that iteration. This is since $\operatorname{top}(\operatorname{best}(w_1)) = w_1 \neq w_2$.
Every time an edge $(m,w)$ is removed, $\operatorname{best}(w) \neq \bot$. This is because $w = \operatorname{top}(m)$.

Suppose now that all edges adjacent to some man $m \in M$ are removed, and consider the iteration in which the last edge adjacent to $m$ is removed. At this point, all edges $(m,w)$ were removed, so by (3) and (1), $\operatorname{best}(w) \neq \bot$ for all women $w \in W$. By (2), the mapping $\operatorname{best}\colon W\to M$ is one-to-one and so in bijection. In particular, $m = \operatorname{best}(w)$ for some woman $w \in W$. But this means that $w = \operatorname{top}(m)$ and so $(m,w)$ would not be removed in Step 4. We conclude that no man $m \in M$ is ever left isolated.

Since we only remove edges, eventually Step 6 will be reached. At this point, $\operatorname{best}(\operatorname{top}(m)) = m$ for all men $m \in M$, and so $\operatorname{top}$ and $\operatorname{best}$ are inverses. This shows that the output is well-defined and a matching.

Moreover, the matching is stable. Indeed, suppose that $(m,w)$ was an unstable pair, $m$ preferring $w$ over $\operatorname{top}(m)$, and $w$ preferring $m$ over $\operatorname{best}(w)$. Since $m$ prefers $w$ over $\operatorname{top}(m)$, necessarily $(m,w) \notin G$. When this edge was removed, $w$ preferred $\operatorname{best}(w)$ over $m$, and by (1), at the end $w$ still prefers $\operatorname{best}(w)$ over $m$, leading to a contradiction.

Finally, the matching is man-optimal. This is because in any stable marriage, a man $m \in M$ is matched to one of its neighbors in the final graph $G$. The marriage output by the algorithm matches $m$ to his top choice $\operatorname{top}(m)$, so it is optimal from the point of view of $m$.

Moreover, the matching is woman-pessimal. For suppose there were some stable matching in which some woman $w \in W$ is matched to a man which she prefers less than her match $m = \operatorname{best}(w)$ returned by the algorithm. Since $G$ represents the only possible matches in stable marriages, $m$ must be matched to some woman he prefers less than $w = \operatorname{top}(m)$. Thus $(m,w)$ is an unstable pair, and we reach a contradiction.

This exposition is taken from Section 6.3 of this paper, where other algorithms are described and analyzed, culminating in Subramanian's fixed point algorithm.


How to solve this very complicated assignment problem

I don't see a way to solve this using standard algorithms for the assignment problem.

If you want an exact solution (i.e., the optimal solution), I would recommend integer linear programming (ILP).  You can introduce zero-or-one variables $x_{i,j,k}$, where $x_{i,j,k}=1$ means that item $i$ is placed in stack $j$ position $k$, and continuous variables $w_j$, where $w_j$ represents the width of stack $j$.

It's then not too hard to write down linear inequalities that capture all your requirements.  For instance, we have $\sum_{j,k} x_{i,j,k} = 1$ (each item is placed in one location) and $\sum_i x_{i,j,k} = 1$ (two items can't be placed in the same location; every position must be full) and $c_{i,k} - w_j \le M (1-x_{i,j,k})$ where $c_{i,k}$ is the width of item $i$ if placed in position $k$ and $M$ is a sufficiently large constant (this ensures that the $w$'s represent the stack widths correctly).  Then, you can minimize $\sum_j w_j$ with an off-the-shelf ILP solver.

I don't know how efficient it will be, or whether it will be adequate for online realtime calculation, but I suggest you give it a try and find out.

If it is too slow, there are some options.  One option is that some ILP solvers come with a way to impose a time limit; the solver tries to find the best solution it can within the time limit, with no guarantee that it will find the optimal solution.  Another option would be to try to craft some heuristic that doesn't necessarily yield the optimal solution, but is fast; maybe a greedy algorithm or something.  For instance, here is an off-the-cuff idea.  Associate with each item the smallest possible width it could have, among all the possible places it can be placed (out of the positions that remain open).  Pick the item with the largest associated value, and place it in the position that minimizes its width.  Update the associated values for all items, and repeat.  No guarantees about the quality of the solution, but this will be fast.  One could also use the smallest amount that it increases the total cost of the solution, out of all possible placements, rather than the smallest width, as the value associated with a particular item.


Boolean expression for sum bit of full adder

1 xor 1 xor 1 = 1, so this is correct in that case as well.


Ordering the incident edges of each vertex to have a specified pre-order traversal

We reduce from Hamiltonian cycle. Given a graph $G$, we construct new labelled graph as follows:

Label each vertex of $G$ by $\mathrm{A}$
To each vertex of $G$ connect it with a hanging vertex "above" it and label this vertex by $\mathrm{F}$
For each edge $e$ of $G$, add a "middle" vertex labelled by $\mathrm{K}$, and connect each "middle" vertex to the two $\mathrm{F}$ vertices above the two $\mathrm{A}$ end points of its corresponding edge.

The sequence will be $\mathrm{AFKAFK}\dots\mathrm{AFK}$$KKK..\dots KKK$ where we repeat the pattern $\mathrm{AFK}$ the number of times equal to the number of vertices of $G$, i.e. $|V(G)|$. And the number of trailing $\mathrm{K}$ (written in italic for clarity) equals $|E(G)|-|V(G)|$, i.e. after finishing the Hamiltonian cycle, the traversal needs to come back and collect the remaining "middle" vertices.

If $G$ is Hamiltonian, clearly we can order the neighborhood of each vertex so that the edge that will be taken at each vertex is in accordance with the Hamiltonian cycle.

Conversely, if we can order the neighborhood of each vertex and choosing a string vertex so that the preorder traversal prints out the required sequence then we can follow the path delineated by the traversal to figure out the Hamiltonian cycle. Indeed, if at some point you get stuck, then there would be the very FIRST time you get stuck somewhere. But clearly, if so, you need to produce a $\mathrm{KK}$ before the trailing "garbage" sequence begins. In short, you cannot get way back and branch (at least for the FIRST time) without printing out a $\mathrm{KK}$.


Term for the tree of all paths starting from a given vertex in a graph

It's the self-avoiding walk tree (SAW tree).

The trees seem to have been first considered by C.D. Godsil (Matchings and Walks in Graphs, Journal of Graph Theory 5(3):285–297, 1981; DOI link; just before Lemma 2.4), though Godsil doesn't use the name.

(And, yes, "self-avoiding walk" is just a mighty-long way of saying "path".)


Concrete understanding of difference between PP and BPP definitions

Vor's answer gives the standard definition. Let me try to explain the difference a bit more intuitively.

Let $M$ be a bounded error probabilistic polynomial-time algorithm for a language $L$ that answers correctly with probability at least $p\geq\frac{1}{2}+\delta$. Let $x$ be the input and $n$ the size of the input.

What distinguishes an arbitrary $\mathsf{PP}$ algorithm from a $\mathsf{BPP}$ algorithm is the positive gap between the probability of accepting $x\in L$ and the probability of accepting $x\notin L$. The essential thing about $\mathsf{BPP}$ is that the gap is at least $n^{-O(1)}$. I will try to explain why this distinction is significant and allows us to consider $\mathsf{BPP}$ to be considered efficient algorithms (even conjectured to be equal to $\mathsf{P}$) whereas $\mathsf{PP}$ is considered inefficient (actually $\mathsf{PP}$ contains $\mathsf{NP}$). All of this comes from this gap.

Let's start by looking at $\mathsf{PP}$ more carefully.

Note that if an algorithm uses at most $r(n)$ random bits during its execution and the error probability is smaller than $2^{-r(n)}$ then error probability is actually $0$, there cannot be any chose of random bits that will make the algorithm answer incorrectly.

Furthermore, an algorithm with running time $t(n)$ cannot use more than $t(n)$ random bits, so if a probabilistic algorithm's error with worst-case running-time $t(n)$ is better than

With a similar argument we can show that the case where the difference between the probability of accepting an $x\in L$ and the probability of accepting an $x\notin L$ is too small is similar to the case where we don't have almost no difference as in $\mathsf{PP}$ case.

Let's now move towards $\mathsf{BPP}$.

In probabilistic algorithms, we can boost the probability for correctly answering. Let's say we want to boost the correctness probability to $1-\epsilon$ for say error probability $\epsilon=2^{-n}$ (exponentially small error).

The idea is simple: run $M$ several times and take the majority's answer.

How many times should we to run $M$ to get the error probability to be at most $\epsilon$? $\Theta(\delta^{-1} \lg \epsilon)$ times. The proof is given at the bottom of this answer.

Now let's take into the consideration that the algorithms we are discussing need to be polynomial-time. That means that we cannot run $M$ more than polynomially many times. In other words, $\Theta(\delta^{-1} \ln \epsilon) = n^{O(1)}$, or more simply

$$\delta^{-1} \lg \epsilon = n^{O(1)}$$

This relation categorizes the bounded error probabilistic algorithms into classes depending on their error probability. There is no difference between the error probability $\epsilon$ being being $2^{-n}$ or a positive constant (i.e. doesn't change with $n$) or $\frac{1}{2}-n^{O(1)}$. We can get from one of these to the other ones while remaining inside polynomial time.

However if $\delta$ is too small, say $0$, $2^{-n}$, or even $n^{-\omega(1)}$ then we don't have a way of boosting the correctness probability and reducing the error probability sufficiently to get into $\mathsf{BPP}$.

The main point here is that in $\mathsf{BPP}$ we can efficiently reduce the error probability exponentially so we are almost certain about the answers and that is what makes us consider this class of algorithms as efficient algorithms. The error probability can be reduced so much that a hardware failure is more likely or even a meteor falling on the computer is more likely than making an error by the probabilistic algorithm.

That is not true for $\mathsf{PP}$, we don't know any way of reducing the error probability and we are left almost as if we are answering by throwing a coin to obtain the answer (we are not completely, the probabilities are not half and half, but it is very close to that situation).

This section gives the proof that to obtain error probability $\epsilon$ when we start with an algorithm with gap $(\frac{1}{2}-\delta,\frac{1}{2}+\delta)$ we should run $M$ $\Theta(\delta^{-1} \lg \epsilon)$ times.

Let $N_k$ be the algorithm that runs $M$ for $k$ times and then answers according to the answer of majority. For simplicity, lets assume that $k$ is odd so we don't have ties.

Consider the case that $x \in L$. The case $x \notin L$ is similar. Then
$$\mathsf{Pr}\{M(x) \text{ accepts}\} = p \geq \frac{1}{2} + \delta$$
To analyze the correctness probability of $N_k$ we need to estimate the probability that majority of the $k$ runs accept.

Let $X_i$ be 1 if the $i$th run accepts and be $0$ if it rejects. Note that each run is independent from others as they use independent random bits. Thus $X_i$s are independent Boolean random variables where
$$\mathbb{E}[X_i] = \mathsf{Pr}\{X_i=1\} = \mathsf{Pr}\{M(x)\text{ accepts}\} = p \geq \frac{1}{2}+\delta$$

Let $Y = \Sigma_{i=1}^k X_i$. We need to estimate the probability that majority accept, i.e. the probability that $Y\geq\frac{k}{2}$.

$$\mathsf{Pr}\{N_k(x) \text{ accepts}\} = \mathsf{Pr}\{Y \geq \frac{k}{2}\}$$

How to do it? We can use Chernoff bound which tells us the concentration of probability near the expected value. For any random variable $Z$ with expected value $\mu$, we have

$$\mathsf{Pr}\{|Z-\mu| > \alpha\mu\} < e^{\frac{\alpha^2}{4}\mu}$$

which says that the probability that $Z$ is $\alpha\mu$ far from its expected value $\mu$ is exponentially decreases as $\alpha$ increases. We will use it to bound the probability of $Y < \frac{k}{2}$.

Note that by linearity of expectation we have
$$\mathbb{E}[Y] = \mathbb{E}[\Sigma_{i=1}^k X_i] = \Sigma_{i=1}^k \mathbb{E}[X_i] = kp \geq \frac{k}{2} + k\delta$$

Now we can apply the Chernoff bound. We want an upper-bound on the probability of $Y< \frac{k}{2}$. The Chernoff bound will give an upper-bound on the probability of $|Y-(\frac{k}{2}+k\delta)| > k\delta$ which is sufficient. We have

$$Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if we pick $\alpha$ such that $\alpha kp = k\delta$ we are done, so we pick $\alpha = \frac{\delta}{p} \leq \frac{2\delta}{2\delta+1}$.

Therefore we have

$$Pr\{Y < \frac{k}{2} \} \leq Pr\{|Y - (\frac{k}{2}+k\delta)| > k\delta\} \leq Pr\{|Y - kp| > \alpha kp\} < e^{-\frac{\alpha^2}{4}kp}$$

and if you do the calculations you will see that

$$\frac{\alpha^2}{4}kp \leq \frac{\delta^2}{4\delta+2}k = \Theta(k\delta)$$

we have

$$Pr\{Y < \frac{k}{2} \} < e^{-\Theta(k\delta)}$$

We want the error to be at most $\epsilon$, so we want

$$e^{-\Theta(k\delta)} \leq \epsilon$$

or in other words

$$\Theta(\delta^{-1} \lg \epsilon) \leq k $$

One essential point here is that in the process we will use many more random bits and also the running time will increase, i.e. the worst-case running-time of $N_k$ will be roughly $k$ times the running-time of $M$.

Here the mid point of the gap was $\frac{1}{2}$. But in general this doesn't need to be the case. We can adopt a similar method for other values by taking other fractions in place of majority for accepting.


Let's look at a simple, concrete example where $d=4$.  Suppose the codebook is $C = \{0000,1111\}$.  This means the sender transmits either the codeword $0000$ or the codeword $1111$ during each block of communication, and no other binary strings are transmitted.  For example, to transmit a $0$ bit, the string $0000$ is transmitted, and to transmit the $1$ bit, the string $1111$ is transmitted.  The hamming distance of this code is $4$.

Suppose the sender transmits one of the above two codewords, and suppose the receiver gets $0010$. Then the receiver knows that the transmitted codeword has been corrupted by the noisy channel because the received vector is not either of the two transmitted codewords (only $0000$ or $1111$ could have been transmitted).  Thus, the receiver is able to "detect" that an error has occurred (i.e. that the transmitted codeword has been corrupted by the noisy channel).  If the noisy channel flips up to any $3$ bits, the receiver will detect an error, but if the channel flips all $4$ bits  - say $0000$ was transmitted and $1111$ was received - then the receiver will wrongly conclude that the received codeword $1111$ was the transmitted codeword.  Thus, we say this code can detect up to $3$ bit errors because the minimum distance between any two codewords in this codebook is at least $4$.  If only up to $3$ bits are flipped, then such an error can't convert one codeword into another because any two codewords differ in at least $4$ positions. More generally, if the hamming distance is $d$, then up to $d-1$ errors can be detected.

Suppose again that the received vector is $0010$.  Then, the receiver will detect that an error has occurred.  But can it correct the error and figure out which codeword was transmitted?  The receiver can use the nearest-neighbor decoding rule, which says if the received vector is not one of the codewords (in the codebook), then make the decision that the transmitted codeword is the one closest (in hamming distance) to the received vector.  This is a good rule when the probability of a bit getting flipped is small. Because $0000$ is closer to $0010$, the receiver concludes that $0000$ was transmitted.  But what if the received vector is $0011$?  Then, both $0000$ and $1111$ are equally distant from the received vector.  The receiver will not be able to correct $2$ errors (it can only detect that an error has occurred, but not correct it).

Ideally, we would like any two codewords to differ in a large number of positions.  Define the sphere of radius $d$ centered around a codeword $x$ to be the set of all codewords which differ from $x$ in at most $d$ positions. For example, the sphere of radius $1$ centered at $0000$ is the subset of vectors $\{0000,1000, 0100, 0010, 0001\}$.  Because the sphere of radius $1$ centered at $0000$ and the sphere of radius $1$ centered at $1111$ are disjoint, the nearest-neighbor decoding rule will decode correctly if the number of bit flips is at most $1$. The above code of hamming distance $4$ can correct up to $\lfloor (4-1)/2 \rfloor = 1$ error.  Because of the possibility that the received vector can be $0011$ or $0101$, etc, the code can't correct $2$ errors.

More generally, if the spheres of radius $d$ centered at any two codewords in the codebook are disjoint, then the nearest-neighbor decoding rule will correct up to $d$ errors.  For any two such spheres to be disjoint, any two codewords must differ in at least $2d+1$ positions.  If there exist some two codewords in $2d$ or fewer positions, then these two codewords could both be the nearest-neighbors of some received vector.  Visualize in your mind the picture in $3$ dimensions of two spheres of radius $d$, which end up being disjoint because the distance between their centers is $2d+1$.

Thus, if the hamming distance is $2d+1$, the code can correct up to $d$ errors. Or, if the hamming distance is $d$, the code can correct up to $\lfloor (d-1)/2 \rfloor$ errors.


Pros and cons of representing strings as lists of characters

I'd say that the main reason for having a separate String representation is performance. For example, Haskell defines a string to be a list of characters type String = [Char]. But in many applications it turns out that this is too slow - you have one constructor for every character, which requires a lot of work from the garbage collector. Then of course you have to duplicate most of the string functions, but the benefit is that you can implement them natively to be very fast.

So I'd suggest: If you are concerned about performance, define a native string type. If not, use list of characters instead.


My goal is to be able to judge what parts of formal verification I
  could apply to my job as a software/network engineer.

If you plan to use formal verification as black boxes, then I would suggest using some tools to have an idea how they work. Here are some open source tools:

Error Prone of Google
Nullaway of Uber
Facebook Infer
Ikos of NASA
Java PathFinder developed by NASA, now maintained by community.
Clang Static Analyzer of Apple
...

If you want to understand their basics, you can start with the book "Principal of Program Analysis". It covers many basic topics from Type Theory to Abstract Interpretation etc.

The book doesn't discuss anything deeply. For example, it doesn't discuss any abstract domains, the key part in abstract interpretation. Recent topics such as separation logic, which Facebook Infer is based on, are not covered either.

If you want to learn advanced topics, the only way is to read the proceedings of top conferences, e.g. POPL, PLDI, CAV, VMCAI, SAS, ICSE, FSE, ASE, ISSTA, etc etc.

A comment by @DmitriChubarov

  As I understand this is a question of why there is so little use of
  formal methods in the practice software development, ... or is there?

There are companies that are earning hundreds of millions a quarter by selling static analysis tools (I work for one of them), so I believe the number of companies that use formal verification is not little at all.


Recursive Call Inside Argument List (C++)

So I did a dry run of the algorithm as suggested by greybeard in the comments. It turns out that for any a and n, after a certain number of recursions, one ends up getting Power(1, 2). This leads to an infinite recursion because Power(1, 2) also leads to Power (1, 2) after a certain number of recursions.


terminology for grouping words in a string?

You are probably looking for the term n-grams, with $n = 2$ in your case. This is very useful in natural language processing and speech recognition.


Polynomially related lengths under two different encodings

Garey and Johnson are referring to the fact that any encoding scheme for some instance $I$ of a problem $\Pi$ will only differ in length (i.e. number of bits) by a polynomial amount. For example, consider two possible ways to encode a graph: adjacency matrix, and adjacency list.

It is not possible to obtain a super-polynomial speedup by using one encoding over another for various instances of problems. Again, this notion relies on the fact that encodings are reasonable. That is to say, we are not unnecessarily padding our encoding with some "junk" information.


Prove or disprove: Complement of language $L=\left\{baba^2ba^3b...ba^{n-1}ba^nb \, | \, n \geq 1\right\}$ is context-free

No, reasoning with the complement will not work as context-free languages are not closed under complement.

Consider an alternative description of $L$: it consists of all strings $ba^{a_1}ba^{a_2} \dots ba^{a_n}b$ such that (1) $a_1 =1$ and (2) for all $1\le k<n$, $a_{k+1} = a_k+1$.


How to show that the set of TMs that accept languages of size two is recognizable?

Based on RanG. answer in comments.

To show ${Lx}$ is unrecognizable, show $\overline{Htm}$ <= ${Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
    def N(x):
        if x == 0 or x == 1 then accept
        M('')
        return accept
    return <N>

  If M is in $\overline{Htm}$ then M loops then N will accept either 0 or 1 then
  |L(N)| = 2 then N is in ${Lx}$

  if M is not in $\overline{Htm}$ then M halts then N
  will accept all x so |L(N)| = $\infty$ then N is not in ${Lx}$


If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?

All that you know is that R is NP-hard.

To show that R is NP-complete, you need to show that it is in NP.  But that is not automatically true.

As an example, let S be the question "Is there a path of cost at most l that visits every node of a graph G?" and R be the question, "What is the cheapest path that visits every node of a graph G?"  These are variants of the Traveling Salesman problem.  S is in NP while R is believed not to be.  The issue being that given a proposed solution, you just add it up for S.  But for R, there is no known polynomial way to verify that you actually have the best path.


Question on pseudocode for Ford-Fulkerson in Kleinberg-Tardos Text

This is pseudocode, not the end-all be-all of the algorithm implementation. It is a very high level overview and by nature is left up to interpretation for the implementation. That being said...

  "When we create the residual graph I was under the impression that each edge is labeled with the corresponding residual capacity."

This is not necessarily the case. You can analyze the residual graph in place, simply based on $f$ and $G$. By this, I mean it is not necessary to explicitly create a new graph $G_f$ because $G_f$ is merely a function of $G$ and $f$.

If this is the case, then the flow function $f$ is passed in to compute the residual capacity of each edge in the path. Similarly to how $G_f$ can be computed in place, if we have a path $P_f$ (from $s$ to $t$) in $G_f$, it doesn't necessarily have to an explicit path in $G_f$. It could be a path in $G$ for which we must compute $P_f$. This is when we might require $f$ to compute the bottleneck.

Again, this is just pseudocode and if you implement in a slightly different way than is described, that's okay as long as the procedure is correct.


Expressing complexity class P using first-order logic with LFP

In Neil Immerman's Descriptive Complexity the proof that P = FO + LFP uses alternating graphs: an alternating graph is a directed graph $G= \{ V, E, A, s, t\}$ where $A$ is the set of nodes marked as universal ($V \setminus A$ are existential). The accessibility relation is defined in this way:

$P_a^G(x,x)$
if $x \in V \setminus A$  $\land P_a^G(z,y)$ holds for some edge $(x,z)$ then $P_a^G(x,y)$
if $x \in A$ $\land \; outdeg(x)>0 \land P_a^G(z,y)$ holds for all edges $(x,z)$ then $P_a^G(x,y)$

The reachability problem $REACH_a$ is defined as $\{G | P_a^G(s,t)\}$ and is complete for P via first-order reductions.

Using LFP one can give a FO + LFP definition of $REACH_a$ (i.e. $REACH_a \subseteq FO+LFP$):

$$\varphi_{as}(P,x,y)\equiv  x = y \lor [\exists z(E(x,z)\land P(z,y)) \land (A(x)\rightarrow \forall z(E(x,z)\rightarrow P(z,y)))]$$

and $REACH_a = (LFP_{P_{xy}\varphi_{ap}})(s,t)$

We have $P \subseteq REACH_a \subseteq FO+LFP$, the inverse $FO+LFP \subseteq P$ follows from the fact that a FO query can be evaluated in $L$ and at most $n^k$ evaluations of $\varphi(R,x_1,...,x_k)$ are needed for $(LFP_{R \varphi})$ ($R$ is a k-ary relation).

For further details you can see the proof on Immerman's book.


This task is simple enough if you already know exactly what a function is and how to construct a truth table; you just have to write down every possible combination of assignments to all variables and functions, e.g., $x = 0$, $f(0) = 0$, and so on. If it isn't obvious, it might be beneficial to walk through a more drawn-out reasoning, which might also be more useful whenever you want to count and/or enumerate all possible functions where the number of functions is bigger, and the functions might not be that relatable (like for example how the negation function is relatable).

First of all we can count how many functions there are.

  Given sets $A$ and $B$, there are $|B|^{|A|}$ functions $f : A \rightarrow B$.

So since we have $\mathbb B = \{0, 1\}$, $^*$ and we are concerned with functions $f : \mathbb B \rightarrow \mathbb B$, we have $2^2 = 4$ functions.

The next step is to make a truth table. But first, let's look at what a function is:

  A function $f : X \rightarrow Y$ is a subset of the Cartesian product $X × Y$ subject to the following condition: every element of $X$ is the first component of one and only one ordered pair in the subset.

So we must find all sets that are subject to these constraints. An example of a set that is not a function is:

$S = \{(1,0), (1,1)\} \subset \mathbb B × \mathbb B$

since $1$ is the first component of two ordered pairs, ie. the value $1$ maps to two different values. Moreover, we don't have a mapping for the value $0$, ie. $f(0)$ is undefined.

Since we are dealing with a domain of size two, and since we have one and only one ordered pair for each member of the domain, all sets (functions) that we are considering are on the form:

$f = \{(0,\_),(1,\_)\}$

where $\_$ is either $0$ or $1$.

So then we list all possible enumerations of two ordered boolean values, and put them in the pair as the second component with the $0$ as the first component and the $1$ as the first component, respectively:

$0,0$

$1,1$

$1,0$

$0,1$

Plugging these in, we get:

$f_1 = \{(0,0),(1,0)\}$ ($f(x) = 0$)

$f_2 = \{(0,1),(1,1)\}$ ($f(x) = 1$)

$f_3 = \{(0,1),(1,0)\}$ ($f(x) = \neg x$)

$f_4 = \{(0,0),(1,1)\}$ ($f(x) = x$)

(As a sanity check, we confirm that we ended up with 4 functions, as expected.)

As a truth table:

$$\begin{array} {|c|c|c|c||c|}
\hline
x & f_1(x) & f_2(x) & f_3(x) & f_4(x)\\ \hline
0 & 0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 \\ \hline
\end{array} $$

* Or $\mathbb B = \{F,T\}$, if you prefer.


Trust in online platforms dealing with virtual goods

As far as I know, sellers can't fully verify that the platform is behaving honestly, so you'll need to trust the platform.  A malicious platform could always sell a copy to someone without giving the seller their cut.


Can we enumerate provably non-terminating functions?

Here is a simple non-terminating function:

while (true):
    do nothing

This certainly does not terminate.

On the other hand, it is not possible to enumerate all non-terminating functions.  The halting problem is recursively enumerable but not decidable, from which it follows that the complement of the halting problem is not recursively enumerable (if it were, the halting problem would be decidable).  See https://en.wikipedia.org/wiki/Recursively_enumerable_language and https://en.wikipedia.org/wiki/RE_%28complexity%29.


Yes, your understanding is correct. You may need a bit more mechanism to ensure there is at least one 1 after the initial 0's.


How to compute the sum of this series involving golden ratio, efficiently?

As D.W. pointed out there should be some kind of recurrence involving the $\tau$ function. Turn's out there is, let us again look at the $\tau$ function series, the first few terms are

$$3,6,8,11,14,16,19,21....   \; \;(1)$$

Now let us look at the difference between consecutive terms of the series,

$$3,2,3,3,2,3,2..... \; \; (2)$$

Turns out sequence $(2)$ is the infinite fibonacci word ( again some sort of strong correspondence between golden ratio and fibonacci sequences ) made up of $2's$ and $3's$. This fibonacci sequence is as follows, the first two terms are

$a_0 = 3$ , and $a_1=3,2$ and for $n\ge 2$, $a_n=a_{n-1}.a_{n-2}$, where "." represents string concatenation. First few terms of the fibonacci word are

$$a_0=3$$
$$a_1=3,2$$
$$a_2=3,2,3$$
$$a_3=3,2,3,3,2$$

and so on. With this construction the summation I mentioned can be calculated very quickly. Also I did not make any use of the fact that modulo was taken by $7^{10}$. It would be interesting if this fact could be used somehow as D.W. suggested.

PS: I solved the question using the same formula in my question. Above I provide only a hint as coming from a non-math background I found the question really interesting and won't ruin it for others.


How to find kth largest element in (max) priority queue in O(m) time?

You can implement FINDLARGEST recursively:

FINDLARGEST(k, vertex) # call with vertex = root
  if value(vertex) < k: exit the function
  output vertex
  FINDLARGEST(k, left-child(vertex))
  FINDLARGEST(k, right-child(vertex))

If there are $m$ vertices whose value is at least $k$, then FINDLARGEST explores at most $3m$ vertices: each eligible vertex together with its two children.


What is the significance of the semi clustering formula in the Google Pregel paper?

Think about what a "good" cluster is. It is a set of nodes which

are strongly interconnected (strong cohesion) and
weakly connected with nodes outside of the cluster (weak coupling).

In particular, the connection among the nodes should be stronger than the connection with the outside. And this is what they do there: $I_c$ is a measure for cohesion -- more and stronger edges inside the cluster mean more cohesion -- and similarly $B_c$ is a measure for coupling. $f_B$ is used to control the influence of coupling.

As for the denominator, they justify it in the slides:

  The score is normalized by dividing with the number of
  vertices in the clique, so that large clusters do not receive
  artificially high scores.

That's actually wrong, but the idea is the same: they divide by the number of edges there could be -- which makes sense because they "count" edges in the numerator, too -- in order to get rid of size effects. Without this rescaling, a large cluster (with many edges) would have a higher score than a smaller on with the same or even better properties. You only want to score the quality of the clusters, though, so rescaling is in order.

I daresay that $\frac{I_c}{f_B B_c}$ would also make sense (and scale itself). Usually, such scores are formulated ad-hoc and their usefulness validated by experiments (over time). That is, somebody wrote it down, used it for clustering, looked at images and was satisfied with the result. Depending on what semantic the edge weights have, the score may also be a "good" approximation for a more complicated one that is harder to compute or makes clustering (computationally) harder. That said, most clustering algorithms in use are approximations -- because clustering is NP-hard -- so the choice of auxiliary score may influence runtime and result quality of those algorithms.


Transition diagram for following token number

digits(.digits)?(E[+ -]?digits)? is a regular expression for the set of strings that the pictured automaton accepts. That is, all of the strings accepted by the automaton will match this pattern. If you're unfamiliar with regular expression syntax, you can check out this explanation from Wikipedia.

In particular, if you see some pattern followed by the ? operator, it means that pattern is optional. So something like digits(.digits)? will match strings of the form digits.digits or just digits because the last (.digits) part is optional.

I would guess that digits is a placeholder for a series of numeric digits (0-9). So something like digits(.digits)? would match strings like "33.5", "0.8", "1.892", "7", etc.


Smallest string length to contain all types of beads

With a little care your own suggestion can be implemented to $O(kn)$, if my idea is correct.

Keep $k$ pointers, one for each colour, and a general pointer, the possible start of the segment. At each moment each of these colour pointers keeps the next position of its colour, that follows the segment pointer. One colour pointer points to the segment pointer. That colour pointer is updated when the segment pointer moves to the next position. Each colour pointer in total moves only $n$ positions. For each position the segment pointer computes the maximal distance to the colour pounters, and one takes the overal minimum of that.

Or, intuitively perhaps simpler, let the pointers look into the past, not the future. Let the colour pointers denote the distance to the respective colours last seen. In each step add the distance to the last bead to each pointer, except the one of the current colour, which is set to zero.

(edit: answer to question) If $k$ is large, in the order of $n$ as suggested, then one may keep the $k$ pointers in a max heap. An update of a pointer costs $\log k$ each of $n$ steps. We may find max (the farthest colour, hence the interval length) in constant time, each of $n$ steps. So $n \log k$ total plus initialization.

Now we also have to find the element/colour in the heap that we have to update. This is done by keeping an index of elements. Each time we swap to elements in the heap (a usual heap operation) we also swap the positions stored in the index. This is usually doen when computing Dijkstra's algorithm with a heap: when a new edge is found some distances to vertices have to be decreased, and one needs to find them.


Boolean algebraic expression vs Propositional logic expression

They are not the same, but I don't blame you for thinking that they are. The reason why it doesn't seem clear that they are the same is that you've only seen one example of each.

So let's step back, define them separately, and then look at some interesting examples.

Propositional logic is a branch of mathematics that studies propositions, their truth or falsity, and how they combine.

What you probably think of as "propositional logic" is actually just one kind of propositional logic, namely, classical logic. However, this is not the only kind of classical logic, and not the only one that is interesting in computer science.

Some theories are built on top of classical logic. Presburger arithmetic, for example, is the theory of natural numbers with addition. Tarski arithmetic is the theory of real closed fields. First-order logic is the theory of quantified variables over non-logical objects.

You can think of these logic systems as types of propositional logic, with more axioms to deal with the extra stuff. Many constraint-type problems are expressible in this framework; you can look up satisfiability modulo theories for more information on how this is used.

But there are also propositional logics which are not "classical". One example of a non-classical logic is intuitionistic logic. This is a logic which models constructive proofs, which is interesting, because constructive proofs are the same thing as well-behaved computer programs. ("Well-behaved" in this sense means there is no unbounded recursion.) They are also the basis for modern type systems, such as that of Haskell.

Constructive proofs (e.g. pick any proof from Euclid's Elements) are implementable as computer programs. Given some geometric objects as input, you could implement the proof (at least in principle) as a computer program which performs the construction.

You can't do that with non-constructive proofs. Let's look as an example to see what I mean. I'll prove that there are two irrational numbers, $a$ and $b$, such that $a^b$ is rational.

Consider $z = \sqrt{2}^\sqrt{2}$. This number is either rational or irrational.

Case 1: If $z$ is rational, then set $a = b = \sqrt{2}$, and the theorem is proven.

Case 2: If $z$ is irrational, set $a = z$ and $b = \sqrt{2}$. Then $a^b = 2$ and the theorem is proven.

QED

The reason why this proof isn't constructive is that it relies on the law of the excluded middle; $z$ must be either rational or irrational, but we don't (and, in a sense, can't) actually test which of them is true.

Intuitionistic logic systems tend to give you proof systems which are decidable. This is an extremely important practical concern. If you consider, for example, the Java bytecode verifier, or the type system for a programming language (both of which prove that some program is type-correct), they must terminate with an answer, so they must be based on a decidable proof system. By allowing propositions which are neither provable nor refutable, you avoid Gödel-like incompleteness.

That's just one example, of course. Other non-classical propositional logics include modal logics (which can be used to model situations where you have multiple agents who know different things; think about network protocols), and temporal logics (where the truth or falsity of a proposition may change over time).

The thing that connects all of them is the notion of a "proposition". Propositional logic can be thought of as the study of a family of logic systems, all of which deal with the notion of a mathematical statement which has a "truth"-type judgment.

Boolean algebra, on the other hand, is a purely algebraic system, characterised by a set of axioms. Saying "Boolean algebra" is like saying "group" or "field" in abstract algebra. Classical propositional logic satisfies the axioms, but so do other mathematical structures.

The subsets of a set $S$, for example, form a Boolean algebra; with the "not" operator corresponding to "set complement", "and" corresponding to "set intersection", and "or" corresponding to "set union". You can think of "true" as being $S$ and "false" being the empty set, but these are not the only "truth values" which the system models.

Lattices form Boolean algebras, and some lattices are important in computer science (e.g. Scott domains). Moreover, some important non-classical logic-like systems naturally form Boolean algebras, such as fuzzy logic.

So what I hope you can see is that while the two notions are related (some Boolean algebras model some propositional logics), they are not exactly the same thing. How they differ is part of what makes them interesting.


What is the time complexity of this randomized algorithm?

This is the coupon collector's problem. You can find its analysis in introductory textbooks on probability theory, among other sources.


Showing Maximum Independent Set is $NP-hard$

Clique is the decision version of Maximum Clique, which is an optimization problem:

Clique: Given a graph $G$ and an integer $k$, decide whether there is a $k$-clique in $G$.
Maximum Clique: Given a graph $G$, find the maximum size of a clique.

Let me mention that these names are not standard. Other people might use Clique or Maximum Clique to refer to slightly different problems. Optimization problems and their decision versions are often confused in the literature, since usually it is clear from context which of the two is referred to.

There is a canonical way to convert an optimization problem to a decision problem, demonstrated above. This conversion ensures, in most circumstances, that the decision version is in NP.

We say that an optimization problem is NP-hard if its decision version is. To show that Maximum Independent Set is hard, you really need to show (by definition) that Independent Set is hard; and this you can do by reduction from Clique (not Maximum Clique).

Also, Clique and Independent Set are really the same problem — you get one from the other by complementing the graph.

Finally, let me stress that Independent Set is NP-complete, but it is not known to be in coNP or to be coNP-hard; indeed, it is conjectured not to be in coNP and not to be coNP-hard (otherwise NP=coNP).


Where does 1.3606 approximation ratio come from for vertex cover approximation?

The fact that nobody found a $1.99$ approximation doesn't necessarily mean that the problem of finding one is $\mathsf{NP}$-hard (e.g., it might be the case that that $\mathsf{P} \neq \mathsf{NP}$ and a polynomial-time $1.99$-approximation algorithm exists, we are just unaware of it).
Additionally, we can prove that finding a $1.3606$-approximation is a $\mathsf{NP}$-hard problem, i.e., if $\mathsf{P} \neq \mathsf{NP}$ no $1.3606$-approximation algorithm exists. This is not a direct consequence of the previous fact, but a separate result by Irit Dinur and Samuel Safra. The details can be found here.


What is the time complexity of enqueue and dequeue of a queue implemented with a singly linked list?

Enqueueing

You don't need to traverse the entire list to find the new tail, you just need to add a new node where the current tail points to and set that node as the new tail.

Pseudocode (assuming that head != null and tail != null):

function enqueue(value) {
    node = new Node(value)     // O(1)
    tail.next = node           // O(1)
    tail = node                // O(1)
    size++                     // O(1)
}

From which we can conclude that the time complexity is $O(1)$.

Dequeueing

For dequeueing, we only need to set the next node of the current head as the new head and return the value of the old head.

Note: Don't forget that if the new head is set to null, the tail should be set to null as well:

Pseudocode (assuming that head != null and tail != null):

function dequeue() {
    value = head.value         // O(1)
    head = head.next           // O(1)
    size--                     // O(1)

    if (head == null) {        // O(1)
        tail = null            // O(1)
    }

    return value               // O(1)
}

All these operations have $O(1)$ time complexity, which makes the time complexity of the dequeue function $O(1)$ as well.

Searching

Searching for a value is done by traversing through all the items, starting from the head. In the worst case scenario, you would need to traverse the entire queue, which makes the worst-case time complexity $O(n)$.

For example, if you want to remove the tail, the time complexity would be $O(n)$. This is because you would need to find the new tail for the queue and since the tail does not have access to the previous element in a singly linked list, you would need to search the entire queue for the new tail.

Pseudocode (assuming that head != null and tail != null):

function removeLast() {

    // Edge case when there is only 1 element in the queue.
    if (head == tail) {                   // O(1)
        value = head.value                // O(1)
        head = null                       // O(1)
        tail = null                       // O(1)

        return value                      // O(1)
    }

    // Searching for the new tail.
    newTail = head                        // O(1)
    while (newTail.next != tail) {        // O(n)
        newTail = newTail.next            // O(1)
    }

    value = tail.value                    // O(1)
    newTail.next = null                   // O(1)
    tail = newTail                        // O(1)

    return tail                           // O(1)
}

From which can be seen that the time complexity is indeed $O(n)$.


Seek to infer "correct" route from sequence of stops

To be clear, this is not an optimization problem; I do not seed to find the "best" route.

Actually this is an optimization problem!  Just instead of optimizing for shortest length or fastest time, you're optimizing for highest likelihood:

  What I seek to do is to infer what is most likely the intended route
   [...]

Now you just have to figure out your model for likelihood.

For example, say that the bus drives$$
\left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{B}\right]{\rightarrow}\left[\mathrm{C}\right]
$$half the time, then$$
\left[\mathrm{A}\right]{\rightarrow}\left[\mathrm{C}\right]{\rightarrow}\left[\mathrm{B}\right]
$$the other half of the time.  But, it tends to do the first route on odd-numbered days, unless it's raining.  Except, the driver "Bob" reverses this pattern, whereas "Suzzy" always does the first one and "Atomic Robot #7" always does the second one.  What do you infer from that?

Math has no opinion on this topic.  For example, if you choose to believe that whatever "Bob" does is always correct, even if every other driver disagrees with him, that's your belief; math doesn't object.

So, what you need to do is construct a model for assessing how likely you believe a particular solution is given a set of data, then optimize for likelihood given the data.


For these hints, I'm assuming that you know (and are allowed to use) the fact that $\{a^nb^n\mid n\ge 0\}$ is not regular.

For (1), if $L_1$ was regular, then since regular languages are closed under intersection, we'd have $L_1\cap b^*c^*$ was regular. What's that language?

For (2), if $L_2$ was regular, then since regular languages are closed under complementation, we'd have $\overline{L_2}$ was regular, and so $\overline{L_2}\cap a^*b^*$ was regular. What's that language?


Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable?

You are right about the fact that being able to conceive a Java program for doing the job, then there must exist a Turing machine which will also recognize that language. However, you don't need the Church-Turing thesis to confirm your statement. You need something weaker, namely the fact that both Java and TM are acceptable programming systems and hence they are isomorphic (ie. they compute the same set of partial functions) by Roger's theorem.

The main point is that Roger's theorem is a theorem and Church-Turing thesis is not proven.


Is there a formal definition of sub-instances or sub-problems?

I don't think there is a widely-used formal definition, and that this is so for a good reason. Sub-problems or sub-instances are tools used in the process of designing algorithms (for "divide and conquer" or "dynamic programming" in particular, but also more generally).
The process of (humans) designing algorithms is not a completely formal process: it relies on intuition and informal insight to arrive at an idea of an algorithm, and eventually refine this idea into an actual formalized algorithm.
As for your final question

I want to know whether I can let the substrings or the prefixs (suffixs) of $x$
be (all of) the sub-instances. Is there a formal definition of sub-instances?

This depends on the context. It could be that you're reading some text where someone has given a formal definition of "sub-instance". If not, then I think it is best to work under the assumption that there is no formal definition of "sub-instance" here.
Given that "sub-instance" is only an informal notion, how do you determine whether something is a sub-instance? The only option is to try it out and see if it works. The idea of something being a sub-instance is equally valid as the idea that it isn't a sub-instance. What you need to do is to determine which of the two ideas is more useful in constructing or reasoning about an algorithm.


How is sound input and output data converted to use with machine learning networks?

Probably the most common way to represent audio for speech recognition is using the Mel-frequency cepstrum coefficients. If you're interested in finding out more about state of the art neural network based systems for speech recognition, I'd recommend checking out some of the recent work by George Dahl.

In regard to the other, more general portion of your question, using "binary" data in the way you describe is a very bad idea (if you mean what I think you mean). The binary representations used to store information in a computer is primarily designed for efficiency, both in terms of operations and space. Thus, this sort of representation is not necessarily representative of the actual characteristics of the data.

An example of this is the difference between signed and unsigned integers. If you're using 8 bit unsigned integers, then 11111111 > 00000001 but if you're using signed (2's complement) integers then 11111111 < 00000001. But, if you just represented the data as binary vectors, then you're essentially forcing a machine learning system to not only figure out whatever relationship you're trying to model, but also whatever encoding scheme you've used. You can avoid this by using representations that respect the characteristics (real valued, categorical, etc) of the data.

Lastly, if you're trying to predict 1 of $k$ mutually exclusive classes (such as characters), then the most common approach is to represent the class label (target) as a $k$ dimensional vector with a 1 at the $i$th position, corresponding to the class, and 0 everywhere else. You'll frequently see this referred to as a 1-of-$k$ or one-hot representation. You'll also want to use an appropriate output function for you're neural net, most likely the softmax function given by

$$
f(x_i) = \frac{\exp(x_i)}{\sum_{j=1}^k \exp(x_j)},
$$
where $x_i$, $i = 1, \ldots, k$, is the total input to the $i$th output unit. You can interpret this type of output as representing the conditional probability of each class given the input. The derivative is also particularly simple under the log-loss, which is what you should probably be using in this scenario.

In conclusion, neural networks are not magic black boxes. Just like any other ML technique, if you just throw data at them without considering the choices (inputs, outputs, loss function, etc) you're making and why, you'll probably have little success.


Compute hash value according to multiplication method

You haven't extracted the 14 most significant bits. First, you have to write $r$ as a $w$-bit number:
$$
00000001000011001100000001000000
$$
Now you extract the 14 most significant bits:
$$
00000001000011
$$
Converting to decimal, this is 67.


When proving a set is not regular is it enough to prove a subset of it regular?

I think you mixed up a few things here. Say, L is indeed regular. Then the pumping lemma guarantees us a pumping length.

If we want to show that $L$ is not regular, we can go on by assuming its regular and for every pumping length we find a word that cant be pumped.

This means, we need to search for a word (for example $ab^pab^pa$ as you have suggested) and show that no matter how you divide this word into the 3 pieces $x,y,z$ ($w=xyz$) of the pumping lemma, you can find an integer $n$ with $xy^nz\notin L$. This would contradict the pumping lemma and therefore the regularity of $L$.

As a side note, showing that a subset of $L$ is not regular doesnt imply that also $L$ is not regular (for example, $\Sigma^*$ is regular, but there are non-regular languages which are obviously subsets of it).


Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

Suppose:

$G$ is some graph with non-zero, positive weights.
The minimum spanning tree of $G$ is denoted by $MST$
$H_C$ is a hamiltonian cycle in $G$.
$H_P$ is a hamiltonian path in $G$, given by removing any one edge of $H_C$.

Since all the edges are positive and non-zero, we immediately get that:

$$w(H_C) > w(H_P)$$

Also, $H_P$ is a subgraph that includes all vertices of $G$ (and connects them), so $H_P$ in fact spans $G$.

Hence, by definition of minimum spanning tree:

$$w(H_P) \geq w(MST)$$

It follows that $$w(H_C) > w(H_P) \geq w(MST)$$

In case we allow zero weights, the inequality holds, it simply will not be strictly greater (for the same reasons noted in the answer). That is:
$$w(H_C) \geq w(H_P) \geq w(MST)$$


Unconstrained subset sum vs constrained subset sum?

If you have $n$ non-negative integers $x_1,\ldots,x_n$ in the range $0,\ldots,T$, then their susbets can sum up only to integers in the range $0,\ldots,nT$. This allows us to solve SUBSET-SUM efficiently in the constrained case. The idea is to use dynamic programming: for $m = 0,\ldots,n$, we determine which of the $nT+1$ potential sums are achieved by subsets of $x_1,\ldots,x_m$.
When $T$ is small, say polynomial in $n$, then this leads to a polynomial time algorithm. This is the constrained case. When $T$ is arbitrary, the corresponding algorithm is not efficient. This is the unconstrained case. The difference between the two cases is the number of potential sums – in the constrained case there are only polynomially many potential sums, in the unconstrained case there could be a lot more. In other words, you can use the dynamic programming algorithm in both cases, but the algorithm will only be efficient in the constrained case.
Let me also mention that the $O^*(2^n)$ algorithm in the unconstrained case can be dramatically improved upon using meet-in-the-middle, to $O^*(2^{n/2})$. A naive implementation of meet-in-the-middle uses a lot of memory, $\Theta^*(2^{n/2})$, but this can be improved to $O^*(2^{n/4})$ (the classic Schroeppel-Shamir algorithm).


Let's do the case $k = 2$. If the prices are $p_1 \geq p_2 \geq p_3 \geq p_4$ then there are three possible pairings $(p_1,p_2),(p_3,p_4);(p_1,p_3),(p_2,p_4);(p_1,p_4),(p_2,p_3)$ with cost $p_1+p_3;p_1+p_2;p_1+p_2$. So the first pairing is the best.

There are several ways to show that this pairing strategy is optimal in general. You might start by showing that given an arbitrary pairing in which $p_1$ is not matched with $p_2$, there is a way to modify it so that $p_1$ is matched with $p_2$, and the overall cost is lower. This leads to one proof.

Another idea is to show directly that the cost is always at least $p_1+p_3+\cdots$. For example, $p_1$ is always the largest in its pair, and $p_3$ is either the largest in its pair, or it is paired with $p_2>p_3$ or with $p_1>p_3$. You have to modify this argument so that you don't double count prices (for example, if $p_1$ is paired with $p_3$ and you follow the argument as stated, you will count $p_1$ twice).

There might be other ways to prove it, so if you have other ideas, by all means go ahead and try them out.


Algorithm for assigning people to groups

This problem is equivalent to Perfect Matching
We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want to find a set of edges that uses every vertex exactly once. This is the perfect matching problem.
To solve this problem, you can use any algorithm for finding a maximal matching, and check if the maximal matching has $n/2$ matches.


How to find a nearly-optimal covering of a set using SAT?

This problem is known as circuit minimization.  It falls within the broad area of logic synthesis.

The problem is known to be $\Sigma_2^P$-complete.  As a result, it is unlikely to be in NP (contrary to what you wrote).  And that means that it is unlikely to be solvable in polynomial time with queries to a SAT solver.  (NP is basically the class of problems you can solve with a SAT solver in a single query; $P^{NP}$ is the class of problems you can solve with an unlimited number of queries to a SAT solver; and $\Sigma_2^P$ is conjectured to be larger still, so a $\Sigma_2^P$-complete problem is conjectured not to be in NP or $P^{NP}$.)  There may still be heuristics that use a SAT solver along the way, but these heuristics either might make mistakes, might fail for some inputs, or might take exponentially long in some cases.

Anyway, there is a lot of literature on circuit minimization.  As far as I know, one standard approach is to use techniques built on Quine-McClusky, Espresso, etc.

You might be interested in approaches based on interpolation.  I believe those approaches use a SAT solver as a building block.


Complexity of covering subset of the monoid $(\{0,1\}^n, \text{OR})$

L. J. Stockmeyer proves that SET BASIS is $\mathrm{NP}$-complete.

Reference:
L.J. Stockmeyer, The set basis problem is $\mathrm{NP}$-complete, Tech. Report RC-5431, IBM, 1975

Each vector of your problem can be seen as subset of $\{1, 2, \dots, n\}$. And the component-wise OR operation is corresponding to set union. So a basis for a collection of Boolean vector in your problem is exactly a set basis.


Say the time spent is some constant factor $c$ times $n^2$. Then we have:

$$c \cdot 10^2 = 10$$
$$c = 0.1$$

Thus then $c\cdot 20^2 = 40$.


As Hendrik Jan mentioned, there are in fact different degrees of undecidability. For example, the problem of deciding whether a Turing machine stops on all inputs is harder than the halting problem, in the following sense: even given an oracle to the halting problem, we can't decide whether a given Turing machine stops on all inputs.

One important technique used to show relations like these is diagonalization. Using diagonalization, given a problem $P$ we can always find a harder problem, namely the halting problem for Turing machines with an access to a $P$ oracle. The new problem $P'$ is harder in the following sense: a Turing machine with an oracle access to $P$ cannot solve $P'$. In that sense there is no "hardest" problem.


How does literals in compiled languages differ from literals in interpreted languages?

A literal is a piece of data which gets its value at compile time.

I don't think that's a good definition of literals. A literal is a source-code token that represents a fixed value of some type. For example, in almost all programming languages, 23 is a literal representing the integer twenty-three. These aren't pieces of data that get their value at compile-time: rather, they are representations of the values themselves.  For example if, in Java, you write

static final int magic = 23;

then magic is a constant (a variable whose value cannot be changed) that is set at compile-time to have the value twenty-three, which is the meaning of the literal 23.

This is no different between compiled and interpreted languages.


Can a non-regular language $L$ have a non regular $L^*$?

Take the Dyck language $D$. It is context-free but not regular and satisfies $D^* = D$.


Generalized sorting algorithm on partially ordered set generated by a relation

You can efficiently test whether $\preceq$ extends to a partial order using topological sorting.  Form a directed graph with vertex set $X$ and with an edge $x \to y$ whenever we have $x \preceq y$ and $x \ne y$.  Then $\preceq$ extends to a partial order if and only if this graph has no cycles, which can be checked in linear time (e.g., by topologically sorting the graph).

Moreover, we can describe a minimal partial order $\le$ that is consistent with $\preceq$, as follows.  Compute the transitive closure of this graph. Now declare $x \le y$ iff there's an edge $x \to y$ in the transitive closure, or $x=y$.  (Equivalently, declare $x \le y$ iff $y$ is reachable from $x$ in zero or more steps, in the graph derived from $\preceq$.)  By construction, the relation $\le$ defined in this way will automatically be reflexive and transitive; if the original graph has no cycles, then it is easy to prove that the relation $\le$ will be anti-symmetric as well and thus will be a partial order.


Difficulty in understanding an approach to SPOJ $d$-query problem

(This answer is no longer very interesting, now that the question has been corrected to clarify that $1 \le a_i \le 10^6$ instead of $1 \le a_i \le 106$.)

This can be solved in $10^6(n+q)$ operations.

First, build a table $T[\cdot,\cdot]$, where $T[j,x]$ is the index of the last occurrence of the number $x$ among $a_1,a_2,\dots,a_j$.  In other words,

$$T[j,x] = \max \{i : a_i=x \wedge 1\le i\le j\}.$$

This table can be built in $10^6n$ steps.

Next, you should be able to see how to answer a query $(i,j)$ quickly, by doing some lookups into the $T$ table.  I'll let you work out the details so you can have the fun of solving the problem.


what's the meaning of LOC(X[j]) = $L_0$ + cj in TAOCP's 5.4.1R?

The key observation may be each array element of X (regrettably called node by DEK, just as the nodes of fig. 63) representing one internal (round) and one external (rectangular) node of figure 63 with no discernible relation.
1&2) Don't think so, for this formula it should suffice to take LOC(X(j)) as the location in MIX's linear memory of (the first word of) the jth element of array X of records of c words each (see 2nd paragraph above), a natural number from 0 to 3999. (Then, there is en.wikipedia.org/wiki/MIX)
3) yes, $cj$ is consise for $c * j$
4) $L_0$ seems to be the location of the first word of all the consecutive words representing Algoritm R's data structure
5) Those LOC()-expressions denote the locations of X's elements 9, 8, and 2, resp.
6) no relation I can see: $17$ happens to be $5 + P = 5 + 12$, the parent (external, PE) of which is (internal) node 8, coincidentally represented by the same element as (external) node 20, parent (internal, PI, used to be FI(/FE) in 1st ed.) of node 5 is 2, $14 = 2 + P$ happens to share the same element of X.


Generating graphs such as found on Sedgewick's Algorithms book on the MST chapters

It appears to be a random geometric graph. Points are placed at random within an area, according to some distribution, and an edge is added between every pair of points whose distance is less than some threshold.

A common case is to distribute the points uniformly at random within the unit square and add edges between all pairs of vertices that are at distance at most $d$ from each other, for some constant $d$. In other cases, the threshold might depend on the number of vertices.


Interpolation: How to generate 3D objects from 2D cross-sections?

A neural network is not a good choice for this.  For this task, you can get a much better solution by analytically solving for the unknown radius of the sphere.  In particular, if the radius of the sphere is $s$, then a slice at height $z$ will have radius $r$, where these three variables satisfy the equation

$$(s-z)^2 + r^2 = s^2.$$

Re-arranging, we find

$$s = {z^2 + r^2 \over 2z}.$$

So, you can solve immediately for the radius of the sphere.  Once you know the radius of the sphere, you can predict the radius of other slices at any height of your choice, using the above equations a second time.

You could certainly train a neural network to interpolate, given enough training data.  For instance, the input to the neural network might be 6 images: the three slices "above" z, and the three "below", and the output is a bunch of slices interpolated between the one above z and the one below; where each image is a picture of the slice.  However I'm not sure how well this will work, and it will likely require a lot of training data to have any chance whatsoever of being useful, so you might do better to look for some other solution.


Enumerating the set of polynomial time Turing machines

The halting problem reduces to $\overline{L}$: given a machine $T$, create a new machine that on input $n$ simulates $T$ for $n$ steps, and if $T$ halts then it enters an infinite loop. (I leave you the details.)

Since the halting problem is complete for $\mathsf{RE}$, it cannot be the case that $\overline{L} \in \mathsf{coRE}$, and so it cannot be the case that $L \in \mathsf{RE}$.


Interactive programming language minimizing reevaluations

The specific CS topic resolving the question is:
Incremental computing
A detailed article explaining a related DSL is:
IceDust: Incremental and Eventual Computation of Derived Values in Persistent Object Graphs


Using Induction to prove that $n^3log^4n=O(n^4)$

You showed that f (n) = o (g (n)). That's it. There is nothing else to prove.

If you look at the definition of o (f (n)) and O (f (n)), they are almost identical except one says "for every eps > 0" and the other says "there is one c > 0". You can take every single eps of the little-o definition and use it as the c in the big-O definition.


Here's an efficient solution based on BDDs

Find $n$ such that $k,a,b < 2^n$. Create $n$ boolean variables, one for each position in an $n-bit$ number
Write out a boolean formula representing every number in that interval. For example, if $n=4$ (so that we are only considering possible inputs in $[0..15]$), then the interval $[2..4]$ can be written as $\neg x_0 \wedge ((x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_2))$ --  there is a $0$ in the $8$'s position, and either the next three bits read $100$, or the next two bits read $01$. Note that this is equivalent to partitioning the interval into subintervals aligned with powers of $2$.
Represent the boolean formula as a BDD
Similarly, write $[k..k]$ as a boolean formula. Use standard BDD algorithms to XOR the two BDDs.
Read the intervals out of the BDD. For example, if $n=5$, and we take the path in the BDD corresponding to setting $x_0=1,x_1=0,x_2=1$, and find that we have reached a true leaf (i.e.: a five-digit binary number that starts with 101 is in the set no matter what its lower two digits are), then the interval $[20..23]$ is in the set.

Depending on the application, you might want to leave the set as a BDD rather than reading it out back into intervals, as the BDD representation may be much more compact.

There is also a more elementary and direct solution. Note that XOR'ing by $k$ is equivalent to sequentially XOR'ing by each bit of $k$. Break $k$ into bits, and break $[a..b]$ into subintervals aligned with powers of two, and see what happens to each subinterval. You can work this out, and implement it efficiently using segtrees, but I expect that it will be equivalent to the BDD solution, which is faster and allows for the use of standard libraries.

Analysis

Analyzing BDDs is slightly tricky, but I'll have a go.

$[a..b]$ can be represented using at most $2\lceil\log(b-a)\rceil$ power-of-2-aligned subintervals. I'm not sure how to properly show it, but visualizing the resulting BDD, we see it will have a sort of "triskelion" structure, with size $O(\log(b-a))$.

Let $n=\max(a,b,k)$. XORing each subinterval by $k$ will preserve the subinterval, but may move it. Since each subinterval takes $O(\log n)$ space to represent  and there are $O(\log n)$ of them, this lets us bound the size of the resulting BDD as $O((\log n)^2)$. I believe this gives us a $O((\log n)^2)$ bound on the entire operation, but don't quote me on that -- the runtime is proportional to the size of the intermediate BDDs, and I'll have a bit more thinking to do to determine what happens there.


First, build an algorithm to solve the  following problem:

Given a threshold $t$ and a flow graph $G$, find the solution that maximizes $N_2$, subject to the requirement that $N_1 \ge t$.

That problem  can be solved using algorithms for minimum cost circulation, which is a generalization of max flow where we can also have lower bounds on certain edges.  (You'll set the cost of all edges out of the source to 1 and the cost of all other edges to 0, as you don't need different costs.)

Then, do binary search on $t$ to find the largest $t$ for which a solution exists.

How do you solve the problem above?  We need to modify the graph.  Instead of adding a single source vertex $s$, we'll add three vertices $s,s_1,s_2$.  Add an edge $s \to s_1$ with lower bound on capacity of $t$.  Add an edge $s \to s_2$ with lower bound 0.   Add edges $s_1 \to a_i$ for each $i$ where $p(a_i)=1$, and $s_2 \to a_i$ for each $i$ where $p(a_i)=2$.  All edges other than the $s \to s_1$ edge have lower bound on capacity of 0.  Now any valid flow for this problem that respects the lower bounds will satisfy $N_1 \ge t$.