Polynomial time algorithm for finding a maximal monotone subset

I stared at this a while now with $k=2$ and got nowhere.

Let's take on $k=2$. To avoid confusion with x and y coordinates, I'll call the vectors $a_i, b_i$ instead.
Lets define $D(i,j)=(a_j-a_i)^T(b_j-b_i) \ge 0$, and $R(i,j)$ to be the boolean relation which holds when $D(i,j)\ge0$.
For $k=1$, R was a total ordering, which is what let us find increasing subsequences. For $k=2$, it's not even a partial ordering, which makes me think any solution will not resemble the $k=1$ case.

Take $x_1,x_2,x_3=(0,0),(0,1),(1,0)$; $y_1, y_2, y_3=(0,0), (-6, 1), (-5,-5)$
$V(1,2)=1$; $V(2,3)=1$; $V(1,3)=-10$

I'd suggest checking if this can be reduced to the longest common subsequence problem (I suspect no, because of the lack of ordering) or to/from some form of linear programming.
To nitpick here, coordinates should really be taken from $\mathbb Z$ bounded by some reasonable (say, polynomial) function for CS problems, not "$\mathbb R$". I suspect you can show it's NP-complete otherwise, say by reduction to the longest common subsequence problem, but in some way that's not really related to whatever your real problem is. That said, I didn't succeed at actually doing so.


Determining minimum number of edges to remove in a bipartite graph so the maximum path length is 2

Figured out this is indeed NP-hard. This is equivalent to finding the maximum spanning star forest in a bipartite graph, which in turn is as hard as finding the minimum dominating set in a bipartite graph, which is NP-hard.


How to reduce constrained proofs to 0-1 IP

If your problem is truly in NP, the reduction follows immediately from the Cook-Levin theorem.  You described how to build a verifier for your problem.  The proof of the Cook-Levin theorem shows how to turn that into a 3SAT instance.  Basically, the variables of the 3SAT formulas are the intermediate states of the verifier, and the formula itself says that each pair of consecutive states are consistent and that the verifier ends up accepting.

I am not persuaded by your proof that it is in NP.  Your proof would be fine if $Y$ is provided on the input in unary, but not if it is provided in binary -- in the latter case, the length of the proof is exponential in the size of the input, so your proposed verifier doesn't run in polynomial time.  If the problem is not in NP, there is no (polynomial-time)  reduction to 3SAT.


Finding the number of distinct permutations of length N with n different symbols

The total number of (different) permutations of strings with $n_i$ characters of type $i$ is given by
$$\frac{(\sum_i n_i)!}{\prod_i n_i!}.$$
In other words, if the length of the string is $n=n_1 + n_2 +...$, you have
$\frac{n!}{n_1!n_2!n_3!\ldots}$ different permutations.
Note that the formula fits your simple case.

Why is this formula correct?

Because $n!$ is the number of permutations. But some permutations give the same string (e.g., aa rotated is still aa). Then we need to "remove" all the permutations that give the same string. For a given string, for each letter $i$, there are $n_i$ permutations that are identical to the string we started with. So (for each possible letter $i$) we divide by this number to get the final result.


How to use Type application Rule to get a desired type

You can look at this rule in two ways:

As a checking rule, it says that, to verify that $t_1 t_2$ has type $T_{12}$, we check that there exists some $T_{11}$ such that $t_1 : T_{11} \to T_{12}$, and we check that $t_2 : T_{11}$. If these checks hold, then the typing of the application must hold.

As an inference rule, it says that to infer the type of $t_1 t_2$,
we infer the type of $t_1$ and verify that it has the form $T_{11} \to T_{12}$ for some types $T_{11}, T_{12}$, infer the type for $t_2$ and check that it is equal to $T_{11}$. If these checks hold, then we return $T_{12}$ as the type of the application.

So for knowing what $T_{11}$ is, it depends on what you're doing. If you're doing checking, then usually it is a type that has already been given to you. If you're doing inference, then you infer the type of the function, and inspect that type to verify that it's an arrow type, and can be broken into its parts. $T_{11}$ is one of these parts you break it into.

There's nothing saying you need to get $T_{11}$ only from the function's type. You could alternately infer it from the type of the argument, and then verify that it matched the function type.


If you can solve it with one tape, you can solve it with multiple tapes by just ignoring all but the first tape.

The other direction is covered by Universal simulation of Turing machines.


Reducing directed hamiltonian cycle to graph coloring

Let $Q \in \sf{NP}$ and $Q' \in \sf{NP\text{-}hard}$. Then, by definition, $Q$ is (many-one) reducible to $Q'$ in polynomial time.

The exact chain of the reductions will depend on the $\sf{NP\text{-}hard}$ness proof of $Q'$. Typically, it is proven by a chain of reductions starting from $\mathrm{SAT}$ and ending with $Q'$ and then using the Cook-Levin theorem. So the chain of reductions will be a reduction from $Q$ to $\mathrm{SAT}$ followed by the chain of reductions from $\mathrm{SAT}$ to $Q'$.

There is usually a more direct reduction for specific problems (without using Cook-Levin), since it is usually easy to find a propositional formula directly expressing the required property (with no reference to TMs). For example, in the case of Directed Hamiltionian Path ($\mathrm{DHP}$) and Graph Coloring ($\mathrm{GC}$), you can reduce:

$\mathrm{DHP}$ to $\mathrm{SAT}$,
$\mathrm{SAT}$ to $\mathrm{3SAT}$,
$\mathrm{3SAT}$ to $\mathrm{GC}$.


Can lambda-calculus be used for knowledge representation?

The λ-calculus was invented to be a logic and foundation of  mathematics (1-4). The most well-known logic to use λ-calculus for formulae (as opposed to proofs in the Curry-Howard approach) is HOL (= Higher-Order Logic). The most well-developed implementation of HOL is Isabelle/HOL (5). To the extent that you believe logic can represent knowledge, you can use HOL to do that, hence λ-calculus.

There is a third approach to using λ-calculus as logic: higher-order Prolog (aka λProlog) (6), which -- like Prolog -- is based proof search, but in HOL.

The relationship between the three approaches (HOL, Curry-Howard and λProlog) is not well-understood.

1. A. Church, A Formulation of the Simple Theory of Types.

2. P. B. Andrews, Churchs Type Theory.

3. F. Cardone, J. R. Hindley, History of Lambda-calculus and Combinatory Logic.

4. J. B. Rosser, Highlights of the history of the lambda-calculus.

5. T. Nipkow L. C. Paulson, M. Wenzel, A Proof Assistant for Higher-Order Logic.

6. D. Miller, G. Nadathur, P. Pfenning, A. Scedrov, Uniform Proofs As A Foundation For Logic Programming.


Let's see what the algorithm does in its first few iterations:

Mark all elements other than 1 as "potentially prime".
Mark all multiples of 2, starting at 4, as "not prime".
Mark all multiples of 3, starting at 9, as "not prime".
Skip 4, since it is known to be not prime.
Mark all multiples of 5, starting at 25, as "not prime".
Skip 6, since it is known to be not prime.
Mark all multiples of 7, starting at 49, as "not prime".

So it continues, until the next element is already larger than $\sqrt{n}$.
Here is how we can describe the contents of the array:

All elements other than 1 are "potentially prime".
All elements not divisible by 2 are "potentially prime", except for 2.
All elements not divisible by 2,3 are "potentially prime", except for 2,3.
All elements not divisible by 2,3,4 (equivalently, by 2,3) are "potentially prime", except for 2,3.

And so on.
Hopefully this gives you some ideas on the loop invariant.


Constructing a sphere ($S^2$) in HoTT directly?

This was asked once on the HoTT-cafe list. The answer is "yes" and I composed a short video which explains exactly how this happens.


How does the cache / memory know where to return results of read requests to?

Every machine instruction encodes the source and destination registers and/or memory locations. For memory location, some temporary buffer (register) within the processor is used. If the memory location happened to be in the cache, the stage of pipeline which depends on the content of memory location, stalls for few cycles.
Also, there are buffer registers between every pipeline stage, that stores the input for next stage and output of previous stage. If the processor is superscalar, i.e., multiple instructions can be in flight at a certain point of time, then multiple copies of buffers are maintained. Since the instruction can be executed Out-of-Order on superscalar processors, buffers like ROB (re-order buffers) are maintained for every hardware (SMT) threads. Put simply, multiple register sets which are copies of processor register sets are maintained within a processor.
In other words, Control unit that control the instruction execution cycles, appropriately route the content of memory location to marked registers. Registers are either specified by instruction code or determined by control unit itself.


Compare two methods of random permutations

Your method of comparison is very easy to defeat. I assume that by "Hamming distance from the regular configuration" you mean the number of fixed points. Make a table of the number of permutations in $S_n$ having $k$ fixed points (this can be computed recursively), and fix a single permutation with $k$ fixed points for every $k$. This way you can sample a permutation in a ways that matches this particular statistic of random permutations, but probably performs rather differently compared to a truly random permutation.


Confusion in the solution to first readers-writers synchronization

But during the completion of the first reader, if there comes another reader (or multiple readers), then that (those) reader(s) will be given priority over the writer.

It's a bit more subtle. The second reader is not given priority. Rather, the reader is not blocked by the first reader. This means that if the first reader takes sufficiently long, then the second reader will eventually start reading, even if there is also a writer waiting to take the lock. It is possible however to have a sequence of events where:

A first reader is reading.
The first reader has finished its task and starts releasing the reader-writer lock. This is not an atomic operation: the first reader needs to perform several operations (decrement read_count, test it for zero, and call signal on rw_mutex), and these operations must look atomic from other processes' point of view so they are performed in a critical section, protected by mutex. Thus “starts releasing the reader-writer lock” means “takes mutex”.
A second reader enters the system and starts working on acquiring the reader-writer lock, but it has not yet finished acquiring the reader-writer lock. The second reader waits on mutex, which is currently held by the first reader.
A writer enters the system and starts working on acquiring the reader-writer lock: it waits on rw_mutex.
The first reader is releasing the reader-writer lock, and it signals rw_mutex, allowing the writer to take it.

This sequence of events is what is going on in the scenario you describe: the second reader is waiting at line 01, and the first reader goes through line 03 then line 04.

In typical operation, this scenario will not occur often, because it depends on the second reader starting to wait on mutex while the first reader holds it. Given that the first reader only keeps that semaphore for a very short time, this scheduling is unlikely: most of the time, mutex is not held.

If the second reader arrives (i.e. calls wait(mutex)) before the first reader enters the critical section to release the reader-writer lock, then the second reader can start reading while the first reader is still reading, and the writer only gets the reader-writer lock once the second reader has finished. If the second reader arrives after the first reader exits that critical section, then it is clear that the already-waiting writer will grab the lock first. It's only if the second reader arrives during the first reader's critical section that there is this possibility of inversion where the writer arrives after the second reader, while the first reader is still in the critical section, and then the writer wins the race.

This kind of rarely-occurring scenario is an illustration of why concurrency is difficult. It's rare, but you still need to make sure your algorithm works in this case, because when it does occur, if your algorithm is buggy, it can bring your system down in a way that's hard to identify and fix. Here, this scenario specifically illustrates the need for mutex: without it, the second reader and the writer could both take the reader-writer lock.

In situations with low contention (i.e. it's rare that multiple processes want the same lock at the same time), as long as your algorithm is correct, the fact that the writer sneaks past the second reader is irrelevant. In situations with high contention, this kind of inversion can lead to starvation, and sometimes more sophisticated algorithm ensuring some kind of fairness property are needed.


Can someone explain why the MAX-CUT problem is in NP?

The certificate is a coloring of the vertices into red and blue (i.e., a partition into two sets). Given such a certificate, you can iterate through all the edges and count the number of edges whose endpoints have different colors. This count you can compare against $k$ and answer accordingly YES or NO.


Instruction Set Architecture (ISA) design

Hint: If there are $X$ of some resource, then it takes $\log_2 X$ bits to encode which of them you chooses. This includes instructions, registers, and memory locations. If you are encoding $N$ copies of the resource, you will need $N\log_2 X$ bits. The instruction should contain an encoding of everything needed to specify it, including the instruction itself.

(Real life CPUs don't quite behave this way. For example, common instructions could have shorter length.)

Example: A computer has $956$ instructions. The instruction NOP takes $\lceil \log_2  956 \rceil = 10$ bits.

Another example: A computer has $13$, and $100$ I/O ports. The instruction IN , which reads a byte from the port into the accumulator, takes $\lceil \log_2 13 \rceil + \lceil \log_2 100 \rceil = 11$ bits.

Yet another example: A (useless) computer has a single instruction but $10000$ registers. The single instruction takes $10$ of them and does something really complicated. It takes $\lceil \log_2 1 \rceil + 10 \lceil \log_2 10000 \rceil = 140$ bits to encode.


Approximation algorithms for Euclidean Traveling Salesman

Euclidean TSP is not even known to be in $NP$, basically because it seems that even to verify if there is a hamiltonian cycle of length at most $k$, we need to computing the sum of square roots. But the problem "$\sum_{i}\sqrt{a_i}<k?$" is not known to be in $NP$.

Anyway Euclidean TSP has $PTAS$.


string concatenation vs language concatenation

C is a regular expression over $\Sigma\{a,b\}$. We can design a finite automaton that can accept the language which can be generated from C. On the other hand, the language D is not regular. Using pumping lemma for regular language it can be proved that D is not regular. Hope this will help you. If you need more explanation then please feel free to ask.


Examples of difference between Hidden Markov Model and Bayesian Network?

A Hidden Markov Model can be expressed as an instance of a Bayesian network of a particular form.  Consequently, a HMM can be viewed as an special case or kind of Bayesian network.  Bayesian networks are more general, and can express other kinds of probabilistic structures as well.  All HMM's are Bayesian networks, but not all Bayesian networks are HMMs.


If set $C$ is recursively enumerable and $B$ is Recursive, and if $B-C$ is recursively enumerable then is $C$ recursive or not?

The argument is wrong.

Your argument is: $B\cap \bar C$ is r.e., $B$ is recursive, so $\bar C$ has to be non recursive, otherwise $B \cap \bar C$ would be recursive -- contradiction.

However, there is no contradiction: $B\cap \bar C$ can be both r.e. and recursive. This is equivalent to $B\cap \bar C$ being recursive. There is no hypothesis contradicting that.

Indeed, take $C$ to be the halting problem (r.e., and not recursive). Take $B=\emptyset$ which is recursive. Then $B\cap\bar C = \emptyset$ which is (recursive and) r.e. . So all the hypotheses are satisfied, but $C$ is not recursive.


Can the end-to-end principle be formalized?

I believe there may be two shortcomings in your application of the end-to-end (e2e) principle:

Firstly, in the sense that you apply it for performance. The end-to-end is a design principle such as to ensure architecture orthogonality, composability, regularity, one or all, provide primitives etc. Such principles have been outlined in related textbooks. Performance is not one of them. In fact, Clark et al, implies that strict end-to-end may result in worse performance so it uses such, as an exception to this principle.

So, if you still want to formalize:

"The end-to-end argument appeals to application requirements, and provides a rationale for moving function upward in a layered system" so you will need formalized application requirements and formalized layered system. Here is an attempt that might help taking it one step further:

Say you have Layer(i) requirements (Layer(0) is for the set of applications you expect to support now or in the future, the application layer) and
firm interfaces Interface(i,i+1) and Interface(i+1,i) (from Layer i to i+1 pre-assume no cross-layering here, easy to change and make it a requirement) and
functions Function(i,j) (Layer i, Function index j, assume data part of function to have it simpler)

Input: Layer(0) requirements (as we said these need to be formalized)

Output: everything else

END-TO-END Output is an Output such that:
For each L, Layer(L) accomplishes its requirements only by functions Function(L,j) (i.e. functions within the layer) and Interface(L,L+1), Interface(L+1,L)

For each Layer L and function Function(L,F) there is no set of Functions S in the output such that Function(L,F)=S (= means equivalent output and side-effects)

So, coming to the second possible shortcoming for the specific e2e principle application (and if I am reading correctly what is being attempted) one can claim that it does not follow the e2e principle at all, quite the contrary. You have your chips provide "some deadlock avoidance" and you have an Interface that is out-of-the-ordinary non-firm and specific to trigger (interrupt) more help from upper layers. This is arguably a cross-layer approach not an end-to-end approach. In other words you have a Function(1,x) not accomplishing its task completely and correctly with set Interfaces - if you want to use the draft formalization provided above (which of course is just a start useful to an extend to fully answer your question but likely not full in itself).


Both BFS and DFS are algorithms for exploring a single connected component, and there are also several others. All such algorithms can be extended to explore all connected components in a graph.


Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither

Let
$$ P = \{ww^{R} : w\in \{a, b\}^{*} \} $$
$$R_a=\{u\in \{a, b\}^{*} : |u|_{a}\equiv 0\ (\text{mod}13)  \} $$
$$R_b=\{u\in \{a, b\}^{*} : |u|_{b}\equiv 0\ (\text{mod}13)  \} $$

We know $P$ is context-free.

We know $R_a$ is regular and $R_b$ is regular. So $R_a\cap R_b$ is regular.

So, $L=P\cap (R_a\cap R_b)$ is context-free.

Exercise 1. (One minute or less) Verify that $L=P\cap (R_a\cap R_b)$.

Exercise 2. Show that $R_a$ is regular.


Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

Suppose that $w$ is in the language. We can write $w$ as a concatenation of runs:
$$
w = a^{i_1} b^{j_1} a^{i_2} b^{j_2} \dots a^{i_m} b^{j_m},
$$
where all indices other than possibly $i_1,j_m$ are strictly positive.
A word of this form belongs to $(a^nb^n)^m$ if all indices are equal. Since $w$ is in the language, there must exist two indices which are different. There are several cases to consider:

$w = \epsilon$.
$i_1 = 0$ and $w \neq \epsilon$. In other words, $w$ starts with $b$.
$j_m = 0$ and $w \neq \epsilon$. In other words, $w$ ends with $a$.
$i_s \neq i_t$ for some $s < t$. The word is thus of the general form
$$ (a+b)^*ba^xb^+(a^+b^+)^*a^yb(a+b)^*, $$
where $x \neq y$.
$j_s \neq j_t$ for some $s < t$. This is similar to the preceding case.
$i_s \neq j_t$ for some $s \leq t$. The word is thus of the general form
$$ (a+b)^*ba^x(b^+a^+)^*b^ya(a+b)^*, $$
where $x \neq y$.
$j_s \neq i_t$ for some $s < t$. This is similar to the preceding case.

Starting with a context-free grammar for $\{a^xb^y : x \neq y \}$ (a standard exercise – separate into cases $x<y$ and $x>y$), you can create a grammar covering all the cases above.


Redistributing a set of uniformly distributed numbers to an arbitrarily defined shape

Here is a simple algorithm. Suppose that the shape is given by a sequence
$$ (x_0,y_0), \ldots, (x_n,y_n). $$
Define $A_i = (x_i - x_{i-1}) \cdot (y_{i-1} + y_i)$ for $1 \leq i \leq n$, and let $A = \sum_{i=1}^n A_i$, $\alpha_i = A_i/A$, and $\beta_i = \sum_{j=1}^i \alpha_i$.

  Sample a value $x$ uniformly on $[0,1]$, and determine $1 \leq i \leq n$ such that $\beta_{i-1} \leq x < \beta_i$. Let $c = (x-\beta_{i-1})/(\beta_i-\beta_{i-1})$.

Note that $c$ is uniform on $[0,1]$.

Here is what we have accomplished so far:

The probability of obtaining a specific $i$ is proportional to the probability that a random point generated according to the desired density lies between $x_{i-1}$ and $x_i$.

This is because the area below the density curve between $x_{i-1}$ and $x_i$ is $(x_i - x_{i-1}) \frac{y_{i-1}+y_i}{2}$.

Consider now the function
$$
\begin{align*}
\varphi_i(t) &= \int_{x_{i-1}}^t y_{i-1} + (y_i-y_{i-1}) \frac{t-x_{i-1}}{x_i-x_{i-1}}  \, dt \\ &=
y_{i-1} (t-x_{i-1}) + (y_i - y_{i-1})\frac{(t-x_{i-1})^2}{2(x_i-x_{i-1})}
\end{align*}
$$
and its normalized cousin
$$
F_i(t) = \frac{\varphi_i(t)}{\varphi_i(x_i)} =
\frac{2y_{i-1}}{y_{i-1}+y_i} \frac{t-x_{i-1}}{x_i-x_{i-1}} + \frac{y_i-y_{i-1}}{y_i+y_{i+1}} \left(\frac{t-x_{i-1}}{x_i-x_{i-1}}\right)^2,
$$
which is the CDF of your density function restricted to the interval $[x_{i-1},x_i]$.

  Output $F_i^{-1}(c)$.

Since $c \sim U(0,1)$, the resulting element has CDF $F_i$, and so has the correct distribution. It remains to explicitly invert $F_i$. Let $a = \frac{y_i-y_{i-1}}{y_i+y_{i-1}}$, $b = \frac{2y_{i-1}}{y_i+y_{i-1}}$, and $s = \frac{t-x_{i-1}}{x_i-x_{i-1}}$ (note that $0 \leq s \leq 1$). If $F(t) = c$ then $as^2 + bs = c$, and so we can calculate the output $t$ as
$$
s = \frac{-b + \sqrt{b^2+4ac}}{2a}, \qquad
t = x_{i-1} + (x_i - x_{i-1}) s.
$$
The formula for $s$ simplifies to
$$
s = \frac{\sqrt{(1-c) y_{i-1}^2 + c y_i^2} - y_{i-1}}{y_i-y_{i-1}}.
$$
We can thus rephrase the second step as

  Output
  $$ x_{i-1} + (x_i - x_{i-1}) \frac{\sqrt{(1-c) y_{i-1}^2 + c y_i^2} - y_{i-1}}{y_i-y_{i-1}}. $$

Another option for the second step is rejection sampling. Let $A$ be the area below the rectangle bounded by $(x_{i-1},0),(x_{i-1},y_{i-1}),(x_i,y_i),(x_i,0)$, and let $R$ be the upper bounding rectangle $(x_{i-1},0),(x_{i-1},y),(x_i,y),(x_i,0)$, where $y = \max(y_{i-1},y_i)$. Generate random points $(x,y)$ in $R$ repeatedly until one of them belongs to $A$, and output its ordinate $x$. Since the area of $A$ is at least half the area of $R$, on average this requires at most two samples.

In the first step you have to determine $i$ such that $\beta_{i-1} \leq x < \beta_i$. While a naive implementation would take time $O(n)$, or $O(\log n)$ using binary search trees, you can use the alias method to reduce sampling time to $O(1)$.


Can any NP-Complete Problem be solved using at most polynomial space (but while using exponential time?)

Generally speaking, the following is true for any algorithm:

Suppose $A$ is an algorithm that runs in $f(n)$ time. Then $A$ could not take more than $f(n)$ space, since writing $f(n)$ bits requires $f(n)$ time.
Suppose $A$ is an algorithm that requires $f(n)$ space. Then in $2^{f(n)}$ time, $A$ can visit each of its different states, therefore can gain nothing by running more than $2^{f(n)}$ time.

It follows that:

  $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$

The statemement is known as part of the relations between the classes, as depicted by the following diagram:

The explanation is simple: a problem $Q$ $\in$ $\mathbf{NP}$ has a polynomial length certificate $y$. An algorithm that tests all possible certificates is an algorithm that decides $Q$ in time $\large 2^{n^{O(1)}}$.

Its space requirement is:

$y$ (polynomial in $n$)
space required to verify $y$. Since $y$ is a polynomial certificate, it can be verified in polynomial time, hence cannot possibly require more than polynomial space.

Since the sum of two polynomials is also a polynomial, $Q$ can be decided with polynomial space.

Example:

Suppose $\varphi$ is an instance of 3-CNF on literals $x_1 \dots x_n$, with $m$ clauses. An assignment $f$ is some function $f:\{x_1\dots x_n\} \rightarrow \{0,1\}$.

It holds that:

There are $2^n$ different assignments.
Given an assignment $f$, it takes $O(m)$ time to calculate the value of $\varphi$, therefore it cannot require more than $O(m)$ space.

So an algorithm $A$ that checks all possible assignments will use polynomial space, run in exponential time and decide 3-SAT.

It follows that:

3-SAT $\in \mathbf{PSPACE}$, and since 3-SAT is NP-Complete, $\mathbf{NP}$ $\subseteq \mathbf{PSPACE}$


Construct a grammar for $\{a^n(bc)^m : m,n \ge 1, m < n/2\}$

Let $n = n'+1$, $m = m'+1$. Then $m < n/2$ translates to $n'+ 1 > 2(m+1)$, i.e. $n' \geq 2m'+2$. Therefore we can write the language as
$$
\{ a^{1+2m'+2+k}(bc)^{1+m'} : m',k \geq 0 \} =
\{ a^3 a^k (a^2)^{m'} (bc)^{m'} bc : m',k \geq 0 \}.
$$
You take it from here.


If your constraints can be described using a small DFA, then you can use sampling-by-counting, which works in the following way. For each $\sigma \in \Sigma$, count the number of legal strings starting with $\sigma$ (as explained below), and use this to sample the first character, say $\sigma_1$. Then, count the number of legal strings starting with $\sigma_1 \sigma$ for all $\sigma \in \Sigma$, and use this to sample the second character; and so on.

It remains to explain how to count the number of strings of length $n$ with prefix $x$ accepted by a given DFA. Let me start with the case $x = \epsilon$. The idea is to use the transfer matrix method: construct a matrix $A$ in which $A(q_1,q_2)$ is the number of edges from $q_1$ to $q_2$ in the DFA (that is, the number of symbols $\sigma$ such that $\delta(q_1,\sigma) = q_2$). It is not hard to check that $A^n(q_1,q_2)$ is the number of words of length $n$ which carry the DFA from $q_1$ to $q_2$. Taking $q_1$ as the initial states and summing over all final states for $q_2$, we obtain the number of words of length $n$ accepted by the DFA.

Given a prefix $x$, we do exactly the same, only counting words of length $n-|x|$ that are accepted by the DFA when started at state $\delta(q_0,x)$.

As a simple example, you can use this technique to sample a word of length $2n$ over $\{a,b\}$ having an equal number of $a$ and $b$. Although the corresponding infinite language isn't regular, you can construct a DFA for this language which has $O(n)$ states, making the above approach feasible. In this particular case there are also known closed formulas for the number of words of length $n$ with prefix $x$.

With some work, you can probably extend this approach to context-free grammars. One thing to try would be to extend the CYK algorithm so that it counts the number of words of given length with a given prefix.


Combinatorial optimization - is there a formal name for this problem?

I don't know the name of your problem, if there is one.

But, concerning the complexity: The decision-version of your problem seems to be strongly NP-complete.
You can easily reduce ExactCoverBy3Sets to it:

Given a ground set $X = \{1, \ldots, 3q\}$ and a set $\mathcal{C}$ of 3-element subsets $C_i$ of $X$. Is there a subcollection $\mathcal{C'} \subseteq \mathcal{C}$ of disjoint subsets that cover $X$ ?

Assume we have $3q$ services $1,\ldots,3q$, each with a price of $q+1$. Furthermore, for each $C_i$, we have a package of the corresponding three elements at a price of $1$. Now, given the list $1,\ldots,3q$ of services to order, there is a solution with cost at most $q$ if and only if there is a solution to the given instance of ExactCoverBy3Sets. Since there are no double orders and since  "You can only use a package if you can completely fill it with services", the sets are disjoint and cover the whole ground set $X$.

So, you won't succeed in finding a polynomial (exact) algorithm or an FPTAS. However, you can search for approximation algorithms for the above problem and/or the related problems SetPacking and MinimumCover (cf. Garey/Johnson, "Computers and Intractibility", Problems SP2, SP3 and SP5).


You should be careful with order of quantifiers. You are given a predicate
$$\exists x \exists y \forall z (z = x ∨ z = y)$$
which is read as
$$\text{ there is } x \text { such that there is } y \text { for all } z \dots $$
while you read it as
$$ \text { for all the values of }  z \text{ there exists } x \dots$$
which would correspond to
$$\forall z  \exists x \dots$$
When you change the order of quantifiers the meaning (and hence the truth value) of the sentence changes. For example consider the set of natural numbers excluding 0. Then
$$\forall x \exists y (x \text { divides } y)$$ is a true sentence since for any $x$ take $y=x$. But the sentence
$$\exists x \forall y (x \text { divides } y)$$
is false since $x$ does not divide $x+1$.

Now as for your question, yes $A=\{0, 1\}$ models this sentence. In fact you could also take a set consisting of a single element, for instance $\{0\}$ or $\{1\}$ (there is no condition such as $x\neq y$).


Assuming $f,g > 0$, we have
$$\max(f(x),g(x)) < f(x) + g(x) \leq 2\max(f(x),g(x)).$$
Therefore $\Theta(f(x) + g(x)) = \Theta(\max(f(x),g(x)))$, in the sense that both sets of functions are equal.

Still assuming that $f,g > 0$, it is also true that $\Omega(f(x)+g(x)) = \Omega(\min(f(x),g(x)))$, in the sense that if $h(x) \in \Omega(f(x)+g(x))$ then also $h(x) \in \Omega(\min(f(x),g(x))$. The stronger bound $\Omega(f(x)+g(x)) = \Omega(\max(f(x),g(x)))$ also holds.

I have mentioned two interpretations of equality. In fact the second one (which really corresponds to $\subseteq$ in this case) is actually the standard one – equality is not symmetric! However, in the case of big $\Theta$ both notions fortunately coincide.


Understanding Binary Search for Kth Smallest element in an Array

Let me start by recalling the question:

  Given an unsorted array of $n$ elements in the range $1,\ldots,m$, find the $k$th smallest element in $O(n\log m)$ time and $O(1)$ case.

Calling the array $A$, the idea is to perform binary search on the array $B$ of length $m$ in which $B[i]$ is the number of elements in $A$ which are at most $i$. If $B[i] \geq k$ but $B[i-1] < k$ (assuming $B[0] = 0$), then $i$ is the $k$th smallest element. We can find $i$ using binary search.

Instead of computing the array $B$ ahead of time, we have "oracle access" to it: we can compute any given entry in time $O(n)$ by going over the entire array $A$. This is the algorithm you link to.


Do polynomial reduction functions work both ways?

The statement

  Formula $F$ is satisfiable $\iff$ graph has an independent set

is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:

  There is a polynomial-time function $\mathcal{G}$ from formulas to graphs such that, for all formulas $F$, $F$ is satisfiable $\iff$ $\mathcal{G}(F)$ has an independent set

Note that, once properly written like this, the statement is no longer symmetric: the reduction function goes in one way (formulas to graphs), and not the other way around. So, proving the above does not also prove the converse reduction.

The converse reduction (from independent set to 3-SAT) holds, but to prove that we need another reduction function $\mathcal{F}(G)$ mapping graphs into formulas.


Starvation in longest remaining time first CPU scheduling

TLDR: Starvation is possible under some assumptions.

Without loss of generality let's assume that in tie situation of longest remaining time first (LRTF) algorithm we give CPU time to process with lowest ID.

Let's also assume that incoming processes IDs are always increasing.

Now let's consider two cases.

1) At some time there will be no new processess.

This is obvious because once new processess will stop arriving then eventually all processess will be executed, so no starvation.

2) New processess will never stop arriving.

Let's say that at time 0 all max time of process is $d$.
In other words:
$d=\max_{p\in\mathcal{P}}(t_p)$. Where $\mathcal{P}$ is set of processess and $t_i$ it remaining time of $i$'th process.

So now let's consider following scenario:

Adversary knows $d$ and that at time 0 there are $n$ processess, at each time unit adversary inserts new process with time $d+1$.

At time $1$ one of processess numbered $1...n$ (the one with time $d$) will consume one time unit. Then new process will arrive with time $d+1$ it will gain one time unit from scheduler. From now no of processess $1...n$ will gain CPU time, because all adversary processess will remain $d$ time units and newly arrived process will have prority over another.

There is on problem with this analysis. It assumes that there can be infinite number of processess in the system. In real operating systems this cannot be achieved.

Now let's assume that adversary doesn't know $d$. He might choose some constant $k>2$ and insert it's processess with that time. At some point in time which is equal to $\sum^{n}_{i=1}{\max(0, k-t_i)}$ adversary processess will starve all other procesess.


Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M)

From the NFA $N$ construction an equivalent context-free grammar $G$ using the standard construction for this, and then construct a PDA $M$ such that $L(M) = L(G)$. The standard construction will (given a suitable definition of the notion of pushdown automaton) give us an automaton with three states only.

The automaton will simulate the leftmost derivations of $G$, and its stack symbols include the set $V$ of nonterminals and the set $\Sigma$ of terminals as well as a bottom marker $\$$. Initially, $\$$ is placed on the stack together with $S$. The main loop of the automaton is that involving the state $q_2$: If a nonterminal $A$ appears as the topmost symbol on the stack and there is a production $A \rightarrow w$ in $G$, then $A$ is replaced by $w$ in reverse. If a terminal $a$ appears as the topmost symbol on the stack and the next input symbol to be read is also $a$, then the automaton proceeds. Finally, if all input characters have been read and the bottom marker is the only symbol on the stack, the computation succeeds.


01 Knapsack with selection of items with minimum total weight

Sure.  It's easy to take any algorithm to solve the ordinary knapsack problem, and apply it to your problem.  In the ordinary knapsack problem, we specify an upper bound on the weight.  Once we find the maximum value achievable with that weight, next we'll try to see if we can reduce its weight further.  Do this by solving a new version of the knapsack problem, the same as the original, except the maximum weight has been reduced.  See how far you can reduce the maximum weight while still achieving the same value.  You can use binary search for that.


LR(1) parsing, problem with look ahead symbols

Since $A\to .Ay$ is in the state constructed for $GOTO(0, x)$, $A\to .A(y)$ and $A\to .(y)$ are also in that state. These combine with the other items for the same productions, which have lookahead $z$.


Following comments by @EvilJS which restarted a bibliographic search, here is relevant material that improves upon the initial algorithm by Alvy Ray Smith, which I called "scanline" in the OP.

It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin & Barsky is the most theory-oriented resource.

Computer Graphics And Geometric Modelling : Implementation & Algorithms
Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. See 2.4 Fill Algorithms.
Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
Fishkin, Ken, “Filling a Region in a Frame Buffer,” in [Glas90], 278–284.
Heckbert, Paul S., “A Seed Fill Algorithm,” in [Glas90], 275–277.
[Glas90] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.


How to handle an undefined case with µ-recursive functions?

$\mu$-recursive functions are partial functions because of the minimization operator. Without minimization, you get primitive recursive functions, and they're total. So an undefined value can only arise because the minimization operator is involved somehow. For example, you can define
$$\mathrm{undef} := \mu(1)$$
where $1$ is the constant function (with arity $2$) whose value is $1$.

In general, to prove that a function is µ-recursive, you proceed as you would to prove that an object is a member of a class. You demonstrate that the object can be built according to the rules of that class, possibly using objects that other people have already proven to be members.


Using Trie Data Structure, you can solve this problem in $O(m + n)$ if we know that values are computer integers (e.g. all 32-bit or 64-bit values).

Let say we know that all integers in $A$ are 32-bit values. Use the following steps:

Create an empty trie. Every node of trie may contains at most two children
for 0 and 1 bits.
Insert all values in $A$ into the tree in $O(32 \times m) = O(m)$
For each value in $B$, traverse the tree from the leftmost bit. If a bit doesn't match with child of a middle node, continue the traverse using the existing child until you reach a leaf. Traversing finishes in $O(32 \times n) = O(n)$

Which in total, the complexity is $O(m + n)$.


You could have written a paper bases on your discovery had you been living many years ago.

In fact, the paper Terminal Context in Context-Sensitive Grammars by Ronald V. Book, 1972 mentioned by Yuval proved the following theorem, edited slightly for the sake of current question.

  Theorem 3. If $G$ is a context-sensitive grammar with terminals $\Sigma$, non-terminals $N$ such that every non-context-free rule is of the form $\alpha Z\beta \to \alpha\gamma \beta$ where $\alpha\in\Sigma^*$, $\beta\in\Sigma^*$ and $Z\in N$, then $L(G)$ is context-free.

The grammar in the theorem above is much more general than the grammar described in the question. In fact, if we restrict $\alpha$ to be empty and $\beta\in\Sigma$, we obtain the grammar described in the question.

You can check that article for a proof of the theorem as well as more insight into how to force context-sensitive grammars to be context-free. (You could probably write a paper if you solve the conjecture at the end of that paper.)

Here is one exercise that is within easy reach.

Exercise 1. If $G$ is a context-free grammar except one rule, which is of form $Aa\to Ba$, where $a$ is a terminal and $A$ and $B$ are two non-terminals, then $L(G)$ is context-free.


Which data structure to use to solve equations?

I assume that we are talking about polynomial equations here, because I want to base my answer on a Gröbner basis method. The example problem given in the question contains equations, inequalities, variables and parameters. We can replace inequalities $f(x_1,\ldots,x_n) \geq 0$ by equations with slack variables $f(x_1,\ldots,x_n) - e^2 = 0$. We can convert parameters $P$ into variables by adding equations enforcing their value $P-11 = 0$. We can convert equations $f(x_1,\ldots,x_n)=g(x_1,\ldots,x_n)$ to the form $f(x_1,\ldots,x_n)-g(x_1,\ldots,x_n) = 0$.

$\left\{
    \begin{array}{r}
      A - 30 = 0\\
      P - 11 = 0\\
      x - e_x^2 = 0\\
      y - e_y^2 = 0\\
      A - e_A^2 = 0\\
      P - e_P^2 = 0\\
 x*y - A = 0 \\
 2*x + 2*y - P = 0
    \end{array}
\right.$

Each equation can be represented as a list of its monomials and their coefficients.
A monomial $M$ is a product $M=x_1^{a_1}\cdots x_n^{a_n}$,  where the $a_i$ are nonnegative integers. The vector $[a_1, \ldots ,a_n]$ is called the exponent vector of $M$. A monomial can be represented by its exponent vector. This statement and the preceding description assumes that we have already fixed an enumeration of the variables. There are certainly more efficient ways to store a single equation, but these are just optimizations.

  Can arbitrary complex instances of this problem solved just with tree transformations ?

It depends a bit on what we consider to be a tree transformation, and whether we mean by solved just the symbolic precomputation, or the entire solution process. A Gröbner basis method is able to transform the intial system into a triangular form, with respect to any admissible monomial order. In our case, we will probably want to use an elimination order such that the parameters are smaller than all other monomials, and the slack variables are bigger than all other monomials. The example system will then be transformed to

$\left\{
    \begin{array}{r}
      e_x^2 - x = 0 \\
      e_y^2 - y = 0 \\
      e_A^2 - A = 0 \\
      e_P^2 - P = 0 \\
      x + y - \frac{1}{2}P = 0 \\
      y*y - \frac{1}{2}P*y + A = 0 \\
      A - 30 = 0 \\
      P - 11 = 0 \\
    \end{array}
\right.$

This would be the results of the preprocessing. We can now solve this system numerically by back substitution. So we set the parameters to $P=11$ and $A=30$, solve the quadratic equation for $y$, then get $x$ from the linear equation, and then check the positivity constraints for $P$, $A$, $y$ and $x$. There are two solutions for $y$, so we have to do part of this process twice.

The are only two operations used during the transformation. The first operation is to reduce a polynomial by other polynomials, that is $f$ is replaced by $f-\sum_{g\in G}q_gg$ where the $q_g$ are polynomials. (This should actually be a multivariate division with respect to a monomial order.) The other operation is to add the S-polynomial of two polynomials. The S-polynomial of two polynomials $f$ and $g$ with leading terms $l_f$ and $l_g$ (with respect to a monomial order) is given by $\frac{a}{l_f}f-\frac{a}{l_g}g$, where $a$ is the least common multiple of the leading terms $l_f$ and $l_g$. In a certain sense, one can really call these operations tree transformations, because we just transform polynomials into other polynomials.

One interesting lesson for myself here was that adding the inequalities and parameters didn't really affect the outcome of the Gröbner basis method. We had to choose an appropriate elimination order for the monomial order. However, there are well know fill-in reduction strategies, and any sufficiently complete strategy would have automatically chosen an appropriate order. (The equation system can be seen as a bipartite graph between the variables and the equations, where a variable is connected to an equation if it occurs in the equation. This bipartite graph already contains enough information to determine an appropriate elimination order such that any harm which could be caused by the inequalities and parameters is avoided.)

  Or do I need something more elaborate ?

One major problem is the order in which to apply the transformations. This already starts with the determination of an appropriate monomial order, but doesn't end there. Some of the methods developed for the direct solution of sparse linear systems can also be applied here. In addition, the reduction to an univariate polynomial of high degree is also a bit dangerous, from a numerical robustness point of view.


Finding the last substring in lexicographical order in O(n) time

Consider a string of 100 million characters with say 100 z’s in between plus a huge number of the characters a to y (and no character lexicographically after z). Find an algorithm that would often give you the correct result in O(n), actually with at most 2n comparisons. Find out why this algorithm doesn’t always run in O(n), then figure out what you can do about it to still run in O(n). For example, if you have a million repetitions of zabcdefabcdef.


Does $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ imply anything?

Yes, we have to admit so. For other normal complexity class $\mathcal{C}$,

either $\mathcal{C}\subseteq \mathrm{PSPACE}$ then we have an interactive protocol with the prover to be replaced by the circuit,

or $\mathcal{C} = \mathrm{EXP}$ in this case, we utilize Meyer's to put $\mathcal{C}$ in $\Sigma_2^p\cap \Pi_2^p \subseteq \mathrm{PSPACE}$ to get back to the previous case.

But in the case of $\mathrm{SUBEXP}$, nothing above applies.

Note that in Meyer's, we have to simulate the machine deciding $\mathrm{L}\in \mathcal{C}$. But as every particular machine $\mathrm{M}$ deciding $\mathrm{L}$ runs in exponential time ($\mathrm{L}$ has infinitely many machines with ever decreasing running time bounds), we cannot have a multi-output circuit for it.


Code isn't arranged randomly in memory. The next instruction to be executed will, by default, be the one at the next memory location, unless something specific (a "jump" instruction) is done to execute code from somewhere else.

So, if your program is literally "Do A, then B, then C, then D, then E", the compiler will place those instructions in consecutive memory cells. If, for some reason, they were in non-consecutive memory cells, the program would have to become something like "Do A, then jump to B's location, then do B, then jump to C's location, etc." The computer has no way of knowing that it's not supposed to execute the next instruction in memory, except being told to do that. And being told to do that requires the execution of some kind of instruction.


Ambiguity with the Top View of a binary tree

I think what they are trying to define is the following.

Given a rooted binary tree $T$, let $V(T)$ be the set of vertices of $T$. For $v \in V(G)$, let $P_v$ the unique path from the root of $T$ to $v$.
We will call an edge $(u,w) \in P_v$ a left edge if $w$ is the left child of $u$, and a right edge otherwise.

Let $\ell_v$ and $r_v$ be the number of left and right edges in $P_v$, respectively, and define $\delta(v) = \ell_v - r_v = 2\ell_v - |P_v|$.

Let $h(u)$ be the depth of vertex $u$ in $T$ and define $\Delta(v) = \{ \delta_u \, : u \in V(T) \wedge h(u) < h(v) \}$.
The top view of $T$ is the set $\{ v \in V(T) :  \delta_v \not\in \Delta(v)  \}$.

In your example the top view would be $\{1, 2, 12, 14, 15 \}$. In general, you can compute the top view in $O(|V(T)|)$ time thought a preorder DFS visit.

I have no idea why this is important, sorry.


Can we do everything in imperative languages with a functional language if it does not allow for a 'state'?

The key with functional programming is not that there is no state, it's that there is explicit state.

What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions.

For example, let's look at the Dynamic Programming method of calculating the Fibonacci numbers. In an imperative language, you'd have something like this:

def fib(n):
  A = {}
  A[0] = 0
  A[1] = 1
  for i in [2 .. n+1]:
      A[i] = A[i-1] + A[i-2]
  return A[n]

To do this without state, you just have to explicitly pass your store around. Using Haskell-ish syntax:

fib n = fibHelper 2 n {(1,1), (0,0)}

fibHelper i end cache =
  if
    i > end
  then
    lookup end cache
  else
    let
      newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
      newCache = insert i newVal cache
    in
      fibHelper (i+1) end newCache

Now, this is a bit contrived, since you don't need the whole array for the Fibonacci numbers, but you can imagine using this for more complicated dynamic programming problems like Knapsack, where you do need the entire set of previously computed values.

The key thing to understand here is that insert is a function which takes a store, and returns a new store, which is equal to the original with a new value added. The original value of cache doesn't get destroyed, so if you had an application where you needed some sort of "undo" operation, you could keep track of your state's history.

You might say "but that looks inefficient! You're creating a whole new store each time!" However, usually in functional languages, these things are implemented cleverly using references, so that there aren't whole new copies of the data lying around.

It's also worth mentioning that this pattern of having a state parameter, passing it around as your computation progresses, and modifying it, is very common. People have invented abstractions, like the State monad, which allow you to write things that look imperative, but which are purely functional "under the hood."


Unclear about proof for unique MST given graph G with distinct weights

The edge $e$ is not necessarily the cheapest edge of $G$ that is in $T$. Rather, it is the cheapest edge in the symmetric difference $T \triangle T'$. It could belong to either $T$ or $T'$ (but not both!), but since both cases are the same, we assume that it belongs to $T$ without loss of generality.

We don't need to separately consider the case that $T$ is disjoint from $T'$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.


Reachibility between first and last layer in grid graph in logspace

I can't post a comment, which would be more appropriate:

Reingold's result gives a logspace algorithm, but reachability on undirected grid graphs was show to be in $L$ by Blum and Kozen about 30 years prior:

M. Blum and D. Kozen. On the power of the compass (or,
why mazes are easier to search than graphs). In IEEE Symposium
on Foundations of Computer Science (FOCS), pages
132–142, 1978.


Famous hacker koan: who was it about, though?

Tom Knight

https://simple.m.wikipedia.org/wiki/Hacker_koan

The item titled "Enlightenment"

Thanks to reinierpost.


Ideal value of d in a d-ary heap for Dijkstra's algorithm

Please note that $ m \leq n(n-1)/2 $, thus $m/n < n/2$. So the example $m=3, n=1$ does not happen.

First, the article clearly claims that this improvement is achieved whenever $ m $ is larger than $ n $,

  By using a $d$-ary heap with $d = m/n$, ..., an improvement over the O(m
  log n) running time of binary heap versions of these algorithms
  whenever the number of edges is significantly larger than the number
  of vertices.

Secondly, the article claims that $d$ must create a balance between $m$ and $n$ in order to improve the running time,

  By using a $d$-ary heap with $d = m/n$, the total times for these
  two types of operations may be balanced against each other...

Generally, we need $n$ min-extract and $m$ decrease-key operations. In the case of $d=2$, each of these operations takes $O(\log n)$ time. However, when you increase $d$, the decrease-key operation becomes faster, but min-extract can become slower. Because, within each min-extract, we also need to run min-heapify that depends on the number of children of the parent in each level.

In the extreme case, if you consider $ d=n $ then $m \log_n n < m \log_{m/n} n$, but the running time won't be better in practice. Because you need at most $ n $ min-extract operations, each includes a min-heapify. Therefore, you need $ n $ min-heapify operations, that will cost $ O(n) $ in this case (because $d=n$ and there are $n$ numbers in the next level of your tree). Thus the running time of your algorithms becomes $O(n^2)$ ($n$ times running min-heapify).


Finding the minimum subset of intervals covering the whole set

Here's an $O(n\log n)$ algorithm, which is optimal in the algebraic decision tree model by an easy reduction from element distinctness (map each element $x$ to the interval $(x,x+\epsilon)$). We follow Kaveh's outline. Stage 1 runs in $O(n\log n)$ time, so we focus on Stage 2.

Let $I$ be the set of intervals in $C = (a,b)$. Define the intervals $l=(a,a+\epsilon)$ and $r=(b-\epsilon,b)$, and consider the interval graph over $I \cup \{l,r\}$ (two vertices are connected if the corresponding intervals intersect). I claim that every path from $l$ to $r$ corresponds to a cover of $C$, and vice versa.

First, consider a path $P$ from $l$ to $r$. Suppose that $P$ doesn't cover some point $x \in C$. We prove by induction that all the intervals in $P$ are to the left of $x$, which leads to a contradiction since $r$ is to the right of $x$. Clearly $l$ is to the left of $x$. Suppose some $p \in P$ is to the the left of $x$, and let $p'$ be the next interval on the path. If $p'$ were to the right of $x$, then since $p$ and $p'$ intersect, $x$ would have been covered. So $p'$ must also be to the left of $x$.

For the other direction, order the intervals in a cover of $C$ in increasing order of their starting point. If two consecutive intervals $(a,b),(c,d)$ do not intersect then the point $x = (b+c)/2$ is not covered. Similarly, the first interval must intersect $l$. While it is not generally true that the last interval must intersect $r$, one of the intervals must, and if we cut the cover short at the first such interval, then we obtain another cover of $C$ which also constitutes a path in the interval graph from $l$ to $r$.

We have reduced the problem of covering $C$ to finding the shortest path in an interval graph. This is solvable in time $O(n\log n)$ and space $O(n)$, as shown for example in An Optimal Algorithm for Shortest Paths on
Weighted Interval and Circular-Arc Graphs with
Applications by Atallah, Chen and Lee.


Turing machine state transition diagram vs finite state machine state transition diagram

Summary : you may still be able to tell them apart , but not necessarily
First refere to the formal definition to a Turing machine from Wikipedia
Now consider the transition function δ :

First , δ does not allow transitions from accepting states , so in a state diagram of a TM you expect some state to have no transitions from it , unlike a DFA where every state must have transitions out of it , other definitions of TMs allow transitions from final states , but have accept/reject states taking effect immediately , and so you don't expect these states to have transitions

δ is a partial function , thus you don't need to define a transition for each state and each symbol , unlike DFAs which require a transition from each on each symbol (refer to Wikipedia under complete and incomplete) , so in a DFA you have all states having equal number of transitions/arrows from them but not necessarily in a Turing machine

Arguments :

1 would be nullified if TM and DFA have no final states to begin with
2 can also be nullified should we choose to provide transition from all states on all symbols for a TM , or go for the less common alternative definition for the DFA in Wikipedia and then not all states need to have equal number of transitions


unambiguous grammar that produce equal number of a and b

The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).

To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to do that is to make sure you match the first $a$ (resp. $b$) after your $b$ (resp. $a$) that hasn't been matched yet.

So you'd get something like $$
S\to aB S\mid bA S \mid \varepsilon\\
A \to a \mid b \square\\
B\to b \mid a\square$$

The idea is the following:

You want $S$ to generate words with as many $a$ as $b$s. At any points you can stop with the $S\to \varepsilon$. If you do add an $a$ with $S\to aBS$, then you need to add a $b$ later, and you put a $B$ to remind you of that, and then you continue with another $S$. The same things applies for $S\to bAS$.
If you have an $A$, it means that you are one $a$ short. If you read an $a$, everything is fine and you've got nothing else to do. But if you read a $b$, you are now two $a$s short. I left a $\square$ for you to fill to encode that.
$B$ works like $A$.

Solution :

   You are two $a$s short so you are twice one $a$ short: $A \to a \mid b AA$. Similarly $B\to b\mid aBB$

For the proof, see this where $a,b,A,B$ are replaced with $0,1,O,I$ and your language is generated by $E$.


Prove L = {a = b ⊕ c | a, b, c ∈{0, 1}*} is not regular

Suppose $L$ were regular. Let $p$ be the pumping constant assumed to exist and consider the string

$$s = 1^p = 1^p \oplus 0^p$$

Clearly, $|s| \geq p$ so for some strings $x,y,z$ we have $s = xyz$ where

$|xy| \leq p$
$|y| > 0$
$xy^iz \in L$ for all $i \geq 0$

If condition 1 is to hold, $y$ must be a string of $1$s. If condition 2 is to also hold, then $y = 1^k$ for some $k > 0$. But then condition 3 fails, since $xy^0z \notin L$.

For $xy^0z =  1^{p-k} = 1^p \oplus 0^k$, and this identity is false irrespective of whether we require $w_1 \oplus w_2$ to be defined for strings of the same length only, or in general.


Select fixed-size connected induced subgraphs in a graph

The problem is unfortunately NP-hard.
Thanks to Dmitry for finding this:
https://www.sciencedirect.com/science/article/pii/0166218X85900083.


NL and NP compute different binary relations, so what?

We know that $NL \subseteq NP$, but that $NL \subsetneq NP$ is not known. So one cannot outright say that $NL$ and $NP$ are different.

We only know for sure $NL \subsetneq PSPACE \subsetneq EXPSPACE$ by space hierarchy theorem. And $P \subsetneq EXPTIME$,and $NP \subseteq NEXPTIME$ by time hierarchy theorem.

We only know for sure is
$$L\subseteq NL \subseteq P \subseteq NP \subseteq PH \subseteq PSPACE =NPSAPCE \subseteq EXPTIME \subseteq NEXPTIME\subseteq EXPSPACE$$

Only above four inclusions are known to be strict. All the other inclusions are unknown and open problems. (Though most but not all have unproven belief that each of them is strict).

See https://en.wikipedia.org/wiki/PSPACE#Relation_among_other_classes.

Also, I think, we might be able to prove that there exists a language $B$ for which $NL^B \neq NP^B$. Probably $U_B$ and $B$ of Baker, Gill and Soloway will work here too. And we are also able to show that $NL^A = NP^A$ for $A = TQBF$, the $PSPACE$ complete problem to decide the true quantified Boolean formulas.


Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$

Once we've fixed the alphabet, the complement is simply the set of all strings over that alphabet that don't have the form $a^nb^{n+1}$. Presumably, here, the alphabet is $\{a,b\}$.  Again, once the alphabet is fixed, there is only one complement.  You've given two and it's unclear whether you mean "I'm not sure which of these answers is right" or "It's the set of all strings that are either like this or like that."

In fact, neither of your two answers is correct. The complement also includes the string $abbb$, even though it has more $b$s than $a$s.


Linear programming maximizes the minimum distance problem

Let's first define some variables.

$$x_i \in \{0, 1\}$$
$$w_i \in \mathbb{Z}^+$$

Where $x_i=1\iff $ location $i$ is selected and $w_i$ equals the minimum distance from node $i$ to any selected city if $x_i=1$ and $\infty$ otherwise. We will use $D$ to represent $\infty$ and in practice $D$ can just be the diameter of the graph. We can constrain these variables below.

$$
\begin{align}
\sum_{i=1}^nx_i &= k\\
w_i & \leq \texttt{distance}(i,j) + D(2 - x_i - x_j)& \forall j\neq i
\end{align}$$

It remains to find the minimum across all $w_i$. We will let this minimum be $y$. We constrain $y$ as follows
$$y \leq w_i \;\; \forall i$$

Now the objective function is clear, we want to find the largest $y$ that satisfies our constraints
$$\text{maximize }{y}$$

Our first constraint verifies that we select $k$ locations. The second gives us the minimum distance from a selected point to any other selected point. The third ensures that we find the minimum across these distances. Unfortunately, this is not a linear program but a mixed integer program.


Trying to verify the solution to a lambda calculus equation

On trying to verify this I first evaluated the L.H.S to be

  $ GX $ = $ Y ( \lambda gx.gg ) $ $X$.

  Now $X$ being the argument will be picked up by the first bound
  variable  so .

  $L.H.S $ = $ Y ( \lambda x . XX) $

This is where you went wrong, and the reason is that you've got the association the wrong way round. $Y ( \lambda gx.gg ) X$ means $(Y ( \lambda gx.gg )) X$.

Taking that into account, the only evaluation step possible is to apply $Y$, giving $$( \lambda gx.gg )(Y ( \lambda gx.gg )) X$$ which is $( \lambda gx.gg )GX$, from which the desired conclusion is immediate.


regular expression to accept all strings other than one containing ads or adlib

Let $[$^$x]$, $[$^$xy]$ be short cuts for $\Sigma - \{x\}$, $\Sigma - \{x, y\}$ etc., i.e., $[$^$a]$ will be regular expression: $(b+c+d+\dots)$.

Then the regular expresseion for words not containing ads or adlib would be

$[$^$a]^*(a[$^$d][$^$a]^*+ad([$^$sl][$^$a]^* $ $+ adl[$^$i][$^$a]^* + adli[$^$b][$^$a]^*)^* (\epsilon + a +ad + adl + adli)$.

Basically we wait for an $a$ and then check it is not followed by the disallowed combinations.

Since regular expressions have built in operators for union, kleene and concatenation only, we will always have trouble with intersection, complement and minus operations. Basically the operation you want in your question is the complement.


Introduce a new node $s_0$ with edges to all $s \in S$ (but no others). Run BFS starting in $s_0$; the quantity you are looking for is

$\qquad\displaystyle \min_{s \in S} d(s, v) = d(s_0,v) - 1$

for every $v \in V$.

Nota bene: The idea extends to weighted graphs; you have to a) give the new edges weight $1$ and b) use an SSSPP algorithm, of course.


In short, the lifecycle of thread does not interfere with the lifecycle of a process.

Processes and threads have different execution cycles; threads will execute and die while their process will continue to run until it gets a exit, truncate or die call due to normal execution (or in case of deadlock handling).

If a process contains only one thread, then if the thread is running, the process is in its running state. Otherwise, it can go into ready, wait, or die.
If a process contains multiple threads, it will execute until all jobs are completed. If a thread goes inactive it will not end a process; a process may enter ready state or be in running state.


Converting a 32-bit bit pattern into floating point number

Suppose you didn't include that shift of $127$, i.e. your number $\nu$ would have the form $\nu = (-1)^S \cdot M \cdot 2^x$ with $x$ being the exponent.

With $8$ bits for the exponent $x$ can have a value from $0$ to $255$. This means you can represent numbers from $\nu = (-1)^S \cdot M \cdot 2^0$ to $\nu = (-1)^S \cdot M \cdot 2^{255}$ .

However, what if you wanted $\nu$ to be $2^{-10}$? It would not be possible.

For this to be possible you want to allow negative exponents $x$. Instead of $x$ ranging from $0$ to $255$ you introduce a shift of 127 such that $x$ ranges from $-127$ to $+128$ .

Now you can represent numbers $\nu$ that range from $(-1)^S \cdot M \cdot 2^{-127}$ to $(-1)^S \cdot M \cdot 2^{+128}$ .


Let's start with stating the pumping lemma, in its contrapositive form:

  Suppose that $L$ is a language such that for all $p>0$, the following holds. There exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$, there exists $t \geq 0$ such that $xy^tz \notin L$. Then $L$ is not regular.

Now let us prove that your language is not regular. Given $p > 0$, let $w = a^pb^p \in L$, which certainly has length at least $p$. Given a decomposition $w = xyz$ with $|xy| \leq p$ and $y \neq \epsilon$, we see that $y = a^i$ for some $i \neq 0$. Therefore $xy^0z = a^{p-i}b^p \notin L$. Hence the pumping lemma applies, and shows that $L$ is not regular.


Why do we need value-returning functions?

"Need" as such, no. There you are right, all the work can be done using void functions, by passing pointers to variables to modify instead, or changing global variables. In fact, everything is compiled down to assembly language, and no such language I know of has "functions" that return values.

On the other hand, we are accustomed (by mathematics, and by lots of it's applications in everyday life) to think in terms of functions that are applied to arguments and return a value. Think of sin x, square root, and a long list of others, like lowly strlen() in C. It is a nice simplification to be able to say:

y = abs(x) - 42 * sqrt(b);

instead of something like:

pabs(x, &xa);
psrqrt(b, &ba);
y = xa - 42 * ba;

Come to think about it, multiplication and subtractions are functions returning values too (X& operator*(const X&, const X&) and X& operator-(const X&, const X&) in C++), and the handling of results and intermediate values soon gets unmanageable. One of the points of a programming language is to handle such bureaucratic details for you, transparently.


Recognizing Regular Languages in Layman terms

the way to test if something is non regular is to use the pumping lemma for regular languages. It can prove that a language is non regular, but it will not necessarily prove that a language is regular. To prove that some language is regular, you can create a finite automata for that language.


Is it possble to store a counter that could reach $\lfloor \frac{N}{x}\rfloor$ using $\lceil\log_2(N+1)\rceil$ - $\lfloor\log_2 x\rfloor$ bits?

This is indeed possible.

First, notice that for storing $\left\lfloor\frac{N}{x}+1\right\rfloor$ values ($0,1,2,\ldots,\left\lfloor\frac{N}{x}\right\rfloor$), you need $\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil$ bits (which might be larger than $\log\left\lfloor\frac{N}{x}+1\right\rfloor$). This won't stop us though :).

We first notice that for every $$\forall 1<x,N\in\mathbb N:\left\lfloor\frac{N}{x}+1\right\rfloor\leq\left\lceil\frac{N+1}{x}\right\rceil$$
To see this, consider the case where $\frac{N}{x}\in \mathbb N$, and thus $$\left\lfloor\frac{N}{x}+1\right\rfloor = \frac{N}{x}+1=\frac{N}{x}+\left\lceil\frac{1}{x}\right\rceil=\left\lceil\frac{N+1}{x}\right\rceil$$ Otherwise, when $\frac{N}{x}\not \in \mathbb N$:$$\left\lfloor\frac{N}{x}+1\right\rfloor =\left\lceil\frac{N}{x}\right\rceil\leq\left\lceil\frac{N+1}{x}\right\rceil$$

Another useful inequality is $\forall r\geq 1:\log\left\lceil r\right\rceil\leq\left\lceil\log r\right\rceil$.

To see this, let $k\in \mathbb N$ such that $2^{k-1}<r\leq2^{k}$.

Now $k-1<\log r\leq k$, and therefore $\left\lceil\log r\right\rceil =k$. Now $\log\left\lceil r\right\rceil\leq k=\left\lceil\log r\right\rceil$.

Finally, we conclude that:
$$\left\lceil\log\left\lfloor\frac{N}{x}+1\right\rfloor\right\rceil\leq\left\lceil\log\left\lceil\frac{N+1}{x}\right\rceil\right\rceil\leq\left\lceil\left\lceil\log\frac{N+1}{x}\right\rceil\right\rceil$$
$$=\left\lceil\log(N+1)-\log(x)\right\rceil$$
$$\leq\left\lceil\log(N+1)\right\rceil-\left\lfloor\log(x)\right\rfloor$$


Fair cake-cutting when players join late

Assume the cake/area is a circle $C$ with radius $r$. Then, we can create
$n$ fair pieces by the canonical cake cutting and thus assign each player an area
of $\frac{\pi r^2}{n}$. We can then assign the $(n+1)$th a small circle around the center,
and subsequent new players rings around that one (swallowing part of the inner circle),
and so on. In this way, every player gets one contiguous piece/plot which shrinks
in a monotone way for the first $n+1$ players, and moves towards the center for
those joining later.

Working out the numbers is simple; for the first new player, simply solve

$\qquad \pi r_1^2 = \frac{\pi r^2}{n+1}$

to get the radius for his plot. For the second, solve

$\qquad\begin{align}
  \pi r_1^2 &= \frac{\pi r^2}{n+2} \\
  \pi r_2^2 - \pi r_1^2 &= \frac{\pi r^2}{n+2}
\end{align}$

to get (outer) radii for both new players, and so on.
It seems that player $n + i$ gets outer radius $r_i = \frac{r\sqrt{i}}{\sqrt{n+k}}$
after $k$ additional players have joined, but I did not prove this.

This is what you get for $n=6$ and $k=0,1,2,3$:

[source]

The same idea works for regular polygons with $n$ sides. If you assume a rectangle
as basic form, you can do a similar thing by assigning the first $n$ equally sized
columns and the following players rows (starting at one side).


Can we load the data on the bus on multiple registers at the same time?

If we somehow turned on multiple load signals at the same time, in theory it should work to transfer the same value to multiple registers in the same cycle.

(Depending on the hardware design technology, there may be some power considerations, such as amplification of the data bus lines as they go into the various registers, since more gates are consuming the data bus lines concurrently; it is possible that such is required anyway, though.)

However, the diagram you're showing doesn't reveal the answer.  Here's the issue: it doesn't show how the load signal is generated and delivered to the various registers.  So, we can't really tell.

If the load signal is driven by an ordinary MUX (under control of say, instruction decode, e.g. some field of the IR), then by design, it would only ever turn one line on at a time, meaning the answer is no.

But an alternate implementation could turn on multiple registers' load signal simultaneously, so in that case, then yes.

See also Register File, regarding "ports", in how processors with general purpose registers deal with the need to read and write them concurrently.


Greedy algorithms: Minimum sum number pairing

Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq b_2 \leq \ldots \leq b_n$. In this notation, the suggested optimum solution is $(a_1, b_1), \ldots (a_n, b_n)$.

Given some arbitrary pairing, let us show we can reduce it to the right pairing without increasing the maximum sum of a pair. This shows that the expected correct solution is at least as good as any other. Equality might hold, eg. if all the values are the same, then any pairing is the joint best.

First suppose that there is some pair $(a_u, a_v)$. Then since there are an equal number of $a$'s and $b$'s, there must also be some pair $(b_s, b_t)$. Clearly $a_u + a_v \geq b_s + b_t$, furthermore $a_u + a_v \geq a_u + b_s$ and similarly $a_u + a_v \geq a_v + b_t$. So if we replace the pairs $(a_u, a_v), (b_s, b_t)$ by $(a_u, b_s), (a_v, b_t)$, we have reduced the maximum sum of a pair, or at worst kept it the same.

So now assume that our pairing is of the form $(a_{i_1}, b_{i_1}), \ldots (a_{i_n}, b_{i_n})$, but that it's not $(a_1, b_1), \ldots (a_n, b_n)$. There must be at least one pair of pairs, $(a_j, b_k)$ and $(a_l, b_m)$, where $j < l$ but $k > m$. (Otherwise, the $b$'s are in the same order as the $a$'s, which means it's the suggested solution.)

This means that $a_j \leq a_l$ and $b_k \leq b_m$. So $a_l + b_m \geq a_j + b_k$, also $a_l + b_m \geq a_j + b_m$, and similarly $a_l + b_m \geq a_l + b_k$. So $(a_l, b_m)$ must be the bigger of $(a_j, b_k), (a_l, b_m)$, and replacing those two pairs with $(a_l, b_k), (a_j, b_m)$ can only reduce the maximum (or keep it the same).

This shows that whatever pairing we start out with, we can swap pairs until we reach the suggested solution, without making the maximum sum any bigger. So the suggested solution must be the best.

I believe you could collapse the two steps into a single argument since both are very similar and rely on showing that two pairs can be 'flipped' without making the maximum sum any bigger. However I find it easier to imagine in two stages.


Turing machine generating $a^b$ for given a and b

It is possible. Practically, $a^b=a*a*a*\dots*a$, hence can be computed using a combination of the multiplication turing machine (to compute the multiplications), and the subtraction TM, in order to count the number of multiplications.

There is a reduction from multiple tapes TM to a single tape TM, so anything possible with multiple tapes is also possible with a single tape (with increased time complexity). To see why, try to think of the "even" spots in a tape as one single tape, and all the "odd" spots as another tape. This allows us to effectively place any number of TM tapes inside one single tape, but if you look carefully into the way its implemented you will see that it will come at the cost of increased time complexity (specifically, its bounded by the space complexity times the time complexity of the multiple tape machine)


Warm starting LP solver at non-basic feasible solution

LP solvers use simplex typically, so starting from nonbasic solution doesn't have too much sense. You can try finding a basic solution to $x_h$ by minimizing $||x-x_h||_p$ over your feasible region. I believe it's still an LP for $p=1$ and $p=\infty$. However, there is no guarantee warm start combined with this is faster.


Subgraph of an interprocedural control flow graph

You are asking several questions. Here are answers to some of them. Your process is obtained by contracting all vertices not belonging to $f_1,f_2$, a process which is similar to the process of contracting edges in the definition of graph minors (though your graph is directed). Semantically, you can produce the graph by repeatedly performing the following contracting procedure for each vertex $v$ which is not $f_1,f_2$:

  Let $(x_i,v)$ be all the incoming edges, and $(v,y_j)$ all the outgoing edges. Delete $v$ and replaces the edges adjacent to $v$ by the edges $(x_i,y_j)$ for all $i,j$.

I don't know what is the most efficient implementation of this process, though I suspect you could find it in the literature once you determine what this operation is known as.


Big Oh notation for a function with two inputs of linear growth

There is a common misconception that the running time always have to depend on a single parameter. This misconception is strange since in graph theory, the running time of many algorithms is stated in terms of two parameters, the number of vertices and the number of edges. As an example, DFS and BFS run in time $\Theta(V+E)$. A priori, we do not know of any relation between $V$ and $E$ other than $E \leq \binom{V}{2}$, and so $\Theta(V+E)$ cannot be simplified further. Since $E = O(V^2)$, any algorithm running in time $O(V+E)$ also runs in time $O(V^2)$. If we know that the graph is connected then $E \geq V-1$, and so $\Theta(V+E)$ is the same as $\Theta(E)$. But for general graphs, we have no reason to assume any relation between $V$ and $E$.

In your case, you seem to want to assume that $k$ and $m$ have the same order of growth. This might be the case or might not be the case, depending on the application you have in mind. Only you can tell. It is possible to state the upper bound $O(k+m)$ in terms of a single variable: it is $O(n)$, where $n = \max(k,m)$ (or $n = k+m$). Whether this is helpful or not is up to you.


The move-to-front heuristic is 4-competitive in the model where swapping adjacent elements costs one unit. This means that if the optimal strategy has cost $N$, then move-to-front has cost at most $4N$. In particular, if a swap list has cost $N$ on some searching sequence, then move-to-front will have cost at most $4N$.
See for example MIT OpenCourseWare or Princeton Slides.


Is there a name for this infinite language?

Non-decreasing sequences of natural numbers.


Assumption $II$ is true for any general graph with non-negative edge weights, including the graph $G$ with specific properties. To understand this, think about the inverse of the statement.
Let's assume the weight a $u,v$ edge is lighter than edge $e$ on the shortest path. The shortest path is made out of $e$ + $C$ where $C$ is some constant. Because $C >= 0$(non-negative graph) and $e$ < edge between $u,v$, by definition the shortest path we have assumed to be optimal is not(because the edge directly connecting $u$ to $v$ would be shorter).
To your specific graph into this, this lighter edge from $u,v$ cannot exist because if it did, it would have to be part of the minimum spanning tree(and thus part of the shortest path as mentioned in your description).


Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.
To be fully clear, item (1) should have been the following.

If $A$ is any independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

"A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$."
Note that "solution" is just a shorthand for "independent set". Let us prove the proposition above.
Suppose $A$ is a maximum-weight solution in $M$. Then $A$ yields $A'=A-\{x\}$, which is a solution in $M'$ according to item (1). (The previous version of item (1) works as well.)
Given any solution $B'$ in $M'$, let $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ Since $A$ has maximum weight in $M$, we have $w(A)\ge w(B)$, i.e.,
$$w(A')+w(x)\ge w(B')+w(x).$$
Cancelling $w(x)$ from both sides, we obtain
$$w(A')\ge w(B'),$$
which says $A'$ is a maximum-weight solution in $M'$. $\checkmark$

A maximum-weight solution in $M'$ yields a maximum-weight solution in $M$ containing $x$.
The other direction, as stated above, can be proved similarly. Here is the proof.
Suppose $B'$ is a maximum-weight solution in $M'$. Then $B'$ yields $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Given any solution $A$ in $M$, let $A'=A-\{x\}$, which is a solution in $M'$ according to (the corrected version of) item (1).
Since $B'$ has maximum weight in $M'$, we have $w(B')\ge w(A')$. Adding $w(x)$ to both sides, we obtain,
$$w(B')+w(x)\ge w(A')+w(x).$$
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$  So the inequality above is the same as
$$w(B)\ge w(A),$$
which says $B$ is a maximum-weight solution in $M$. $\checkmark$


LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$

Repeatedly remove an $a$ from the beginning and a $bb$ from the end until the string becomes empty. If you cannot do it at any point, reject, otherwise, accept.


How to read a number from highest place value to lowest?

Well, you could construct the inverse of that number. 12312 will become 21321 and then use the piece of code you wrote. So:
while (n)
{inverse = inverse * 10 + (a % 10), a /= 10;}.


Number partitioning targeting ratio of subset sums and equal size

The problem is NP-hard (assuming the numbers are represented in binary).  If you could solve your problem efficiently, you could solve the Partition problem: Partition is the special case where the minimum difference is zero (and the target ratio is 1:1).  Therefore, you should not expect any simple algorithm to be both efficient and always correct.

If you want a heuristic that gives an approximation, greedy algorithms are reasonable.  I suggest you try adapting the standard algorithms for the Partition problem.  Another approach is to use an integer linear programming solver.


Should we always think of problems higher in the polynomial hierarchy as harder than problems lower in the hierarchy?

The quote you give is an informal claim/intuition.  Don't try to read too much into informal claims; they are intended to give you a sense of what's going on, but for specific details, you need to look at the precise technical claim.

I suspect the source of your confusion is that you are using the same phrase  in two or three different ways in different places, without realizing it.  This is the logical fallacy of equivocation.  In particular, I don't think you're using "harder than" in exactly the same way each time you use it.  This then leads to you reaching conclusions that seem absurd or confusing.  One way to remedy the confusion is to understand more clearly exactly what you mean by "harder than", and then walk through your logic.

One possible meaning of "P is harder than Q" is that the "running time of the fastest algorithm to solve P is larger than the running time of the fastest algorithm to solve Q, in some specific theoretical model of computation".  This is a statement about theoretical complexity.  Note that this meaning depends on the model of computation.  P might be harder than Q in one model of computation (e.g., classical computation), but not in another model (e.g., quantum computation).

A second possible meaning of "P is harder than Q" is "Q reduces to P".  This is a theoretical statement, which has implications for the previous statement (if Q reduces to P, then the running time of the fastest algorithm for P can't be too much less than the running time of the fastest algorithm for Q).  Note that this notion of "harder than" is as a partial order.  There might be two problems P,Q such that neither "P is harder than Q" nor "Q is harder than P" are true; the problems might be incomparable.

A third possible meaning of "P is harder than Q" is "in practice it's probably harder (takes more time or costs more) to solve instances of P than instances of Q".  This is a statement about engineering and what is feasible in practice, rather than theory.  For instance, this will depend on whether quantum computers are feasible to build, in practice -- something that no one knows the answer to right now.  If quantum computers are feasible, then we'll discover that factoring is much easier than all NP-complete problems, because a quantum computer can solve factoring quickly but can't solve NP-complete problems quickly (we think).  If quantum computers aren't feasible, then factoring might turn out to be not much easier than some NP-complete problems.

Finally, just because a problem isn't in PH doesn't necessarily mean it is harder than all problems in PH -- so just because Recursive Fourier Sampling is not in PH doesn't necessarily mean it is harder than all problems in PH (in the sense of the existence of a reduction).

As a final complication, Recursive Fourier Sampling is a funny kind of problem.  It's not an ordinary decision problem.  Rather, it's an oracle problem.  Oracle problems can't be directly compared to ordinary problems.


The reduction that you suggested does not work. For example, consider a graph $G = (V, E)$ that consists of 9 disjoint triangles ( triangles that do not touch each other). $G$ has a triangle which a hamiltonian cycle of length $3 = 27^{\frac{1}{3}} = |V|^{\frac{1}{3}}$, yet $G$ has no hamiltonian cycle.
A simple correct reduction operates as follows. Given an undirected graph $G = (V, E)$, the reduction outputs $G$ with additional $|V|^3 - |V|$ isolated vertices. I leave the details to you.


Is there a zero-knowledge protocol for bit vector agreement?

I think you actually want secure multi-party computation, not zero-knowledge proofs.  In secure multi-party computation, Alice has a secret input $a$, Bob has a secret input $b$, and we want to compute $f(a,b)$ so that both Alice and Bob learn $f(a,b)$ but neither one learns anything more about the other's secret.  That maps directly to your situation.  In your situation, $f$ is the Hamming distance function that counts the number of positions where Alice and Bob's bitvectors agree.

It's a standard theorem that for every poly-time computable $f$, there is a poly-time protocol to compute $f(a,b)$ in a secure multi-party computation sense.  There are also toolkits to automatically derive such protocols, given a circuit/description of $f$.  For instance, you could look at VIFF or UVA's toolkit.

You'll want to be aware of the differences in threat model between the honest-but-curious threat model (aka semi-honest threat model) vs malicious threat model.  The honest-but-curious threat model is a bit of an academic curiousity; for most real applications, I suspect the malicious threat model will be more appropriate, but the protocols do tend to be more expensive.

The following paper might be of interest as well, not for your particular problem, but as an interesting tool for computing monotonic functions, where the inputs are sets:

Lea Kissner and Dawn Song.  Privacy-Preserving Set Operations, CMU-CS-05-113.

(I previously thought your problem could be reduced to Cardinality Set Intersection, from Section 5.2 of the following paper, by making Alice's set is $S_1 = \{i : a_i=1\}$, Bob's set is $S_2 = \{i : b_i=1\}$, and computing $|S_1 \cap S_2|$ -- but as you accurately point out, that doesn't work, because you actually want to compute $|S_1 \Delta S_2|$.)

There are a bunch of cryptographers who hang out on Cryptography.SE and who are knowledgeable about this area.


The problem can be solved in time $\tilde{O}(n^{4/3})$, using several algorithms:

Agarwal, Partitioning arrangements of lines II: Applications.
Chazelle, Cutting hyperplanes for divide-and-conquer.
Matoušek, Range searching with efficient hierarchical cuttings.

There is an essentially matching lower bound due to Erickson, New lower bounds for Hopcroft's problem. See also Williams and Yu, Finding orthogonal vectors in discrete structures.


A basic misconception about mathematics is that it is a purely formal game. Promulgated by the formalist school, we are taught that all that matters in mathematics are formal proofs. Yet in practice, completely formal proofs almost never get written; and mathematical thought has a strong informal component. In order to get further in mathematics, you need to understand mathematical concepts intuitively rather than just formally. A formal proof might be the end result, but the thought process is more liberal.

Furthermore, mathematicians are interested in things beyond definitions, theorems and proofs: key insights are sometimes more interesting than the proof itself or the result being proved. The philosophy behind the proof uncovers a deep truth which reaches much beyond the proof itself.

Such is the case here. Garey and Johnson are explaining how they conceive of NP-completeness proofs. They describe three basic types:

Proofs by special case: If a special case of a problem is NP-hard, then so is the original problem. For example, if 3-coloring is NP-hard, then the $k$-coloring problem (with $k$ a parameter) is also NP-hard. This can in principle be modeled formally by using very weak reductions — in this case, to reduce 3-coloring to $k$-coloring, it might suffice to use an $\mathsf{NC^0}$-reduction.  In contrast to what you write, this is certainly not a bijection, since when $k > 3$, the correspondence is less direct.
Proofs by gadget reduction: These are proofs in which each "basic unit" of the original instance is replaced by a "gadget" in the new instance. For example, when reducing SAT to 3SAT, we replace a clause $\ell_1 \lor \cdots \lor \ell_n$ by the clauses $\ell_1 \lor \ell_2 \lor x_2$, $\lnot x_2 \lor \ell_3 \lor x_3$, ..., $\lnot x_{n-2} \lor \ell_{n-1} \lor \ell_n$.  Basic unit is a completely informal concept. It doesn't have a formal definition. It is supposed to help you conceptualize this kind of proof. Garey and Johnson give several examples, which might help you in constructing similar NP-hardness proofs.
Proofs by indirect gadget reduction: These are proofs in which several "components" of the original instance are replaced by several kinds of gadgets. For example, when reducing from SAT, we might have different gadgets representing variables and clauses, which are connected together in an appropriate way.  Once again, component is a completely informal concept. The difference between direct gadget reduction and indirect gadget reduction is significant in our mind, but cannot necessarily be described formally.

This description is useful since it covers many NP-hardness proofs, and even other hardness proofs such as PSPACE-hardness. Understanding these techniques is helpful for coming up with new hardness proofs. However, in no way is this case distinction supposed to be formal. It is just a mental aid.


First, let us see what the halting proof attempts to prove:

  There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $y$.

We call the function which $H$ is supposed to compute the halting predicate.

The program you are suggesting, which consists of simulating a run of program $x$ on input $y$, definitely doesn't always halt. What we are attempting to show is that there is no other devious way to computing the halting predicate in a way which does always halt.

The proof you are describing is a proof by contradiction. We assume that there is a program $H$ that always halts and computes the halting predicate correctly. Under this assumption, we reach a contradiction. Hence the conclusion is that no such program exists.

  How does $H$ know whether $x$ halts on $x$?

The assumption that the proof by contradiction is making is that there does exist an $H$ which computes the halting predicate. What the proof shows is that $H$ actually doesn't compute the halting predicate correctly. So $H$ cannot tell whether $x$ halts on $x$, and that is exactly what the proof shows.

  The answer is $H$ must simulate $x$ on $x$.

This is not true. There are similar predicates which can be computed. For example, we can decide whether a program halts on all inputs within 100 steps. We can do so even though there are infinitely many potential inputs, and so the naive solution, which is to run the program on all inputs for 100 steps, can be improved.

What the proof shows is that there is no computable way to decide whether a given program $x$ halts on a given input $y$. It doesn't show that $H$ must simulate $x$ on $y$; indeed, $H$ could store the answers for selected pairs $(x,y)$ in a table, and for these pairs it could just return the correct answer by doing a table lookup. This approach can only handle finitely many pairs $(x,y)$, and the proof shows that no other computable approach works.


How does value decompression work for Facebook's Gorilla in the case where count of leading zeroes is not stored

I found my answer after reading the reference implementation: https://github.com/facebookarchive/beringei/blob/92784ec6e22572f28500c76b669276007635c875/beringei/lib/TimeSeriesStream.cpp

The use of the term "meaningful bits" in the paper is ambiguous. I thought the sentence "use that information for the block position and just store the meaningful XORed value." means to store the bits with all the trailing and leading zeroes stripped because "meaningful XORed value" is a value with no leading and trailing zero. But, according to reference implementation you just strip off same amount of leading and trailing zeroes as previous value delta; the meaningful bits in this case may still contain some leading and trailing zeroes.

So, for the example in the question, we should store 0ff0 as meaningful bits instead of just ff.


You are mixing two things here: syntax and semantics.

First, syntax. What is the language of strings $L_P \subseteq \Sigma^*$ with $\Sigma = \{\mathtt{a}, \dots, \mathtt{z}, \mathtt{)}, \mathtt{(}, \mathtt{,}\}$ that describe a set of paths as you specify them? You can specify $L_P$ by the formal grammar

$\qquad\begin{align}
  S &\to T\mathtt{,} S \mid \mathtt{(}S\mathtt{)}S \mid T \\
  T &\to [\mathtt{a}\dots\mathtt{z}]
\end{align}$

Note that the key feature is recursion for the parts inside parentheses. Depending on the parsing algorithm you want to employ, you may have to refactor this grammar.

Next, which set of paths does a given string $p \in L_p$ describe? Note that this is independent of the syntax; we could define anything we want as the meaning of $p$. Your specification is quite precise, and can be described by these by recursive functions:

$\qquad\begin{align}
  \varphi(t) &= \{t\} \quad, t \in [\mathtt{a}\dots\mathtt{z}], \\
  \varphi(t\mathtt{,}w) &= \varphi(t) \cdot \varphi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in \Sigma^*, \\
  \varphi((v)w) &= (\psi(v), \{\varepsilon\}) \cdot \varphi(w) \quad, v, w \in \Sigma^* \\
\end{align}$

and

$\qquad\begin{align}
  &\psi(t) = \{t\} \quad, \mathtt{t} \in [\mathtt{a}\dots\mathtt{z}], \\
  &\psi(t\mathtt{,}w) = \psi(t) \cup \psi(w) \quad, t \in [\mathtt{a}\dots\mathtt{z}], w \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, \\
  &\psi(v_0(w_1)v_1(w_2) \dots v_{k-1}(w_k)v_k) =  \\
    &\phantom{=}\bigcup_{i \in [0..k]} (\psi(w_1), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_{i}), \{\varepsilon\}) \cdot \psi(v_i) \cdot (\psi(w_{i+1}), \{\varepsilon\}) \cdot \dots \cdot (\psi(w_k), \{\varepsilon\}) \quad, v_i \in [\mathtt{a}\dots\mathtt{z},\mathtt{,}]^*, w_i \in L_P. \\
\end{align}$

Note how $\varphi(p) \subseteq [\mathtt{a}\dots\mathtt{z}]^*$ is the set of paths described by $p$.

Warning: Your syntax has the troublesome feature that a comma-separated list of path elements has different meaning outside and inside of parenteses (resulting in two functions for the semantics). In combination with your semantics, that means e.g. that you can not describe the set of paths $\{ad, abcd\}$.

Warning: Your semantics have the troublesome feature that any list of atoms in parentheses may produce at most one atom (selection), but if one element of the list is another list we suddenly get more (selection + concatenation). In other words, the semantic of $\mathtt{,}$ inside of parentheses changes depending on context. This is what makes the semantics so horrible. But then, maybe that is how it has to be: you seem to want it that way.


How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

Since I see questions about the pumping lemma on this site quite often, I decided to write a bit of a longer answer hoping that it helps people "get" the PL rather than just treating it as a "plug-n-chug" tool given to us by the gods of math.
Understanding the PL
I think the best way to go about it is to basically (re-)derive the lemma.
The idea is that if some language $L$ is regular, then there exists some DFA $A$ such that $A$ recognizes $L$.
Now say that $A$ has $m$ states and suppose that we have some $w \in L$ with of length $n > m$ (note that any infinite $L$ must contain such a word) and consider the run of $A$ on $w$.
As $w$ has more characters than $A$ has states, there must be some state $q$ which occurs at least twice in $A$'s run on $w$, i.e. if we draw out the run through the graphic representation of $A$ we find some loop.
In more formal terms, this means that there must be some substring $s$ of $w$ -- so $w$ can be written as $w = rst$ where $r$ and $t$ are remaining parts of $w$ left and right of $s$ -- such that $A$ is in state $q$ on the both the first and last symbol of $s$.
At this point, we need to understand the D part of DFA: $A$ is deterministic, so given that we start from the initial state on any input of the form $r\Sigma^\ast$ (any string starting with the substring $r$) we will always end up at the state $q$ and similarly, starting from $q$ on the word $s$ we always end up at $q$ again and finally, starting on $q$ given the word $t$ we always end up at the same (accepting) state.
I like to think of such deterministic machines as music boxes; if you start the at the same point they end up playing the same melody.
This means that we can now create new words which $A$ must also accept by making $A$ go into state $q$ and presenting it with $t$, and the easiest way to do so is by taking the known string $r$ to get it to the state $q$ initially, then repeating $s$ some $k \geq 0$ times (which, because we start at $q$ now) will always get us back to $q$ and then appending $t$ to make $A$ go into an accepting state.
Hence these words are of the form $w_k = rs^kt$ for some $k \geq 0$.
Taking a step back, we have now basically argued that $A$ cannot distinguish between $w$ and $w_k$; the result of the computation will always be the same.
This is the essence of how the pumping lemma works.
Using the PL
To apply the pumping lemma we must now find such $w$ and $k$ where $w \in L$ and $w_k \notin L$. Usually one will not be able to give $w$ directly as the size of the automaton $A$ is unknown (in fact we are trying to argue that such an $A$ does not exist, so yeah).
In most cases, this boils down to taking a "large" string in $L$ such that the middle part of said string is big enough for us to find some part that if repeated would give us the $w_k$ we need.
Let us get specific now.
Our language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \mathbb N\}$.
We assume that $L$ is regular and thus admits a DFA $A$ of size $m$.
If we consider the string $w = a^{10m + 1} b^{40m + 2} \in L$, we find that a state repetition must already occur in the $a$-part of $w$ as $a^{10m + 1}$ has more symbols than $A$ has states.
Hence there must be a decomposition $w = rst$ where $r = a^{\ell}$, $s = a^k$ and $t = a^{10m + 1 - \ell - k} b^{40m + 2}$ with $0 \leq \ell < m$ and $0 < k \leq m$ (Can you figure out why the bounds on these variables are this way? This is a good test to see if you are confident with the first part, I think).
If we now consider the word
$$ w_2 = rs^2t = a^\ell (a^k)^2 a^{10m + 1 - \ell - k} b^{40m + 2} $$
and unpack it to
$$ a^{m + k + 1} b^{40m + 2} $$
we see that $w_2$ is not in $L$.
It follows that $A$ does not recognize $L$ as we assumed that $A$ accepts $w \in L$ and then argued that it must also accept $w_2 \notin L$.
As the choice of $A$ was arbitrary we find that no DFA can recognize $L$, which means that $L$ is not regular.