Why the Cook-Levin reduction is not a parsimonious reduction?

The string $u$ is the certificate for $x$ with respect to $L$ and $M$, while the string $y \circ z$ is the certificate for $\phi_x$ with respect to $SAT$ and a verifier TM for SAT. $M$ is an oblivious deterministic TM with two tapes - an input tape and a work/output tape. Although I did not find this clearly stated anywhere, it seems reasonable to assume that the output of $M$ is 1 if the final state is $q_{halt}$, and the contents of the output tape are $1 \Box \Box \ldots$, and the heads are positioned at their initial locations at the left ends of the tape. In Garey and Johnson, the formalization of the Turing machine contains two halt states $q_Y$ for accept, and $q_N$ for reject, all other states are designated non-halting - using such a formalization could simplify this reduction; however, Arora and Barak have kept things more general by not focussing on Boolean functions, since the scope of their text is larger.
Any certificate $u$ can be mapped to some certificate $y \circ z$ such that $y = x \circ u$, and $z$ equals the snapshots of $M$ - this map is clearly injective. Similarly, $y \circ z$ may be mapped to $u$ by extracting the appropriate substring - in this case, let us prove that the map is injective. Assume that two certificates $y_1 \circ z_1$ and $y_2 \circ z_2$ may be mapped to the same certificate $u$. This implies that $y_1 = y_2 = x \circ u$, which in turn implies that $z_1 = z_2$ since these strings record the $T(n)$ snapshots of the deterministic TM $M$ starting for the same input $y_1 = y_2$. Given these two injective maps, we can infer that the two sets of certificates have the same cardinality, and hence the reduction is parsimonious.
However, the authors seem to think otherwise. Excercise 2.13.a asks the reader to make the reduction parsimonious, and even a hint is provided:

"Modify the machine M so that it clears up its work tape before
outputting a 1 and moves both heads to one end of the tape. Then the
final snapshot and head locations are unique."

Note that the suggested modification does not affect the reduction at all! Using our definition of output, we are already assuming that $M$ is doing everything the hint suggests. The only issue I can see is that Condition (4) only examines the last snapshot $z_{T(n)}$ to determine whether the output was 1 but $z_{T(n)}$ only captures a small portion of the output tape - I would question whether this is an accurate test for whether $M$ halted and produced the output 1 - that is, I am not sure that the reduction given in the text is correct.


Do the minimum spanning trees of a graph have the same number of edges with a given weight?

The question and this post refers to this answer at its version 2.

  First of all, what does minimum disagreeing weight mean?

The better word should have been "distinguishing". If the set of edges of some fixed weight in $T_1$ is different from that of $T_2$, then $T_1$ and $T_2$ disagree on that weight, i.e., that weight is distinguishing the two minimal trees.

  What is supposed to be $g(e)$?

That is a typo. It should have been $w(e)$.

  Why is $w(e') \lt w(e)$ here? isn't $e'$ same as $e$ ? and why does  $T_1,T_2$ contradict as minimal spanning trees?

Let us use a new dummy variable instead of $e'$ for the last part of that answer.

Let $f \in C_{T_1}(e) \cap T_2$. Had $f$ weighed the same as $e$, we should have update $T_1$ by using $f$ instead of $e$. Since we have done all such updates, $f$ must weigh differently from $e$. That is the conclusion in the previous paragraph, "all edges in $T_2 \cap C_{T_1}(e)$ (where $T_1$ is the updated version) have weights other than $w(e)$".

There are two disjoint cases.

the case when $w(f)\lt w(e)$. Consider the spanning tree $(T_1 \setminus \{e\}) \cup \{f\}$, which is lighter than $T_1$.
the case when $w(f)\gt w(e)$. Consider the spanning tree $(T_2 \setminus \{f\}) \cup \{e\}$, which is lighter than $T_2$.

In either case, we have found a spanning tree that is lighter than a minimum spanning tree, which is a contradiction.


Time complexity of transforming one string to another

As told by OP, the problem and its the solution come from Elements of Programming Interviews in Java by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.

Here is the excerpt of the book that analyzes the time-complexity of the solution.

  The number of vertices is the number d of words in the dictionary. The number of edges is, in the worst-case, $O(d^2)$. The time complexity is that of BFS, namely $O(d + d^2) = O(d^2)$. If the string length $n$ is less than $d$ then the maximum number of edges out of a vertex is $O(n)$, implying an $O(nd)$ bound.

The above analysis in the book is correct. Please note "word" and "string" are used interchangeably here.

Here is OP's analysis, with the only modification that I use $d$ to denote the number of words so as to be consistent with the book.

  The second loop is a constant (right?), it doesn't change with the size of $d$, so I don't think that is a part of the calculation for the run time.

OP's analysis is not wrong, either, if we assume that the length of the strings in the dictionary is bounded by a constant. This assumption is not unreasonable since it conforms to our ordinary experience about words in a normal dictionary. In fact, OP's analysis has been included in the book as well! It is the very last statement of the excerpt above.

Is there a logical inconsistency between the bounds $O(d^2)$ and $O(nd)$? No, since they apply to different situations with different assumptions. For example, in the worst case where every string differ in exactly one character with every other string, if we let $d$ go to infinity, then the maximal string length $n$ will goes to infinity as well. That is, "The second loop" does "change with the size of $d$"! Those strings are very unlikely to be words in our ordinary dictionary because of their huge lengths, of course.

In fact, in all cases, $d \leq 26n$. So $O(d^2)$ implies $O(nd)$.


What does the symbol # mean when it comes to languages

This seems to just be a case of a lack of care in the definition. The symbol $\#$ isn't anything special, but is commonly used as a separator simply for the reason that it's not normally used for much else.

So in the language in question, all the strings in the language have two parts, $w$ and $x$, which are separated by the character $\#$, so you can easily tell which part of the string you're processing (just by keeping track of whether you've gone past the $\#$ or not).

Implicitly the strings $w$ and $x$ do not include the symbol $\#$, but the way it's written (at least in the question) this is not clear.

So, assuming that my interpretation is correct, a more explicit definition might be:

  Let $L$ be a language over $\Sigma\cup\{\#\}$, where $\# \notin \Sigma$ such that $$L = \{w\#x \mid w^{\mathcal{R}}\text{ is a substring of } x, \text{ and } w,x\in\Sigma^{\ast}\}$$


Does this problem map to the Set Packing problem?

You cannot reduce set-packing to your problem, unless P=NP.

There is a linear-time algorithm for your problem.

Remove all vertices of type 1 and all their neighbors. Let $m'$  (resp. $n'$) be the set of remaining vertices in $m$ (resp. $n$).
If $|m'| \ge k$ and the neighborhood of $m$ contains all the vertices in $n'$, the answer is yes.

If any of the above two conditions is not satisfied then the answer is no:

If $|m'| < k$ then any set $S \subseteq m$ with $|S| \ge k$ contains a vertex that is adjacent to some vertex of type 1 in $n$.
If there is a vertex $v \in n$ of type 2 that is not in the neighborhood of $m'$, then every vertex $u \in m$ that is adjacent to $v$ is also adjacent to a vertex of type 1 in $n$.


Number of Final States Subset Construction for NFA to DFA

Think about which states in the new NFA don't contain a state that was in $F$. These are   $\emptyset$ and every combination of states from $\mathcal{Q}-F$, i.e. $\mathcal{P}(\mathcal{Q}-F)$.

In your 3-state example, the only elements of $\mathcal{P}(\{1,2,3\})$ that don't contain 1 or 2 are $\emptyset$ and $\{3\}$, which constitute $\mathcal{P}(\{3\})$, with cardinality 2, so we have $\mid F'\mid=8-2=6$.

For your 7-state example with $\mid F\mid=2$, the size of $\mathcal{P}(\mathcal{Q}-F)$ is 32, which means there are $\mid F'\mid=128-32=96$ states that also contain at least one state that was in $F$.

So your conjecture of $2^{\mid F\mid}-2^{\mid\mathcal{Q}-F\mid}$ is correct.


If X is in NP-complete and complement(X) is in NP, show that for all Y in NP, complement(Y) is also in NP

Note that

$$
A \leq B \iff \overline{A} \leq \overline{B}
$$

where $\overline{A}$ denotes the complement of $A$. Indeed, if $f$ is a reduction for either side, it is also a reduction for the other side (exercise: prove this using the definition of $\leq$).

From this, your statement quickly follows.


It's short-hand for "$n^{f(n)}$ for some function $f(n)\in O(1)$".  In other words, the function is at most $n^c$ for some constant $c$.

You can see this by directly substituting the definition of $O(1)$ in the expression.  $g(n)=n^{O(1)}$ if there's constant $c$ such that, for all large enough $n$, $f(n)\leq n^{c\cdot 1} = n^c$.

This includes all polynomially-bounded functions.  For example, for $n>0$,
$$n^2+3n = n^2(1+\tfrac3n) = n^{2+\log(1+3/n)/\log n} = n^{O(1)}\,,$$
since, for $n\geq 3$, we have $1<1+\tfrac3n\leq 2$ and $\log n>1$, so the exponent is between $2+\log 2$ and $2$.


You have 00000000 as the number, it implies how many bits are used. The 1 at the front comes from carry bit, but two complements does not extend number of bits used, so the answer is 00000000, as the carry is discarded because it doesn't fit given space.

You can check it (to convince yourself) by converting code back from 2's complement to decimal. 00000000 yields 0, while 100000000 gives -256.


Why isn't Busy Beaver Infinite for n < trivial k?

Busy Beaver function considers only terminating TMs, that is only those that execute for some finite number of steps.


What is the complexity of this algorithm for sparse matrices?

They say the running time is $O(n+|b|+f)$, where $f$ is the number of floating point operations taken during the entire computation.  This takes some careful reading to understand what they mean.

They mean, if you take the total number of floating-point operations that are performed inside the innermost loop, and call that $f$, then the running time is not too much more than $f$.  In other words, they are saying we do $O(n+|b|)$ operations for updating the loop indices, plus the time taken by the body of the innermost loop (summed over all the iterations).

The body of the innermost loop might indeed take $5 n|b|$ operations in total (say), in which case the total running time would be $O(n + |b| + 5n|b|) = O(n|b|)$, as you had expected.

Note that $f$ is not the number of floating point operations in a single iteration of the innermost loop; it is the total across all iterations of the loop.  So $f$ is not 5.

Why do they count it this way?  Presumably, the floating point operations are ones that we'll have to do no matter what, because they are essential to the operation you're doing; they instead want to focus on the extra book-keeping needed to update loop indices etc. and make sure that doesn't add too much extra cost.

Finally, I'll note that you changed the pseudocode.  The pseudocode they show is not the same as what you listed in the question.  In the book the pseudocode of the innermost loop is not "for $i=j+1$ to...", but rather "for each $i>j$ for which $l_{ij}$".  That's not the same.  Since $l$ is a sparse matrix/vector, there are more efficient ways to iterate over the non-zero entries of $l$ than iterating over all possible values of $j$ and testing whether that element is non-zero.  This also affects the running time.


Expected length of a random walk on a line

The behavior when $p = 1/2$ and when $p > 1/2$ is rather different. When $p > 1/2$, in expectation you move $2p-1$ steps to the left, so you will hit the origin after a linear number of steps. When $p = 1/2$, the situation is more complicated.

Consider a random walk on the line started at the origin. The number of walks of length $2n$ which never move right of the origin is $\frac{\binom{2n}{n}}{n+1}$ (these are the Catalan numbers), and so the probability that you move right of the origin at the first time after exactly $2n+1$ steps is
$$
q_{2n+1} = \frac{1}{2^{2n+1}} \frac{\binom{2n}{n}}{n+1} = \Theta\left(\frac{1}{n^{3/2}}\right).
$$
Therefore the expected number of steps until you first move right of the origin is
$$
\sum_{n=0}^\infty (2n+1) q_{2n+1} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty.
$$
On the other hand, the number of visits to the origin is
$$
\sum_{n=0}^\infty \frac{\binom{2n}{n}}{2^{2n}} = \sum_{n=0}^\infty \Theta\left(\frac{1}{\sqrt{n}}\right) = \infty,
$$
so you will move right of the origin infinitely many times.

The conclusion is that a random walk started at $i > 0$ will hit the origin almost surely, but the expected time to reach the origin is infinite.

Your case is, however, different, since you "bounce" at $i = n$: when at position $n$, you always move to $n-1$. You can think of the situation in the following way. Although the actual set of positions is $0,\ldots,n$, we imagine reflecting this set along the point $n$, adding $n-1$ new positions $n+1,\ldots,2n$. Here position $n+k$ really plays the role of position $n-k$. We can run the random walk as usual, declaring victory upon reaching either position $0$ or position $2n$.

After $t$ steps, the displacement from the initial position has binomial distribution $\mathrm{Bin}(t,1/2)$, which is close to a normal distribution $N(t/2,t/4)$. Therefore after $t$ steps, we expect to be at a distance of about $\Theta(\sqrt{t})$ from where we started (this can be shown formally by considering the squared displacement and using Chebyshev's inequality, which requires an estimate of the fourth moment of a binomial random variable). In your case, we start at some position $i \in \{1,\ldots,n\}$. After $\Theta(n^2)$ steps, we expect to be about $\Theta(n)$ far from where we started, and so, hit either $0$ or $2n$. Therefore the process should converge in $O(n^2)$ steps.

We can also solve the recurrence directly when $p = 1/2$. Recall that the recurrence is
$$
E[X_i] = 1 + \frac{E[X_{i-1}] + E[X_{i+1}]}{2},
$$
with initial conditions $E[X_0] = E[X_{2n}] = 0$.

Let $N_i = E[X_i] + i^2$. Then
$$
N_i = 1 + \frac{N_{i-1} + N_{i+1} - (i-1)^2 - (i+1)^2}{2} + i^2 = \frac{N_{i-1}+N_{i+1}}{2},
$$
with initial conditions $N_0 = 0$ and $N_{2n} = 4n^2$.

Let $M_i = N_i - 2ni$. Then $M_i$ satisfies the same recurrence as $N_i$, with initial conditions $M_0 = M_{2n} = 0$. It is easy to check that the minimum and maximum of the sequence $M_0,\ldots,M_{2n}$ must be attained at the endpoints (since $\max(M_{i-1},M_{i+1}) \geq M_i$ and $\min(M_{i-1},M_{i+1}) \leq M_i$), and so $M_i \equiv 0$. Therefore $N_i = 2ni$, and so
$$
E[X_i] = i(2n-i) = n^2 - (n-i)^2.
$$


Data structure with insert, and delete-min (or max) in $O(1)$?

No; at least, it seems unlikely.  Such a data structure would contradict the lower bound on comparison-based sorting algorithms and would imply linear-time sorting algorithms (where none is known to exist).

Suppose we want to sort $m$ numbers from the range $1..n$, where $m \ll n$.  If we had your data structure, we could do that in $O(m)$ time.  However, this seems implausible.  The fastest comparison-based algorithm runs in time $\Theta(m \log m)$, which is  larger than $O(m)$.  Counting sort takes $O(m+n)$ time, which is much larger than $O(m)$ when $m \ll n$.  Van Emde Boas sorting takes $O(m \log \log n)$ time, which is still larger than $O(m)$ time. Han & Thorup's sorting algorithm takes $O(m \sqrt{\log \log n})$ time, which is still larger than $O(m)$ time.

So, you should not expect there to be any data structure of the form you list, as that would imply a huge breakthrough in sorting algorithms.

However, there is probably an algorithm where those operations can be done in $O(\log \log n)$ time, or possibly even $O(\sqrt{\log \log n})$ time, by applying Van Emde Boas trees or Han & Thorup.  See also https://en.wikipedia.org/wiki/Integer_sorting#Sorting_versus_integer_priority_queues.


Minimal number of nodes needed to connect a disconnected graph

I think you are looking for the vertex version of the Steiner tree where

$A$ is the set of terminal nodes and
$B$ is the set of vertices you want to use to create a tree.

In the Vertex-Weighted Steiner Tree problem you are given a graph $G = (V,E)$ and a set of terminal nodes $T \subseteq V$ and are asked for a minimum set $U$ such that $T \subseteq U$ and $G[U]$ is connected.

This problem has been studied as the node‐weighted Steiner tree problem by

Segev, 1987, The node‐weighted steiner tree problem, Networks.
Yeh and Chang, 1998, Weighted connected domination and Steiner trees in distance-hereditary graphs, Discrete Applied Mathematics.

and is indeed NP-complete.

On the positive side, it might be solvable in time $3^k \text{poly}(n)$ where $k$ is the number of connected components in $G[T]$.  The simplest preprocessing step is to contract all the edges in $G[T]$ first, that is, replace all the connected components with a single node, and remove parallel edges.  (That is, it is fixed-parameter tractable (FPT) in the number of connected components in $G[T]$).


Is there any algorithm so it can solve stable marriage problem with incomplete preference lists

I am not completely familiar with the problem, but maybe these couple of papers (or references therein) dealing with stable marriage with partial preferences (of which your setting could perceived as a special case) may be helpful:

https://www.math.unipd.it/~frossi/stc-care5-cr.pdf

https://www.aaai.org/ocs/index.php/IJCAI/IJCAI13/paper/view/6840/6488


Are all possible programming languages a formal system?

Technically, yes, because you can make your formal system have a single axiom that says “the sequence of symbols is in the set $S$” where $S$ is the set of programs in the programming language. So this question isn't very meaningful. The notion of formal system is so general that it isn't terribly interesting in itself.

The point of using formal systems is to break down the definition of a language into easily-manageable parts. Formal systems lend themselves well to compositional definitions, where the meaning of a program is defined in terms of the meaning of its parts.

Note that your approach only defines whether a sequence of symbols is valid, but the definition of a programming language needs more than this: you also need to specify the meaning of each program. This can again be done by a formal system where the inference rules define a semantics for source programs.


The language of tuples $\langle n,i,j,b \rangle$ such that the $j$th bit of the $i$th prime factor of $n$ is $b$ is in NP. In particular, it is in #P. More accurately, there is a #P algorithm that on input $\langle n,i,j \rangle$ gives the $j$th bit of the $i$th prime factor of $n$ (either $0$ or $1$). Since the permanent is #P-complete, we can reduce this algorithm to the computation of some polysize permanent.


"higher intensity" and "high signal intensity" in images

The intensity of a pixel is its value (e.g., from 0 to 255).  For instance, in a black-and-white/grayscale image, pixel intensity 0 means the pixel is black, and pixel intensity 255 means the pixel is white; intensities in between the two are shades of grey.

"White matter lesions have higher intensity" means that the pixels in the area of a white matter lesion have higher intensity values.

In this context "signal intensity" is presumably a synonym for "intensity".


Given an algorithm, do worst case time complexity "class" vary with array and linked list?

Note that complexity classes are classes of problems, not classes of algorithms. Specifically, complexity classes are classes of problems that can be solved within particular resource bounds by some algorithm.  So, for example, sorting is in polynomial time because there is at least one algorithm that sorts with this resource bound. (In fact, you probably know many algorithms that do this.)

When it comes to comparing different algorithms for solving the same problem, yes, they may have different resource usage. The fact that you have random access to the elements of an array but not to a linked list means that you can probably design more efficient algorithms based on arrays compared to those based on linked lists. And note that, by using different data structures, they are different algorithms: they involve different computational steps.

Note also that all of this is dependent on your model of computation. For example, if you're solving computational problems using Turing machines, then arrays and linked lists are essentially the same thing, because we can only access the array by moving the tape head sequentially through the elements. Typically, though, when analyzing actual algorithms, we use models of computation, such as the random access Turing machine, that correspond more closely to actual computers.


Estimate complexity of integer sequence enumeration

Here is a simple recursive solution that runs in exponential time.

Geometrically you want to enumerate the lattice points which lies inside
the first quadrant of the $n$-hypercube of height $m$ and on the intersection of the $D_1$-radius $L_1$ sphere and the $D_2$-radius $L_2$ sphere (let call them respectively $S_1$ and $S_2$), up to reordering of the coefficients.

Denoting by $V_n$ the volume of the $n$  unit dimensional ball, we have :

$m^n/n!$ points in the intersection of the hypercube and the quadrant (let's call it $D$) with the ordering ,
$\alpha = O\left(m^n e^{\frac{-(D_1-nm/6)^2}{3nm}}\right)$ in $S_1\cap D$ (see theorem 1.3 of http://www.doiserbia.nb.rs/img/doi/1452-8630/2008/1452-86300802222R.pdf), considering the ordering condition.
$\beta = \frac{1}{n!2^{n}}V_n D_2^{n/2} + O\left(D_2^{n/2-1+\epsilon}\right)$ in $S_2$ (Generalized Gauss circle problem+quadrant condition+order condition). I'm not considering intersection with the hypercube here, so the global complexity will be an overestimation.

Depending on your parameters choose the minimum of $\alpha$ or $\beta$.
If its $\alpha$ perform a recursive enumeration of the integers partitions of length $n$ with the restriction on $m$ and use early abort to
discard solutions which are getting out $S_2$.
In the other case, enumerate the lattice point on $S_2$ ( with recursive orthogonal projections for instance) and check for the appartenance in $S_1$ for each returned vector.

Hence the global complexity will be dominated by $min(\alpha, \beta)$.


Batch processing in increase-key function using binary heap

If $P$ is the number of processing units available, consider $P$-ary heaps¹. When descending to perform some operation on a set of keys, you can fork whenever keys lead to different children. If the heap is balanced, this results in independent taks for a uniformly chosen set of keys (and sufficiently big $n$) after having descended a constant number of levels (claim).

The above can only be expected to work well on shared memory systems. As soon as you have NUMA or distributed memory, you want to assign one subtree to every processing unit (and its memory). I suggest you give the root $P$ children, each of which is an (arbitrary) heap in its own right. All operations are send as messages to the corresponding subtree's processing unit. Operations that need the subtrees to interact block the root.

I think $P$ would be the correct branching degree, but you'd have to do some analysis and/or experiments.


Why to implement Open list in Heuristic search with priority queue

Your question is not perfectly clear to me, so maybe I answer a different question from what you intended. The article you linked talks about A* as a search algorithm that uses a heuristic to speed up searching, so I'll talk about this.

In a naive search you explore a graph for example in breadth first order: You start at some node, then visit its neighbors, then the neighbors of the neighbors and so on until you reach your goal state (or there is nothing more to explore).

Now suppose you had some function (the "heuristic") that can tell you more or less accurately how close a particular node is to your goal node. Then you can speed up your search by visiting nodes that are closer to your goal first. Now it depends on the quality of your heuristic how you should do that.

If your heuristic is perfect, that is, it tells you the distance to the goal accurately for every node, then you can just look at the neighbors of your start node and proceed to the node with the smallest distance to the goal. From there again you look at the neighbors and proceed to the one with the smallest distance to the goal. You don't need to keep any memory of possible alternative routes, because your heuristic exactly tells you which node you have to go to.

If the heuristic is not perfect however, the picture changes. Say your heuristic is optimistic, that is, it always underestimates the distance to the goal. Then can't assume that the neighbor with the smallest heuristic distance to the goal is always the correct node to which to proceed, because it might turn out that the true distance is much larger than what your heuristic told you. So you have to remember some alternative routes.

You can do that as follows: Maintain a set of nodes to which you could proceed (the neighbors of all nodes that you have already seen but not visited). This is you open set. In each step you continue searching from the node in the open set where the distance from the start plus the heuristic distance to the goal is smallest.

Now how do you find this node in the open set? You could store the open set as a list look at all nodes in each step to find it, but that is inefficient. Instead you could maintain the open set as a heap, where finding the minimum is cheap.

So this is why you want to use a heap in a heuristic search. It speeds up finding the next node from which to proceed with your search.


Is the identity function a many-one reduction from a language to super-set?

In order to disprove this, it is enough to disprove the conclusion that if $L_2$ is decidable then so is $L_1$. Can you think of a counterexample for the latter claim?

Another option is to directly disprove the fact. For $f$ to be a many-one reduction from $L_1$ to $L_2$ would mean that $x \in L_1$ iff $x \in L_2$, that is, $L_1 = L_2$. So to disprove this you only need to find two languages $L_1,L_2$ such that $L_1 \subsetneq L_2$.


Lower limit on the number of check bits needed to correct single errors

The comment by @gnasher is right. Moreover, if the code was $k$ error correcting with $m$ data bits, each of the $2^m$ legal messages would require
$$
1+n+\binom{n}{2}+\cdot+\binom{n}{k}=\sum_{j=0}^k \binom{n}{j}
$$
bit patterns dedicated to it, where $\binom{n}{j}$ is the number of words at Hamming distance $j$ from a given word.


How does this example violate Liskov substitution principle, which then causes violation of the open-closed principle?

The listing does not appear to be a good illustration of LSP violation, since no clear reason is given why the draw method couldn't be a virtual method of Shape. If it was, then there would be no need to do any type query in drawShape: calling draw would work for all subclasses of Shape.

The Liskov Substitution Principle is typically described in terms of contracts. For example: the contract of the square root function requires that the input is non-negative and ensures that the square of the output is equal to the input.

Hence, an overridden method in a subclass is substitutable for the corresponding method in the superclass if it:

requires no more of its input than the superclass contract
ensures no less of its output

A subclass is LSP-conforming if all its methods are LSP conforming.

Hence, a better illustration of LSP violation might be a rotate method, in which all shapes except Square can be rotated by any angle, but Square is only rotatable by some multiple of 90% (such a requirement would actually demonstrate that the Square should not be a subclass of Shape).

In general, LSP violation causes OCP violation because there is no meaningful action that a 'closed' function can take without needing knowledge of specific subclasses in the type hierarchy.

The standard example of this is to have a Circle class be a subclass of an Ellipse class that has a resize(xaxis,yaxis) method. Unless the semantics of resize are so diluted as to be largely useless ('maybe resize yourself or throw an exception') then subclasses can end up in a state that is inconsistent with anything meaningful/useful to the 'closed' function that is calling its methods.

A good discussion of the LSP (including the 'Circle-Ellipse' issue) can be found here


Is there an algorithm to find all vertices that are inside of a shape?

It seems to me that the problem is not about graph theory, but computational geometry. Phrased slightly differently, your input is a set of two-dimensional points $P$ (corresponding to the coordinates of the vertices of some graph drawing) and a polygon $Q$. The task to determine a subset $P'$ of the points $P$ that are contained within $Q$.

One possible algorithm is to iterate over each point $p$ in $P$, and check whether $p$ is inside $Q$. This classic point in polygon problem has many simple and efficient algorithms.


Does Types and Programming Languages use a recursive equation to define a recursive type or its generator?

You've stumbled across the difference between isorecursive and equirecursive types.

Equi-recursive types say "types are (possibly) infinite trees, and a recursive type is the solution to a recursive equation". Specifically, $\mu x\ldotp T = [\mu x \ldotp T/x]T$. These are conceptually simple, but in practice difficult to work with, since deciding whether two types are equal (or worse, subtypes of one another) or not is tricky.

Conversely, isorecursive types say that recursive types are just syntax. You are allowed to unroll them according to the equation above, but $\mu x\ldotp T$ and $ [\mu x \ldotp T/x]T$ are fundamentally different types, and must use the explicit fold and unfold instructions.

If you keep reading Pierce, he will explain this in the book.

Answering your specific questions:

The "loop" is that the definition on the RHS or the = is allowed to reference the name defined on the left. This is awkward for theory, because we don't want to treat top-level definitions as special.
Yes, $\mu$ is similar to $\lambda$ in the sense that they both bind variables. However, it's different in that there's always a very specific thing that gets plugged in for the bound variable with $\mu$, whereas $\lambda$ is useful precisely because we can plug the variable with anything. Also, the bound variable of $\mu$ denotes a type, whereas with $\lambda$ it denotes a term.
Yes, and that's the point of the $\mu$ operator. It says "I am the syntax that takes the generator for a type, and turns it into an actual type you can use like any other type in your program." And it make explicit the role of $X$ in the equation your outline.
Again, this is the job of $\mu$ by definintion. It is the piece of syntax that says "given the generator, tie the knot and make it an actual type."

The thing is, you can't really understand $\mu$-types on their own. Otherwise it's just syntax. The key is in the type rules for $\mu$ types. For isorecursive types, there are fold and unfold rules that allow us to "run the generator" one step. For equirecursive types, there are special rules in how type equality is determined that allow us to treat $\mu x \ldotp T$ as actually being the solution generated by the recurrence equation. But, these type rules will change depending on the specific language or calculus you're using.


Why is the following language not context-free?

Your first approach is not very clear. What are $n$ and $m$? You have to fix a word in order to use the Pumping lemma; please see our reference question for how it's done.

Your second approach is fundamentally flawed as CFL is not closed against complement, i.e. your PDA construction does not work. Also, note that $L^c$ does not only contain words of the form $a^nb^{n^2}$, but also all that do not match $a^*b^*$.

Towards showing that $L$ is not context-free, note that $\mathrm{CFL} \cap \mathcal{L}(a^* b^*)$ is closed against complement (see here). Therefore, if $L$ was context-free so would be

$\qquad L' = \{a^n b^m \mid m = n^2\}$.

It is easy to show that $L'$ is not context-free by using the Pumping lemma.


How can I find the center character of a two-tape Turing Machine in n transitions?

You explicitly try to find the middle position and then check whether it has a $c$ at that position. You can save some time by using the power of nondeterminism here. Choose any $c$ and check whether the number of symbols after that position matches the number before that position.

When the computation makes a wrong choice it will not accept. If there is indeed a $c$ at the middle position there is a guess that will accept.


Converting Binary Search Tree into Decreasing Ordered Linked List

The idea seems alright, just a tiny bit of comments:

InsertFront(T) should instead be InsertFront(T.root) (or you will get a linked list of trees).
As is, your function takes two arguments: a tree T and a linked list L, and add the in-order of T in front of L, and returns nothing. If you want a function that returns the in-order, you could add:

inOrder(T){
   L <- empty linked list
   toList(T, L)
   return L
}


The best estimate I know of can be found in Efficient networks for quantum factoring, by David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, and John Preskill, which gives $72 (\log N)^3$.

Having said that, a straight comparison of number of steps on a quantum computer versus number of steps on a classical computer is problematic for various reasons. First, as D.W.'s answer says, the number of steps depends on the exact architecture of the quantum computer, which we won't have until one is built. Second, the time required for a single step on a quantum computer is likely to be quite a bit slower than a single step on a classical computer.1 Again, we won't know how much slower until quantum computers exist.

1 If it was faster, you could use the same architecture to build a classical computer that would be at least as fast, and probably faster because for a classical computer, you don't need to worry about maintaining quantum coherence.


Nondeterministic polynomial time algorithm versus certificate/verifier for showing membership in NP

The certificate you propose might not be polynomial in the size of the input.
The input size of the problem is $O(n^3 + \log k)$, while your certificate has size $\Omega(k \log n)$. This is not polynomial, e.g., for $k = 2^n$.
Your certificate would work if you set it, e.g., to an empty list whenever $k = \Omega(\frac{n^2}{\log n})$, and modify the verifier to just check whether the input configuration of the cube is solvable for any such value of $k$ (thus ignoring the certificate).


Distinguishability of distributions that are not close given just one sample

Total variation distance, which is exactly half of your notion of distance, is equal to
$$
d_{TV}(D,U) = \frac{1}{2} \operatorname{Distance}(D,U) = \max_A \bigl|\Pr_{x \sim D}[A(x)] - \Pr_{x \sim U}[A(x)] \bigr|.
$$
You can take $A$ to be the indicator of $\Pr[D(x)] \geq \Pr[U(x)]$. The event $A$ might be hard to compute, but it could also be easy to compute. In the latter case, you will be able to efficiently distinguish between $D$ and $U$, even using only one sample. This may even be possible in the former case, though with an advantage less than the total variation distance.

Here is a proof of the equivalence between the two formulations.
Since
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
-\left(\Pr_{x \sim D} [\overline{A(x)}] - \Pr_{x \sim U}[\overline{A(x)}]\right),
$$
where the overline represents negation, we have
$$
\delta_{TV}(D,U) = \max_A \bigl( \Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \bigr).
$$
Let $S = \{ x : A(x) \}$. Then
$$
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] =
\sum_{z \in S} \bigl(\Pr_{Z \sim D}[Z = z] - \Pr_{Z \sim U}[Z = z]\bigr).
$$
This formula makes it clear that an optimal choice for $S$ is
$$
S = \{ z : \Pr_{Z \sim D}[Z = z] \geq \Pr_{Z \sim U}[Z = z] \}.
$$
For this choice of $S$, we have
\begin{align}
d_{TV}(D,U) &=
\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)] \\ &=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] \\ &=
\bigl(1-\Pr_{x \sim D}[x \notin S]\bigr) - \bigl(1-\Pr_{x \sim U}[x \notin S]\bigr) \\ &=
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S].
\end{align}
By definition of $S$, we have
\begin{align}
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] &=
\sum_{z \in S} \Pr_{Z \sim D}[Z = z] - \sum_{z \in S} \Pr_{Z \sim U}[Z = z] \\ &=
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
\end{align}
Similarly, we have
$$
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] =
\sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr|.
$$
It follows that
\begin{align}
\mathrm{Distance}(D,U) &=
\sum_{z \in S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| + \sum_{z \notin S} \bigl| \Pr_{Z \sim D}[Z=z] - \Pr_{Z \sim U}[Z=z] \bigr| \\ &=
\Pr_{x \sim D}[x \in S] - \Pr_{x \sim U}[x \in S] +
\Pr_{x \sim U}[x \notin S] - \Pr_{x \sim D}[x \notin S] \\ &=
2\bigl(\Pr_{x \sim D} [A(x)] - \Pr_{x \sim U}[A(x)]\bigr) \\ &= 2d_{TV}(D,U).
\end{align}


What is the "description" of a Turing machine?

The description is a string that encodes the formal specification of the machine, comprising:

the set of states,
the start state,
the set of halting states (or, where appropriate, the sets of accepting and rejecting states),
the tape alphabet,
the input alphabet,
the transition function.

Some authors also explicitly include the identity of the blank symbol in the description of the machine; others leave it to convention (e.g., stating that the alphabet will always be $c_1, \dots, c_k$ for some $k$, and $c_1$ is the blank symbol).


The problem cannot be approximated. Consider the reduction that you described from k-clique to your problem but this time assign zero weight to the original edges. Any (multiplicative) approximation algorithm also solves the k-clique problem this is because it must return 0 if there is a k-clique.


I will assume that the alphabet is binary (not really important), and show that $Tape_M(t,i)$ cannot be computed in $o(t/\log t)$ time for every $M$.

Consider a Turing machine $M$, which on the empty input, loops for all integers $i$ and does the following:

Simulate the $i$'th Turing machine $M_i$ on the input $\left(g(i),i\right)$ for $\frac{g(i)}{\log g(i)}$ steps (the function $g$ will be determined later). If it produced output $r$, then write $\overline{r}$ in the $i$'th cell and never change that cell again (you can move forward on the tape and preform the next iterations on the rest of the tape).

Suppose for the purpose of contradiction that there exists a Turing machine $A$ which computes $Tape_M(t,i)$ in $f(t)=o(t/\log t)$ time. Let $j$ be a large enough index of $A$, i.e. $M_j=A$, such that for $t\ge j$ : $f(t)<t/\log t$ (one can encode Turing machines in such a way that every machine has infinitely many representations, e.g. by allowing redundant zeros at the end). When $M$'s loop reaches $j$, it executes $Tape_M(g(j),j)$, which according to our assumption, halts within $\frac{g(j)}{\log g(j)}$ steps with some symbol $r\in\{0,1\}$. $M$ then writes $\overline{r}$ in the $j$'th cell, and it is never changed again. Now suppose that up until the $j$'th iteration, $M$ used less than $g(j)$ time, then after $g(j)$ steps, $M$ has $\overline{r}$ written in the $j$'th cell, which contradicts the fact that $Tape_M(g(j),j)=r$.

It remains to pick $g$ in such a way that until the $j$'th iteration, $M$ uses less than $g(j)$ time. The time required for $j$ iterations is $T_j=\sum\limits_{i=1}^j \frac{g(i)}{\log g(i)}\le j\frac{g(j)}{\log g(j)}$, assuming $\frac{g(i)}{\log g(i)}$ is monotonically non decreasing. Now, we want to pick $j$ such that $T_j\le g(j)$, which is satisfied when $\frac{jg(j)}{\log g(j)}\le g(j)$, or equivalently $g(j)\ge 2^j$.


I'll assume that a prefix code is a set of words in which no word is the prefix of any other, and "maximal" means it is impossible to add any word to the set and keep this property.
Let $w$ be a maximal-length word that is not in $X$. There are two possibilities:

At least one (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could not add $w$ even if we first remove all words in $F$ from $X$;
No (shorter) word in $X \setminus F$ is a prefix of $w$, in which case we could add $w$ to $X$ without needing to first remove any words in $F$, contradicting the assumption that $X$ is maximal.


Separating two strings without a separating character

Just an extended note for the "quoting" techniques:

You can also pick one character of the alphabet (e.g. $a$) and interpret it as a space and use $aa$ for $a$:

 hello world  -> helloaworld
 amazing spacing -> aamaazingaspaacing

However it is easy to see that this approach can lead to ambiguities:

 a are doubled -> aaaaare doubled
                 --OK_DECODING   -> a are doubled
                 --WRONG_DECODING-> aa re doubled

These ambiguities can be avoided/ignored if we assume that the "special" character $a$ appears only in a well defined format and context.

Indeed this technique is still used for representing quotes or double quotes in well-known formats: e.g it is used for strings in the CSV format: every string is double quoted and the double quotes in a string are "doubled".

 COLUMN 1 | COLUMN 2            | COLUMN 3
 42        | My name is "Nobody" | He said "To be or not to be"
 43        | "Quote me"          | Charater " embedded

Are represented in CVS files as:

 42,"My name is ""Nobody""","He said ""To be or not to be"""
 43,"""Quote me""","Character "" embedded"

It is also used for single quotes in the SQL language:

 SELECT 'This is a quoted string: ''Hello world''!!!'

But more modern languages/formats usually prefer the escape technique (see Yuval's answer)


Why is it that O(N + P) where P < N/2 reduces to O(N)?

In the Big-O notation, constant factors are irrelevant.

Then if $N>P$, $O(N+P)$ reduces to $O(N)$, by swapping $N$ and $P$ we have that if $P>N$, $O(N+P)$ reduces to $O(P)$.


I'll provide an example model using linear regression, however the idea translates to classification in a straightforward manner.

Sparse linear regression is used when we have a model $y = X\beta + \epsilon$ where $y \in \mathbb{R}^n$, $X \in \mathbb{R}^{n \times p}$, $\beta \in \mathbb{R}^p$ and $\epsilon \in \mathbb{R}^n$ when $n \ll p$. If we expect only a small number of columns in $X$ to actually contribute to $y$ then we can impose a penalty on $\beta$ such that "non-important" columns $X_i$ have their corresponding $\beta_i = 0$. We can formally write this as $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_0$$
where $\|\cdot\|_0$ is the $\ell_0$ norm that counts the number of non-zero entries. Unfortunately fitting this model exactly is difficult. We can approximate this objective by using the $\ell_1$ norm instead. That is we find $\beta$ for $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_1.$$ This model is known as LASSO in the context of linear regression and can be fit by a variety of methods in relatively little time.

All of this hinges on $n \ll p$. If your data are of the form when $n \approx p$ or $n > p$ I'm not sure if sparsity will help much, as you should have enough data to guide inference to true $\beta$ values (provided other assumptions hold, heteroskedasticity, independence, etc). The key takeaway is that you have a large number of predictors and you suspect a small amount of them to actually characterize $y$.


NP-complete problems not "obviously" in NP

There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness.

[AN6] NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL
INSTANCE: Sequences $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ of pairs of integers, with each $b_i[j] \geqslant 0,$ and an integer $N$.
QUESTION: Is $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ not divisible by $z^N - 1$?
Reference: [Plaisted, 1977a], [Plaisted, 1977b].  Transformation from 3SAT.  Proof of membership in NP is non-trivial and appears in the second reference.

The other three I found in the appendix are:

[LO13] MODAL LOGIC S5-SATISFIABILITY
[LO19] SECOND ORDER INSTANTIATION
[MS3] NON-LIVENESS OF FREE CHOICE PETRI NETS


Is this problem just an application of traveling salesman? If not is it some other already "solved" problem?

This problem comes down to a transportation problem (actually the Wikipedia article is not very good), although it is not exactly the problem you are stating. As David Richerby stated in the comments, your problem is formulated contradictory, therefore I would suggest a reformulation, where you fix the number of vertices that each path visits. But while reading yourself into the capacitive transport problem, you will find out yourself what changes fit best for your task.
Solving these problems can indeed, as stated by Raphael, be solved via min-cost max-flow algorithms.
When you decided on a new version I am happy to extend my answer to fit your needs.


Scheduling Algorithm for aperiodic multiprocessor tasks

One technical term that might help you focus a literature search is "load balancing".  See, e.g.,

The Power of Two Choices in Randomized Load Balancing, Michael Mitzenmacher,  IEEE Transactions on Parallel and Distributed Computing, 12(10), pp. 1094-1104, 2001.


Difficult Question to Understand (Computer Artitechture)

Well, as binary typically goes, one bit represents two possible values: 0 and 1. With two bits there are a possible combination of four values: 0, 1, 2, 3 in hex/decimal/octal or 00, 01, 10, 11 in binary. Expand out to three bits you have eight values. 0 to 7 or 000, 001, 010, 011, 100, 101, 110, and 111.

Expand upon this and you'll have your understanding.

For reference (with a nice animation for counting on any base): https://www.mathsisfun.com/binary-number-system.html


Introduction To Algorithms 3rd Edition MIT Press: Red Black Tree insertion error in pseudo-code?

In an email with one of the authors it became clear that the following pseudo-code rule applies.

(this is not an actual quote, but the format seems better for this)

  Whenever there is an else clause. The first statement of that else clause will be on the same line as the else clause. This can be a variable assignment, an if-statement or other things.

If that was too abstract, the code from question should be interpreted as follows:

RB-INSERT-FIXUP(T, z)
  while  z.p.color == RED
    if  z.p == z.p.p.left
      y = z.p.p.right

      if y.color == RED
        z.p.color = BLACK   // case 1
        y.color = BLACK     // case 1
        z.p.p.color = RED   // case 1
        z = z.p.p           // case 1

      else                  // this is the difference compared to code in the question
        if z == z.p.right
          z = z.p           // case 2
          LEFT-ROTATE(T, z) // case 2
        z.p.color = BLACK   // case 3
        z.p.p.color = RED   // case 3
        RIGHT-ROTATE(T, z.p.p) // case 3

    else (same as then clause with "right and "left" exchanged)

  T.root.color = BLACK


Is it decidable whether a pushdown automaton recognizes a given regular language?

It is undecidable whether a PDA recognizes $\Sigma^*$, the set of all strings over the input alphabet.

Added. It is undecidable to check that $L(G)=\Sigma^*$ as a consequence of the fact that "non-valid" computations of a TM can be coded as strings of a CFG. This is Lemma 8.7 of Introduction to Automata Theory by Hopcroft and Ullman. The authors refer for this result to Hartmanis (1967), Context-free languages and Turing machine computations.

A convenient coding of the computations of a Turing machine $M$ is as follows. A configuration of TM $M$ is a string of the form $xpy$ where $uv$ is the contents of the tape, and the state $p$ is indicated at the postion where the head resides. It is important to note that computational steps of a TM are local changes: $ucpav \vdash uqcbv$ for the instruction $(p,a,q,b,L)$ where the head moves left, and $ucpav \vdash ucbqv$ for the instruction $(p,a,q,b,R)$ where the head moves right.

A valid computation can be coded as a string $w_0\#w_1^R\#w_2\#w_3^R\# \dots$ where $w_0 = q_0x$ codes the initial configuration on string $x$, and we have proper steps $w_i \vdash w_{i+1}$. The last configuration in the string should be final, i.e., have a halting/final state.

It is now an exercise to verify that the strings that are not valid computations can be generated by a CFG $G_M$ (or accepted by a PDA). The strings that do not consist of configuration sequences are even regular. Otherwise one non-deterministically guesses a position where not $w_i \vdash w_{i+1}$. This part of the string is generated by a grammar that is similar to one for $\{ x\#y^R \mid x,y\in \{a,b\}^* , x\neq y\}$.

If the TM $M$ has no accepted strings, it will have no valid computations, and all strings are generated by the grammar $G_M$.


Why do algorithms with runtime of O(n) are said to have asymptotic upper bound, when linear functions don't have asymptotes?

Word "asymptotic" is used to emphasize the condition $\exists n_0\in \mathbb{N}$ $\forall n> n_0$ for inequality $0\leqslant f(n)  \leqslant C g(n)$ and generally does not contain any mention of limit or asymptotic. Even well known definition of O big, using $\lim\sup \frac{f}{g}$, have sense only when limit point for O big is not limit point for $g$'s zeros.
As to linear function, for example $f(n)=an+b$, then it easy to find solution for $an+b \leqslant C n $ finding $C>a$ and taking $ n \geqslant n_0= \lfloor \frac{b}{C-a} \rfloor+1 >0$. So we obtain $f(n)=an+b \in O(n)$ i.e. linear function is O-big $n$.


How to prove NP-completeness of this variant of the set cover problem?

Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is.

Now by reducing set cover to your problem, given an instance $(U, \mathcal{F}, k)$ of set cover, where $U$ is the universe, $\mathcal{F} := \{F_1, \dots, F_m\}$ the collection of sets and $k$ the maximum number of sets in the answer. We build the instance $(U, \mathcal{F}', k')$ as follows. If $k$ equals 0, then we output No. Otherwise, if $U \in \mathcal{F}$, we output yes. Else, Let $\mathcal{F}' := \mathcal{F} \cup \{U\}$, which means we add a new set  to the collection, namely the set consisting of the whole universe. We also set $k' = k + 1$. We claim the original insatnce has a solution of size $k$ for the set cover problem if and only if the new instance has a solution of size $k+1$ of your problem.

For the first direction,  given a solution of size $k$ for thr set cover problem, add the new universal set to the solution to build a solution for your problem of size $k+1$. (Why does this work?)

Now the harder direction, given a solution for the built instance of your problem of size at most $k+1$, if the universal set is a part of thr solution, the  we can remove it to get a solution for the original insatnce of set cover with size at most $k$. If the universal set is not present, then remove any set from the solution (since you can switch this set with the universal set getting back to the previous case).

By this far we proved the hardness of the problem. For the completeness proof, note that given a solution of size $k+1$, we can count for each element in the universe how many times it was covered in the solution in polynomial time. Hence we can proof a positive witness in polynomial time and the problem is NP-complete.


Switching between user-level and kernel-level threads

Exceptional Control Flow

There is a process called exceptional control flow to deal with the problem of switching between kernel code and user code. Switching between user mode programs actually need the kernel code being executed between.

Context Switching

When a user mode program times out, an external timer triggers an interrupt. Then the operating system kernel takes back the control, save all registers used by the program. Then schedule another program to run.

Exceptions and Interrupts

There are some kinds of exceptional interrupts from outside, for instance user hit Ctrl-C or when you try to open a file (syscall), it will switch to kernel code. When the file is opened for you, the program will come back running. Another example is on modern virtual memory systems, if a memory requested is currently in a disk, not on memory, the system will interrupt the program by a page fault. Then the computer continue to run kernel code to fetch that portion of memory and come back to the program.


Min-plus matrix multiplication implementation

In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition.

If you want to adapt matrix multiplication to the tropical semiring, you literally need to replace every occurrence of $+$ with $\min$, and $*$ with $+$.

To this effect, look at the line:

  sum+= A[i][k]*B[k][j]

Let's rewrite it "properly", as:

  sum= sum+A[i][k]*B[k][j]

Then, in the tropical semiring, this becomes:

  sum= min(sum, A[i][k]+B[k][j])

And you're done.


Turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols

I'm assuming that $\_$ denotes the blank character. A strategy for the TM  you are looking for is the following:

Check if the input is a single $0$, if so accept.
Replace every other $0$ with $\_$. If, during this process, the number of encountered $0$s is odd, reject.
Pack all the $0$s together. This can be done as follows:

Reset the head to the beginning of the tape (search for a $0$ preceded by two $\_$).
Locate the last $0$ (i.e., the only one followed by two $\_$) and, in the process, remember if a $\_$ is encountered before it.
If no $\_$ is encountered you are done. Otherwise continue.
Replace the last $0$ with $\_$.
Locate the first $0$ and write write $0$ before it.
Repeat from step 3.2.

Repeat from step 1.


I have no comment on the precedence of the factorial operator; my inclination is to consider it to have higher precedence than other operators because of the almost universal rule that postfix operators bind more tightly than other operators.

When implementing that, you need to create a pseudotoken to modify the default precedence of the prefix operator:

%precedence PREFIX_OP
%right      '^'
%precedence '!'
%%
expr : '!' expr %prec PREFIX_OP
     | expr '^' expr
     | expr '!'
     | '(' expr ')'
     | T_NUMBER

(Using actual character constants in your grammar really makes it more readable, and it also simplifies writing the lexer. So I did that.)

To understand this, remember that precedence relations always compare the precedence of a reduction with the precedence of a shift. These are two distinct things; they only seem to be the same because (f)lex sets the precedence of a reduction (i.e. the right-hand side of a rule) to be equal to the precedence of the last non-terminal in the rule (unless it is specified explicitly with %prec). That's often the "right thing" but it leads to a lot of confusion because it makes it appear that the precedence comparison is between two objects of the same type.

In the resolution of !3!, the parser must decide what to do after seeing !3. The only thing it can do with the 3 (a T_NUMBER) is reduce it to an expr; there is no ambiguity and thus no need to consult precedence relations. (Consequently, %nonassoc T_NUMBER has absolutely no effect, which is which I removed it from the grammar.) It then has two options:

reduce '!' expr to expr
shift the second !

To decide, it precedence-compares the reduction expr: '!' expr with the terminal !. Since the precedence of the reduction was explicitly set with %prec PREFIX_OP this results in a comparison between reduction PREFIX_OP and shift !; the shift wins. The same would happen with 2^3! because the comparison will involve the reduction expr: expr '^' expr whose last terminal is '^' with the shift !.

In your original grammar, the precedence declaration

expr: expr '!' %prec T_FAC

had no effect whatsoever, because that reduction is never ambiguous (3 ! 2 is a syntax error; no grammar rule applies to it.) Furthermore, the ambiguity between the reduction expr '^' expr and the shift !  was incorrectly resolved because the terminal was declared as having lower precedence than the reduction. Just changing the order of the precedence list wouldn't have the desired result because that would also change the precedence of the reduction expr: '!' expr.


Calculating force between n points placed on the x-axis

Suppose that the charges are $q_1,\ldots,q_n$. You need to calculate, for all $i$,
$$
F_i = q_i \sum_{j>i} \frac{q_j}{(i-j)^2} - q_i \sum_{j<i} \frac{q_j}{(i-j)^2}.
$$
In matrix form, we get
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n
\end{bmatrix} =
\begin{bmatrix}
0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} \\
-1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\
\frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n
\end{bmatrix}
$$
What the FFT allows us to do is to quickly multiply by a circulant matrix. In order to obtain a circulant matrix, all you have to do is add $n-1$ dummy coordinates:
$$
\begin{bmatrix}
F_1/q_1 \\ F_2/q_2 \\ \vdots \\ F_n/q_n \\ \ast \\ \vdots \\ \ast
\end{bmatrix} =
\begin{bmatrix}
0 & 1 & \frac{1}{4} & \frac{1}{9} & \cdots & \frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \cdots & -1 \\
-1 & 0 & 1 & \frac{1}{4} & \cdots & \frac{1}{(n-2)^2}  & \frac{1}{(n-1)^2} & \cdots & \frac{-1}{4} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
\frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2} & \frac{-1}{(n-4)^2} & \cdots & 0 & 1 & \cdots & \frac{1}{(n-1)^2} \\
\frac{1}{(n-1)^2} & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \frac{-1}{(n-3)^2}  & \cdots & -1 & 0 & \cdots & \frac{1}{(n-2)^2} \\
\vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\
1 & \frac{1}{4} & \frac{1}{9} & \frac{1}{16} & \cdots & \frac{-1}{(n-1)^2} & \frac{-1}{(n-2)^2} & \cdots & 0
\end{bmatrix}
\begin{bmatrix}
q_1 \\ q_2 \\ \vdots \\ q_n \\ 0 \\ \vdots \\ 0
\end{bmatrix}
$$
We don't really care about the $n-1$ asterisked entries. The new matrix is $(2n-1)\times(2n-1)$, and so FFT still runs in $O(n\log n)$. Of course, if your FFT works only for powers of 2, you need an extra padding step.


Infinite Intersection/Union of regular languages

For every word $w$, there's a language $\{ w\}$, which is regular, and $\Sigma^* \setminus \{ w\}$, which is also regular.

But, we can express every language (regular or not) $L$ as an infinite union: $L = \bigcup_{w \in L} \{ w \}$, which is an infinite union of regular languages.

For intersection, you do the opposite:

$L = \bigcap_{w \not \in L} (\Sigma^* \setminus \{w \})$.

So, we know that there are regular languages, and non-regular languages, and they can all be expressed as infinite unions or intersections of regular languages.


Is properly quantified 3SAT complete for PSPACE and all PH levels?

QSAT with only 2 literals per clause was shown to be in P back in 1979.

Since the $\Sigma_k$ and $\Pi_k$ versions of QSAT can be reduced to equisatisfiable problems with 3 literals per clause using only a slight modification the method used to transform a SAT instance to 3SAT (i.e. putting all the new variables in the innermost existential group), those limited problems continue to be complete for their levels of the polynomial hierarchy.


Is there a way to access hard drives while computer sleeps?

Sure.  It all depends on the architecture of the machine.  For instance, if there is a co-processor that is awake and responds to the network requests by accessing the hard drive, that would be one way to accomplish it.

If you're asking about a specific product or technology, that is off-topic here.  But conceptually, you can certainly build a computer that has this capability.  Whether any individual computer does have that capability is a question about that specific product or technology.


Generating all strings that a regular expressions describe

There is a standard construction for converting regular expressions into finite automata (check here or any textbook on formal languages). Once you have such an automaton in hand (either NFA or DFA) you can enumerate all accepted strings with a breadth-first search from the initial state looking for finite states (ordered by length).

Be careful, though: in general, regular expressions specify infinite languages. You can easily specify a length limit, though.


Loop invariant for adding 2 arrays storing binary value of integer

Step 1: Fix the typo in c[i=]. That's obviously wrong. (Done).

Step 1a: Try what happens when your algorithm adds 11 and 01. Notice that the result is wrong.

Step 1b: Fix the bug in your code. Check what happens in your algorithm again.

Step 2: Write down what is true at the end of the function which proves that the code is correct.

Step 3: Write down what is correct after the last iteration where i = 1, before setting C [1] = carry, which will lead to the statement in Step 2.

Step 4: Write down what is correct after each loop iteration, for each value of i.

Step 5: Write down what must be true before each loop iteration to get the result in Step 4.

Step 6: Figure out how Step 4 leads to Step 5.

Step 7: Check that Step 5 is true before the first iteration.


Alternate proof of the Caro-Wei theorem for lower bounding the independence number

An algorithmic proof is given by Murphy [1, Section 1], where he attributes the algorithm to Erdös [2].

As a side remark, I don't know what the original proof of Caro or Wei is, but I believe the proof you mention is due to Alon and Spencer [3].

[1] Murphy, Owen. "Lower bounds on the stability number of graphs computed in terms of degrees." Discrete Mathematics 90.2 (1991): 207-211.

[2] Erdös, Paul. "On the graph theorem of Turán." Mat. Lapok 21. (1970): 249-251.

[3] Alon, Noga, and Joel H. Spencer. The Probabilistic Method. John Wiley & Sons, 2004.


Can a computer determine whether a mathematical statement is true or not?

The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:

Every even integer greater than two is a sum of two primes.

The class $\mathcal{C}$ contains all statements of the form:

For all natural $n_1$ there exists natural $n_2$ such that for all natural $n_3$ there exists natural $n_4$ such that ... there exists natural $n_{2m}$ such that $P(n_1,\ldots,n_{2m})$,

where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.
Another popular choice for the class $\mathcal{C}$ is:

The following algorithm halts: ...

In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.

It is crucial that the algorithm be required to answer correctly for all statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a single statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:

The statement is valid.

The statement is not valid.

Similarly, we can design an algorithm that answers correctly on two different statements $A,B$. One of the following will work:

The statement is valid.

The statement is not valid.

If the statement is $A$, then it is valid, otherwise it is not valid.

If the statement is $B$, then it is valid, otherwise it is not valid.

We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for infinitely many statements, whether they are valid or not.


Determine whether two collections of items can be paired

Yes. You're just looking for a maximum matching in the bipartite graph where one side is the items, the other side is the slots and there's an edge between an item and each slot it's compatible with.

There are a number of efficient algorithms for this. The standard method taught to CS undergraduates is the augmenting paths algorithm of Hopcroft and Karp.


Are divide and conquer searches applicable to unimodal decision problems?

No.  Any algorithm for this problem requires at least $n-2$ time in the worst case.  Thus, the problem requires $\Omega(n)$ time.  You can't use binary search.

There's a simple adversary argument: each time the algorithm reads some index in the array, the adversary just answers 0.  After the algorithm has read $n-2$ different positions in the array, there are still two possibilities for where the 1 could be, so whatever the algorithm outputs at that point is wrong for at least one input (there exists an input array that makes the algorithm wrong).


Dijkstra's algorithm: why are distances initialized to infinity and not some negative number?

If you read the algorithm closely, you'll not that edge weight relaxation is triggered if new_weight < old_weight. This comparison is naturally true if all undiscovered edges are initialized with infinity (or, in programming, the largest representable value), and the algorithm correctly picks up the first "real" value it finds.

If you used a negative value, you'd have to treat it as a special case which is a lot less nice.

Note that in classic algorithms, we often disregard the size of the stored numbers (RAM model, uniform cost model). If that is not a good model for your application you have to describe more closely how you represent numbers, and in particular infinity. In practice, you can represent infinity either by a special value that is larger than any number (that's the C++ constant you mention), or you just use the maximum weight you see in the input graph plus one.


You seem to be confused about terminology. You start correctly: "a problem is NP-hard". This already answers your question: hardness is a property of problems, not sets of problems or of instances.

To refresh, a problem is a question of the form, "Does the input object have this interesting property?" An instance is a specific object you're asking about.  So, for example, 3-colourability is the problem, "Can the vertices of the input graph be coloured red, green and blue such that there is no edge between vertices of the same colour?"  When you ask that question of a specific graph $G$, then $G$ is the instance.  (And a set of problems is just a set of problems: you know what a set is and you know what a problem is.)


This can be formulated as a mixed-integer quadratically constrained quadratic programming (MIQCQP) problem, integer programming with quadratic constraints and a quadratic objective function.   You can find off-the-shelf  solvers out there, and I think some of them support MIQCQP.  Unfortunately MIQCQP is a pretty hard problem, so it's hard to know whether this will be effective, for the size of problem you have.  But it could be worth a try.

You can encode the max by the two constraints $p_j \ge 0$, $p_j \ge (\sum_i X_ij - D_j)^2$, where $p_j$ is a variable representing $p(X,j)$.  Since you're going to minimize a sum of $p_j$'s, this suffices (the minimization objective will chose the smallest $p_j$ that satisfies both inequalities, which is the max).

Alternatively, if you're willing to remove the "squaring" in the definition of $p(X,j)$, this could be formulate as an instance of integer linear programming.


Simplex Algorithm: Why must the optimal value of the LP lie on the face or vertex of a polyhedron?

Suppose $P = \lbrace x: Ax \leq b \rbrace$ is the polyhedra, where $x \in \mathbb{R}^n$. Further assume $P$ is full dimensional, then let $x_0$ be some interior point in P. Let $c \in \mathbb{R}^n$ (and $c \neq 0$) be the objective function you are interested to minimize (say). Then since $x_0 \in int(P)$, there exists a ball $B$ centered at $x_0$ with radius $\epsilon > 0$ s.t. $B \in int(P)$. Now consider any unit vector say $u \in \mathbb{R}^n$ s.t. $c^t u \neq 0$ (notice that it is always possible to select such a $u$), then both ($x_0 + \epsilon * u$) and ($x_0 - \epsilon * u$) are in  $B$, so by extension also in $P$. Now evaluate the function at 3 points, namely $x_0, x_0 + \epsilon * u, x_0 - \epsilon * u$. The objective you would get are-:
$c^T x_0 , c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u) $. Clearly if since $c^T  u \neq 0 $, one of $c^T  x_0 + \epsilon (c^T  u) ,  c^T  x_0 - \epsilon (c^T  u)$ must be lower than $c^T x_0$. This illustrates that the objective at $x_0$ is greater than some other point on the ball, hence $x_0$ cannot be optimum. You can repeat this argument for every other interior point and claim that such an interior point cannot give the optimum. Hopefully this gave you the intuition. More generally, suppose a point $x \in P$, can be represented as convex combination of 2 other points $y, z \in P$, we can repeat the same type of argument and say that the objective at $x$ cannot be strictly lesser than the objectives at both $y$ and $z$. A vertex is an example of a point that cannot be represented as convex combination of 2 other points from the same polyhedron.


Fastest algorithm to decide whether a (always halting) TM accepts a general string

Dkaeae brought up a very useful trick in the comments: the Linear Speedup Theorem. Effectively, it says:

  For any positive $k$, there's a mechanical transformation you can do to any Turing machine, which makes it run $k$ times faster.

(There's a bit more to it than that, but that's not really relevant here. Wikipedia has more details.)

So I propose the following family of algorithms (with hyperparameter $k$):

def decide(M, w):
    use the Linear Speedup Theorem to turn M into M', which is k times faster
    run M' on w and return the result

You can make this as fast as you want by increasing $k$: there's theoretically no limit on this. No matter how fast it runs, you can always make it faster by just making $k$ bigger.

This is why time complexity is always given in asymptotic terms (big-O and all that): constant factors are extremely easy to add and remove, so they don't really tell us anything useful about the algorithm itself. If you have an algorithm that runs in $n^5+C$ time, I can turn that into $\frac{1}{1,000,000} n^5+C$, but it'll still end up slower than $1,000,000n+C$ for large enough $n$.

P.S. You might be wondering, "what's the catch?" The answer is, the Linear Speedup construction makes a machine with more states and a more convoluted instruction set. But that doesn't matter when you're talking about time complexity.


Balanced allocation-Hash table- overflow probability

A more formal statement of the claim is as follows. There is a constant $C > 0$ and for each $k$, a function $\epsilon(n)$ satisfying $\lim_{n\to\infty} \epsilon(n) = 0$, such that if you throw $n$ balls into $k$ bins, then with probability at least $1-\epsilon(n)$ the contents of each bin is at most $ \frac{n}{k} + C(\sqrt{(\frac{n}{k})\log k}+\log k)$.


Expected number of common edges for a given tree with any other tree

Let $T$ be your reference tree (on $n$ vertices), and let $R$ be the random tree. Label the edges of the tree randomly from $1$ to $n-1$. Let $X_i$ denote the event that the $i$th edge of $R$ is an edge of $T$. Linearity of expectation shows that the expected size of $T \cap R$ is $\sum_i \Pr[X_i]$. Each $X_i$ is a uniformly random edge, and so it belongs to $T$ with probability $|T|/\binom{n}{2} = 2/n$. Hence the expected size of the intersection is $(n-1) \cdot 2/n = 2(1-1/n)$.


Runtime analysis of bit sorting algorithm with input size and integer size

If you treat $b$ as a constant, then $O(2^b n)$ is $O(n)$, and $O(n)$ is right.

If $b$ is not a constant, $O(2^b n)$ is not $O(n)$.

I think it would help to review Landau notation.  The running time is whatever it is; it is some value $T(n,b)$ that depends on both $n$ and $b$.  The big-O notation helps us understand how this value grows as you increase $n$ but hold $b$ fixed, or how it grows as you increase both $n$ and $b$.  You have to decide which of those you want to understand (do you want to understand its behavior as you increase $n$ while holding $b$ fixed?  do you want to understand how it grows when you increase $b$ while holding $n$ fixed?  do you want to understand how it grows when you increase both of them?  that will lead to different results and different ways of applying big-O notation).


Citing from Wikipedia (https://en.wikipedia.org/wiki/2%E2%80%933%E2%80%934_tree)

Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.

Thus, since the squares in the bottom row do not hold data elements, they are not nodes of the 2-3-4 tree.
Then, using the definition of height from https://stackoverflow.com/questions/2603692/what-is-the-difference-between-tree-depth-and-height the height of your tree is 2.


What features of a problem make it NP-complete/hard?

By definition, a problem is NP-complete if it's in NP and every other problem in NP can be reduced to it. The only literal answer to the question is that one: essentially, a problem is NP-complete only if it can be proven to be NP-complete. Since proof is a creative activity, it's not possible to give a series of rules, along the lines of "If a problem looks like X, Y or Z, then it's NP-complete."

However, there are some common features. First, the problem must be in NP, which means that we must be able to efficiently check a potential solution (e.g., check a proposed colouring for a colouring problem). Of course, designing efficient algorithms is also a creative act but, usually at least, proving that a new problem is in NP is fairly straightforward.

Once I've convinced myself that a problem is in NP, the thing that usually makes me feel that it might be NP-complete are non-locality and the presence of some kind of conflicting goals. Examples:

Satisfiability problems are non-local in the sense that choices for the variables in one clause also affect many other clauses. There are competing goals in that clauses containing $X$ want us to make $X$ true, but clauses containing $\neg X$ want the opposite.
In colouring problems, we wish to use as few colours as possible but features of the graph cause us to need many colours. Choices for colours in one part of the graph may have cause problems far away (see, e.g., Erdös's famous result that, for any $k$, there are graphs of arbitrarily large girth that are not $k$-colourable despite the fact that having large girth means they look locally like trees).
In something like vertex cover, we're looking for a set that is, in a sense, "small but powerful". We can trivially find large vertex covers but the difficulty is in finding a small set that still does everything that we need.

Another feature can be that the "obvious" algorithm that you first think of seems to involve uncontrollable backtracking when you try to make it really work. For example, you might try to solve independent set greedily by starting with a single vertex and iteratively adding vertices that don't send any edges to the set you've built so far. But you soon realise that a bad choice early on can limit your options later and you start having to backtrack. Satisfiability problems tend to work like this, too.

However, be aware that adding even more restrictions to a problem can make it easier.  For example, everything I've said above might make you suspect that 2-colourability and 2-SAT are NP-complete. But it turns out that 2-colourable graphs are so special that you can easily detect them and the back-tracking in 2-SAT can be kept under control.


What is the running time of this recursive algorithm?

You can write your recurrence as
$$
T(n) = (n+1)(T(n-1) + 2T(n-2) + T(n-3) + 2T(n-4) + \cdots).
$$
In particular, $T(n) \geq (n+1) T(n-1)$. This means that the sequence $T(n)$ grows very rapidly, and in particular
$$
T(n-1) + 2T(n-2) + \cdots \leq T(n-1) \left[ 1 + \frac{2}{n} + \frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \cdots \right] = (1+O(1/n)) T(n-1).
$$
Therefore
$$
T(n) \leq (n+O(1)) T(n-1).
$$
This means that
$$
T(n) = O((n+O(1))!),
$$
and so
$$
T(n) = O\left(n^{O(1)} (n/e)^n\right).
$$
This improves on your bound by a square root.


Expander Graph - Is the following graph family an expander graph?

Given $n$, consider the set of vertices $S = \{ (a,b,c) : c < n/2 \} \subseteq V_n$. Assuming for simplicity that $n$ is even, this set contains exactly half the vertices. An edge connects $x \in S$ to $y \notin S$ iff $x = (a,b,n/2-1)$ and $y = (a,b,n/2)$, for a total of $n^2$ edges. Therefore the expansion of $S$ is $|E(S,\overline{S})|/|S| = n^2/(n^3/2) = 1/n$, which converges to zero.


Design patterns for simple text based scripting language?

The last time somebody asked this question, I replied: why not just use an existing language?

What you have right now is an API.

You can provide a library in which your commands are function calls, or method calls, or whatever suits you.  This saves you from having to design and implement a language, and it saves your users from having to learn yet another little special-purpose language. They still need to learn your API, of course.

I'd say this is the standard design pattern for exposing APIs: as libraries for one or more existing languages.

If you really want to create a new language, you need to specify and implement its syntax and semantics.

For dealing with syntax, using a parser generator is definitely the standard approach. Any language whose programs don't just consist of simple lists of statements will have nested structures and most will allow syntactic recursion (i.e. among the various types of language constructs, some can appear within themselves arbitrarily often). For instance, you may wish to allow a command invocation as an argument to another command invocation, or you may want to have a construct to express iteration or choice that can be arbitrarily nested. In that case, you don't want to parse and process nested constructs with regular expressions, you want grammars, and parser generators are the standard way to work with grammars.

As to the surface syntax, the basic way in which the source code is chopped up into meaningful tokens of your language, I think the most important general lesson is: keep it general, easily readable and context-independent. Make the structure of your programs easy to understand for humans and computers.  Examples not to follow are such atrocities as Makefiles or /bin/sh in which the correct application of whitespace and quotes is advanced witchcraft.

As to the semantics, one of the things to decide is what sort of programming paradigm to support.  Are all commands of a program executed strictly in sequence without anything else ever interfering?  Then, a standard, strictly sequential imperative programming language may be a good option. Can commands set concurrent events in motion, or can multiple programs be running at once?  Then, a fundamentally concurrent language may be more appropriate.

Another thing to decide is to what extent you want your language to scale. If scripts can grow large and can be invoked by other scripts, you probably want to provide mechanisms for preventing different pieces of code from biting each other in the leg (e.g. scopes for names, local variables). But this is probably a later concern.


Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Here's an approach that I suspect will work very quickly.

I suggest you start by enumerating all possible values for an $S_i$, i.e., all possible 6-element subsets of $S$ that contain exactly one element of $N$ as a subset.

How many such sets do you expect to find?  By a crude back-of-the-envelope estimate, I estimate there will be only a handful, maybe 10 of them are so.  This estimate might be wrong, but this would be easy for you to test.

Let $\alpha$ be the number of possible such sets (i.e., $\alpha$ counts the number of ways to choose a 6-element subset of $S$ that contains exactly one element of $N$, i.e., there are $\alpha$ possible values for each $S_i$).  I am predicting you'll find $\alpha \approx 10$, or something similarly small.

If this prediction is accurate, this suggests a simple, naive algorithm to enumerate the partitions: namely, enumerate all ${\alpha \choose 5}$ ways to choose five valid possibilities for the $S_i$, and check whether those five sets forms a partition.  The running time of this algorithm is $O(\alpha^5)$.  If $\alpha$ is very small, say $\alpha=10$, this will be plenty efficient.

If it turns out that $\alpha$ is a bit larger, you can optimize this naive algorithm a bit.  Enumerate all ${\alpha \choose 2}$ ways to choose two out of these $\alpha$ 6-element sets, say $S_4,S_5$.  Filter out pairs that have an overlap (i.e., an element of $S$ in common).  Now store them in a hashtable, keyed by $S_4 \cup S_5$.  The hashtable will contain $O(\alpha^2)$ entries and can be constructed in $O(\alpha^2)$ time.  Next, enumerate all ${\alpha \choose 3}$ ways to choose $S_1,S_2,S_3$.  If $S_1,S_2,S_3$ are pairwise disjoint, look up $S \setminus (S_1 \cup S_2 \cup S_3)$ in the hashtable to see whether there is pair $S_4,S_5$ that can be combined with $S_1,S_2,S_3$ to form a full partition of $S$.  The running time of this optimized algorithm will be $O(\alpha^3)$.

And note that if $\alpha$ is indeed small, say $\alpha=10$ as I'm predicting, then it will be easy to enumerate all $\alpha$ possible values for an $S_i$.  You just enumerate all possible elements of $N$, then try extending each with three more elements of $S$, one by one, testing each one to make sure that the resulting set does not contain any other element of $N$ as a subset.  (In other words: select an element $T$ of $N$; select an element $x$ of $S \ T$, and check that $T \cup \{x\}$ does not contain any other element of $N$ as a subset; select an element $y$ of $S \setminus (T \cup \{x\})$, and check that $T \cup \{x,y\}$ does not contain any other element of $N$ as a subset; select an element $z$ of $S \setminus (T \cup \{x,y\})$, and check that $T \cup \{x,y,z\}$ does not contain any other element of $N$ as a subset.  Each step is pretty easy to do, and the overall running time should be very fast, assuming that $\alpha$ is indeed small as I expect.)

So, I suggest you start by running a little experiment to measure $\alpha$, then see if any of these algorithms is fast enough.  If it's not, edit your question to provide more details, including the value of $\alpha$.

Why do I estimate that $\alpha$ might be about 10?  Here's my crude back-of-the-envelope calculation.

First off, there are ${30 \choose 6} \approx 2^{19}$ ways to choose a 6-element subset of $S$, and ${30 \choose 3} \approx 2^{12}$ ways to choose a 3-element subset of $S$.  Therefore, $N$ contains about half of the possible 3-element subsets of $S$: in other words, if we pick a random 3-element subset of $S$, it'll be in $N$ with probability about 50% (roughly).

Also, for any 6-element subset $S_i$ of $S$, there are ${6 \choose 3} = 20$ ways to choose a 3-element subset of $S_i$, and each one has about a 50% chance of being an element of $N$.  We want there to be exactly one 3-element subset of $S_i$ that is in $N$.  This is like doing 20 coin flips, and we want to get exactly one heads (and the rest tails).  The probability of that is ${20 \choose 1} \times 2^{-20}$, i.e., $20/2^{20}$.  So, if we pick a 6-element subset of $S$, it will have probability about $20/2^{20}$ of being a valid possible value for some $S_i$.

Finally, there are $2^{19}$ possible 6-element subsets.  So, we expect that about $2^{19} \times 20/2^{20} = 10$ of them will be a valid possible value for $S_i$.  So, I'd expect $\alpha \approx 10$, using this crude argument.

This is a very crude estimate, because it assumes everything behaves randomly.  It is not rigorous, both because your set $N$ might not be random; and also because I made independence assumptions all over the place, even though things are not independent.  So, you will need to check empirically whether this estimate turns out to be accurate or not -- fortunately, that should be pretty easy to do.


CSP Forward checking with n-ary (and binary) constraints

Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking.

Another further improvement would be assigning a least constraining value (LCV) to a variable with minimum value in the domain (MRV).


Prove that the following language is not a regular language

Assume towards contradiction that the language is regular.
Let a be the "pumping length" given by the pumping lemma.
Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$.
By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$,
$|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$.
Consider $w' = xy^0z$.
Note that the length of zeros in w' is strictly less than p, and that the length of ones in w' is still exactly p. Also note that the length of zeros in w' is at least 2 since $z$ itself contains at least two copies of zero. Therefore, the number of zeros in w' is $ 1 < k < p $.
But in order to be in $L$, $w'$ has to satisfy $p \ \ mod \ \ k = 0$, which is equivalent to $k | p$ - contradiction!


Find if two numbers are linked by a greatest common divisor

That's an interesting problem. First of all, calculating directly the gcd between two numbers is clearly the fastest way to decide if they are connected. But as you noticed, quite unefficient for your problem.
A solution is to use prime factorization. Let's denote $P(z)$ the multiset prime factorization of a number $z$. Thus, you note that $gcd(x, y) = P(x) \cap P(y)$.
Once you have the prime factorization $P(x_0)$ of a number $x_0$, you may compute all sub-multisets (there are $2^k$ for $k$ primes values), and if the product $p$ of any sub-multiset is above $g$, any multiple of $p$ lesser than $n$ is connectected to $x_0$. Also note that all these multiples are a clique.
In fact, to generate all the connected numbers, you are only interested by "irreductible" sub-multisets. By irreductible, I mean that removing any (the smallest) prime factor would make the product lesser than $n$. Indeed, a reductible sub-multiset is already a multiple of an irreductible one and would generate no new connection. This may help to prune the loop on all sub-multisets of $x_0$.
Let's take a small example: $n = 100$, $g=10$, $x_0=60$.
$P(x_0) = \{2, 2, 3, 5\}$. The irreductible sub-multisets above $g$ are:

$P(12) = \{2, 2, 3\}$ => generating connections to $12 \times [1, 8]$
$P(15) = \{3, 5\}$ => generating connections to $15 \times [1, 6]$
$P(20) = \{2, 2, 5\}$ => generating connections to $20 \times [1, 5]$

Thus, we may generate the exhaustive list of the numbers conneted to $x_0$: $12, 24, 36, 48, 60, 72, 84, 96, 15, 30, 45, 75, 90, 20, 40, 80, 100$.
Also note that by construction you already have partially the prime factorization of all these numbers.
In your question, it is quite unclear of what may be the limits of ($n$, $g$). Or if your several ($x$, $y$) share the same ($n$, $g$). What I discussed until now is the fastest way I found to explore the graph of connections. But for very high ($n$, $g$), it may be unconvenient to list explicitely all connections of a number. If you do a BFS/DFS, an important point is that there is no point to explore again the clique of an irreductible multiset. In fact, I think I would try to do the BFS/DFS on the graph of these irreductible multiset instead of the graph of the number values.
Also remember that it may exist no path between $x$ and $y$. For example with $g = 20$ and $n = 80$, one may identify some connected components:

$\{31, 62\}$
$\{35, 70\}$
$\{21, 42, 63\}$
$\{25, 50, 75\}$


Heap-like data structure allowing peek at largest & smallest

One simple approach is to use a max-heap.  Separately keep track of the minimum element stored in the heap.  Then all operations can be done relatively efficiently:

Load from array can be done in $O(n)$ time, building Build-Heap.
Each of the peek operations takes $O(1)$ time.
Decreasing the maximum element can be done in $O(\lg n)$ time.  You decrease it and fix up the heap property (or extract it and re-insert it). Then, check whether it got reduced below the previous-smallest and if so update the minimum.

This seems likely to be reasonable for many workloads.

Alternatively, you could store the elements as a balanced binary tree with the leaves in sorted order.  Keep track of a pointer to the leftmost leaf and a pointer to the rightmost heap.

To load from array, sort the elements and then create a balanced binary tree; this can be done in $O(n \lg n)$ time.
All of the peek operations take $O(1)$ time.
The decrease operation can be implemented in $O(\lg n)$ time, by deleting the maximum and then inserting it in the new place, using standard data structures for balanced binary trees that support $O(\lg n)$ time insertion and deletion (e.g., AVL trees, red-black trees, etc.)

This too will likely be reasonable for many workloads.


Model Counting for Sum of Conjunctive Formulas

When $C = 0$ and each $f_i$ depends on two inputs, your problem is equivalent to #2-MONOTONE-SAT, which is #P-complete, see for example this question on cstheory.


A NFA is defined so that if there is any accepting path for the given input string, it will accept. It's perfectly allowable for an NFA to have two paths to acceptance. If no path accepts, then the NFA doesn't accept.


Finding all possible simple directed graphics given a set of nodes

Any of those will work, as long as you view the graphs $A\to B$ and $B\to A$ as different graphs. If you view them as being the same graph, then things are much more complex as you have to either do isomorphism testing or somehow enumerate in a way that doesn't produce isomorphic graphs more than once.

The fundamental barrier is that, in an $n$-vertex digraph has $n(n-1)$ possible edges, each of which may be present or not, so there are $2^{n(n-1)}$ possible digraphs on $n$ vertices. Your program must output all of these which is going to be infeasible for all but small graphs.


Much of the interest in circuits stems from the following implication:
$$
\mathsf{NP} \not\subseteq \mathsf{P/poly} \Longrightarrow \mathsf{P} \neq \mathsf{NP}.
$$
In words, if we show that some problem in NP doesn't have polynomial size circuits then we have proved that P≠NP.

Unfortunately, we don't really know how to prove lower bounds on general circuits. We do know how to prove lower bounds for constant depth circuits and for monotone circuits, which is the main reason we are interested in these models at all.

We already know of functions in $\mathsf{NP}$ which don't have polynomial size constant depth circuits. Unfortunately, these functions are in $\mathsf{P}$, and so won't help in proving $\mathsf{NP} \not\subseteq \mathsf{P/poly}$. What we want is to improve our techniques so that they apply for circuits with polynomial depth — that would show that $\mathsf{NP} \not\subseteq \mathsf{P/poly}$.

Now, to your question. While it is true that every function can be represented as a CNF and so as a constant depth circuit, sometimes allowing larger depths makes a big difference. For example, Parity has an exponential size CNF (and even exponential size constant depth circuits), but has a polynomial size circuit of logarithmic depth (and even a polynomial size formula). In other words, Parity exhibits an exponential blowup when converting from circuit to CNF. This shows that lower bounds on CNFs (probably) won't be able to separate P and NP according to the program laid out above.


Is there a bounded-time algorithm for Envy-free cake-cutting?

A bounded-time algorithm for the problem has been presented by Haris Aziz and Simon Mackenzie (A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents, arXiv:1604.03655, April 2016).


Find every edge for which every s,t-path in a DAG goes through that edge

Compute the dominator tree of the flow graph $(G,s)$, i.e., the graph $G$ with source node $s$.  Let $s=v_0,v_1,\dots,v_{k-1},v_k=t$ be the sequence of nodes in the path from $s$ to $t$ in the dominator tree.  Check each pair $(v_i,v_{i+1})$ of consecutive nodes in this sequence; if it is an edge of $G$, it is visited on every $s,t$-path, so output it.  It is possible to see that this enumerates all such edges.
The running time is nearly linear time.  It is possible to compute the dominator tree in nearly linear time, and then the rest of the algorithm clearly runs in linear time.  In particular, the Lengauer-Tarjan algorithm computes the dominator tree in $O(E \alpha(E,V))$ time, where $\alpha(E,V$) is an inverse Ackerman's function -- thus nearly linear.  There is also an $O(V+E)$ time algorithm by Buchsbaum, Kaplan, Rogers, and Westbrook and by Georgiadis and Tarjan, but it is more complex to implement in practice.  If you are interested in ease of implementation, you might also be interested in work by Cooper, Harvey, and Kennedy.


Thanks to G. Bach and Yuval Filmus.

If every $A, B \in NP$ and $A \oplus B \in NP$, then let $E$ to be some language $E\in NP$. Since $\Sigma^*\in NP$ then $E \oplus \Sigma^* \in NP$. But $ E \oplus \Sigma^* = \bar E$, so $\bar E \in NP$, and we got that $NP \subseteq coNP$.

Let $D$ to be some language $D\in coNP$ ($\bar D \in NP$). Since $\Sigma^*\in NP$ then $\bar D \oplus \Sigma^* \in NP$. But $ \bar D \oplus \Sigma^* = D$, so $\bar D \in NP$, and we got that $coNP \subseteq NP$.

And then $NP = coNP$.


Big theta notation in substitution proofs for recurrences

By definition, a function $f(n)$ is $\Theta(n^2)$ if there exist constant $b,c,N$ such that for all $n \geq N$,
$$ bn^2 \leq f(n) \leq cn^2.$$
In particular, as long as $n \geq N$, we can always replace $f(n)$ by $cn^2$ when upper-bounding an expression.
In your example of $cn^2 + n$, when $n \geq 1$ we have $n \leq n^2$ and so $cn^2 \leq (c+1)n^2$.