If you set both the values and the weights of each item corresponding to the lowest four levels to $0$, this problem is exactly the standard knapsack problem, so it is no easier than the standard knapsack problem, i.e. it is NP-hard.

You can use the dynamic programming algorithm for the standard knapsack problem to solve this problem, except that you should consider six cases instead of two: the item is not chosen, or its level $a,b,c,d$ or $e$ is chosen, then take the maximum value. The complexity is $O(nmW)$ where $m$ is the number of levels.


Is computing 2^n NP-complete problems EXPTIME or NEXPTIME complete?

I am not 100% sure that I understand the question but here is an attempt where I reformulate your problem.

You have $A,B\subseteq \{0,1\}^*$ and know that $A$ is NP-complete. Furthermore you have a reduction $f$ such that $f(x)\in B$ iff $x\in A$ and such that $|f(x)|$ is in $\log(O(|x|)$. Does that make $B$ NEXPTIME-hard?

Well, since $A$ is NP-complete, I can translate any question $y$ of the the form "does a nondet. TM $M$ halts in time $n$?" into an equivalent question $g(y)$ for $A$, using the reduction that establishes the NP-hardness of $A$. It is thus possible to translate an NEXPTIME-hard question $y$ of the form "does $M$ halts in time $2^n$?" into an equivalent $g'(y)$ for $A$. That reduction is very simple to describe but it produces instances of exponential size. If we could compute $f(g'(x))$ efficiently, we would have a reduction showing that $B$ is NEXPTIME-hard. This is possible in many cases --remember that $g'$ is very simple and that $|f(g'(x))|$ is in $O(|x|)$-- but this depends on knowing $f$ and how nicely it interacts with $g'$.

So I'd say that in general you cannot say that $B$ is NEXPTIME-hard but in many specific cases you'll manage to show it is.

(Final note: the above is about lower bounds. You cannot provide upper bounds for the complexity of $B$ from the assumptions. They only talk about the part of $B$ that is in the image of $f$).


How to prove closure property of regular languages using regular expressions?

You can prove it using this approach:

if $E$ is a regular expression then you can recursively define its reverse in this way:

if $E = \emptyset$ then $E^R = \emptyset$
if $E= (E_1)$ then $E^R = (E^R_1)$
if $E = a \in \Sigma$ then $E^R = a$
if $E = E_1 \cdot E_2$ then $E^R = E^R_2 \cdot E^R_1$
if $E = E_1 \cup E_2$ then $E^R = E^R_1 \cup E^R_2$
if $E = E_1^*$ then $E^R = E^{R\,*}_1$

You can prove that each "step" is correct and after a finite amount of transformations the procedure ends. At the end you get a regular expression (recursively built from $E$) that defines $E^R$.


Tight bound on the number of divisors of n

Assume your input is $n$. I also assume that you know that we measure the time complexity of an algorithm as a function of input length to this algorithm which is $\log_2{n}$ in this case. Then even the following simple loop would take exponential time (as a function of input size)

for i=1 to n:
   print "hi"
end

since it loops $n$ times, where $n = 2^{\log_2{n}} = 2^{\text{input size}}$.

More precisely, its running time (as Yuval Filmus commented) is roughly $O(nn^{1/{\log{\log{n}}}})$ which is still exponential. But since your algorithm is $O(n^2)$ it is pseudo polynomial (polynomial in the numeric value of the input, not input size).


What are the gap functions in the $AC$ hierarchy?

Razborov-Smolensky prove that the classes $\mathrm{AC}^0[p]$ and $\mathrm{AC}^0[q]$ are incomparable when $p$ and $q$ are distinct primes, which also implies
$$\mathrm{AC}^0\subsetneq\mathrm{AC}^0[p]\subsetneq\mathrm{ACC}$$
for prime $p$. That's about it: it is consistent with the present knowledge that uniform $\mathrm{AC}^0[6]$ coincides with all of the polynomial hierarchy PH, so no classes in between have been unconditionally separated (uniformly or nonuniformly).


For downloading a file, yes, this would work.

For a file download, there is a much simpler method: let $n$ be the total number of bytes of the file to be downloaded, and $k$ the number of bytes we have downloaded so far; then $k/n$ is a good estimate of our progress (the fraction of the file we've downloaded so far).

This turns out to be equivalent to your entropy-based notion, if we assume that the file contents are iid bits (i.e., uniform distribution over all possible files of that length).

So why count bytes instead of use entropy?  Well, if they're equivalent, they are just two different ways of describing the same thing.  However, it's much simpler to just count bytes.  Also, counting bytes has the advantage of being something that can be implemented.  Calculating the entropy of the file requires some way to measure entropy, which requires a formula -- and in this case, the formula is to count bytes, so we reduce back to the standard metric.

A progress bar for a software update isn't nearly as easy, because it often involves multiple different kinds of operations, which progress at different speeds.  Also, there is often no uncertainty: the installer knows exactly what files it is writing.  The purpose of the installation is to have a side effect.  We want to measure how long it will take until that side effect is completed.  It's not clear that this will fit into the entropy framework, because an entropy framework doesn't take into account how long it will take for those side effects to complete.  For instance, how long will it take to write one 100MB file and 1000 1KB files?  Hard to say, but I can tell you it's not simply proportional to the number of bits in the files, or the number of bits of entropy -- short files may require a seek, so the time to write a file is not proportional to the length of the file.


Order of argument application in lambda calculus

It seems that your book uses the notation
$$
\lambda x_1 \ldots \lambda x_n (M_1 \ldots M_k)
$$
instead of the more commonly found (in my experience)
$$
(\lambda x_1 \ldots \lambda x_n. M_1 \ldots M_k)
$$
Both notations are used for logical quantifiers by different authors, so it's not completely surprising. E.g., compare
$$
\exists x (P(x) \land Q(x))
\qquad {\rm vs} \qquad
(\exists x. P(x) \land Q(x))
$$

In the second style, the scope of binders ($\lambda x$, $\exists x$) extends as far to the right as possible.

About application order: the notation of your book
$$
\lambda x_1 \lambda x_2 \lambda x_3 (M) N_1 N_2 N_3
$$
stands for
$$
(((\lambda x_1 (\lambda x_2 (\lambda x_3 (M)))) N_1) N_2) N_3
$$
It is correct that the outermost application is of $N_3$ but this does not get bound to $x_1$. To see where $M_3$ goes, one first needs to reduce the function
$$
((\lambda x_1 (\lambda x_2 (\lambda x_3 (M)))) N_1) N_2
$$
to a lambda, and this involves applying $N_2$ first. That will require applying $M_1$ first, in turn.

The net effect is that $N_i$ gets bound to $x_i$.

Since you mentioned the Haskell notation, it is basically the same thing, even if Haskell uses the other notation (binders extend to the right as possible).


Guidelines for the future: start with reviewing the definitions.

According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w_0$."

OK, but this is cheating.

So let's start with an equivalent definition:

  A code $C$ is perfect if it attains the Hamming bound

what is this Hamming bound? Basically, it's a counting argument. If you have a word $w\in F^n_q$, how many words are there with in $F^n_q$ whose distance from $w$ is at most $e$?
If you do the counting, you will get there are exactly $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ such words. [Why? If the distance is $i$, choose $i$ indices (out of the $n$ possible indices), each such index can get any of the $q-1$ different values from $w$ in that index.]
The bound then says that if we split the universe into disjoint "balls" where each ball contains a center $w$ and all the $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ words within distance $e$ from $w$, we will have at most $$\frac{|F^n_q|}{size(ball)} = \frac{q^n}{\sum_{i=0}^e \binom{n}{i} (q-1)^i}$$ such (disjoint) balls.

A code that attains the Hamming bound means that any word is within distance $e$ of some codeword. That is, if you think on each codeword in $C$ as a center of a ball with radius $e$, then the codewords cover the entire universe: no word in $F^n_q$ is left outside some ball. Note that the distance of this code is $2e+1$: two codewords belong to two different "balls", and each ball is of radius $e$ (in Hamming distance).

But if the entire space is covered with balls, it means that any word is within distance $e$ of some codeword. This is exactly the first definition I wrote in this post. Thus, if you take any other word and make it a codeword, this word already belongs to some ball, so it is within distance $e$ from the center of that ball, and the new code cannot have a minimal distance greater than $e$.


A neural net will work with any arbitrary topology, as long as it has no cycles. We often use layers because it is easy to implement and because it allows a human to set parameters for how large the net should be, such as "four layers with 5, 6, 7 and 10 nodes, respectively".

I cannot find anything on the web about neural networks that are not organised into layers, but there is nothing principally impossible about them. Here's an idea for a rainy sunday afternoon: implement a neural net as a directed acyclic graph and use an evolutionary algorithm to find a good topology. Compare it to a layered neural net with similar numbers of nodes and edges.


Why does this grammar derive into $\beta \alpha ^*$ instead of $\alpha ^* \beta$?

Try some derivations:

$A\Rightarrow \beta$
$A\Rightarrow A\alpha\Rightarrow \beta \alpha$
$A\Rightarrow A\alpha\Rightarrow A\alpha\alpha\Rightarrow \beta \alpha\alpha$

The pattern is clear: starting from $A$, we'll generate strings of the form $\beta\alpha\dotsc\alpha$, in other words, $\beta\alpha^*$. Since at any stage we have $A$ on the left of the sentential form, we'll eventually generate strings with $\beta$ on the left.

If the grammar had been $A\rightarrow \alpha A\mid \beta$, then we'd derive strings of the form $\alpha^*\beta$.


How to simulate a k tape non deterministic turing machine with 2 tapes?

I think the idea is that we can run with just the first tape of the original machine while pretend other $k-1$ tapes exist. We pretend knowing states of other tapes by guessing every possible ones.

After the first tape executed, for those machines stopped in accept state, run with the second tape to see whether the guesses with respect to that tape were correct. Reject all wrong guesses. Repeat until all $k$ tapes are executed.

  Isn't the guess in non deterministic turing machines always correct?

For NDTMs, "correct guess" is that guess which will lead the machine into accept state.  We need to reject all incorrect guesses by verifying them to make only the correct guesses (for our problem) correct (for NDTM).


Globally-optimized nearest neighbors lookup

Here's one approach -- not necessarily the fastest.  This can be viewed as an instance of the assignment problem, or equivalently, finding a minimum weight perfect matching of a bipartite graph.  Imagine a bipartite graph with $\mathcal{A}$ being the set of vertices on the left, $\mathcal{B}$ being the set of vertices on the right, and an edge between every pair of vertices  whose weight is equal to the distance between those points.  Now you are looking for a perfect matching of minimum weight.  Once the graph is built, there are standard algorithms for this, such as the Hungarian algorithm or linear programming.

The first step in such an approach is to compute all-pairs distances, i.e., the distance between every point in $\mathcal{A}$ and every point in $\mathcal{B}$.  This takes $O(nma)$ time.  Based on your original question, it appears that $n \approx 20$, $m \approx 50,000$, and $a \approx 800$, so that part should be very fast.

Unfortunately, the Hungarian algorithm might be too slow.  The running time in this setting will be $O((n+m)^3)$, which might be too slow for your needs.  I think a tighter analysis shows that its running time is actually $O(n^3m)$, which might be fast enough for your needs, but I'm not certain about that.

If the Hungarian algorithm is too slow, here is a heuristic that you could try.  In each stage, we'll have a non-optimal solution and iteratively try to improve it.  (You can start with the greedy solution, to get the process started.)  Suppose our current solution assigns $f(b_j)$ to the point $b_j$.  Let $t$ be a threshold.  Filter the graph to include only edges $(a_i,b_j)$ where $\Delta(a_i,b_j) \le \Delta(f(b_j),b_j) + t$, and delete all isolated left vertices.  Now find a minimum weight perfect matching in that graph.  That will be a new solution that is at least as good as the previous solution.  In each stage, increase $t$ according to some schedule.  If you keep $t$ small, this won't necessarily give you the optimal solution, but it will make the Hungarian algorithm more efficient because it works with a smaller graph.

Theoretically, you can find a value for $t$ that enables you to prove that this will find the optimal solution (namely, a lower bound for the sum can be obtained by matching each element $b_j$ to its nearest neighbor in $\mathcal{A}$, ignoring the constraint that the elements of $\mathcal{C}$ be unique, and summing those distances; now if you let $t$ be at least the difference between the cost of the current solution and that lower bound, and apply this scheme, if it converges -- yields the same solution you started with -- then you know you've found the optimal solution).  However I don't know whether that will be useful in practice.

Anyway, this is one approach.  It might not be the best or fastest, because it doesn't take into account the geometrical structure.  But it's something you could try, to see if it meets your needs.


Comparing two recurrence relations w.r.t. asymptotic growth

You can sort of get a feel of the asymptotic behavior of a recurrence by flatting out the recurrence into an equivalent problem of the form $A_k = c_1(k) A_{k-1} + c_2(k)$.

First of all, to see that $O(n^2)$ is an extremely loose bound, notice how $T_1(16)$ expands out:
\begin{align*}
T_1(16) &= 4 T_1(4) + 3 \cdot 16 \\
&= 4 (2 T_1(2) + 3 \cdot 4) + 3 \cdot 16 \\
&= 8 + 2 \times (3 \cdot 16)
\end{align*}
Similarly, you'll find that $T_1(256)$ expands out to
\begin{align*}
T_1(256) &= 16 T_1(16) + 3 \cdot 256 \\
&= 16 (8 + 2 \times (3 \cdot 16)) + 3 \cdot 256 \\
&= \frac{256}{2} + 3 \times (3 \cdot 256)
\end{align*}
This strongly suggests that $T_1(2^{2^k}) = 2^{2^{k-1}} + 3k 2^{2^k}$, or $T_1(n) \approx \frac{n}{2} + 3 n\log_2 \log_2 n$. We can show this by first relaxing the domain of the function to those of the form $2^{2^k}$. Since $\sqrt{2^{2^k}} = 2^{2^{k-1}}$, we have
$$
T_1(2^{2^k}) = 2^{2^{k-1}} T_1(2^{2^{k-1}}) + 3 \cdot 2^{2^k}
$$
Let $A_k = T_1(2^{2^k})$, then
\begin{align*}
A_k &= 2^{2^{k-1}} A_{k-1} + 3 \cdot 2^{2^{k}} \\
&= 3 \cdot 2^{2^{k}} + 2^{2^{k-1}}(3 \cdot 2^{2^{k - 1}} + 2^{2^{k - 2}}A_{k-2}) \\
& \cdots \\
&= 2^{2^{k - 1}}A_{0} + 3 \cdot 2^{2^{k}} + 3 \cdot 2^{2^{k}} + \stackrel{k}{\dots} + 3 \cdot 2^{2^{k}}
\end{align*}

which shows that when $n = 2^{2^k}$, then $T_1(n) = \Theta(n\log\log n)$. Suppose we now open $T_1(n)$ over the whole real domain (that is, we relax the domain restriction imposed previously), then it should be easy to show that if $T_1(x) = 1$ whenever $x \in [1, 2]$, then $T_1(n) = \frac{n}{2} + 3n \log_2\log_2 n$ extends uniformly. (Proof: Use the same derivation above, but for some other $p \in [1, 2]$, do the case analysis on $p^{2^k}$ instead)

Therefore, we have $T_1(n) = \Theta(n \log\log n)$ and $T_2(n) = \Theta(n^2 \log n)$. Asymptotically, $T_2$ still dominates $T_1$.


What time complexity is a reachability algorithm?

You can calculate all reachable nodes in $O(V+E)$ time and $O(V)$ space, using DFS on the fly.

If you want to use less than $O(V)$ space, then the problem becomes much more challenging.  I recommend looking at how the SPIN model checker works.  See https://en.wikipedia.org/wiki/Bitstate_hashing.  Even then, the space required is probably still $O(V)$, just with a lower constant factor.


Prove that an $n$-length string has $2^n$ i18n-style abbreviations

The proof should be easy once you've modeled the problem sufficiently precisely. Your examples demonstrate some assumptions about possible abbreviations that you don't describe in the accompanying text.

The first and last letter are always kept unchanged. For example, hat can only be abbreviated h1t (or left unabbreviated).
If successive letters are abbreviated, then they must all be included in the same number. An equivalent way to state this is that you cannot have consecutive numbers in an abbreviation. For example, code cannot be abbreviated as c11e: if both the o and the d are abbreviated then the number 2 must be used to replace them both together.
You seem to waver as to whether the original word counts as a (trivial) abbreviation. I'll include it as an abbreviation in my answer.

Under these rules, an abbreviation is uniquely determined by the set of letters to abbreviate. A letter that can be abbreviated is determined by its position, which is an index between $2$ and $n-1$ where $n$ is the number of letters in the word. Therefore, for a word of length $n \ge 2$, the set of possible abbreviations is uniquely determined by the set of indices in the range $[2,n-1]$ to abbreviate. In mathematical terms, there is a bijection between abbreviations of a given word of length $n$ and the set of all subsets of $[2,n-1]$.

The set of integers $[2,n-1]$ has $n-2$ elements. The set of its subsets $\mathscr{P}([2,n-1])$ has $2^{n-2}$ elements. Given the bijection above, the number of abbreviations is also $2^{n-2}$.

Follow-up exercise (significantly harder): some of these abbreviations are useless, in that they are no shorter than the original. There is one trivial abbreviation where all the letters are kept, but there are also abbreviations which involve the replacement of a single letter by 1, such as h1t (no shorter than hat) or a2i1e (no shorter than a2ive). How many abbreviations actually shorten the word?


Succinct data structure to return occurences of letters until an index

To put it another way, you want to implement rank queries on an arbitrary string with an arbitrary alphabet.

If $n$ is of modest size, the usual approach is to use a Wavelet tree, associating a succinct binary rank index with each node in the tree. The shape of the tree is arbitrary, but using a Huffman tree gives you a data structure that is very close to zero-order entropy compression.

When the alphabet is very large, though, the size and implementation of the tree itself becomes a concern. A way to fix this which seems to work well in practice is to store $\left\lceil \log_2 n \right\rceil$ rank-select indexes of length $|S|$, but use an index implementation that it sensitive to local variation in density, such as esp or RRR.

This is covered in Claude & Navarro's 2008 paper, Practical Rank/Select Queries over Arbitrary Sequences. There may be some more recent work than this if you chase citations, but that's a good start.


Randomly selecting element from data structure, probability based on weight

I think it would work with a complete tree with elements stored in leaves, the whole thing being stored in an array (the same way as for heaps). You also need to store in each node the sum of the weights of all its children.
To be able to modify weight, you would also need a corresponding array (or hashtable if ids are not consecutive integers), to know where in the heap is stored an element with given id.

To know how to select an element, when exploring the tree t of weight t.weight, you can generate a number r between $0$ and t.weight, and go left if r < t.left.weight and right otherwise.
To insert, just put it at the last available leaf position and modify the weights of all its ancestors.
To delete, switch the position with the last leaf, and modify the ancestors of both the deleted node and the switched leaf.
To modify weight, use the corresponding structure to know the position of the element of given id, and modify the weights of its ancestors.

All operations can be done in $O(\log n)$.


Edit: My apologies, misunderstood what you meant by sentinel earlier. It seems to me that you are correct, and this is indeed a typo. When you include comparison against the sentinel at $a[0]$, you perform $i - 1 + 1 = i$ comparisons on a worst case sift.


Are there functions in the same Θ-class that are not linear transformations of each other?

Your proof must be wrong since the result is incorrect. For example, if $f=x^2$ and $g=x^2+x$ then $f = \Theta(g)$ but $f$ is not an affine shift of $g$. To see where the proof goes wrong, I suggest substituting these $f$ and $g$ in the proof and seeing which step fails. This is how one debugs their proof.


Is it true that P is not equal to deterministic linear space complexity class?

We do know that $\mathsf{P} \neq \mathsf{DSPACE}(n)$. This is proved in answers to a question on Mathoverflow. The idea is that $\mathsf{P}$ is closed under polynomial blowup while $\mathsf{DSPACE}(n)$ isn't (due to the space hierarchy theorem); consult the link on Mathoverflow for the details.


Why does Patience sorting find the longest increasing subsequence?

With the two insights from (II) it is obvious that no increasing sequence can use two cards (or more) from one pile.

This means: No increasing sequence can use more cards then the number of piles.
But patience sort returns the number of piles.

So: patienceSort(seq) >= correct(seq)

See also: Slides from Princeton with pictures.

Thank you very much Yuval Filmus :-)


How is this definition of the quantum Fourier transform to be understood?

The index $\mathbf{k}$ goes over all vectors in $\{0,1\}^n$ (which can be identified with $\mathbb{Z}_2^n$). The index $\mathbf{x}$ also has the same range, and $\mathbf{k} \cdot \mathbf{x} = \sum_{i=1}^n k_i x_i$. You can think of this sum as being computed modulo 2 (or in $\mathbb{Z}_2$) if you wish, since $(-1)^2 = 1$.

As an example, when $n = 2$ we get
$$
\begin{align*}
\tilde{a}_{00} &= \frac{a_{00} + a_{01} + a_{10} + a_{11}}{2}, \\
\tilde{a}_{01} &= \frac{a_{00} - a_{01} + a_{10} - a_{11}}{2}, \\
\tilde{a}_{10} &= \frac{a_{00} + a_{01} - a_{10} - a_{11}}{2}, \\
\tilde{a}_{11} &= \frac{a_{00} - a_{01} - a_{10} + a_{11}}{2}.
\end{align*}
$$

This is exactly the tensor square of the $2\times 2$ Hadamard matrix.


If regular expressions were allowed to be infinite, then any language would have been regular.

Given the language $L=\{w_1, w_2, \ldots\}$, we can always define the regular expression $R = w_1 + w_2 + \cdots$, which exactly defines $L$.
(Example: the regular expression $R_1 = \epsilon+0+1+00+01+10+11+\cdots$ defines $L_1=\{0,1\}^*$.)

We know that some languages are not regular, so this shows that infinite regular expressions describe a larger class of languages than finite regular expressions.


Number of $n \times n$ binary matrices whose rows and columns sum to at most $m$

Given $1 \leq m \leq n$, we want to determine the cardinality of the following set

$$\{ \mathrm X \in \{0,1\}^{n \times n} \mid \mathrm X 1_n \leq m 1_n \,\land\,  \mathrm 1_n^{\top} \mathrm X \leq m \mathrm 1_n^{\top} \}$$

Vectorizing, $\tilde{\mathrm x} := \mbox{vec} (\mathrm X)$, we obtain

$$\bigg\{ \tilde{\mathrm x} \in \{0,1\}^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\}$$

or,

$$\bigg\{ \tilde{\mathrm x} \in [0,1]^{n^2} : \begin{bmatrix} 1_n^{\top} \otimes \mathrm I_n\\ \mathrm I_n \otimes \mathrm 1_n^{\top}\end{bmatrix} \tilde{\mathrm x} \leq m \begin{bmatrix} \mathrm 1_n\\ \mathrm 1_n\end{bmatrix} \bigg\} \cap \mathbb Z^{n^2}$$

Thus, we want to count the number of integer points inside a convex polytope, or, in other words, to count the number of solutions a given integer program (IP) has. Take a look at De Loera's survey [0] and the references therein.

[0] Jesús De Loera, The Many Aspects of Counting Lattice Points in Polytopes, 2005.


Genetic Algorithm Minimum Population Size

There is no minimum to population size but it has a few drawbacks when it is too low.

when it is too low your genetic algorithm is almost going to be a deterministic or greedy algorithm and besides that you are going to lose the effect of weak answers. it has been proved that even the weakest answer can move the algorithm to a good answer. The nature of genetic algorithm is randomization and bias to better answers, when the population size is too low non of these are regarded.

When the population size is too low the population is going to lose the diversity so most likely your algorithm will fall in local optimums.

When the population size is too low you will face a few problems in Replacement step. because the population size is too low you will have to reject the unfeasible answers and it is a very bad idea for more illustration, look at this picture:

Let the red color be all of the answers (feasible and unfeasible), the yellow be the space of feasible answers, the green be the space of good answers that are around the optimums and the little blue spot be an unfeasible answer. As you can see an unfeasible answer is very close to the space of good answers so may be a little variation to this unfeasible answer lead to a very good answer, yes? that is why I say when the population size is too low you are going to limit yourself in Replacement step and you will have to remove the unfeasible answers and removing such answers has the bad effect that I just explained.

If the population size is too big your algorithm will be brute force! I recommended you to read the Schema Theory to know how to provide an appropriate population size.


Isomorphisms between regular graphs of same degree

Of course not.

Consider, for example, the cycle $C_6$ with six vertices and the graph obtained by the union of two copies of $C_3$. Then both are 2-regular, but they are obviously not isomorphic.

This is also the case if we restrict the question to connected graphs. Consider, for instance, the following two 3-regular graphs:

You can see they are not isomorphic because the second one contains cycles with six vertices that have chords; this is impossible in the first graph since it has precisely four six-cycles and you can see none of them have chords. (Or even easier: The second one has a five cycle, whereas the first one has only cycles with three, four, six, or more vertices.)

What you might be able to prove is that all 2-regular and connected graphs are isomorphic (see, e.g., this), but this is a big restriction compared to the original question.


$PCP\left(O(1),O(1)\right)=P$.

Suppose you are allowed to toss at most $r$ coins, and that the proof length is bounded by $l\in\mathbb{N}$. Given input $x$, you can compute the acceptance probability of the verifier relative to any proof in $\{0,1\}^{\le l}$. To do this, for every proof $\pi\in\{0,1\}^{\le l}$ and every possible outcome of the random coins $w\in\{0,1\}^r$, simulate $V^{\pi}(x,w)$ and count the number of $w$'s who caused $V^\pi$ to accept. Note that this requires only polynomial time in $|x|$. Now, accept $x$ iff during this process you have found a proof $\pi$ which causes $V$ to accept $x$ with probability $1$.

Note that the constant bound on the proof length does not immediately follow from the definition (in the above you only have a constant bound on the number of queries), but follows from the fact that if $L\in PCP(r(n),q(n))$, then $L$ has proofs of length $\le 2^{r(n)}q(n)$. See this question for details.


Two's complement max with a different base

As long as different 4 digit numbers in base b represent different decimal numbers, the particular notation one uses is not relevant to see how many integers can be represented. I'm not sure how the two-complement notation generalizes to the b-complement notation, but if the above property holds, then clearly there will be 9^4 representable integers.

My guess is that the first digit does not need to be 0 or 8, it can be any digit. That is, I think one could use the following encoding:

0000 0
...
4444 MAX
4445 MIN = -MAX
4446 MIN+1
...
8888 -1


Can we convert any given turing machine to a turing machine with only 2 states? if so, how?

You can't always find an equivalent Turing machine (in the sense that it has the same language) having less than $N$ states.

Note that the semantics of a Turing machine is determined by its states and transition function. After fixing the alphabet, to fully describe a machine you only need to specify how it reacts to every symbol from every state. This description has length of $O(|Q|\log |Q|)$. Thus, if you bound the number of states by some constant $N$, then there's only a finite number of different machines ($\sim N^N)$, which means that not every decidable language has an equivalent machine in this set.


You say that your goal is to create a model and compute the likelihood of a test sample using that model.  For that purposes, you do not need to find a way to interpret the hidden states, and you do not need to engineer the model so the hidden states have a meaning that you can understand.  Instead, let the standard Baum-Welch algorithm compute a reasonable model that fits the training data, and don't worry about the meaning of the hidden states.
If you had a physics model where you knew what the hidden states "should" be, based on some domain knowledge (e.g., about the movement patterns of bones and joints), then you could incorporate that into your model in hopes of improving the model... but that's not required.  Since you don't seem to start from such a place, there is no need to try to force the hidden states to take on any particular human-understandable meaning.


For the first fact, consider the array $1,\ldots,n,n+1,\ldots,2n$. Sorting its two halves doesn't alter the array. When the two halves are merged, the element $n+1$ would be compared against all elements in the left half.
The second fact is true for every $O(n\log n)$ sorting algorithm: such an algorithm performs $O(n\log n)$ comparisons overall, and so $O(\log n)$ comparisons per element on average.
The third fact is true for every comparison-based algorithm: any such algorithm must perform $\Omega(n\log n)$ comparisons, and so $\Omega(\log n)$ comparisons per element on average; in particular, some element is compared $\Omega(\log n)$ times.
Finally, let us note that the AKS sorting network corresponds to a sorting algorithm which performs $O(\log n)$ comparisons per element (since its depth is $O(\log n)$, and each element can only be compared once in each layer).


Empirical studies about benefits of Q&A sites for programming

There was a presentation on ICSE 2011, at the New Ideas and Emerging Results track, entitled "How do programmers ask and answer questions on the web?". They only had initial results, but they sounded very interesting and promising. Maybe you could contact the authors if you need more info (they're from the Dept. of Comput. Science, University of Victoria, Victoria, BC, Canada). Here is the full reference:

Treude, C.; Barzilay, O.; Storey, M. How do programmers ask and answer questions on the web?. In Proc. of the 33rd International Conference on Software Engineering (ICSE), 2011.

UPDATE: This paper was just mentioned at the Stack Exchange blog:

Chris Parnin, Christoph Treude, Lars Grammel, Margaret-Anne Storey. Crowd Documentation: Exploring the Coverage and the Dynamics of API Discussions on Stack Overﬂow. Georgia Institute of Technology, Tech. Rep, 2012. [PDF]


How to order the functions based on complexity $2^n$ vs $n^{\log n}$?

Firstly, your plot is wrong. See this:
https://www.wolframalpha.com/input/?i=plot%5B+y%3D2%5Ex,+y%3Dx%5Elog_2(x)%5D

Take the base 2 logarithm of them:
$\log_2 (2^n) = n$, $\log_2 (n^{\log n}) = \log n \cdot \log_2 (n)$.

As you can see, $n$ is larger than $\log n \cdot \log_2 (n)$; therefore $2^n = \omega(n^{\log n})$.

So, the answer to your first question is no. I also show you an easy proof sketch.


Expanding on Timot's comment, $\# P$ consists of all functions which can be expressed as the number of accepting computations of some non-deterministic Turing machine running in polynomial time. It is also the class of all functions which can be expressed at the number of non-accepting computations of some non-deterministic Turing machine running in polynomial time (exercise).

If $f \in \# P$ then $\{ x : f(x) \geq 1 \} \in N\! P$ and $\{x : f(x) = 0 \} \in \mathrm{co}N\! P$; and vice versa, if $L \in N\!P$ ($L \in \mathrm{co}N\!P$) then it can be expressed in the form $\{ x : f(x) \geq 1 \}$ ($\{ x : f(x) = 0 \}$) for some $f \in \# P$.


Is the set of Gödel numbers of computable constant functions recursively enumerable?

Your intuition is good: checking whether $x \in S$ is stronger than checking $x \in K$ ($K$ the halting problem, i.e. $K = \{ x \mid f_x(x) \text{ halts}\}$). In other words,

$\qquad\displaystyle \langle \operatorname{sgn} \circ f\rangle \in S \implies f \in K$.

However, the reverse does not hold and no similar implication works for $\overline{K}$, the reduction partner we really want (as it's not semi-decidable).

A small interlude: the title you chose does not actually fit the question! The set of all constant functions is in fact recursively enumerable, e.g. by

$\qquad\displaystyle \varphi_i(x) = i$

which is clearly a computable function. Many sets of functions are enumerable like this, but not all.

What you are really asking is: given a Gödel numbering (e.g. an encoding of all Turing machines), what about the set of all indices (read: programs) that compute this here set of functions? That's another thing entirely because of the properties such a Gödel numbering has. The distinction is important, see e.g. here.

The basic idea for a reduction is always this: build a function that depends on $x$ and whose encoding is in $S$ if and only if $x \in \overline{K}$ -- then we got a deal.

So, consider

$\qquad\displaystyle g_x(n) =
    \begin{cases}
        n, &f_x(x) \text{ halts after at most $n$ steps } \\
        1, &\text{else}
    \end{cases}
$

which is clearly computable. Note furthermore that given $x$, we can compute $y$ with $f_y = g_x$; such compilation is possible because we have (or can assume) a Gödel numbering. Now, clearly

$\qquad \langle g_x \rangle \in S \iff x \in \overline{K}$

holds; thus $S$ can't be semi-decidable since $\overline{K}$ would then be semi-decidable, too, contradicting what we know.


find shortest paths from source to all vertices using Dijkstra’s Algorithm?

I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's.

First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column i and j corresponds to the shortest distance from vertex i to vertex j.

Second, to mark the all-path shortest paths' path, you simply set the parent property of each vertex j to the current vertex i you are visiting from every time you have to relax the edge going to j from i. Keeping one set of vertices and edge will be sufficient as an APSP will also produce a tree, similar to a SSSP tree.


What are some of the best circuit separations that we know of and that we suspect?

For all uniform classes $\operatorname{UF}$, for essentially any non-uniform class $\operatorname{NU}$, one will

have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \:$, $\:$ since $\operatorname{NU}$ should be uncountable and $\operatorname{UF}$ is countable.

("Proof:" $\;\;\;$ By any reasonable definition of being uniform, for a language to be in $\operatorname{UF}$

there must be something in a particular at-most-countable set of things such that the

thing determines the language, so there are at most countably many languages in $\operatorname{UF}$.

On the other hand, for each subset $S$ of $\:\{\hspace{-0.03 in}0,\hspace{-0.05 in}1,\hspace{-0.03 in}2,\hspace{-0.03 in}3,...\hspace{-0.04 in}\}\:$,$\:$ the definition of $\operatorname{NU}$ should

mean that [the language consisting of exactly the strings whose length is in $S\hspace{.02 in}$] is in $\operatorname{NU}$.

In that case, since those languages are all different, $\operatorname{UF}$ will be uncountable.

"Therefore," one will have $\: \operatorname{NU} \not\subseteq \operatorname{UF} \;$.)

In particular, $\;\;\; \mathsf{non-uniformAC^0} \: \not\subseteq \: \operatorname{PSPACE} \;\;\;$ and

$\mathsf{non-uniformACC^0} \: \not\subseteq \: \operatorname{NEXP} \;\;\;$, $\;\;\;$ so both claims in your initial sentence are false.

It is far more interesting to ask which uniform classes

are subsets of which non-uniform classes.

$\operatorname{REG}$ $\: \not\subseteq \: \mathsf{non-uniformAC^0} \;\;\;$, $\;\;\;$ since $\;\;\;$ parity $\: \not\in \: \mathsf{non-uniformAC^0}$ $\:\:\:\:$.

$\operatorname{NEXP} \: \not\subseteq \: \mathsf{non-uniformACC^0} \;\;\;$; $\;\;\;$ which your question on cstheory was asking about.

$\operatorname{MA_{exp}}$ $\cap \hspace{.03 in}\operatorname{co-MA_{exp}}$ $\: \not\subseteq \:$ $\operatorname{P/poly}$ $\;\;\;$, $\;\;\;$ by page 16 of this paper.

$\operatorname{AM_{exp}}$ $\: \not\subseteq \:$ $\operatorname{(NP\cap coNP)/poly}$ $\;\;\;$, $\;\;\;$ by this paper. $\;\;\;\;\;$ (The right-hand-side of

the last non-containment is likely smaller than the class one would think it means.)

This paper shows that $\operatorname{MA_{exp}}$ can't be decided by circuits with "half-exponential" size.


Find path from s to t that goes through another node w

If you don't care about simplicity, a path from $s$ to $t$ that goes through $w$ is just a path from $s$ to $w$ concatenated with a path from $w$ to $t$.


Is the difference of a non-recursive and recursive set recursive?

The empty set is recursive, hence B cannot be the empty set.

You are right the B-A is recursively enumerable.

You cannot prove B-A is not recursive for a good reason: it may be
recursive. Maybe you can imagine an example of A recursive, B
not recursive, and B-A recursive. Hint: it is not even necessary that
B be recursively enumerable, or A recursive.

Proof that $B-A$ can have properties more specific than recursively
enumerability (i.e. compatible with being recursively enumerable),
indpendently of the properties of B.

   Consider 2 disjoint alphabets $\Sigma$ and $\Sigma'$, such that
 $\Sigma\cap\Sigma'=\emptyset$. Take $C=\Sigma'\,^*$ and
 $A=\Sigma^*$. Let $E$ be a non-recursive language in $\Sigma^*$. Let
 $B=C\cup E$. Then $B$ is a non-recursive language on the alphabet $\Sigma\cup\Sigma'$, because $C$ is recursive (trivially). Now you can see that $B-A=C$ since substracting $A$ removes precisely $E$, i.e. all words in B that are in $\Sigma^*$. So you have $B$ non-recursive, and both $A$ and B-A are recursive. Here I chose $A$ recursive. But I could have chosen any non-recursive language on $\Sigma^*$ that contains $E$.

Similarly, you cannot prove anything about A-B. Think why.


How to handle generator polynomial in CRC if given in (x+1) (x^3+ x^2 +1) form?

When computing CRC, we are working over the field of two elements. In this field, 2=0. Therefore
$$
(x+1)(x^3+x^2+1) = x^4+x^2+x+1.
$$


Help in understanding how to apply nonlinear function in hashing

Cryptographers have studied various schemes for using chaos theory to try to construct cryptographic primitives (hash functions, encryption algorithms, etc.).  None of them have been successful.  Chaos simply does not seem useful for designing cryptographic algorithms.

First, many of the chaos-based schemes have been broken.  They didn't have as much nonlinearity as the designers anticiapted.

Second, the chaos-based schemes are slower than the state of the art.  You need to iterate many times to get reasonable mixing/nonlinearity.  By the time you do that, you end up with something quite slow.  In comparison, we know of alternative schemes for hashing and encryption that are very fast and appear to be very secure.  So, chaos-based schemes are simply not competitive.

In my opinion, chaotic maps do not appear to be a promising angle for hashing or other cryptographic algorithms.


$$\mathcal{N}(x|m,\Sigma)=(2\pi)^{-k/2}|\Sigma|^{-1/2}\exp\left(-2^{-1}(x-m)^T\Sigma^{-1}(x-m)\right)$$
where $x,m$ are vectors of dimension $k$, $\Sigma$ is a $k\times k$ matrix, $|\Sigma|$ is its determinant. The vector $m$ represents the mean of the multivariate normal, and $\Sigma$ the covariance matrix, which must be positive definite.


Context-free languages are not regular but decidable; on the other hand recursively enumerable languages are not regular and only semi-decidable. So sadly only knowing about the non-regularity of a language does not help with determining its decidability.


What's the difference between environment and memory in terms of programming languages?

Functions

The terms "associate" and "map" together with "finite" indicate that both definitions refer to finite mathematical functions.

A (mathematical) function is a relation that associates each element of a set, the domain of the function, to a single element of another set (possibly the same set), the codomain of the function [Wikipedia].

Another way to put this, for finite functions are: a finite set of ordered pairs.

Map is usually defined as a synonym to function.

Thus the definitions could be rewritten as follows:

Environment

An environment is a finite function that associates each element in the finite set of variables (domain), to a single element in the finite set of values (codomain). The range would be the set of all possible values (possibly infinite).

Memory

A memory is a finite function that associates each element in the finite set of locations (domain), to a single element in the finite set of stored values (codomain). The range would be the set of all possible values (possibly infinite).

Sets

  Does this mean that environments are a part of memory?

Since this is about sets, if you by part mean subset, then the answer would be no.

However, the codomains are definitely related, if a variable is associated with a value in the environment, a location must also be associated to a stored value in the memory, that corresponds to the variable value.

Extending the Environment

  The part that especially confuses me is when we "extend the environment."

It seems the aim of the text is to build an interpreter. You start out with no variables declared (including procedures), i.e., an empty environment and then you interpret/parse/analyze the code to make these associations, i.e., extending the environment.

In Practice

It might be helpful to think of the memory as the values stored somewhere in the physical memory and the environment as the values that the interpreted process currently knows about.


All possible Red Black Trees with this set {1,2,3,4,5}

Testing all 120 insertion orders is indeed much to much work in order to check out all trees. Moreover, there might be trees that are valid, but which are not found by inserting keys in some order.

A better appraoch would be to designing the trees by level. The number of black nodes on each path is equal, so a RB-tree with five keys can at most have two levels with black nodes: three levels would need seven keys.

It is perhaps helpful to consider a black node together with its red children as one single node with 1,2 or 3 keys (and 2,3 or 4 children). (In that way we get 2-3-4-trees.) Now either (1) the root has 2 keys and three children with each a single child, or (2) the root has 1 key with 2 children with a total of 4 keys. Remember a node with two keys can be represented in two ways as a RB-tree (the red child can be left or right.)

According to the OEIS there are eight such trees. Good luck.


Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

An array is the only thing that will get you consistent lookup in constant time.

Removal & Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal


Pumping Lemma for regular languages (by Wikipedia):
Let $\displaystyle L$ be a regular language. Then there exists an integer $\displaystyle p\geq 1$ depending only on $\displaystyle $ such that every string $\displaystyle w$ in $\displaystyle L$ of length at least $\displaystyle p$ ($\displaystyle p$ is called the "pumping length") can be written as $\displaystyle w=xyz$ (i.e., $\displaystyle w$ can be divided into three substrings), satisfying the following conditions:

$\displaystyle |y|\geq 1$
$\displaystyle |xy|\leq p$
$\displaystyle (\forall k\geq 0)(xy^{k}z\in L)$

Task
The given Language is $L = \{a^nb^mc^{n+m}|m,n\geq 0\}$. We want to show that L is not regular through proof by contradiction using the pumping lemma.
First we assume that $L$ is regular as you wrote. This implies the existence of the pumping length $p$. You called the pumping length $n$ which might lead to confusion cause $n$ appears in the definition of the language; so I called it $p$. Since we make a proof by contradiction we need to choose a word $|w| \geq p, w\in L$ and show for every possible partition into $w = xyz, |xy|\leq p, |y|\geq 1$ that there is a $k$ such that $xy^kz\notin L$.
Now what $w$ could you choose? I think $a^pb^pc^{2p}$ is a good choice.
Because $w = xyz = a^pb^pc^{2p}, |xy|\leq p, |y| \geq 1$ implies that $x = a^{i}, y = a^j, i+j \leq p, j\geq1$ thus $xy^pz \notin L$ because the the string would look like $a^{i+p\cdot j}b^pc^{2\cdot p}$ and $i+p\cdot j + p \neq 2p$, so the property of the language is violated. That's how proof using the pumping lemma usually looks like.


Time complexity and space complexity in recursive algorithm

One thing comes in mind is memoization. Simple well studied problem for this is Fibonacci numbers, simple recursion is as follow:

fib(int n)
{
  if (n < 3)
    return 1;

  return fib(n-1) + fib(n-2);
}

But with memoization, we can use an auxiliary array to get rid of extra calls:

f[1]=f[2] = 1;
fib(int n)
{
  if (n < 3)
    return 1;

  if (f[n] == 0)
     f[n] = fib(n-1) + fib(n-2);

  return f[n];
}

This simple change, reduces the time from $\Theta(\phi^n)$ to $\Theta(n)$.

The memoization technique sometimes uses more memory, but very faster in time, and one of a tradeoffs that software developer should be care about it is this.

Explanation of the memoization of Fibonacci numbers:

First we create an array $f$, to save the values that already computed. This is the main part of all memoization algorithms. Instead of many repeated recursive calls we can save the results, already obtained by previous steps of algorithm. As shown in the algorithm we set the $f[1],f[2]$ to $1$.

In the first if we actually check whether we are in the start or not. But we can remove this if statement. But for make it simpler to read I left it.

In the second if, we check if the value of fib(n) is already computed or not. This prevents us from multiple call for the same number, for example suppose we want to compute f(6), then in normal recursion we have the first recursion tree as shown in the following figure and in the memoization version we have the second tree. The reason is, in memoization we just compute the green vertices one time and then we save them into the memory (array $f$) and if needed we fetch them later.

In the following figure, green nodes are parts which are necessary to be computed (in this way), yellow nodes are precomputed ones, and red nodes are the nodes that are repeatedly computed in the first recursion.

As is clear from the image, in the normal case we have just precomputed f(1) and f(2), but in the memoization case, all functions for less than $n-1$ are precomputed, and this causes exponentially smaller recursion tree. (In memoization number of red nodes is zero, which is exponential in the normal recursion).


position to insert element in inserionsort (equality of probablity)

Try counting the number of permutations where it is inserted in position $i$.  How does this number depend on $i$?  That will lead immediately to a proof.

In general, when you need to calculate a probability of some event, and you have a uniform distribution, one way is to use counting to compute the probability: count the number of outcomes where the event is true, and then divide by the total number of possible outcomes.


Is a set of TM deciding specific length of language reducible?

Here is a similar example, to get you started. Let $L_n$ consist of all encodings of Turing machines that accept some string of length $n$.

Claim: $L_{n-1}$ reduces to $L_n$.
Proof: Let $M$ be an input to $L_{n-1}$. Construct a new machine $M'$ which on input $x$, if $x$ starts with a zero then $M'$ rejects, and if $x=1y$ then $M'$ simulates $M$ on $y$. Then $\langle M \rangle \in L_{n-1}$ iff $\langle M' \rangle \in L_n$ (exercise).

Your proof will be different, but the proof technique will be similar.


Can an $NDTM$ simultaneously perform a set of operations on all strings of a given length?

The easier way to think of NTM's is not as they are capable of "spawning branches", but as they are capable of "splitting into two branches, and each branch knows who it is (the first branch is 0, and the second is 1)"
In this way of thinking (that also actually represents what's going on inside the TM), splitting into $2^b$ branches means doing the "split" operation $b$ times.
Lets do a simple example with $b=2$:
In the first split, we have two branches: 0,1.
In the second split, the "0" branch splits into branches "00" and "01" (notice that these are not numbers! They are strings) and the "1" branch splits into "10" and "11".
Notice that every string of length 2 is either one of the 4 final branches, and therefore this is how we would be able to non-deterministically check every string of length $b=2$.
The same applies for any other $b$ (note that if its not a constant, it will maybe harm the time or space complexity of the machine)


Is there a low degree vertex in planar graphs?

Yes, this is true.
It is a direct consequence of Euler's formula. The formula entails that the average degree is strictly less than 6, which implies the existence of a vertex of degree at most 5.
It doesn't have a name in itself, but Euler's formula is the overall subject.


Do there exist algorithms for which the Big-O cannot be found out?

There are some algorithms for which, as of today, we are not able to prove termination, much less to bound complexity.

A simple case is given by the Collatz function: in pseudocode

function Collatz(n):
  if n <= 1  then return 1
  if even n then return 1 + Collatz(n/2)
  return 1 + Collatz(3*n + 1)

It is believed that, for any natural $n$, Collatz(n) will eventually stop recursing. However, we do not know whether this is is the case. Consequently, we also do not know an upper bound for the time complexity of this algorithm.


Maximum-weight set of cliques of size 3 with no common vertices in undirected graph

This problem is NP-complete even when all edge weights are 1, since that restriction is equivalent to the problem Partition Into Triangles, which "Computers and Intractability" (Garey and Johnson, 1979) lists as NP-complete on p. 192, attributing the result to a personal communication from T. J. Schaefer in 1974, apparently based on a reduction from 3-Dimensional Matching.
So, no efficient algorithm can be expected. For an exponential-time exact algorithm, I would probably try branch and bound intertwined with maximum bipartite (2-)matching, as follows: At each stage, we have a vertex $v_i$, which we will take to be the lowest-numbered vertex of a triangle, and the decision is which of its neighbour vertices $v_j$ should become the highest-numbered vertex in the triangle. For each possible $v_j$, to test feasibility of the choice, create a new, bipartite graph with a vertex for each low+high vertex pair decided so far, as well as a vertex for each as-yet unprocessed vertex, and an edge between two vertices whenever the low+high pair represented by one would form a triangle in the original graph with the other and the latter vertex is numbered between the low and high vertices represented by the former. Run maximum bipartite matching on this new graph, and check that every low+high pair decided so far is saturated (adjacent to a matched edge) -- if this fails, then the current assignment of low+high vertices cannot be extended to a full triangle partition and the branch can be pruned. I think this algorithm, which chooses just 2 vertices within each triangle, will result in B&B tree depths of around 2/3rds the fully naive approach in which all 3 vertices of each triangle are chosen.


Since none of the comments gave the concrete answer, I'll write it explicitly here in case anyone needs it (like I did).

Firstly, unfortunately, the inverse of a band-limited matrix is a full (non-band-limited) matrix in general, so just filling out the entries of the inverse matrix would take $\Omega\left(n^2\right)$. So I'll assume you just want to solve a linear system $A x = b$.

Using the algorithm in this paper, a general band-limited matrix $A$ of size $n \times n$ with bandwidth $k$ can be decomposed into triangular $k$-bandwidth matrices $L$ and $U$ in $O \left( k^2 n \right)$ time. From there, $L U x = b$ can be solved quickly in $O(k n)$ time. So overall, the runtime will be $O\left(k^2 n\right)$. As a followup, if $k$ is constant, that means that the system can be solved in linear time (highly useful).


how do we demonstrate using Boolean algebra that these NAND and NOR gate combinations are XOR gates

The nice thing about small Boolean circuits like this, is there are only a few possible inputs.

With two input wires, there are $2^2=4$ possible inputs to your circuit: $00, 01, 10, 11$. You can test each one and write down its output. Then compare that to the XOR gate's outputs.

If the two line up, then the circuits are equivalent! And if they're not, something has to be adjusted.


How can context switch affect the modification of a variable?

A context switch is simply the operating system pausing the execution of one process and starting another. As such, context switches are required for any concurrency problem since, if there are no context switches, there's only one process executing so there is no concurrency.

In your example, the race condition occurs because what the function update really does is:

Read the value of myTotalAmount from memory;
Add amt to this value;
Store the result back in the memory.

Context switches at bad times can cause a race if the processes don't protect against that.  Let's say that myTotalAmount currently has value zero.

Process B reads the value of myTotalAmount, which is zero.
Process B calculates the new value 0+5=5.
Context switch.
Process A reads the value of myTotalAmount, which is still zero.
Process A calculates the new value 0+10=10.
Process A writes the value 10 to myTotalAmount.
Context switch.
Process B writes the value 5 to myTotalAmount.

(Note that ordering the steps 13456728 would give the same result.)


Recurrence relations and induction: guessing the right bound

For sure, $T(\sqrt{n})\leq T(n)$, so $T(n)\leq 2T(n-1)+n$, but this produces an exponential upper bound, which is correct but to big to be useful.
Anyway, in this case if we start from the solution of the recurrence $S(n)=S(n-1)+O(n)$, which is $O(n^2)$, we observe that $S(\sqrt{n})=O(n)$, so also the solution of $T(n)=T(\sqrt{n})+T(n-1)+O(n)$ is in $O(n^2)$.
I have to admit that this approach doesn't seem (also to me) very formal, so I've confirmed that guess by explicit calculation.
Indeed, suppose $T(n)=an^2+bn+c$, then $T(\sqrt{n})+T(n-1)+n=an^2+(1-a)n+b\sqrt{n}+a-b+c$: we have equality if $a=1$, $b=0$ and $c=-1$, so $T(n)=n^2-1$. Clearly, this is not an exact solution as it depends on the starting point, I mean, it is correct only if $T(1)=0$; in general you have to check that $T(n)=O(n^2)$ (actually, $T(n)=\Theta(n)$) by induction.

So, returning to your question: no, you cannot simply split the equation and take the solution with larger order of growth.
E.g., consider the recurrence $T(n)=T(n^{3/4})+T(n-1)+n$: if $S(n)=O(n^2)$, then $S(n^{3/4})=n^{3/2}$ is no more a $O(n)$, so we cannot conclude as before.
But if you have a recurrence of the form $$T(n)=T(f(n))+T(g(n))+O(h(n))$$
(with reasonable assumption of functions $f,g,h$, I mean, positive, monotone, ...)
and the solution of, say, $S(n)=S(g(n))+O(h(n))$ is such that $S(f(n))=O(h(n))$, then you can make the (more than) reasonable assumption that $T(n)=O(S(n))$, and confirm it by induction.


Is it feasible to solve this subset cover problem with SAT solver?

Optimization with SAT is usually referred as MaxSAT instead of Min SAT. In particular, I suggest looking for solvers for "weighted partial MaxSAT", for example MaxHS and RC2.

The problem size you have is fairly small in the context of modern MaxSAT-solvers, so yes it is worth trying. There are no guarantees that the solver will work efficiently, and it is very hard to predict if it will work efficiently, so the best thing to do is to try.


Partition into paths in a Directed Acyclic Graphs

This problem can be solved with minimum-cost flow in polynomial time.

The flow network should should contain source and sink vertices $s$ and $t$, and for each vertex $v \in V$ two vertices, $v_{in}$ and $v_{out}$. The vertex $v_i$ should have an edge form $v_{in}$ to $v_{out}$ with capacity $b_i$ and cost $-3$. For each original edge $(u, v) \in A$, create an edge from $u_{out}$ to $v_{in}$ with capacity $\infty$ and cost $0$. For each $v$, create an edge from source $s$ to $v_{in}$ with capacity $\infty$ and cost $1$ and an edge from $v_{out}$ to sink $t$ with capacity $\infty$ and cost $1$.

Now in optimal flow, the cost will be $2 \cdot P -3 \cdot \sum b_i$, where $P$ is the optimal number of paths used.


Reference/book recommendations for search data structure

I highly recommend MIT course on Advanced Data Structures, I was watching  Eric Demaines lectures, he shows multiple examples, here are some of them:

Van Emde Boas tree
Y-fast trie

Here some suggested reading from their website:

Data Structures and Network Algorithms by Robert E. Tarjan (covers
BSTs, splay trees, link-cut trees)
Open Data Structures by Pat Morin (covers BSTs, B-trees, hashing, and
some integer data structures)

MIT course

YouTube lectures


About a symmetric rank decomposition of a SYM◦SYM circuit's truth table matrix

The fact that the same letter is used twice doesn't mean that it signifies the same thing. In particular, in your first question, clearly $a \in \{0,\ldots,s\}$ and $b \in \{0,1\}$, whereas in the second question, it is explicitly stated that $a,b \in \{0,\ldots,t\}$. From your excerpts, it seems that the second $a,b$ are of the same "type" as the $a$ in your first question.

Your third question is unanswerable given your excerpts. It could be that the construction is instantiated with several different values of $t$. In any case, I would look at the place in which the construction is invoked to find out what the value of $t$ should be.


Is $k$-CLIQUE W[1]-hard for parameter $n - k$?

I believe this is FPT.

FInding a $(n - k)$-clique is equivalent to finding an independent set of size $n - k$ on the complement.  This is equivalent to finding a vertex cover of size $k$.  And the latter is FPT.


It's probably easier solving this using the Master Theorem.

T(n) = 6T(n/6) + 2n + 3

So in this case A=6, B=6, and D=1 because f(n) = 2n + 3 and 2n^1 + 3 = 2n + 3

We of course assume the base case is a constant such that T(1) = C

So we can easily see that the answer for this is

  T
  (
  n
  )
  =
  Θ
  (
  n log n
  )
, since A is equal to B to the power of D.

We can see that is true just by plugging in the values

= A = B^D

= 6 = 6^1

= 2 > 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.


Is a language with only a stack of fixed-size integers Turing-complete?

If your language supports an arbitrarily large array of integers (even of numbers in $\{0,1\}$), then you can simulate the tape of a TM. Then, clearly your language is Turing complete.

EDIT: based on your comment, you don't have an arbitrary array.

In this case, you can do the following:
If you can keep two counters (integers), and increase or decrease them, and check whether they are 0, then you can simulate a two counter machine (Minsky Machine), which is Turing complete (with a caveat).

If you also bound the maximal value that an integer can take, then I believe that your machine is no more powerful than a PDA.


What complexity class decision problems can be solved by only addition, multiplication, division and subtraction?

The question isn't exactly well-defined, but seems like a good/interesting question to me. I believe the answer you might be looking for is the class of Elementary Recursive functions. This class consists of almost exactly what you described: Problems solvable by functions that can be written with only addition, subtraction, and multiplication of integers. (Except, we also require a zero function and a "projection" function that outputs one of the inputs.)

You can get more functions (the Primitive Recursive functions) by additionally allowing functions that call themselves (but are guaranteed to terminate). Finally, you can get the class of all Turing-computable functions by introducing a minimization operator: find the minimum $x$ such that $f(x) = 0$.

Anyway, it turns out that $\mathsf{EXPTIME} \subsetneq \mathsf{ELEMENTARY}$, so it includes many (most?) problems that we'd usually consider interesting.


Here is one simple algorithm.  Pick one room that has too many people in it, and one room that has too few people in it, and move one person from the first room to the second room.  Repeat until convergence.


Remove features with too little variation

Step 1. Identify a measure of variation for a feature.
Step 2. Remove all features for which this measure is below some threshold (or is below that of msot other features).
There are many measures of variability that you could use in step 1: standard deviation, interquartile range, range (max minus min), median absolute deviation, and more.  Any of these are probably reasonable.


How to determine the polynomial runtime of an NP reduction?

The problem here is a misunderstanding of the point of the reduction. NP-complete problems are not known to have polynomial time algorithms. If they do, then P $=$ NP, if they don't then P $\neq$ NP - this is the BIG question of theoretical computer science.

The point of the reductions you're looking at is to show that the problem $L'$ is NP-complete, and thus at least as hard as anything else in NP. It does this by demonstrating that if you could solve $L'$ in polynomial time, then using the reduction you could solve $L$ in polynomial time too (take the instance of $L$, convert it to an instance of $L'$, solve that, then use that solution to get the solution to the original instance).

As $L$ is NP-complete, this also means that if we could solve it in polynomial time, we could solve every problem in NP in polynomial time (hence the intuition that NP-complete problems are in some sense the "hardest" problems in NP).

Just to add some technical bits on top of that, a problem $\Pi$ is NP-complete if:

$\Pi \in$ NP, and
$\Pi$ is NP-hard.

A problem $\Pi$ is in NP if there is an non-deterministic algorithm that solves $\Pi$ in polynomial time in the size of the input or equivalently we can check an answer to an instance of $\Pi$ in deterministic polynomial time.

A problem $\Pi$ is NP-hard if for every problem $\Phi \in$ NP, there exists a polynomial time reduction such that $\Phi \leq_{p} \Pi$ (this can be a different reduction for each $\Phi$). In practice what we do is actually chain these reductions together, so say we have an NP-hard problem $\Pi'$, then we know that there's reductions from everything in NP to it, so if we can show that $\Pi' \leq_{p} \Pi$ then by composing the reductions, we can show that there's a reduction from everything to $\Pi$ (we just go via $\Pi'$).

So just to come back to the original question, we don't know if there's a polynomial time algorithm for $L'$ - most(?) people would probably suspect that there isn't, as lots of people have spent lots of time trying to find even one polynomial time algorithm for any NP-complete problem and there's been no luck so far (of course such an algorithm for any of them means a polynomial time algorithm for everything in NP). The reduction 'just' shows that $L'$ is one of these hard problems.


Normal form after decomposition of a relation

I think you are wrong.

Here is a rough sketch of a proof (by contradiction) that the original claim is true.

Suppose that the claim is false: this means that R1 or R2 (or both) are not
in 3NF. Without loss of generality, suppose that R1 is not in 3NF. This means that, among all the dependencies
holding in R1, there is at least a dependency X → A in which X is not a superkey
(and so it is neither a candidate key) and the attribute A is not prime.

Now consider the definition of lossless decomposition: for each possible
valid istance r of R, we have that r = πT1(r) ⨝ πT2(r), where T1 are the attributes of R1 and T2 are the attributes of R2.

This means that each valid instance of R1 is a projection on the attributes T1
of some valid instance of R. But this implies that if X → A is valid in an instance r1 of R1, it will be also valid in an instance r of R obtained by joining r1 with some instance of R2 (because, for the definition of join, the tuples of r1 will appear in r unchanged, possibly repeated).

So this means that X → A is also valid in R, contradicting the initial hypothesis that R is in 3NF.


Interactive proof system for graph nonisomorphism

The slide describes a proof system for graph non-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives from the fact that it cannot work if the graphs are isomorphic. If $G_0 \equiv G_1$ then no matter what the prover does, the acceptance probability is only $1/2$.

How should we assign the bit? Proof systems don't work in this way. A proof system has two guarantees:

Completeness: if the input belongs to the language (in this case, the two graphs are not isomorphic), then there is a proof that convinces the verifier.
Soundness: if the input doesn't belong to the language (in this case, the two graphs are isomorphic), then no proof convinces the verifier.

When proving these two properties of the proof system, we specify a proof only in the first case. In the second case we have to show, instead, that no proof works. It's a different quantifier:

Completeness: if $G_0 \not\equiv G_1$ then there exists a proof which convinces the verifier with probability 1. (When proving completeness, we need to specify the proof that convinces the verifier.)
Soundness: if $G_0 \equiv G_1$ then all proofs convince the verifier with probability 1/2. (When proving soundness, we don't need to specify a proof. Indeed, we need to show that all proofs perform badly. In a sense, a proof is given to us, and we have to show that it doesn't convince the verifier.)


Which Graph Algorithm should I use to find all possible groups in a graph?

These are called the connected components of the graph.

For most purposes, any graph traversal algorithm will suffice for finding the connected components. However, if you have a really big graph, see this question on Stack Overflow for practical considerations.


Solution to recurrence $T(n) = T(n/2) + n^2$

Try this way:
$$
\begin{align*}
T(n) &= T(n/2) + n^2 \\
T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\
T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)}
\end{align*}
$$

You will end up with:
$$
\begin{align*}
T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\
T(n) &= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots
\end{align*}
$$

We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.

Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c_1f(n)$ and a lower bound of $T(n) \ge c_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.


Quick and space-efficient way to find whether two sets intersect

Build a $k \times k$ table $ans$ of answers, storing in each entry the smallest (according to some total order) element in that intersection or a sentinel value (e.g. -1) if the intersection is empty, and also maintain a mapping from each element to the set of all sets that contains it (e.g. using a hashtable of hashtables).

When you add an element $x$ to a set $i$, you can efficiently find all other sets $j$ for which $ans[i][j]$ might need to change, and the change itself is also simple: set $ans[i][j] = \min(ans[i][j], x)$.  Removing an element will also be efficient, except in the rare case when you remove that minimum shared element, which requires fully recomputing (just) $ans[i][j]$.


Well a language is XX iff there exists an XX grammar for it. There might be other grammars for an XX language. For instance you might have a context-free grammar for what is actually a regular language.

Read the book. It contains techniques (with examples!) that show how some non-LL(1) grammars can be transformed into LL(1) grammars. The techniques are called elimination of left recursion and factorization.


How to use dynamic programming to solve this?

This is the famous change-making problem.

If you want to solve it with dynamic programming, you have to come up with a suitable recursion. The central question is:

  Assuming you know the optimal coin choices for all $k < n$ (cents), how do you derive the optimal choice of coins for $n$ (cents)?


Longest Path A*, Admissible Heuristics, and Optimalness

It seems to me (and correct me if I'm wrong) that a regular A* algorithm would work absolutely fine with your problem. The problem is that you're confused about the word underestimates. When we're searching for the shortest path we want a heuristic that will never lead us down a path that will be longer than what we estimate it to be, in your case you never want to be led down a path that will be less than what you estimate it to be (which you say you have).

A heuristic is a function that gives $h(n) = 0$ at the goal.

An admissible heuristic is one that never overestimates the distance to the goal. In your cause you want the longest path rather than the shortest, so an admissible heuristic never underestimates the distance to the goal.

So if you have a heuristic that gives you at least the correct distance from the current node to the goal node or a larger value and you order your queue by largest $f(n)$ then you have a correct implementation of A*.

On the other hand if your heuristic both may underestimate or overestimate you're aren't guaranteed to find an optimal path.

We can prove the optimality of this easily (this is an adapted proof from Russell and Norvig's Artificial Intelligence A Modern Approach).

Let $G$ be an optimal goal state, with path cost $f^*$. Let $G_2$ be a suboptimal goal state with path cost $g(G_2) < f^*$. Now assume that A* has selected $G_2$ from the queue. Because $G_2$ is a goal state it would terminate the search with a suboptimal solution.

Consider a node $n$ that is a leaf node on an optimal path to $G$. Because $h$ is admissible (never underestimates), we must have

$f^* \leq f(n)$

And if $n$ was not chosen over $G_2$ then

$f(n) \leq f(G_2)$

Combining these we get

$f^* \leq f(G_2)$

Because $G_2$ is a goal state $h(G_2) = 0$ thus $f(G_2) = g(G_2)$. So we have a contradiction that $f^*$ is an optimal longest path and that $G_2$ is suboptimal. Thus A* will never expand a suboptimal solution and is an optimal algorithm.


Checking if several sets of pairs covers a given set of pairs

Here are some hints.

First, reduce your problem to the following one: given a collection of $N$ subsets $A_1,\ldots,A_N \subseteq [N]$, determine if there is some permutation $\pi$ such that $\pi(i) \in A_i$.

Given the $A_i$, construct a bipartite graph in which node $i$ on the left is connected to node $j$ on the right if $i \in A_j$. A permutation $\pi$ such that $\pi(i) \in A_i$ exists iff this graph contains a perfect matching. We know how to test whether a bipartite graph contains a perfect matching efficiently.


Clarification on the inapproximability of set cover

The hardness proof appears in an earlier paper of Moshkovitz, The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover; Dinur and Steurer proved a version of the Projection Games Conjecture, thus completing the NP-hardness proof. Moshkovitz clearly states that $n$ is the size of the universe, and she also assumes that the number of sets is polynomial in $n$.

Feige had proved earlier that if you can approximate set cover better than $\ln n$ then $\mathsf{NP}\subseteq \mathsf{DTIME}(N^{\log\log N})$. He improved on earlier result of Lund and Yannakakis which showed a hardness of $0.72\ln n$ under the same assumption.

The threshold $\ln n$ (where $n$ is the size of the universe) is important since it is achieved by the greedy algorithm. The analysis of the greedy algorithm shows that after $OPT \cdot t$ steps (where $OPT$ is the size of an optimal solution), we have covered a $1-e^{-t}$ fraction of the universe. When $e^{-t} < 1/n$, we have covered the entire universe (since we cover more than $n-1$ elements). Hence after at most $t = OPT \cdot \ln n$ steps, the greedy algorithm manages to cover the entire universe. This is where the dependence on the size of the universe comes from.


Can the semantics of a numeric hierarchy be faithfully represented in Haskell?

Yes, it is definitely possible. However your approach is a good starter but keep in mind to have a functional approach on writing code in Haskell. You can create expressions so you can define and 'override' methods.

As a suggestion I will give a part of code of how such expressions can look like as values and types.

data Exp = Lit Value
         | Assign Name Exp
         | Variable Name
         | Apply Exp Exp
         | Assist Name Exp
         | Exp :+:  Exp
         | Exp :-:  Exp
         | Exp :*:  Exp
         | Exp :=:  Exp
         | Exp :==: Exp
         | Exp :/=: Exp
         | Exp :>:  Exp
         | Exp :>=: Exp
         | Exp :<:  Exp
         | Exp :<=: Exp
         | Exp :&&: Exp
         | Exp :||: Exp
         deriving (Show)

This is some code out of a language I've written for controlling micro-controllers. The evaluation can be done as following:

-------------------------------------------------
-- Evaluate Expressions Utilities
-------------------------------------------------
-- Evaluate Integer Arithmetic operations
evalInt :: KDLMap -> Exp -> Int
evalInt _ (Lit n)          =  kdlintToInt n
evalInt k (Variable n)     =  kdlintToInt $ searchVariable' n k
evalInt k (e :+: f)        =  evalInt k e + evalInt k f
evalInt k (e :*: f)        =  evalInt k e * evalInt k f
evalInt k (e :-: f)        =  evalInt k e - evalInt k f
evalInt _ _                =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Integers
evalIntBool :: KDLMap -> Exp -> Bool
evalIntBool k (e :<:   f)         =  evalInt k e <  evalInt k f
evalIntBool k (e :>:   f)         =  evalInt k e >  evalInt k f
evalIntBool k (e :<=:  f)         =  evalInt k e <= evalInt k f
evalIntBool k (e :>=:  f)         =  evalInt k e >= evalInt k f
evalIntBool k (e :/=:  f)         =  evalInt k e /= evalInt k f
evalIntBool k (e :==:  f)         =  evalInt k e == evalInt k f
evalIntBool _ _            =  Prelude.error "Unable to perform operation."

-- Evaluate Boolean operations with Booleans
evalBool :: KDLMap -> Exp -> Bool
evalBool _ (Lit n)         =  kdlboolToBool n
evalBool k (Variable n)    =  kdlboolToBool $ searchVariable' n k
evalBool k (e :&&: f)      =  evalBool k e && evalBool k f
evalBool k (e :||: f)      =  evalBool k e || evalBool k f
evalBool _  _              =  Prelude.error "Unable to perform operation."

For more information, hit me up. I will provide it on my github quite soon, so you can see more. But to answer your question, yes it's definitely possible.


Is it possible to uniformly shuffle N items into a deque of size N where you can only modify the first or last elements?

The final algorithm:
for each new element k:
    perform a random cyclic shift of the sequence on the deque
    insert k to the end of the deque
    perform an inverse cyclic shift

Now, why does it work? (There is probably a simpler way to put it; this is how I understand this)
We generate a random permutation $p$ (we would need additional memory for that, but I'll explain how to avoid it). We replace each input number $a_i$ with pair $(a_i, p_i)$. Now it suffices to sort the pairs based on the second element. It works because different permutations correspond to different orders of elements after sorting.
To perform the sorting, we simply emulate insertion sort:

Let $[p_1, \ldots, p_m]$ be the current numbers in deque, and they are in sorted order.
Then another number $k$ arrives, such that $p_1 < \cdots < p_i < k < p_{i+1} < \cdots < p_m$.
We perform the cyclic shift: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i]$.
We insert $k$ in the back: $[p_{i+1}, \ldots, p_m, p_1, \ldots, p_i, k]$
We perform an inverse cyclic shift: $[p_1, \ldots, p_i, k, p_{i+1}, \ldots, p_m]$

To avoid storing the permutation, notice that it suffices to decide the relevant order of elements at the moment of insertion. I.e. for each element, you randomly determine its position among existing elements in the deque and perform the shifts as described.


No, $\mathsf{EXP^{EXP}=2EXP}$, a set of languages decidable in $O\left(2^{2^{\mathrm{poly}(n)}}\right)$ time.

This is just because you can give exponentially long input to an oracle which can solve it. So, the total power is $\exp(\exp(n))\ne \exp(n)$.

To see why $\mathsf P$ is self-low just take a machine that can run quadratic time and give to it the same oracle. While the resulting machine will be able to solve all languages in $\mathsf{DTIME}(n^4)$ it is still polynomial. Generalizing, $\mathrm{poly}(\mathrm{poly}(n))=\mathrm{poly}(n)$.

Was wrong, now understood that this is the only way to make machine that faster. Thanks to Ariel.

P.S. There is a parsimonious exp-time reduction from $\mathsf{2EXP}$-complete problem to an exponentially longer $\mathsf{EXP}$-complete problem.


Graph theory: determining maximum number of edges

The following identity is well-known:
$$
2|E| = \sum_{v \in V} d(v).
$$
In words, if we sum all degrees in a graph, we get twice the number of edges. To see this, divide each edge $(x,y)$ into two halves: the $x$-half and the $y$-half. We think of the $x$-half as a half-edge labeled $x$. The left-hand side counts the number of half-edges. On the right-hand side, $d(v)$ counts the number of half-edges labeled $v$, and so in total, the right-hand side also counts the number of half-edges.

If the graph has maximum degree $\Delta$ (in your case, $\Delta = 5$) then
$$
2|E| = \sum_{v \in V} d(v) \leq \sum_{v \in V} \Delta = \Delta |V|,
$$
and so $|E| \leq (\Delta/2) |V|$; there is equality if the graph is $\Delta$-regular (all degrees are exactly $\Delta$).


Hash Table: Relation between position of a value and Hash table size

No.  If you use SHA512, you can use any modulus $S$ you want: it doesn't need to be prime.  A power of two is fine and is no better or worse than a prime.

The reason is that the cryptographic properties of SHA512 ensure that the output of SHA512 is (for all practical purposes) essentially a uniformly random 512-bit string.  Because $2^{512}$ is so much larger than your modulus, after reducing modulo $S$, the result will be approximately uniform.  Any non-uniformity will be incredibly, exponentially small: so small that it's not detectable within your lifetime, or the lifetime of the solar system.  (I know there's another answer that claims non-uniformity is a problem, but that answer failed to quantify the extent of the non-uniformity and thus came to the wrong conclusion; the amount of non-uniformity is so exponentially small that it's completely irrelevant in practice).

So, go ahead and use any modulus that's convenient.  It doesn't need to be a power of two or a prime number, if you're using SHA512 as your hash function.


Kolmogorov complexity vs purposefully inefficient Turing machines

You are stating the theorem incorrectly. The theorem states that the Kolmogorov complexity is the same up to a constant for essentially optimal description languages, which are those in which you can describe running a Turing machine on an input $x$ using $|x| + O(1)$ bits. Given this definition, it is a simple matter of playing with definitions to see that all such description languages result in the same notion of Kolmogorov complexity, up to an additive constant.


Computer vision methods without "pre-training"

Yup, there are lots of them.  For example, image segmentation through graph cuts, camera calibration, image morphing, image stitching, reconstruction of a 3D scene from multiple 2D images, optical flow algorithms, motion tracking, image restoration and inpainting, and probably many more.


What algorithms exist for solving natural number linear systems?

Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \{s_1,\ldots,s_n\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v_1,\ldots,v_{2n},u$ of your problem as follows. For each $1 \leq i \leq n$, we put $v_i$ to be the vector with two non-zero entries: $v_{i,i} = 1$ and $v_{i,n+1} = s_i$, and $v_{n+i}$ to be the vector with a unique non-zero entry $v_{n+i,i} = 1$. The target vector is $u=1,\ldots,1,T$. Each natural combination of $v_1,\ldots,v_{2n}$ equal to $1,\ldots,1,\ast$ must select exactly one of each of $v_i,v_{n+i}$, and so encodes a subset of $S$ whose sum is the value of the last component.


Why is recursive programming problematic for branch predictors

It would seem that recursion isn't the problem at all, but a pattern of branches that is hard to predict. For example, if you calculate n! using recursions (if n = 0 -> return 1 else return n * factorial (n-1)) that should play very nicely with branch prediction. For example 25! will start with 25 taken branches, followed by one branch not taken.

If you calculated fib (n) by simulating the recursion using a stack, you would have mostly a loop, with the exact same branches inside the loop, and as far as branch prediction is concerned, it would be just as good / bad with no recursion anywhere in sight.

PS. This was about predicting whether a branch is taken or not taken. Newer processors use other branch-related predictions: Predicting the target of a branch (for example for virtual functions, where a branch will lead to one of possibly many implementations of a virtual functions), and prediction of the target of a "return" instruction, where the processor predicts that a "return" instruction most likely branches to the instruction after the previous "call subroutine" instruction.


Difference between multitasking, multithreading and multiprogramming

The Wikipedia article Computer multitasking covers this well. In summary:

Multitasking: there is more than one process and the operating system somehow decides which to run next.
Multithreading: threads are essentially subprocesses, which share memory (separate processes cannot normally access each other's memory) but which are independently scheduled.
Multiprogramming: a form of multitasking in which a process keeps running until it tries to access an I/O device, at which point another process is chosen to run so the CPU doesn't idle waiting for a punched card reader or something.


Repeated point in polygon: preprocessing complexity given logarithmic query time?

Your problem is a special case of planar point location. The algorithm/data structure you found by Snarak and Tarjan can answer point location (and thus point in polygon) queries in $O(\log n)$ time using $O(n \log n)$ preprocessing and $O(n)$ space. That is optimal. There are two other data structures that achieve this: a data structure by Kirkpatrick and a randomized incremental approach. The randomized incremental approach can be improved to $O(n \log^* n)$ expected preprocessing time in case of a simple polygon, and is fairly simple besides.


Does types being terms imply your dependend theory is considered polymorphic?

These three “flavors” are usually presented as the lambda cube. They aren't really flavors but properties that can be combined independently, so there are not $3$ but $2^3 = 8$ flavors. In fact you could go as high as $4$ properties yielding $16$ flavors:

terms depending on terms, i.e. functional languages (e.g. $f : x \mapsto x+2$);
terms depending on types, i.e. polymorphism (e.g. $\mathrm{head} : [X] \rightarrow X$);
types depending on types, i.e. type operators (e.g. $\mathrm{list} : X \mapsto [X]$);
types depending on terms, i.e. dependent types (e.g. $\mathrm{array(int)} : n \mapsto \mathrm{int}^n$).

Theories without lambda abstraction tend to be less interesting and do a bad job of encoding most programming languages, so they're generally left out.

If you introduce transitive universes, then having types depending on terms automatically gives you types depending on higher-order terms, i.e. types. The Barendregt cube tends to collapse when terms and types are collapsed. However this doesn't necessarily give you all the polymorphism you want. The Barendregt cube is a classification; it doesn't reflect all the properties of the language. In particular, polymorphism can be more or less explicit, requiring you to thread type arguments down to every function, or not.

I think the right way to put it is that you're automatically speaking of a type system that can encode a polymorphic type system, but not necessarily give it to you the way you want.


Extracting regex submatch boundaries without backtracking

It occurred to me after I made this post that I could store the states in a linked list format:
typedef struct stateRecord {
    struct stateRecord *next;
    size_t state;
    size_t startIdx;
    size_t endIdx;
} stateRecord;


What is the time complexity of the Bailey–Borwein–Plouffe formula?

A good place to start is the BBP paper. In Section 3 (1st paragraph of page 8) they state that the running time for $n$ digits is $O(n\log nM(\log n))$, where $M(m)$ is the complexity of integer multiplication; currently the best known algorithms give $M(m) = O(m\log m 2^{O(\log^* m)})$ bit complexity, though Fürer himself (inventor of the first algorithm with that complexity) argues that this is not the correct complexity measure.


RSA cryptosystem: Encrypting a signed message

Encrypts the resulting message/signature pair with the public key of Bob (the recipient):
  Is that $P_B((M'', \sigma))$? What does this mean: $(P_B(M''), P_B(\sigma))$ or $(P_B(M''), \sigma)$?

Neither. It's simply $P_B(M'')$. The resulting message/signature pair refers to $M''$.


What runtime complexity if DNF formula not PAC-learnable, $O(2^N)$ or $O(2^{2^N})$ runtime?

There's a misconception here.  PAC learning doesn't require the learning to find the shortest formula.  It merely requires the learner to find any formula that has sufficiently low generalization error.  If there are multiple formulas that meet that criteria, the learner is allowed to output any of them -- not necessarily the shortest.

Take a closer look at the formal definition, and hopefully you'll see how that follows from the definition.


If X reduces to a problem in NP, is X in NP?

The answer depends on what you mean by the notation $\le_p$.

If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes".  It follows from the definition of NP.  See What is the definition of P, NP, NP-complete and NP-hard? to learn more.
Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT.  Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY).  We know that SAT is in NP.  However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise.  While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

What is the difference between these terms?
Can one show NP-hardness by Turing reductions?
https://cstheory.stackexchange.com/q/138/5038
https://cstheory.stackexchange.com/q/686/5038


Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints

This is straight up a minimum-cost flow problem. All it's missing is a an edge from the source to each porter with zero cost and capacity equal to the porter, and a zero cost edge from each urn to the sink with capacity equal to that urn.


Is the simulation of how a warehouse functions (eg Amazon) a discrete event simulation problem

Like many real-world models, this type of situation can be modeled both continuously and discretely. For example, if you defined the problem as a series of equations defining the rates at which items arrived and departed it would be continuous, but if you modeled it at a more microscopic level, showing individual arrivals and departures of trucks, it would be discrete. Then, going further, if you were to model the actual acceleration of the trucks as they departed the loading bay, it would become continuous again.

In general, job shop-type simulations are usually modeled as a series of discrete events. You may want to refer to queuing theory.

Note that there is an open source project called Facsimile that does discrete event simulation and is intended to do the kind of simulation you are aiming at. There are also a lot of commercial systems that specifically do industrial logistics and job shop simulation; for example AnyLogic is one such package.

You can also use generic simulation languages like Modelica to create the simulation.

In general, it is good idea to use simulation software rather than write your own simulation in many cases because there are many subtleties to it that you would not expect. Using an existing simulation package you can create your simulation in a fraction of the time it would take to program it and the result is potentially much more reliable with less risk of bugs.


What is the complexity of an in-place merge algorithm for forward iterators

Your algorithm is very similar to insertion sort or selection sort. Here is some pseudocode which hopefully captures your algorithm:

inplace_merge(A[1,...,n], B[1,...,m])

C[1,...,n] = A[1,...,n]
C[n+1,...n+m] = B[1,...,m]
for i from 1 to n:
   if C[i] > C[n+1]:
     find position j in {1,...,m} such that C[n+j] < C[i] <= C[n+j+1] (where C[n+m+1]=∞)
     C[i], C[n+1,...,n+j-1], C[n+j] = C[n+1], C[n+2,...,n+j], C[i]
return C

The invariant is that at the end of each iteration, C[1,...,i;n+1,...,n+m] and C[i+1,...,n] are both sorted, and that the multiset of elements never changes.

Consider what happens when all elements in the array A are larger than all elements in the array B. In this case, j always equals m, and so the running time of each iteration is $O(m)$, and the total running time is $O(nm)$.

In contrast, the mergesort merging algorithm merges the two arrays in time $O(n+m)$, and should be preferred over your algorithm.


Is the language $L = \{a^pb^q \ | \ p \ge 1, \ q \ge 1, \ p \ge q^2 \ or \ q \ge p^2\}$ context free?

If $L$ is context-free, then according to Parikh's theorem, the set $\{(p,q) : p,q \geq 1, p \geq q^2 \text{ or } q \geq p^2\}$ is semilinear, say it is the union of the linear sets $L_i$. Each linear set is either a singleton or of the form $(a,b) + \mathbb{N}(x,y)$. In the latter case, I claim that either $x = 0$ or $y = 0$. Otherwise, for large $n$ we have $\frac{a+nx}{b+ny} \approx \frac{x}{y}$, and in particular it isn't the case that $a+nx \geq (b+ny)^2$ or $b+ny \geq (a+nx)^2$.

It follows that there exists a finite set $F$ such that
$$
\bigcup_i L_i = F \cup \bigcup_j (p_j+\mathbb{N}t_j,q_j) \cup \bigcup_k (p'_k,q'_k+\mathbb{N}t'_k).
$$
Let now $z \geq 2$ be some integer larger than all indices in $F$ and all $p_j,q_j,t_j,p'_k,q'_k,t'_k$, and consider the point $(z^2,z)$, which should be contained in this union. By construction, it is not contained in $F$ or in any $(p_j+\mathbb{N}t_j,q_j)$. If $(z^2,z) = (p'_k,q'_k+nt'_k)$ and $(p,q) = (p'_k,q'_k+(n+1)t'_k)$, then we must have $q \geq p^2$, which implies that $z+t'_k \geq z^2$. This again contradicts our choice of $z$.
It follows that $(z^2,z)$ is missing from the union, and we reach a contradiction.


Algorithm and proof for combining a list of node connections into groups of nodes efficiently

You should look into DFS and BFS, which can solve this problem in $O(n+m)$ time where $n$ is the number of nodes and $m$ is the number of edges.

The performance of the algorithm you described is much worse than you think, because you potentially have to relabel nodes many times. Consider the edges presented in this order:

$v_{2k},v_{2k+1}$

$\vdots$

$v_2, v_3$

$v_0, v_1$

$v_{2k}, v_{2k-1}$

$\vdots$

$v_3, v_4$

$v_2, v_1$

The introduction of the edge $v_{2k}, v_{2k-1}$ requires relabeling $v_{2k}$ and $v_{2k+1}$, introducing $v_{2k-2}, v_{2k-3}$ requires relabeling $v_{2k-2}, v_{2k-1}, v_{2k}$ and $v_{2k+1}$. Finally, introducing $v_2,v_1$ requires relabeling $v_2,\ldots,v_{2k+1}$. This ends up being quadratic in $n+m$.

The idea behind your algorithm is somewhat valid though, and you can implement it much more efficiently using the Union-Find data structure which, if you will, can "defer" the relabeling.


Can anybody explain intuitively why quick sort need log(n) extra space and mergesort need n?

Quicksort: For quicksort, your intuition about recursion requiring O(log(n)) space is correct. Since quicksort calls itself on the order of log(n) times (in the average case, worst case number of calls is O(n)), at each recursive call a new stack frame of constant size must be allocated. Hence the O(log(n)) space complexity.

Mergesort: Since mergesort also calls itself on the order of log(n) times, why the O(n) space requirement? The extra space comes from the merge operation. Most implementations of merge use an auxiliary array with length equal to the length of the merged result, since in-place merges are very complicated. In other words, to merge two sorted arrays of length n/2, most merges will use an auxiliary array of length n. The final step of mergesort does exactly this merge, hence the O(n) space requirement.

To see exactly how the auxiliary array is used, check out this implementation of merge.

Summary: The key difference between the two lies in the space requirement of the operation performed at each recursive step. The partition step used in quicksort is an in-place operation, while merging usually requires an auxiliary array.


Origin of a story about a computer in the 50's recommending offing Pensioners

The story is clearly made up.

There was no AI in the 1950's that could have come up with that.

There is no AI today and for many years that could come up with that.

Actually, an AI wouldn't come up with this idea at all. You would need a very well calibrated combination of AI and AS (Artificial Stupidity) to achieve this result.


Consider the following counter example

Let $A = aa$

Let $B  = aab$

Let $Z = aabaa$

Your code will return false while the answer is true.

This is because you are giving preference to matching $A$ before matching $B$. There is no property of the problem that says that it is optimal to match all characters to $A$ before $B$ in case the character can be in both $A$ and $B$.


Find the shortest sub-tree with node deletion

This can be solved with dynamic programming.

Define $A[u,v]$ as follows.  Consider all trees obtainable by starting with the subtree rooted at $v$, removing some of the nodes, and making $u$ be the parent of all of the nodes with no parent.  (Or, to put it another way: all of these trees are a subset of the subtree rooted at $u$; they contain $u$ as their root; and every node in them other than $u$ is either $v$ or a descendant of $v$.)  Then $A[u,v]$ is defined to be the length of the minimal-length tree of this sort.

Notice that we have a recursive relationship for $A[u,v]$.  In particular, if $w_1,\dots,w_k$ denote the children of $v$, then we have

$$A[u,v] = \min(d(u,v) + A[v,w_1] + \dots + A[v,w_k], A[u,w_1] + \dots + A[u,w_k]).$$

(Here the first term in the $\min$ corresponds to the case where $v$ is included in the tree, and the second term where $v$ is not included.)

As a result, we can compute all of the $A[u,v]$ values using dynamic programming.  There are at most $O(|V|^2)$ many values to compute, and each one can be computed in $O(k)$ time where $k$ is the maximum degree of the tree, so the total running time is $O(|V|^2 k)$.