Prove that we can change probability in definition of PP class

Lets say a separation using $p\in\mathbb{Q}$ exists for $L\subseteq\Sigma^*$ if there exists a polynomial probabilistic Turing machine $M$ such that:

$x\in L \Rightarrow \Pr\left[\text{M accepts x}\right]> p$

$x\notin L \Rightarrow \Pr\left[\text{M accepts x}\right]< p$

$L\in PP$ iff there exists a separation for $L$ using $\frac{1}{2}$ (we can use a strong inequality in both cases). We proceed to show that $\forall p,q\in (0,1)\cap \mathbb{Q}$, if there exists a separation for $L$ using $p$, then there exists a separation using $q$.

We shall use the fact that a probabilistic Turing machine with access to unbiased random coins, is able to simulate an $\alpha$-biased coin for any rational (this can be strengthened) $\alpha\in [0,1]$, in $O(1)$ expected time. See lemma 7.14 in Arora and Barak's book for a proof.

Now, given a machine $M_p$ with separation $p$ for $L$, lets consider a machine $M_q$, which starts by tossing an $\alpha$-biased coin. If the outcome is $1$ then it accepts, otherwise it simulates $M_p$ on the input and returns it's answer.

Since we want $M_q$ to be polynomial in the worst case, we restrict the simulation of the $\alpha$-biased coin to a certain number of iterations, such that the simulation halts with probability $1-\epsilon$ (this can be done for any $\epsilon>0$, simply use the fact that the simulation runs in expected constant time, and apply Markov's inequality). If the simulation didn't halt, $M_q$ accepts. In this case we have:

$\Pr\left[\text{$M_q$ accepts x}\right]=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)\Pr\left[\text{$M_p$ accepts x}\right]\right)$, so:

$x\in L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]>
\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)
$

$x\notin L \Rightarrow \Pr\left[\text{$M_q$ accepts x}\right]<
\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)
$

This means it is enough to require $q=\epsilon+(1-\epsilon)\left(\alpha+(1-\alpha)p\right)$. Equivalently,

$\alpha=\frac{q-p-\epsilon(1-p)}{1-\epsilon}$.

Since $p,q\in (0,1)\cap \mathbb{Q}$, if $q>p$ we can find a small rational $\epsilon$ and rational $\alpha\in (0,1)$ to satisfy this. If $p>q$ you can change $M_q$ to reject when the outcome of the $\alpha$-biased coin is 1. When this equality holds, $M_q$ achieves $q$ separation for $L$ and we are done.


The system operates in a synchronized fashion using a shared clock. This removes the ambiguity.


Representing Integral domains in computer memory?

In general this question has no precise answer: the class of integral domains is not even a set, much less a countable set! (For example, for each set $A$, we can find an integral domain $D_A$ larger than $A$, e.g. $\mathbb{Z}[A]$, which is sufficient to show that integral domains can't be all gathered into a set).

In general you need to specify something to describe the elements of the set, and how to compute multiplication and addition.

A popular choice, which covers a large portion of the interesting examples, is to take a known ring or field $R$, typically $\mathbb{Z}$ or $\mathbb{Q}$, or some finite field $\mathbb{F}_q$, and look at some quotient ring of the form $D = R[X_1,\ldots,X_n]/(P_1,\ldots,P_k)$, where the $P_i$ are polynomials in the $X_j$.

Now it's not even clear that $D$ is an integral domain, which is equivalent here to the fact that $I=(P_1,\ldots, P_k)$ is irreducible. This can be determined using the Gröbner basis method as explained here.

Now there is an obvious representation for the elements of $D$: every element is represented by a polynomial, which we know how to represent, and do addition and multiplication on. The only issue is equality, since it needs to be modulo $I$. But this also is possible using known techniques, similar to the Gröbner basis ones.

It would be great if someone had implemented all of this up somewhere, though. Oh but they have! The Sage mathematical software toolchain builds on all of these observations to offer a ton of ways to concretely work with these kinds of rings. They even have an is_integral method for quotient rings!

Sage is a fantastic piece of software that I highly recommend, which probably does a lot of what you want.


Upper bound on the number of edges relative to the height of a DFS tree

After running a DFS, all the edges in $G$ can be classified as tree edges or back edges. Each back edge connects a vertex on the tree to one of it's ancestors. For each vertex it can point to at most $h-1$ ancestors, thus you can have at most $(h-1)|V|$ back edges. There are $|V|-1$ tree edges. You can have at most $h|V|-1$ edges.


solving the recurrence t(n)=t(n-2)+d*(n^2)/2 with iteration method

This answer assumes that $T(1) = \frac{d}{2}$

Your recurrence relation, in closed form, would be:

\begin{align}
T(n) & =  \frac{d}{2} n^2 + \frac{d}{2} (n-2)^2 + \frac{d}{2} (n-4)^2 + \dots + \frac{d}{2}\\
& = \sum_{i=0}^\frac{n-1}{2} \frac{d}{2}(n-2i)^2\\
\end{align}

Which, with little effort, can be simplified further:

$$\dots = \frac{d}{2} \sum_{i=0}^\frac{n-1}{2}n^2-4ni+4i^2
 = \frac{dn^2}{4}(n-1)
-2dn\sum_{i=0}^\frac{n-1}{2}i
+2d\sum_{i=0}^\frac{n-1}{2}i^2$$

For further simplification, you can use the facts that:

$$\sum_{i=1}^n i=\frac{n(n+1)}{2}$$

$$\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}$$

But I'll leave that to you.


Checking whether two paths are intersecting in a tree

This is a standard exercise.  Try drawing some pictures with the different cases, and you'll see how to formulate a criterion for when they overlap, in terms of the lowest common ancestor.

Just computing $LCA(u_1,v_1)$ isn't gonna be enough, because that only gives you information about the first path, and doesn't depend at all on the second path.  So try computing the LCA of some other pair of nodes.

Since this looks like an exercise, I'm not going to solve your problem for you, but I'll describe for you how you can approach this problem so you can solve it yourself.

Every path falls into one of two categories: either it goes down (i.e., $v_1$ is a descendant of $u_1$); or it goes up and then down (i.e., $u_1$ and $v_1$ are descendants of some common ancestor, $w_1 = LCA(u_1,v_1)$, where $w_1 \ne u_1$ and $w_1 \ne v_1$).  So, there are two possibilities for the first path, and two possibilities for the second path: four cases in all.
You can quickly classify each path, put it into these categories, and find the endpoints and the common ancestor.  (Exercise for you: How?)

Now, you have four cases.  For each case, draw some pictures and work out the criteria under which the two paths intersect.  It's straightforward.

For instance, let's take the first of the four cases.  Suppose both paths go only down: $u_1$ is an ancestor of $v_1$, and $u_2$ is an ancestor of $v_2$.  Can you figure out how to tell whether they overlap?  Some tips: If $LCA(u_1,u_2)=u_1$, what can you conclude?  If $LCA(u_1,u_2)=u_2$, what can you conclude?  If $LCA(u_1,u_2)$ is something else, then what can you conclude?

Now do similar reasoning for each of the four cases.

Note: I am also assuming that you have a rooted tree; otherwise, the problem is not well-defined (as the LCA is not defined in non-rooted trees).

My thanks to @babou for his helpful comments and feedback on an earlier version of this answer.


Different context-free grammars for the same language

Grammar 1 matches a. Grammar 2 does not. So they are not identical, and at least one of them is not a grammar of your indicated language.

As Yuval Filmus indicates in a comment, the general question of whether two CFGs produce the same language is undecidable. Obviously, it can be decided in certain cases (such as this one); searching for a counterexample is usually straightforward, although it obviously won't terminate if the two grammars turn out to produce the same language.

For simple exercises like this one, you should be able to prove (or disprove) that a grammar produces a given language. A simple technique which often works is induction over the length of the string.


What is the complexity of k-clique problem with a predetermined vertex in the solution?

It is still $\mathsf{NP}$-complete.
Consider the following reduction from the normal $\mathrm{Clique}$ problem:
Given a graph $G$ and some desired clique size $k$, add a new vertex $v^\ast$ which is connected to all vertices of $G$ to obtain a new graph $G^\ast$.
Then $(G^\ast, k + 1, v^\ast)$ is a yes-instance of your modified $\mathrm{Clique}$ problem if and only if $(G, k)$ is a yes-instance of $\mathrm{Clique}$.


Find any of the 3 largest among $n$ elements

I don't know what do you mean by comparison graph. However, here is my solution for question 1.

Suppose you have a list of $m$ elements, and you want to find the largest element. You can do this with $m-1$ comparisons.

Do you know how to proceed?

    You can simply ignore the first two elements in your list. This gives you a new list $L'$ of $n'=n-2$ elements, You can determine the largest element of $L'$ with $n'-1=n-3$ comparisons. This element is one of the three largest.


What are positive and negative circles in weighted digraph?

A circle is a path in the graph ($v\to u_1 \to u_2 \to \cdots \to v$) starting from some node $v$, that goes back to node $v$, thus "closing a circle".

The "value" of a circle, is the sum of the weights of the edges in the circle. If they sum to a negative value -- the circle is "negative"; otherwise, it is "positive".


Injectivity not required for unification algorithms?

Here $f$ is not a mathematical function.  Rather, it is a function symbol.  Don't think of $f(a,b)$ as the result of evaluating the function at parameters $a,b$.  Rather, think of it as a term in a symbolic expression -- it is a syntactic object that is not intended to be interpreted in the way you are interpreting it.

If you like, you can think of it as though every function symbol in a symbolic expression is an injective function; but that's not really accurate, that's just a crude way to think about symbolic expressions.

You can't define $f(x)=x+y$.  $f$ is an uninterpreted function symbol.  You're not allowed to define a particular function.  Rather, $f$ is a stand-in for a function that is not yet defined. One way to think about it is that any conclusions that you draw from unification, are conclusions that should hold for all functions $f$ (not just a single one).


web content "mining" using supervised learning tequniques

In short, this is probably difficult.

Your question is not fully specified, since you did not write the details of the data you are parsing and since estimating the possible changes to it is a matter of guesswork.

Once this web site changes format, then if we assume that the products remain the same, you are essentially looking at supervised learning task: given a list of known product web pages, make an "extractor function" that outputs the desired field.

If you are lucky and all the product pages are identically structured then this problem might be quite easy. You simply need to identify the path to the node of the HTML in which the desired information lies. On the other hand, if the web pages have a varied structure, or no structure at all, then the problem may be much more difficult.

There are some academic works in these areas, but don't get your hopes up. Look for the keywords "automatic web extraction".


Proving greedy choice property of fractional knapsack

Remember that $O$ is assumed to be an optimal solution.
If $O'$ is a solution that is at least as good as $O$, then $O'$ has to be optimal too.

In particular, since $O$ is optimal, $O'$ cannot be better than $O$; so $O'$ must be exactly as good as $O$.  Since there's nothing better than $O$, and since $O$ and $O'$ have the same goodness, there can't be anything better than $O'$ either.  Consequently, $O'$ is also optimal: both $O$ and $O'$ are optimal solutions.  (There can be more than one optimal solution.)


Is at least one of L and L complement Turing recognizable

No, try to think of a counting argument (i.e, the size of each class) in the following way:
There are $2^{\aleph_0}$ possible words in the language, hence $2^{2^{\aleph_0}}$ total languages. However, the number of turing machines is bounded by the total possible number of words (since you can encode a TM as a string), hence there are at most $2^{\aleph_0}$ TMs, and thus we get that $|RE| \le 2^{\aleph_0}$. Follow the definition of $co-RE$, to see that the same argument gives $|co-RE| \le 2^{\aleph_0}$ as well. Thus, $|RE\cup co-RE| \le 2^{\aleph_0}$ as well.
Thus $|RE\cup co-RE|\le 2^{\aleph_0}<2^{2^{\aleph_0}}=|P(\{0,1\}^*)|$, and thus there must be some $L\in P(\{0,1\}^*)\setminus (RE\cup co-RE)$ as you asked.
In fact, this shows there are waaaaay more languages that aren't RE or co-RE than languages that are.


A two's complement operation is simply a one's complement operation followed by the addition of 1 to the result. One's complement is easy: simply invert all of the input bits.

The addition of 1 must be done with a 4-bit adder. A 4-bit adder is constructed using four stages of a 1-bit full adder. The 1-bit full adder accepts two bits, plus a Carry input, and generates the sum of the two bits, plus a Carry output. The following diagram is a 1-bit full adder:

We can cascade four of the 1-bit full adder stages together, feeding the Carry output of each stage to the Carry input of the next stage. The inverted (one's complement) inputs are applied to the B inputs of the four stages. To perform an addition of 1, we apply the 4-bit binary value 0001 to the A inputs. The complete boolean circuit is shown below:

The above circuit can be reduced by noting that each XOR operation on the input of each adder stage can be replaced either with an inverter if the A input is a 0, or a NOP (no operation) if the A input is a 1. On further analysis, further reductions may be made to the circuit, as well.


Solve recurrence relation that depends on depth of recursion

diplodoc explained in the comments one way to solve the recursion. Your recursion is
$$
A_n = 1 + \frac{A_0 + \cdots + A_{n-1}}{n+1}, \quad A_0 = 1.
$$
The trick is to calculate
$$
(n+1)A_n - n A_{n-1} = (n+1 + A_0 + \cdots + A_{n-1}) - (n + A_0 + \cdots + A_{n-2}) = 1 + A_{n-1},
$$
and so $A_n = A_{n-1} + 1/(n+1)$. From here it follows easily that $A_n$ is the $(n+1)$th harmonic number.

Another possibility is to use generating functions. Let
$$
P(x) = \sum_{n=0}^\infty A_n x^n.
$$
Since $\frac{1}{1-x} = 1 + x + x^2 + \cdots$, it follows that
$$
\frac{xP(x)}{1-x} = \sum_{n=0}^\infty (A_0 + \cdots + A_n) x^{n+1}.
$$
Integrating, we get
$$
\int_0^x \frac{yP(y)}{1-y} \, dy = \sum_{n=0}^\infty \frac{A_0 + \cdots + A_n}{n+2} x^{n+1}.
$$
It follows that
$$
\frac{1}{1-x} + \frac{1}{x} \int_0^x \frac{yP(y)}{1-y} \, dy = P(x).
$$
In terms of $Q(x) = \int_0^x \frac{yP(y)}{1-y} \, dy$, this reads
$$
\frac{1}{1-x} + \frac{Q(x)}{x} = \frac{(1-x)Q'(x)}{x},
$$
which simplifies to
$$
\frac{x}{1-x} + Q(x) = (1-x)Q'(x) = [(1-x)Q(x)]' + Q(x),
$$
and so
$$
(1-x)Q(x) = \int^y \frac{y}{1-y} \, dy = \int^y \left(\frac{1}{1-y}-1\right) \, dy = C - x - \log(1-x).
$$
It follows that
$$
Q(x) = \frac{C-x-\log(1-x)}{1-x}.
$$
Since $Q(0) = 0$, we deduce $C = 0$.
Differentiating and multiplying by $(1-x)/x$, we find that
$$
P(x) = \frac{-\log(1-x)}{x(1-x)} = \frac{\sum_{n=0}^\infty x^n/(n+1)}{1-x},
$$
from which we can extract the coefficient of $P(x)$ to be $H_{n+1}$.

Finally, we can solve this without using any recurrences. Consider a random permutation of the numbers $1,\ldots,n+1$, which we think of as the $n$ places and the goal. The frog jumps to the first number. If it is not $n+1$, it scans the list to the first larger number, and jumps there. Repeat in this way, until you get to $n+1$. You can check that this defines the same random process.

Given a permutation, the number of jumps is the number of left-to-right maxima, that is, elements which are larger than all that precedes them. The probability that the $i$th number is a left-to-right maximum is exactly $1/i$, and so linearity of expectation shows that the expected number of jumps is $1 + 1/2 + \cdots + 1/(n+1)$.

As a bonus, the last solution allows us to calculate higher moments of the distribution. The main observation is that the indicator variables $X_i$ for the $i$th number being a left-to-right maxima are independent Bernoulli random variables. This implies that the variance of the number of left-to-right maxima is
$$
\sum_{i=1}^{n+1} \frac{1}{i} \left(1-\frac{1}{i}\right) = H_{n+1} - \sum_{i=1}^{n+1} \frac{1}{i^2} = H_{n+1} - \frac{\pi^2}{6} + O\left(\frac{1}{n}\right).
$$

One checks that the central limit theorem applies, and so the total number of left-to-right maxima is asymptotically normal.

Why is the answer roughly $\log n$? One might expect the answer to be closer to $\log_2 n$, since at each step, $n$ is roughly cut in half. However, this argument assumes that the changes to $n$ are additive, whereas in reality they are multiplicative. It is better to consider instead the effect of each step on $\log n$. If $m$ is the new value of $n$, then the expected value of $\log m$ is
$$
E[\log m] = \frac{\log 1 + \cdots + \log n}{n+1} \approx \frac{1}{n}\int_0^n \log x \, dx = \left.\frac{1}{n} (x\log x-x)\right|_0^n = \log n - 1.
$$
Therefore the value of $\log n$ decreases by roughly 1 each step, and so we expect the number of steps to be around $\log n$ rather than $\log_2 n$.

(With some work, this intuition can be made rigorous.)


What structure is used for accessing the most frequent elements top k over a stream of elements?

This is possible in $\mathcal O(\log n)$ time using self-balancing tree (or heap), using frequencies as keys. This extends the node to keep a list (or once more a tree) of elements of equal frequency.
To access top k elements you can either augment the tree with additional pointers to allow traversal in $k$ steps or use $\mathcal O(\log n)$ recursive one.
Better approach is to keep $k$ elements in that tree-like structure and in another one the rest.

If elements are fixed, you can use hash-table to store them, so keeping a table per frequency would result in expected time $\mathcal O(1)$, here using knowledge of the elements will help to minimize number of collisions.


Why can level-triggered interrupts be shared but not edge-triggered interrupts?

Consider the scenario where an interrupt IS shared by two devices with the following scenario:

Device 1 requests service.
The processor starts serving device 1.
        Device 2 requests service.
Device 1 no longer requests service.
The processor finishes serving device 1.
        The processor starts serving device 2.

Here device 1 will assert an interrupt request in step 1. It de-asserts that request in step 5, but the request remains asserted due to step 3.

Now in step 6, if level triggered requests are used, the processor will service the other device since the request level is still asserted. With edge triggered requests, nothing will happen because there will be no new "edge" to be detected. The request remained asserted throughout the scenario. This is a failure of the interrupt system.

This is why only level triggered interrupts, in general. may be shared.


CLRS Question 8-6 Lower bound on merging sorted lists

Let us consider any comparison-based algorithm for merging two ordered lists $A,B$ of length $n$, focusing on the case in which all $2n$ numbers are distinct. When the algorithm terminates, the results of the comparisons determine the merged list. Stated differently, if we describe the algorithm as a decision tree, then each leaf is labelled with the merged list, which is some permutation of the elements in $A \cup B$. Since all elements are different, each possible such permutation must be represented as some leaf.
Since the lists $A = (a_1,\ldots,a_n)$ and $B = (b_1,\ldots,b_n)$ are ordered, the permutation $\pi$ labeling each leaf must satisfy the following property: if $i < j$ then $a_i$ appears before $a_j$ and $b_i$ appears before $b_j$. This implies that $\pi$ is determined from the set of indices containing elements of $A$. There are $\binom{2n}{n}$ such possible sets, and all corresponding permutations can actually happen, as can be seen by assigning the element in the $k$th the number $k$. For example, if $n = 2$ then the possible orders are:

$a_1,a_2,b_1,b_2$ – achieved for $A = 1,2$ and $B = 3,4$.
$a_1,b_1,a_2,b_2$ – achieved for $A = 1,3$ and $B = 2,4$.
$a_1,b_1,b_2,a_2$ – achieved for $A = 1,4$ and $B = 2,3$.
$b_1,a_1,a_2,b_2$ – achieved for $A = 2,3$ and $B = 1,4$.
$b_1,a_1,b_2,a_2$ – achieved for $A = 2,4$ and $B = 1,3$.
$b_1,b_2,a_1,a_2$ – achieved for $A = 3,4$ and $B = 1,2$.

Therefore the decision tree must contain at least $\binom{2n}{n}$ leaves. Since it is binary (we assumed that no two elements are equal), its depth must be at least $\log_2 \binom{2n}{n}$. Stirling's approximation shows that $\binom{2n}{n} = 4^n/\Theta(\sqrt{n})$, hence $\log_2 \binom{2n}{n} = 2n - \Theta(\log n)$.


Determining whether a relation is the "union" of two other relations

The following should suffice:

for each (x,y) in P:
    if (x,y) in Q, print "nope" and quit
for each (x,y) in Q:
    if (x,y) in P, print "nope" and quit
count the number of pairs in P and Q.
if this sums to |S|^2, output "yup, otherwise output "nope".

You could use any method.  For instance, you could compute $P \cup Q$ directly, then compute $P \cap Q$ directly (say, using mergesort-like methods), and check that each has the desired value.

All of these will have essentially the same asymptotic running time.


Problem in Papadimitriou's "Computational Complexity" seems odd

Rice's theorem is about non-trivial properties of partial functions. It states that if $P$ is a non-trivial property of partial functions, then no algorithm can decide, given the description of a Turing machine $M$, whether $L(M) \in P$.

Rice's theorem doesn't say anything about the operation of Turing machines. A property like "$M$ ever writes $\sigma$" is not a property of $L(M)$, and so Rice's theorem doesn't apply to it.


Efficiently finding duplicates in lists of numbers

Use any efficient set data structure, based e.g. on hashtables or balanced search trees.

Keep in mind that such optimizations are dwarfed by the exponential nature of any algorithm I assume you will come up with.

That said, you may want to check out pseudo-polynomial algorithms for Knapsack, and problem variants that have polynomial-time algorithms.


If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases the required storage by a very large factor. In your case, your matrices need a total of 38,762,521,924 entries, so you'll need at least 4,845,315,241 bytes, or about 4GB, of storage per matrix. Since the Monster group has size about 8 × 1053, though, I seriously doubt you can fit everything into memory.

Another note: the arithmetic you're describing happens to have the plus operator defined as binary XOR and the multiplication operator defined as bitwise AND. Therefore, you could, in a language like C or C++, use the ^ operator to denote addition and the & operator to denote multiplication.

Finally, the complexity of multiplication depends on the matrix multiplication implementation. The naive method takes time O(n3), where n is the dimension of the matrix, but since the matrices are large you could probably use either the Strassen algorithm (time complexity about O(n2.8)) or Coppersmith-Winograd, the latter of which requires about O(n2.37) multiplications. You'd probably have to empirically profile these algorithms to see which is best, since the constant factors hidden here are pretty huge.

Hope this helps!


Why researchers don't study the parameterizations of the problems unlikely to be NP-Hard?

This is not true, there is a program known as "FPT inside P" where we look for interesting parameterizations for problems inside P. The results are perhaps indeed more scattered as opposed to FPT for hard problems which you tend to see much more.

For example, look at the work of Niedermeier and others [1,2] for graph matchings. There is also work for longest path on interval graphs [3]. You will find more by looking at papers that reference the ones mentioned.

[1] Korenwein, Viatcheslav, André Nichterlein, Rolf Niedermeier, and Philipp Zschoche. "Data Reduction for Maximum Matching on Real-World Graphs: Theory and Experiments." In 26th Annual European Symposium on Algorithms (ESA 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[2] Mertzios, George B., André Nichterlein, and Rolf Niedermeier. "The power of linear-time data reduction for matching." Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2017.

[3] Giannopoulou, Archontia C., George B. Mertzios, and Rolf Niedermeier. "Polynomial fixed-parameter algorithms: A case study for longest path on interval graphs." Theoretical Computer Science 689 (2017): 67-95.


Fast hashing algorithm for mapping/quantizing a collection of floats onto a small set of sorted floats

Take X, multiplied by say 10,000, rounded down to the nearest integer. In plain C, z = (int) (x times 10000.0).
There are 10,000 possible values of z. For most values of z, you can determine the index from z. So create a table with 10,000 entries. In the table, store an index i if you can prove that x should be mapped to i, knowing z, and store -1 if you can’t prove this.
As a result, you get the correct value probably in 9,980 of 10,000 values, and then you use whatever slow algorithm you have for the remaining 1 in 500 values.
PS. The same table size would be used for double precision numbers. Whatever the table size, there will be only few values X that cannot be mapped correctly using this method, maybe 10 or 20. If you take a table of size 10,000 then 99.8% or 99.9% are mapped correctly, and 0.1% or 0.2% need a slow algorithm. The exact same thing happens with double. You could use 1000 entries, then the 10 or 20 failing ones would be 1% or 2%.
And a nice thing is that this method will work however the Y values are distributed. Only if the number of Y values is larger, then you might want to increase the table size.


Is there anything that MUST be done on a multi-core CPU?

The question is: under what constraints?

There are certainly problems where, if we ask the question "can we solve this problem on hardware X in the given amount of time", the answer will be no.

But this is not a "future-proof" answer: things which in the past could not be done fast enough in a single core probably can be now, and we can't predict what future hardware will be capable of.

In terms of computability, we know that a single-tape Turing Machine is capable of computing all the same functions as a single or multi-core computer, so, runtime aside, there are no problems that a multi-core computer can solve that a single-core can't.

In terms of something like graphics, literally everything that is on the GPU could be done on the CPU... if you are willing to wait long enough.


How to perform matrix multiplication in Mixing Columns step of AES?

If you want to implement it, I suggest you read the spec.  The material you were given is probably not enough to implement it.

The reason that looks confusing is that it is not ordinary multiplication; it is multiplication in a finite field.  There are lots of resources where you can learn about finite fields.


How do you convert a regular expression to its disjunctive normal form?

The proof is by structural induction. I will define an operator $T$ that takes an arbitrary regular expression, and outputs an equivalent regular expression in disjunctive normal form:

Base cases: $T[\epsilon] = \epsilon$, $T[\sigma] = \sigma$, $T[\emptyset] = \emptyset$.
If $r = s + t$, then we define $T[r] = T[s] + T[t]$.
If $r = st$, by induction we know that $T[s] = s_1 + \cdots + s_n$ and $T[t] = t_1 + \cdots + t_m$, where $+$ doesn't appear in any of the $s_i$ or $t_j$. We define $T[r] = \sum_{1 \leq i \leq n} \sum_{1 \leq j \leq m} s_i t_j$.
If $r = s^*$, by induction we know that $T[s] = s_1 + \cdots + s_n$. We define $T[r] = (s_1^* \cdots s_n^*)^*$.

It is routine to prove by structural induction that $T[r]$ is a regular expression in disjunctive normal form which is equivalent to $r$.


Before adressing the actual questions, one remark on your work so far: the left cancellation in 2.a. is not correct in general, the critical pair would just be $x\circ(e\circ z) \approx x\circ z$. Consequently, you don't get the critical pair 2.b. The problem with this cancellation is that the equation you get does in general not follow from the axioms you started from; for example, if you are working in the language of rings, you might at some point derive the critical pair $0*x \approx 0*y$, but it would be incorrect to deduce $x\approx y$ (which would mean that you only have a trivial model). No sound rewriting procedure, including Huet's, should allow this reduction.

On the other hand, you are missing the critical pairs you get by unifying (variable-renamed versions of) $x\circ e$ or $x\circ i(x)$ with all of $(x\circ y)\circ z$ (i.e. using the second $\circ$). The resulting critical pairs are

$x\circ(y\circ e)\leftarrow (x\circ y)\circ e\to x\circ y$, which after reduction becomes the trivial equation $x\circ y\approx x\circ y$, and
$x\circ(y\circ i(x\circ y))\leftarrow(x\circ y)\circ i(x\circ y)\to e$, which cannot be reduced further and gives the rule $x\circ(y\circ i(x\circ y))\to e$ (assuming that $\circ\triangleright e$ in the precedence $\triangleright$ used to define the LPO, just as you did when orienting $x\circ i(x)\approx e$).

For the basic completion procedure:

Whenever you create a critical pair, you reduce both sides as far as possible using the current set of rules. If the resulting normal forms are not equal, you create a new rule. For example, your 2.c. gives a new rule $x\circ(i(x)\circ z)\to e\circ z$. On the other hand, unifying $(x\circ y)\circ z$ with $x_1\circ y_1$ gives the critical pair $(x\circ y)\circ(z\circ z_1)\leftarrow((x\circ y)\circ z)\circ z_1\to(x\circ(y\circ z))\circ z_1$, which can be reduced to the trivial $x\circ(y\circ(z\circ z_1))\approx x\circ(y\circ(z\circ z_1))$ and discarded.
Whenever you create a new rule $l\to r$, you must consider all critical pairs between it and the existing rules $l_1\to r_1,\dots,l_n\to r_n$, checking for unifiability of $l$ with each non-variable subterm of $l_i$ and vice versa. Also remember to check for self-overlaps, i.e. unifiability of $l$ with its own subterms, as we did above for associativity. You only stop when all critical pairs of the existing rules have been examined and either produced new rules, or been discarded.

This procedure can be improved quite a bit. In particular, you can use new rules to simplify old ones (and possibly discarding them if they become trivial, meaning they are subsumed by the new rule), and a good heuristic for picking the next critical pair to examine can drastically cut down on the amount of rules.


Genetic Algorithm, Neural Network, Deep Learning, Machine Learning Similarities and Applications?

Here's a quick dictionary:

Machine learning is a very broad subject encompassing mainly algorithms whose goal is classifying inputs to different categories. For example, an automated post system has to be able to read letters and digits. After the characters are segmented into individual characters using techniques from computational geometry, a computerized algorithm converts the images into digits and letters. Such an algorithm is trained using classified examples, that is, many examples of each digit and letter which are shown to the algorithm.
Neural networks are a machine learning algorithm loosely based on the works of the nervous system, including the brain. They are examples of the paradigm of deep learning.
Genetic algorithms are used to solve optimization problems (i.e. find the most stable structure supporting a bridge). They are loosely based on evolutionary biology.


Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties

Let $\tilde\Sigma = \{\tilde a,\tilde b\}$. It is well-known that the language $X = \{a^n b^n : n \geq 0\}$ is context-free. Let $h \colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $h(a) = h(b) = a$ and $h(\tilde a) = h(\tilde b) = b$. The following language is context-free:
$$ h^{-1}(X) = \{uv : u \in \Sigma^*, v \in \tilde\Sigma^*, |u| = |v| \}. $$
Let $t\colon \Sigma \to \tilde\Sigma$ be the homomorphism defined by $t(a) = \tilde a$, $t(b) = \tilde b$. The following language is regular:
$$
Lt(L)^R = \{ uv : u \in L, v \in t(L)^R \}.
$$
Since the context-free languages are closed under regular intersection, it follows that the following language is context-free:
$$
h^{-1}(X) \cap Lt(L)^R = \{ uv : u \in L, v \in t(L)^R, |u| = |v| \}.
$$
Finally, let $s\colon \Sigma \cup \tilde\Sigma \to \Sigma$ be the homomorphism defined by $s(a) = s(\tilde a) = a$, $s(b) = s(\tilde b) = b$. The following language is context-free:
$$
s(h^{-1}(X) \cap Lt(L)^R) = \{ uv : u \in L, v \in L^R, |u| = |v| \}.
$$
This is the language you're interested in.


Finding the union, subtraction, and intersection of two DFAs

Yes, your understanding on point 2 is correct.

Your understanding on point 3 is mostly correct, except where you say "mark final state as explained in 1st bullet point in point 1".  That statement doesn't type-check, as you can't do that to the $\epsilon$-NFA.  If you've created an $\epsilon$-NFA, then its states are of the form $S_1$ or $S_2$ (where $S_1$ is a state of DFA1 and $S_2$ a state of DFA2), not of the form $S_1S_2$.  So, it's not an option to mark $A_1F_2$ as final, as that's not a state of the $\epsilon$-NFA.  Fortunately, you don't need to do that.  You create the $\epsilon$-NFA as you described, then that works immediately with no further changes needed.  The final states of the $\epsilon$-NFA are the final states of DFA1 and the final states of DFA2.  (Perhaps you are thinking: create the $\epsilon$-NFA, convert it to a DFA using the subset construction, then mark final states specially.  But there's no need to mark final states specially: the subset construction already takes care of marking the final states correctly.)

No, you can't do this for intersection or subtraction.  Try it on some examples.  I think you'll quickly be able to find some examples where it goes wrong.  Also, my comments about point 3 apply here as well.


Approximating the biggest acyclic subgraph of a given weighted digraph $G= (V,E)$

First: The upper bound is as stupid as they come: Namely, that at most, the optimal solution contains all edges.

With this upper bound, our approximating algorithm now asserts the following statement:
In every weighted, directed graph $G =(V,E)$ there exists a subgraph $G' = (V,E'), E'\subseteq E$ so that $G'$ is acyclic, and $\sum_{e\in E'} weight(e) \ge \frac 1 2 \sum_{e\in E} weight(e)$, i.e. we can choose the edges in $E'$ so that they accumulate at least half of the weight of all edges in $E$.

To find such a graph $G'$, we enumerate the vertices in $V$ as $x_1,...,x_n$, and now create two edge sets using it:
$$
E_1 = \{(x_i,x_j)\in E\mid x_i<x_j \} \\
E_2 = \{(x_i,x_j)\in E\mid x_i>x_j \}
$$
Differently put, imagine the graph $G$. Now move the vertices, so that they form the line $x_1,...,x_n$ from left to right (while keeping the edges intact).
Now, for $E_1$, you remove all edges going left.
For $E_2$, you remove all edges going right.

Each of the corresponding graphs $G_1 := (V,E_1), G_2:=(V,E_2)$ is acyclic, and $E_1\dot\cup E_2=E$, i.e. $E_1, E_2$ contain all edges in $E$ exactly once.

Therefore, either $G_1$ or $G_2$ has to contain at least half of the edge weight, and thus one of them is the wanted subgraph.


clique, independent set, and minimum vertex cover

Of course, $n$ being the largest of the given answers will satisfy all conditions. You are expected to find the least upper bounds though.


Attempt to write a function with cubed log runtime complexity $O(\log^3 n)$

Your program is correct. Your could also iterate Math.Log(n)*Math.Log(n)*Math.Log(n) times. Not sure if that is considered cheating.


Problem Set Solutions/Interrupts & Exceptions/Problem 1

The question I have met in class before. I cannot add comment so I write here. Notice the note 'Assume that the result of an instruction can be written in the last cycle of its execution, and that a dependent instruction can (if selected) begin its execution in the cycle after that.' which means instead of WR in the 1st cycle after the completion of EXE, it WR in the last cycle of EXE.

E.g. The I1 starts its EXE in 2nd cycle and end in 5th cycle (2, 3, 4, 5). So I1's WR happens in the last cycle of EXE which is 5th cycle.

For the rest of the table you should fill them based on the given notes, kind of the manual of a specific processor. This is not the general case which you will encounter in other scheduler problems. Wish it helps you.


This problem, which I'll call CO for Column Ordering, is NP-hard.  Here's a reduction from the NP-hard problem Vertex Cover (VC) to it:

Decision problem forms of VC and CO

Let the input VC instance be $(V, E, k)$.  It represents the question: "Given the graph $(V, E)$, is it possible to choose a set of at most $k$ vertices from $V$ such that every edge in $E$ is incident on at least one chosen vertex?"  We will construct an instance $(A, k')$ of CO that represents the question: "Given the matrix $A$ with elements in $\{-1, 0, 1\}$, is it possible to permute the columns of $A$ such that a 1 appears before a -1 on at least $k'$ rows?"  These two problems are stated in decision problem form, whereby the answer to each is either YES or NO: formally speaking, it is this form of a problem that is NP-complete (or not).  It is not too difficult to see that the more natural optimisation problem form stated in the OP's question is roughly equivalent in terms of complexity: binary search on the threshold parameter can be used to solve the optimisation problem using a decision problem solver, while a single invocation of an optimisation problem solver, followed by a single comparison, is enough to solve the decision problem.

Constructing an instance of CO from an instance of VC

Let $n=|V|$ and $m=|E|$.  We will build a matrix $A$ with $(n+1)m + n$ rows and $n+1$ columns.  The top $(n+1)m$ rows will be formed of $m$ blocks of $n+1$ rows each, with each block representing an edge that needs to be covered.  The bottom $n$ rows contain vertex "flags", which will cause a column (corresponding to a vertex) to incur a fixed cost if it is included in the left-hand side of the CO solution (corresponding to a vertex being included in the vertex cover of the VC solution).

For each vertex $v_i$, create a column in which:

among the top $(n+1)m$ rows, the $j$-th block of $n+1$ rows all contain a +1 when edge $e_j$ is incident on $v_i$, and 0 otherwise, and
the bottom $n$ rows are all 0 except for the $i$-th, which is -1.

Create one more "fence" column that consists of $(n+1)m$ copies of -1, followed by $n$ copies of +1.

Finally, set the threshold $k'$ for the constructed CO instance: $(n+1)m + n - k$.  In other words, we allow at most $k$ rows in which a -1 appears before a +1.  Let's call this number of violating rows the "cost" of a CO solution.

Proof

The correspondence between a solution to the CO instance and a set of vertices in the original VC instance is: Every column to the left of the fence corresponds to a vertex that is in the set, and every column to the right of the fence corresponds to a vertex that is not.

Intuitively, the -1s in the top of the "fence" column force the selection of a subset of columns to be placed to its left that together contain +1s in all these positions -- corresponding to a subset of vertices that are incident on every edge.  Each of these columns that appears to the left of the "fence" has a -1 on a distinct row somewhere in the bottom $n$ rows, incurring a cost of 1; the +1s in the bottom of the "fence" ensure that all columns placed to its right incur no such cost.

Clearly a VC solution using at most $k$ vertices yields a solution to the constructed CO instance with cost at most $k$: Just order the columns corresponding to vertices in the vertex cover arbitrarily, followed by the fence column, followed by all remaining columns in any order.

It remains to show that a solution to the CO instance with cost at most $k$ corresponds to a vertex cover with at most $k$ vertices.

Suppose to the contrary that there exists a solution to the CO instance with cost at most $k$ that leaves some row in the top $(n+1)m$ rows with a -1 before a +1.  This row belongs to a block of $(n+1)$ rows corresponding to a particular edge $uv$.  Every row in this block in the original instance $A$ is identical by construction; permuting columns may change these rows, but does not affect the fact that they are identical.  Thus each of these $n+1$ identical rows has a -1 before a +1 in the solution, implying a cost of at least $n+1$.  But $k \le n < n+1$: contradiction.

Since each of the $m$ blocks of rows in the top $(n+1)m$ rows have a +1 before a -1, each of the corresponding edges is covered by a vertex corresponding to a column to the left of the fence: that is, this subset of vertices constitutes a vertex cover.  Since none of the top $(n+1)m$ rows have a -1 before a +1, the only place where cost can accrue in the solution is in the bottom $n$ rows, from columns placed to the left of the fence.  Each such column has cost exactly 1, so given that the cost is at most $k$, there must be at most $k$ such columns, and hence at most $k$ vertices in the cover.

Finally, it's clear that the CO instance can be constructed in polynomial time from the VC instance, meaning that if a polynomial-time algorithm existed for solving CO, any VC instance could also be solved in polynomial time by first constructing a CO instance as described above and then solving it.  Since VC is NP-hard, CO is too.


How to convert finite automata to regular expressions?

There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea.

State removal method

This algorithm is about handling the graph of the automaton and is thus not very suitable for algorithms since it needs graph primitives such as ... state removal. I will describe it using higher-level primitives.

The key idea

The idea is to consider regular expressions on edges and then removing intermediate states while keeping the edges labels consistent.

The main pattern can be seen in the following to figures. The first has labels between $p,q,r$ that are regular expressions $e,f,g,h,i$ and we want to remove $q$.

Once removed, we compose $e,f,g,h,i$ together (while preserving the other edges between $p$ and $r$ but this is not displayed on this):

Example

Using the same example as in Raphael's answer:

we successively remove $q_2$:

and then $q_3$:

then we still have to apply a star on the expression from $q_1$ to $q_1$. In this case, the final state is also initial so we really just need to add a star:

$$ (ab+(b+aa)(ba)^*(a+bb))^* $$

Algorithm

L[i,j] is the regexp of the language from $q_i$ to $q_j$. First, we remove all multi-edges:

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

Now, the state removal. Suppose we want to remove the state $q_k$:

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

Note that both with a pencil of paper and with an algorithm you should simplify expressions like star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅ (By hand you just don't write the edge when it's not $∅$, or even $ε$ for a self-loop and you ignore when there is no transition between $q_i$ and $q_k$ or $q_j$ and $q_k$)

Now, how to use remove(k)? You should not remove final or initial states lightly, otherwise you will miss parts of the language.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

If you have only one final state $q_f$ and one initial state $q_s$ then the final expression is:

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

If you have several final states (or even initial states) then there is no simple way of merging these ones, other than applying the transitive closure method. Usually this is not a problem by hand but this is awkward when writing the algorithm. A much simpler workaround is to enumerate all pairs $(s,f)$ and run the algorithm on the (already state-removed) graph to get all expressions $e_{s,f}$ supposing $s$ is the only initial state and $f$ is the only final state, then doing the union of all $e_{s,f}$.

This, and the fact that this is modifying languages more dynamically than the first method make it more error-prone when programming. I suggest using any other method.

Cons

There are a lot of cases in this algorithm, for example for choosing which node we should remove, the number of final states at the end, the fact that a final state can be initial, too etc.

Note that now that the algorithm is written, this is a lot like the transitive closure method. Only the context of the usage is different. I do not recommend implementing the algorithm, but using the method to do that by hand is a good idea.


Problems that are NP but polynomial on graphs of bounded treewidth

There are probably thousands of examples; there's a short list at ISGCI; the Wikipedia article has plenty of links. Search for "bounded treewidth" and "parameterized complexity treewidth" for many, many more.

Essentially, the problems become easy on graphs of bounded treewidth because:

Although it's NP-complete to determine if a graph has treewidth at most $k$ [1], there is, for every $k$ a linear-time algorithm to compute a tree decomposition of any graph that does actually have treewidth $k$ [2].
Once you have the tree decomposition, you can solve many problems by dynamic programming.

A simple example, which doesn't even use dynamic programming, is the Clique problem. Any clique of a graph must be contained completely in some node of the tree decomposition. That means that a graph of treewidth $k$ can have no clique of size greater than $k+1$ and, to find a clique of size at most $k+1$, you just have to see if each node of the decomposition contains the clique you're looking for. That can be done in linear time if $k$ is a fixed constant, since you're just checking for cliques in $O(n)$ graphs that each have at most $k+1$ vertices.

For a more complicated example, suppose you want to know if a graph $G$ of treewidth 4 is 3-colourable. First, compute the tree decomposition. Each vertex of the tree corresponds to a subgraph of at most 5 vertices of $G$. For each leaf of the tree, compute by brute force all 3-colourings of the corresponding subgraphs. This is in polynomial time because there are at most $n$ leaves, each corresponds to a subgraph with at most 5 vertices and there are at most $3^5=243$ 3-colourings of any such subgraph. Now, for each vertex $v$ of the tree that's adjacent to a leaf, enumerate all the 3-colourings that are compatible with possible colourings of the leaves adjacent to $v$.  (That is, the 3-colourings of the subgraph corresponding to $v$ that can be extended to a 3-colouring of the graph corresponding to $v$ and all its adjacent leaves.) At this point, you can forget about the colourings of the leaves, since everything you need to know about them is now encoded in the distance-1 vertices. Now, iterate up the tree.  You can imagine doing something similar for Hamiltonian path, constructing a path through the whole tree by joining up paths in the subtrees; that's more complicated.

[1] Arnborg, Corneil, and Proskurowski, "Complexity of finding embeddings in a k-tree"., SIAM Journal on Matrix Analysis and Applications 8(2): 277–284, 1987. DOI.

[2] Bodlaender, "A linear time algorithm for finding tree-decompositions of small treewidth", SIAM Journal on Computing 25 (6): 1305–1317, 1996. DOI.


Language of walks in a grid – context-free?

If your language $L$ were context-free then so would $L \cap u^* l^* d^* r^*$ be. However, $L \cap u^* l^* d^* r^* = \{ u^n l^m d^n r^m : n,m \geq 0 \}$, which is known not to be context-free (this can be proved using the pumping lemma).


Scheduling distributed computational graph

The general problem of mapping a graph, where nodes are computational  operations and edges are transfers of data (i.e. dependencies), to computational resources is known as graph partitioning.

The general graph partitioning problem is NP-hard and therefore not directly solvable. However, there are good heuristic approaches. There are a number of open-source frameworks for graph partitioning, for example Metis, Scotch and Zoltan.


Computing optimal assignments using little memory

Your problem is closely related to the assignment problem, and can be solved efficiently using techniques derived from that literature.  I'll show how to solve it, by building up a solution step by step.

Maximizing the lowest rating

Here is how you could efficiently find the assignment that maximizes the lowest rating.  First, focus on the associated decision problem:

Input: movie ratings; an integer $t$
Goal: find an assignment where each person is assigned to a movie they rate at least $t$ or higher

This decision problem is an instance of bipartite matching, and can be solved using standard algorithms for it.  Namely, look for any assignment that assigns each person a movie that they related at least $t$.

Now, to find the assignment that maximizes the lowest rating, use binary search over $t$.

This doesn't solve your problem yet, because it doesn't take into account that you want to resolve ties by maximizing the average rating.

Resolving ties by maximizing the average rating

First, find the largest value $t$ such that there exists an assignment where everyone is assigned a movie they rate $\ge t$.  (See above for how to do it.)  Now if there are multiple such assignments, we want to find one of them where the average rating is maximized.

How do we do that?  Answer: use a standard algorithm for the Hungarian algorithm.

In more detail, we do several steps:

Delete any (person,movie) rating where the person has rated the movie something less than $t$.  It's not OK to assign that person that movie.
Now, you have an instance of the assignment problem, where each person has rated some of the movies with scores that are $t$ or larger.  You want to find a matching assignment) that maximizes the average of the scores of assigned movies.  Since every solution must assign 1 movie to each of the 100 people, the size of every assignment is the same, so maximizing the average is equivalent to maximizing the sum.  Maximizing the sum of the ratings is exactly the assignment problem.  Therefore, you can use any standard algorithm for solving the assignment problem (e.g., the Hungarian algorithm).

This will find an optimal solution: i.e., an assignment that maximizes the lowest rating, and that resolves ties by maximizing the average rating.

If you want to find the top-5 solutions, you can use an algorithm for enumerating solutions to the assignment problem in a streaming/output-sensitive fashion.  See, e.g., Algorithm for a list of best solutions to the Assignment problem and Does Ford-Fulkerson always produce the left-most min-cut.


Lambda calculus lists construction explanation

There are several ways to define lists in lambda calculus. You can find them here.
Your definition doesn't seem to fit exactly in any of those (please, check that).
Anyway, I'll try to answer to your questions.

Lists (and many data types) can be defined in lambda calculus in terms of the way to deconstruct them.

If you are familiared with the fold operation, you know it follows this specification:

$fold\ Nil\ e\ f$ = $e$
$fold\ (Cons\ x\ l)\ e\ f$ = $f\ x\ (fold\ l\ e\ f)$

Many functions over lists can be defined with $fold$. For example, if you want to sum the elements of a list $l$ of integers, you can do:

$sum\ Nil = 0 $
$sum\ (Cons\ x\ l) = +\ x\ (sum\ l) = x + sum\ l$

Or just say:

$sum\ l = fold\ \, l\ 0\ +$

In this case, you can imagine that the $sum$ functions replaces the empty list with $0$ and the cons operator with '+'.

So, if we want to define lists in lambda calculus, a way of doing it is to define each constructor ($Nil, Cons$) to do the work of $fold$.
The fist step is to state that $fold$ is just the identity function ($\lambda x . x$).  Then we get the $fold$ specification to be our specification for $Nil$ and $Cons$:

($\lambda x . x$)$\ Nil\ e\ f$ = $e$
($\lambda x . x$)$\ (Cons\ x\ l)\ e\ f$ = $f\ x\ ((\lambda x . x)\ l\ e\ f)$

This is the same as:

$Nil\ e\ f$ = $e$
$(Cons\ x\ l)\ e\ f$ = $f\ x\ (l\ e\ f)$

Rewriting it a bit, we get:

$Nil$ = $\lambda e\ f.e$
$(Cons\ x\ l)$ = $\lambda\ e\ f. f\ x\ (l\ e\ f)$

So, this answers fits in the last form of definition of lists from the wiki (using right fold). But it is important to notice that is not the only way. The way you posted seems to do the same as here, but instead of using the $fold$ operator, using some sort of $destructor$, where:

$destructor\ Nil\ m\ n = m$
$destructor\ (Cons\ x\ l)\ m\ n = n\ x\ l$


What if the travelling salesman travelled by plane?

I suggest you read more about the Traveling Salesman Problem.  All of your questions are answered in other standard references (such as the Wikipedia link I gave).  No, the greedy algorithm is not optimal. You may be interested in the Euclidean TSP, which remains NP-hard.  The greedy algorithm is not optimal for that case, either.  No efficient algorithm is known that can always find the optimal solution, though there are algorithms that may be useful in practice.


Equivalent regular grammar with minimum number of nonterminals

A regular grammar corresponds directly to a finite automaton, mapping each non-terminal to a state. So this question is equivalent to asking how to minimize the number states in a finite automaton. Unfortunately, minimizing NFAs is hard. See, for example, Gregor Gamlich, 2007.


Why do we prefer DFS to find connected components?

Two components $G_1(V_1, E_1)$ and $G_2(V_2, E_2)$ are connected if and only if there is a path between any vertex $v_1\in V_1$ and any other vertex $v_2\in V_2$. Here I'm assuming that both components are known to be connected, i.e., there is a path between any pair of vertices $v_i, v_j$ in any component (so that finding a path between any pair of vertices between both components fully connects them).

Hence, in finding connected components the procedure consists of starting in any vertex of $G_1$ and collecting all nodes that are reachable from it. Clearly, this can be done either with depth-first search or breadth-first search:

Breadth-first search visits nodes in order of their depth from the start state, $s$. This way, it finds all paths of length 1, then length 2 and so on. Its main advantages are: it guarantees it will eventually find a solution (given sufficient memory, see below) and that the solution found is optimal; also, it can avoid transposition by maintaining a CLOSED list that stores all nodes previously expanded. Its main disadvantage is that it takes an exponential amount of memory (unless the graph being traversed is known to be polynomial but this is a rare case indeed).
Detph-first search generates paths of arbitrary length until a goal is found or a threshold is reached. Its main advantage is that it takes memory which is linear in the depth of the search tree developed. Its main disadvantage is that it cannot guarantee that it will ever find a solution and, if it does, that the solution is optimal.

Now, considering the problem stated above it becomes clear that the goal is not to reach a specific goal but to collect nodes reachable from the goal state. For this, there is no specific need to be optimal so that the question reduces to whether the available memory might be enough or not: whereas Breadth-First search does not provide any guarantee, Depth-First search does.

That is why we use Depth-First Search Mostly because: one, there is no need to find an optimal solution; second, memory matters!

Cheers,


What is the underlying pattern/rule in this question?

I believe the pattern you are looking for is dynamic programming. In the case at hand, the answer for a message can be based on answers for prefixes of the message. This leads to a linear time and linear space algorithm that computes answers for all prefixes in order of increasing length.


Lets say for the sake of argument we have 6 units of memory available and three processes in a current state where each holds 2 resources. Each process needs 3 resources to finish and release its memory units to use by the others. This state is not safe, in fact this state is deadlock. Each needs one extra memory unit to finish, but this would require another process to release its units. No ordering of these 3 processes will be safe.

You are not looking at the state of the program, but the entirety of the program, in which case, with no new resource creation and single threading, every state is safe.

Edit for clarity: From the definition of a state: "In computer science and automata theory, the state of a digital logic circuit or computer program is a technical term for all the stored information, at a given instant in time, to which the circuit or program has access".

The import point is "given instant". The state could be at the initial state as your argument would require, or it is at some arbitrary point in execution


Delete a consecutive range of leaves from a binary tree

Yes.  This can be done in $O(d)$ time.  As a nice consequence, if we have a balanced binary tree, then $d = O(\lg n)$, so range-deletion can be done in $O(\lg n)$ time, regardless of how large the range is.

This is hard to explain without a picture, but the key insight is this: it suffices to delete a set $S$ of nodes, where $S$ can be chosen so that $|S| \le 2d$.  (This will of course delete all of the descendants of every node in $S$.)  Since $|S| = O(d)$, the running time to delete the nodes in $S$ will be $O(d)$.  In other words, the interval $[i,j]$ can be expressed as a union of $O(d)$ subtrees.  Roughly speaking, the set $S$ will be chosen by taking a subset of the siblings of the nodes on the path from $i$ or $j$ to the root.

In particular, we will define

$$S = \{n : L(n) \subseteq [i,j] \text{ and } L(\text{parent}(n)) \not\subseteq [i,j]\},$$

where $L(n)$ is the set of leaves that are descendants of $n$.  I will show first that deleting $S$ has the desired effect, and second that that $|S| \le 2d$, from which it will follow that the range-deletion can be done in $O(\lg d)$ time.

Lemma 1. Deleting $S$ will have the effect of deleting leaves $i,i+1,\dots,j-1,j$ but not any of the other leaves.

Proof. Consider any leaf $\ell$ with $i \le \ell \le j$.  Then $\ell$ is a descendant of some $n \in S$: if $\ell \notin S$, then some ancestor of $S$ must be in $S$ (imaging walking up from $\ell$ along the path towards the root; consider the last ancestor $n$ of $S$ such that $L(n) \subseteq [i,j]$; since $L(\ell) =\{\ell\} \subseteq [i,j]$, such an ancestor must exist).  Conversely, a leaf $\ell$ is deleted only if it is a descendant of some $n \in S$; but by construction, $L(n) \subseteq [i,j]$ and $\ell \in L(n)$, so it follows that if leaf $\ell$ is deleted, $\ell \in [i,j]$.

Now let's show that $|S| \le 2d$.  Let $P(\ell)$ denote the set of nodes along the path from $\ell$ to the root.  Let $Q(\ell)$ denote the set of siblings of the nodes in $P(\ell)$ ($\ell$'s sibling, $\ell$'s parent's sibling, $\ell$'s parent's parent's sibling, and so on).  Then I claim:

Lemma 2. $|Q(\ell)| \le d$ for all $\ell$.

Proof. Since the tree has height $d$, $|P(\ell)| \le d$.  Now $|Q(\ell)| \le |P(\ell)| \le d$.

Lemma 3. $S \subseteq Q(i) \cup Q(j)$.

Proof. Suppose $n \in S$, so that $L(n) \subseteq [i,j]$ but $L(\text{parent}(n)) \not\subseteq [i,j]$.  Let $m$ be $n$'s sibling.  Note that $L(\text{parent}(n)) = L(n) \cup L(m)$.  It follows that we must have $L(m) \not\subseteq [i,j]$ (otherwise $L(\text{parent}(n)) \subseteq [i,j]$ and $n$ wouldn't be in $S$).  Also $L(n) \cap L(m) = \emptyset$ and $L(n)$ and $L(m)$ are adjacent intervals ($L(n) \cup L(m)$ is itself an interval; there is no gap in between $L(n)$ and $L(m)$).  It follows that either $i \in L(m)$ or $j \in L(m)$, i.e., $m$ must be an ancestor of either $i$ or $j$, i.e., either $m \in Q(i)$ or $m \in Q(j)$.

Lemma 4. $|S| \le 2d$.

Proof. Follows from Lemma 2, Lemma 3, and the union bound.

Caveat: I haven't checked whether rebalancing can also be done in $O(d)$ time.  For instance, for a balanced binary tree like an AVL tree or a red-black tree, we have $d=O(\lg n)$, and it would be nice if we could delete the entire range in $O(\lg n)$ time.  However, it's not clear whether this is possible.  While we can indeed delete the nodes in $S$ in $O(\lg n)$ time, I haven't checked whether it's possible to do all necessary subsequent rebalancing operations in $O(\lg n)$ time.  Rebalancing is certainly doable in $O((\lg n)^2)$ time, but I don't know whether it can be done in $O(\lg n)$ time.


Equisatisfiability in the reduction from 4-SAT to 3-SAT

You're right in saying that they should be equisatisfiable. And they are.

I'm not sure why you think converting your unsatisfiable $4-\text{SAT}$ instance into a $3-\text{SAT}$ instance would make it satisfiable. Because it doesn't.

If a $4-\text{SAT}$ instance is unsatisfiable, then no matter how you choose to assign truth values to your variables, there will be some clause that is not satisfied. Without loss of generality, let that clause be $(a \vee b\vee c\vee d)$. Since this clause is not satisfied by your assignment, it follows that all of $a, b, c$ and $d$ are false.

Now converting this into a $3-\text{SAT}$ instance gives you these pair of clauses: $(a \vee b \vee z)(\neg z \vee c\vee d)$. Note that since $a, b, c$ and $d$ are all false, in order for both of these clauses to be satisfied, both $z$ and $\neg z$ need to be true, which is impossible.

In other words, the resulting $3-\text{SAT}$ instance is also unsatisfiable.


Finding many different minima of nonlinear cost function

Suppose you have already found $x_0,\dots,x_{k-1}$ and now  your goal is to find $x_k$.  Let $\mathcal{R}$ denote the region of points that are orthogonal to $x_0,\dots,x_{k-1}$.  Then your problem is to minimize $G(x_k)$ subject to the requirement $x_k \in \mathcal{R}$.  This is a straightforward equality constraint in optimization, and can be handled in a number of ways.  Probably the simplest is to use projected gradient descent, which is like gradient descent but in each step you project the point onto the hyperplane $\mathcal{R}$.  Given how you have defined $\mathcal{R}$, the projection operation in this case is easy.


How can we minimize the total distance of cross pairs in an array

Let's follow Karolis's suggestion. Consider any solution with pairs $(a,b)$ and $(A,B)$ with $a \leq A$ and $B \leq b$, and write $A = a + \delta$, $B = b - \epsilon$. If we instead pair them $(a,B),(A,b)$, then instead of $|a-b|+|A-B|$ we get $|a-B|+|A-b|$. So we want to show
$$ |a-b|+|A-B| \geq |a-B|+|A-b|. $$
Substitute the expressions for $A,B$:
$$ |a-b| + |a-b+\delta+\epsilon| \geq |a-b+\epsilon| + |a-b+\delta|. $$
In terms of $C = a-b$, this is
$$ |C| + |C+\delta+\epsilon| \geq |C+\epsilon| + |C+\delta|. $$
Rearranging, this is the same as
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$
So we need to look at the function $D \mapsto |D+\epsilon| - |D|$, whose values are
$$ |D+\epsilon| - |D| = \begin{cases} \epsilon & D \geq 0, \\ 2D+\epsilon & -\epsilon \leq D \leq 0, \\ -\epsilon & D \leq -\epsilon \end{cases} $$
We see that this is an increasing function of $D$, and so $C+\delta \geq C$ implies the inequality we want,
$$ |(C+\delta)+\epsilon| - |C+\delta| \geq |C+\epsilon| - |C|. $$


Prove Subset-Sum is NP-complete - Alternative reduction?

In general, each $NP$-hard problem can be reduced to all other known $NP$-hard problems (there exist hundreds).

For the subset-sum there is for a example knapsack. Subsetsum is a specialisation of knapsack.

The other way, if you could solve subset-sum in poly-time, then you would also be able to solve PARTITION (and 3-PARTITION and 4-PARTITION)


Where is the second face in a graph with 3 nodes?

You probably smack your head against the wall for this but: One face "inside" the triangle, the other one is "outside".


True
True
False

To find the proofs, proceed as follows:

Show that any string $x \in R \cup S$ belongs to $S \cup R$, and vice versa.
Ditto 1.
Find a string $x$ that is in $(R \cup S)^*$ but not the LHS. Hint: what about $rsr$ where $r \in R, s \in S$?


The second loop in your solution requires time $O(\log n)$ and can be safely ignored since its time complexity is dominated by the previous sorting step.
The call to Quicksort requires time $O(n \log n)$ in expectation and $O(n^2)$ in the worst case.
You can solve your problem in $O(n)$ worst-case time as follows:
create a max-heap with the elements in the array. Then, perform $\log n$ extract-max operations.
Creating the heap takes $O(n)$ time while each of the maximum extractions requires $O(\log n)$ time, for a total time of $O(n + \log^2 n) = O(n)$.


As mentioned by the OP in the comments, CLRS is using the ideas of Fredman, Komlós and Szemerédi, Storing a Sparse Table with $O(1)$ Worst Case Access
Time.

Corollary 4 gives a range of parameters for which the construction succeeds with probability $1/2$; this could be amplified to any constant with minimal loss of parameters.

Lemma 2 shows how to derandomize the construction, but the resulting algorithm isn't practical.

You can also probably choose parameters for which the construction succeeds with high probability, in which case you can try your luck and not even check the hash function.


Can you increase data rate by increasing number of bits?

Theoretically you can, but in reality you can not. The problem in raising the number of bits one symbol represents is that you have to space the symbol levels closer and closer together. Therefore even small amounts of random noise lead to misinterpreted symbols. A first attempt at calculating the maximum data rate is Nyquist's formula:

maximum data rate [bit/s] = $2H\cdot log_{2}(V)$

Where $H$ is the bandwidth in $Hz$ and $V$ is the number of symbol values.

This formula indicates that unlimited data rate can be achieved when enough symbol levels are used, but, as we have already seen, that is not possible because of random noise. Shannon's formula takes that into account:

maximum data rate [bit/s] = $H\cdot log_{2}(1 + S/N)$

Where $S$ is the signal strength and $N$ is the noise level.


Automatic Downcasting by Inferring the Type

Upcasts always succeed.

Downcasts can result in a runtime error, when the object runtime type is not a subtype of the type used in the cast.

Since the second is a dangerous operation, most typed programming languages require the programmer to explicitly ask for it. Essentially, the programmer is telling the compiler "trust me, I know better -- this will be OK at runtime".

When type systems are concerned, upcasts put the burden of the proof on the compiler (which has to check it statically), downcasts put the burden of the proof on the programmer (which has to think hard about it).

One could argue that a properly designed programming language would forbid downcasts completely, or provide safe casts alternatives, e.g. returning an optional type Option<T>. Many widespread languages, though, chose the simpler and more pragmatic approach of simply returning T and raising an error otherwise.

In your specific example, the compiler could have been designed to deduce that parent is actually an Apple through a simple static analysis, and allow the implicit cast. However, in general the problem is undecidable, so we can't expect the compiler to perform too much magic.


How is the oracle function for Grover's Search algorithm obtained?

Here's the problem Grover's algorithm helps you solve:

Input: a function $f$
Output: a value $r$ such that $f(r)=0$

If you're paying attention, you should ask how $f$ is specified.  This is the oracle part: $f$ is provided as a black box.  That means, given any $x$, the algorithm can evaluate $f(x)$, but the algorithm can't "look inside the black box" and see how $x$ is represented.  So, the algorithm doesn't have a way to "look at the choice of oracle function"; all the algorithm can do is supply some value $x$ and ask for the value of $f(x)$, and do that over and over again.

Why is this useful?  There are some situations where we can easily specify a function $f$ but it seems to be very hard to find a value $r$ such that $f(r)=0$.  (In fact, in many of those situations, even knowing how $f$ is implemented doesn't seem to help.)  For instance, $f$ might be the SHA256 cryptographic hashing function: given any string $x$, we can efficiently compute its hash $f(x)$, but there seems to be no way to invert it short of trying lots and lots of candidate strings to see if any of them work.

Another example is $f(x,y)=x \times y - 179...23$, where $179..23$ is some specific large number that is known to be a product of two primes but whose factorization is unknown (we don't know what the primes are) -- we probably wouldn't actually use Grover's algorithm on that specific example, but it illustrates an example where we know how to specify a function where it's still hard to find an input that maps to zero.

Take a look at https://en.wikipedia.org/wiki/One-way_function and https://en.wikipedia.org/wiki/Grover%27s_algorithm.


Existence of particular/specialized halting oracles

Yes. Given a machine $M$ and input $I$, one of the two things happens:

$M(I)$ halts.
$M(I)$ does not halt.

We may not be able to predict or compute which of these happens, but one and only one happens simply by rules of classical logic.
Now to show that $H_{M,I}$ exists we consider two cases:

If $M(I)$ halts then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "yes".
If $M(I)$ does not halt then $H_{M,I}$ exists because we can take it to be a machine that immediately halts and outputs "no".

Note: we proved existence of $H_{M,I}$, but we did not give a way of computing $H_{M,I}$ from $M$ and $I$, which is impossible as that would give us the halting oracle (exercise).
So, what Yuval said.


Indeed, this is the prototypical NP-complete language.

Recall what NP-hardness means: For all languages $L'$ in NP, there is a polynomial time reduction from $L'$ to $L$.
Normally, when one wants to prove NP-hardness, one takes a language $L''$ which is itself already known to be NP-hard and establishes a reduction from $L''$ to $L$.

But not so in this case! It is much more natural to directly construct a reduction from $L'$ to our $L$, only using the fact that $L'$ belongs to NP.


Remove x last elements of an array and reinsert them before position y

We can assume without loss of generality that $y$ is the first position, and that the first position is zero. Suppose that there are $n$ elements in the array. Then we want to apply the permutation $\pi(i) = (i+x) \pmod n$. Two elements $i,j$ are in the same cycle of $\pi$ if $i \equiv j \pmod {(n,x)}$, which means the the cycle leaders (minimum elements of each cycle are $0,\ldots,(n,x)-1$. In other words, for each $j < (n,x)$, we need to consider the elements
$$
A[j],A[j+x],A[j+2x],\ldots,A[j+(n/(n,x)-1)x]
$$
and rotate them one step to the right. This can be done using constant memory, and takes time $O(n/(n,x))$. Overall, the running time will be $O(n)$.

You don't actually need to determine $(n,x)$. Instead, you can simply count how many elements were touched. For example, you can consider the following pseudocode:

touched = 0
current = 0
while touched < n:
    origin = current
    element = A[current]
    repeat:
        current = (current + x) mod n
        swap A[current] and element
        touched = touched + 1
    until current = origin
    current = current + 1
end while


What is an extremely basic asymmetric cipher that I can present at the pub?

If you want to present public key cryptography to your parents or friends, then I suggest you follow some guidelines. First, don't talk about specific functions, nobody cares about SHAxxx, keep your talk conceptual. The problem solved by public key cryptography is allowing two parties who never met before to securely exchange information in a public channel. Do not confuse this with other applications that are achieved by public key encryption, such as digital signatures or authentication.

An illuminating simple illustration of this that I have seen is the following. Suppose that two parties have a bucket and a number of colors, and they want to agree on a specific secret compound. They are allowed to send each other a bucket with a certain compound, but anything sent is exposed to an evil adversary. The underline assumption is that mixing colors is easy, but decomposing a mixture to its ingredients is hard. This assumption (which is easily connected to the formal side of things) allows you to achieve their goal. Pick a public color $P$, and allow both parties to pick a secret color, let us denote them by $S_1,S_2$. The first party then sends a bucket of a mixture of $P,S_1$. Similarly, the second party sends a bucket containing a mixture of $P,S_2$. Finally, each side adds his private color to the mixture he received, and now both parties have a mixture of $P,S_1,S_2$, which (by our assumption) remains secret from any eavesdroppers. A formal version of this is the Diffie-Hellman key exchange protocol, which relies on the hardness of discrete log.

Now, my understanding of the bitcoin protocol is limited, but when talking to your parents about it, I see no reason to go into cryptography. Most of the popular explanations I have seen unnecessarily delve into implementation details, and start talking about finding a preimage of a hash such that the result would have $x$ number of zeros, loosing sight of the actual problem. As before, I suggest to keep the talk conceptual. What problem is the bitcoin trying to solve, and why isn't this trivial? To my understanding, the bitcoin solves the problem of maintaining a distributed ledger, specifically avoiding the double spending problem. The motivation is to avoid having a central authority, and this can be achieved by allowing each participant to approve a transaction (instead of giving this authority to the bank). To avoid adversarial participants approving their own invalid transactions, the concept of proof of work is introduced. POW uses the hash as a black box, so you can avoid mentioning specific candidates.


Could someone check my recursive program correctness proof that returns $F(x, y) \rightarrow x + y$?

As mentioned by Apass.Jack, you cannot apply IH to the $y>0$ case, since $ (x+3)+(y-1)=x+y+2>k$. I think you will want to do induction on $k=\min(x,\,y)$. Then you have no problem applying IH, since either $x$ or $y$ will always be smaller in the recursive call. The only difficulty here is that in your base case, you now need to cover when one of $x$ or $y$ is zero and the other is arbitrary. I will omit the case when both are zero, for brevity.

In the case that $y$ is zero, then the result will be $\text{FUN}(x-3,\,0)+3$. If $x$ is a multiple of 3 and positive, then this will eventually give $\text{FUN}(0,\,0)$ and then 3s will be added until you get $x$ again. This is what you wanted, since $x+y=x+0=x$. Note that the recursive calls retain the conditions that $x\geq0$ and a multiple of 3.

In the case that $x$ is zero, then the result will be $\text{FUN}(3,\,y-1)-2$, assuming your algorithm terminates, since if the algorithm took the $\text{FUN}(-3,\,y)+3$ branch, then there would be an infinite recursion. This implies that $y>0$ initially. Then this branch will continue to be taken until $y=0$, in which case we will return $\text{FUN}(3y-3,\,0)+3$. This is the case when $x>0$ and $y=0$, covered above. Then we get $3y-3+3-2y=y=0+y=x+y$. The $-2y$ comes from subtracting 2 recursively $y$ times.


To solve this, consider what happens when exactly $k$ corners of $C$ lie inside $T_1$, for $k\in \{0,1,2,3,4\}$, where $C\setminus T_1$ denotes the area of $C$ not covered by $T_1$:

If $0$ corners of $C$ lie in $T_1$, then $T_1$ doesn't cover any corner of $C$. So any rectangle covering $C\setminus T_1$ must cover all corners of $C$, so the smallest of these rectangles is $C$ itself.
If exactly $1$ corner of $C$ lies in $T_1$, the $C\setminus T_1$ contains $3$ corners of $C$ and the smallest rectangle covering this area is again $C$ itself.
If exactly $2$ corners of $C$ lie in $T_1$, then $C\setminus T_1$ is a rectangle, so the smallest rectangle covering it is itself. More precisely, this is the rectangle with as corners the two intersection points of the edges of $C$ and $T_1$ and the two corners of $C$ not covered by $T_1$.
If $3$ corners of $C$ lie in $T_1$, then $4$ corners of $C$ lie in $T_1$, so $k$ cannot be $3$.
If $4$ corners of $C$ lie inside $T_1$, then $C$ is fully covered by $T_1$, so the smallest rectangle covering the remainder has area $0$.

So, to determine the size of the smallest rectangle covering $C\setminus T_1$, we simply count the number of corners of $C$ inside $T_1$, apply the proper case and we're done.


That's why buffers are used.

While the transfer is in progress the peripheral writes the data into a buffer and the cpu ignores it and just works on its own clock.

Then when the transfer to the buffer is complete the peripheral will issue an interrupt (or other toggle a transfer complete pin) and the cpu will read from the buffer and if applicable let the next transfer start.

The buffer used can be the RAM this is often referred to as Direct Memory Access. The peripheral is attached to the memory bus and can issue reads and writes to ram directly.


I don't think there is an algorithm that works for any infinite probability distribution. However, you have taken the case of a geometric distribution for which there happens to be a neat answer. It was proposed by Gallager in this paper [1]. So if you apply his algorithm, you will see that you obtain exactly the same answer you proposed.

[1] Gallager, R., & Van Voorhis, D. (1975). Optimal source codes for geometrically distributed integer alphabets (corresp.). IEEE Transactions on Information theory, 21(2), 228-230.


How does this answer for automata and Hamming distance not lead to inconsistencies?

Consider the case where $k=1$. In other words, we're allowing a single error. We take our base automaton and apply this "error-allowing transformation" to it.

The transformed automaton generally works as follows:

The state $(q, 0)$ means "the underlying automaton is in state $q$, and we haven't made an error yet".
The state $(q, 1)$ means "the underlying automaton is in state $q$, and we have made a single error".
From any state $(q, 0)$, we can make the "correct" transition, or make any "incorrect" transition (a transition meant for any other symbol) and change the $0$ to a $1$.
From any state $(q, 1)$, we can only make the "correct" transition. In other words, once we've made one mistake, we can't make any more!
If we reach either $(a, 0)$ or $(a, 1)$, where $a$ is an accepting state, then we accept.

Hopefully this makes sense; let me know in the comments if it doesn't.

Now the key is, this works for any base automaton. So if we want $k=2$, we can just apply this transformation once, and then apply the transformation again!

The states now look like $((q, 0), 0)$. If we reach the state $((a, 1), 1)$, then we've made exactly two errors. And once we've made exactly two errors (there are no more zeroes to turn into ones), we're not allowed to make any more errors, we have to follow the base automaton exactly.

And then you can apply the transformation again for $k=3$, and again for $k=4$, and so on, for any natural $k$. Induction! QED.

(Another way to prove it is to allow errors in every state $(q, \psi)$ as long as $\psi < k$. This way doesn't involve induction, and might be a bit easier to grasp, since you have a straightforward "error counter".)


Is polynomial over x with real roots decidable?

Maybe I should summarize what I was saying in the comments.
Yes, the problem should be formulated precisely in order to give an answer.
About the cases in which the answer is NO:
For those formulations in which the answer is NO it is usually for a trivial reason. For example, one case that is mildly interesting is if we are considering the polynomials with coefficients that are computable numbers. These are numbers for which there is an algorithm such that for any given precision it terminates and gives you the digits of the number up to that precision. So, the input of $D_1^*$ in that case, would be a finite collection of such algorithms, one for each coefficient. Well, in this case $D_1^*$ cannot be decided, even for a constant polynomial. This is just because we cannot tell if that constant is zero or not.
The context in Sipser's book:
Now, I looked at the book by Sipser. They mention $D_1$ in the context of the Hilbert's tenth problem, which concerns polynomials (in several variables) with integer coefficients. In this context and many others you can indeed decide $D_1^*$.
The interesting part:
If the coefficients are such that we can (algorithmically) perform the following operations:

sum, subtraction, multiplication, division,
test if positive, test if negative, and test if zero.

Then we can decide if a polynomial has a real root.
For example, we can consider $D_1^*$ as a problem about polynomials with integer coefficients, or rational numbers, or constructible numbers, or algebraic numbers, or perhaps consider the problem with arbitrary real numbers but in a Blum-Shub-Smale machine instead of a Turing machine. As long as we can do the six basic operations above, we should be okay.
One way to decide could be using Sturm's theorem. Sturm's theorem says that the number of real roots of a square free polynomial with real coefficients in an interval $(a,b]$ is equal to the difference of the number of changes of sign at $a$ and the number of changes of sign at $b$ of the values of a Sturm sequence. See in the link above.
If the polynomial input $p$ has complex coefficients we can just work with the $\gcd$ of its real and imaginary parts. If the polynomial is not square-free, then we divide it by the $\gcd(p,p')$ to make it square-free. These transformations don't preserve the answer. Remember that one can compute $\gcd$ using using the Euclidean algorithm. So, we only need the arithmetic operations mentioned above.
One way to construct a Sturm sequences is the following: The first term is $p$, the second term is $p'$, the derivative of $p$. If $q_i,q_{i+1}$ are two consecutive terms of the sequence constructed so far, then the next term $q_{i+2}$ is equal to the remainder of $q_{i}$ divided by $q_{i+1}$ and with the sign switched. This procedure is always finite since remainders always have smaller and smaller degrees.


What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?

It can be shown that the context sensitive grammars you describe are equivalent to just asking for productions $\alpha \to \beta$ with $\lvert \alpha \rvert \le \lvert \beta \rvert$. So allowing productions $A \to \varepsilon$ just removes the restriction on lengths, and you have landed on unrestricted grammars.


How can P=NP relate to creativity and proof automation, as said by Scott Aaronson?

There is a relatively often cited quote

  "If P=NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss; everyone who could recognize a good investment strategy would be Warren Buffett."

However, Scott has later distanced from it:

  Given how many confusions and weird misinterpretations it’s spawned, I, Scott Aaronson, hereby formally disown my statement about how “everyone who could appreciate a symphony would be Mozart” if P=NP.

(source)


Does $(a \mid b)^*$ match $a^n$ and $b^n$?

Yes: $(a\mid b)^*$ is the concatenation of any number of $a$'s and $b$'s, so the expression matches $a^n$ and $b^n$.

As you can read more about on Wikipedia, the vertical bar $\mid$ is the boolean "or" relation (one or the other must be included in the regular expression), while the asterisk $^*$ indicates that the preceding element is repeated zero or more times. Hence:

$(a\mid b)^*$ is equivalent to $(a\;|\;b)(a\;|\;b)(a\;|\;b)\cdots$ repeated any number of times (even zero).

For each term, you can select either $a$ or $b$, so strings like $aa$, $aaaa$, $bb$ and $bbb$ are valid.  In particular, this expression matches the empty string $\epsilon$, which has zero $a$'s and zero $b$'s.


Reduction from minimum dominating set to the set cover

Let $G$ be an instance of dominating set and construct an instance of $(U,\mathcal{S})$ of set cover as you describe. The claim is that $G$ has a dominating set of size $k$ if and only if there is a subfamily $\mathcal{S}' \subseteq \mathcal{S}$ with $k$ members that covers $U$.

In the first direction, which you indicate is clearer, let $D$ be a dominating set of size $k$. Construct $\mathcal{S'}$ by adding into it the set corresponding to the closed neighborhood of every $v \in D$. Clearly, $\mathcal{S}'$ has size $k$ as $D$ has size $k$. Further, by the definition of a dominating set, $\mathcal{S}'$ also covers $U$.

In the second direction, let $\mathcal{S}'$ be a set cover for $U$. Build $D$ such that if the set $S_v$, the set corresponding to the closed neighborhood of $v$, is in $\mathcal{S}'$, add the vertex $v$ to $D$. Because $\mathcal{S}'$ covers $U$ which by construction corresponds to the vertex set of $G$, we have that $D$ is a dominating set. Moreover, we clearly have that $D$ has size $k$ as $\mathcal{S}'$ has size $k$.

Your second question however is unclear. A reduction "being related to another reduction" is not a formal statement. In an informal sense, you can use similar ideas to establish other reductions between dominating set, set cover and/or vertex cover but you have to work through the details yourself.


Stroke Width Transform: Gradient Direction and Rays

You basically have to sample points from p in the direction of p's gradient dp.
You get the dp from the x and y gradient maps. And sample from where? from the edge map and the gradient maps. First check if it is a edge from the edge map. If it is not then take another step in the dp direction. If it is an edge then compute the gradient direction from the x and y gradient map. If that gradient points back to p with about π/6 of tolerance then that is the q you are looking for.

Be careful with back over while vs white over black. The gradients will point in opposites directions when you invert the image. That is why you have to run the algorithm twice since SWT does not know which case are we dealing with. One with the original gradient directions and another flipping the gradients in the opposite direction.


NP-COMPLETE:Why say "reduction algorithm computes reduction function"?

A function is a mapping from elements in the domain to elements in the range. Here is an example of a function: $f(n) = n!$. If you want a machine to compute $f(n)$ given $n$, you need an algorithm, for example: given $n$, multiply together all the numbers from $1$ to $n$. There can be other algorithms for computing $f$. The function exists without reference to a machine. In fact, some functions (such as the halting function) cannot be computed by any algorithm.

You might be confusing the mathematical meaning of the term function with its meaning in programming languages, which is what you describe.


How all values hash to the same value with a given formula

They want you to interpret a string of characters as a multi-byte integer.
So for example abe is intended to mean:
256^2*a + 256*b + e


Is "represents" a symmetric relation in the provided answer to TAOCP exercise 1.1.9?

I slept on it and remembered there was another wording issue that was bugging me: "generates an equivalence relation". I wasn't familiar with it and assumed it just meant "is an equivalence relation". Turns out I was wrong. It has a very specific meaning that Wikipedia describes thusly:

  Given any binary relation $A \subset X \times X$ on $X$, the equivalence relation generated by $A$ is the intersection of the equivalence relations on $X$ that contain $A$.

In short, no, "represents" isn't a symmetric relation, nor did Knuth claim it is; he claimed that an equivalence relation could be constructed from it, which is true. Apparently my "knowledge of high school algebra", listed as the primary prerequisite to reading, is lacking.


Help wrapping my head around a combinatorial optimization problem

Here is a complete MIP (Mixed Integer Programming) model that should do the trick. I just use some random data (weights) with 100 widgets and 50 possible bins. When solved the variable NumUsedBins gives the maximum number of bins and the variable x gives the assignment. The equation 'order' is to make sure we use lower numbered bins first. The strange statement about optcr is to tell the solver to solve to optimality (for very difficult problems you may want to stop at 5% or so).

With 1000 widgets this becomes somewhat difficult to solve to optimality.


Polynomial time reducibility is an equivalence relation

A polynomial-time reduction from $A$ to $B$ is a polynomial-time computable function $f$ that maps an instance $x$ of a problem (language) $A$ to an instance $f(x)$ of a problem $B$ such that $x \in A \iff f(x) \in B$.
Polynomial-time (Karp) reductions are reflexive (since $A \le_p A$), as it follows by choosing $f(x) = x$.
Polynomial-time reductions are transitive, i.e, if $A \le_p B$ and $B \le_p C$ then $A \le_p C$ by choosing $f = h \circ g$, where $g$ (resp. $h$) is a polynomial-time computable function such that $x \in A \iff g(x) \in B$ (resp. $x \in B \iff h(x) \in C)$.
However, Polynomial-time reductions are not symmetric. That is, it is not true that $A \le_p B \implies B \le_p A$.
Consider for example a binary alphabet, $A = \{0,1\}^*$, and $B = \{0\}$.
The function $f(x) =0$ is a valid polynomial-time reduction from $A$ to $B$ but there is no polynomial-time reduction from $B$ to $A$.


Does "output" always imply halting in computability?

The output of Turing machine is the content of the tape when it halts.

This is the standard definition. If a machine has written some string $s$ to its tape but hasn't halted yet, a straightforward reduction from the undecidability of the halting problem means that you have no way of knowing if it will ever write more characters to its tape, so you can't know if $s$ will be the "final" output. That means, for example, that you can't say that, if a non-halting computation never changes the string on the tape after the $t$th step, then the output is that unchanging tape string.

However, see Andrej's answer for a way of getting a well-defined output from a non-halting machine. The key point there is that the output tape is read-only so once a bit of the output has been written, you know that bit will never change.


If $L = L(M)$ then $L$ is a subset of $L(M)$ and $L(M)$ is a subset of $L$

This is just a set-theoretical equality. Two sets are equal precisely when they are included in one another: $A = B$ iff $A\subseteq B$ and $B\subseteq A$. The notation is applied in the context of languages of automata. In order to show an automaton $M$ defines language $L$, you have to show it accepts all strings from $L$, and no more than those strings.

Basic, when doing automata and language theory, I am afraid.


Avoiding overflow in computing the ratio of two large numbers

Yes, when $x\ge355$, computing $e^{2x}$ as a double-precision float in IEEE 754-1985 standard, leads to an overflow.

$$x + \frac{e^x-x}{e^{2x} + 1}= x + e^{-x} - \frac{x+e^{-x}}{e^{2x} + 1}\approx x+ e^{-x}$$

The difference between the two sides of the approximate sign is smaller than the minimal positive number in IEEE 754-1985 standard, $2^{−1022} \approx 2.225×10^{−308}$, when $x>367.2$.

So, once $x>367.2$, you can just use $x+e^{-x}$ instead.


How to prove that the minimum square partition of a 3X2 rectangle has 3 squares

The case $w = 3$ is somewhat boring. Here is how to show that you need at least three squares. There is some square $S_1$ touching the bottom-left corner. There is some square $S_2$ touching the bottom-right corner. These squares must be different. At least one of them doesn't go all the way to the top, and so one of the other two corners remains uncovered, requiring another square.

I'm not sure how to extend this proof beyond $w > 3$. Let me just mention that a classical result of Dehn shows that if an $h \times w$ rectangle can be tiled by squares then $h/w$ is rational, and moreover there is some integer $c$ such that if you scale everything by $c$ then all squares have integer sides.


Hashing using search trees instead of lists

For lists, insertion, find and delete are respectively in $O(1)$, $O(n)$, $O(n)$. Sorted list are worse. Binary search itself is for sorted arrays, in which the operations are in $O(n)$, $O(\log n)$, $O(n)$. If you want "insertion" and "delete" operations then you need more than just binary search.

You probably want something like binary search trees. It is a lot easier to find references about it once you have the proper terminology. These operations are in $O(\log n)$ worst-case time, for example for the implementations using AVL trees and red-black trees.


How do I apply patch sized features to larger images?

The options are various.

If you want a naive and easy workaround simply resize your image (shrink it) and trust that the interpolation would preserve information.

If not, you might want to use Gaussian Pyramids or Spatial Pyramid Match Kernels:

http://www.ifp.illinois.edu/~jyang29/papers/CVPR09-ScSPM.pdf
http://www.vision.caltech.edu/Image_Datasets/Caltech101/cvpr06b_lana.pdf

Other options are a bit untidy. For example, you might take overlapping samples from it, apply some sort of feature extraction and if those features are still big for you, apply a PCA or LDA for dimensionality reduction. (There are more clever sampling strategies such as farthest point sampling : http://webee.technion.ac.il/people/zeevi/papers/17-00623193.pdf

Also taking a look at the covariance matrices might provide you relevant information. Why don't you also check:

http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en/us/pubs/archive/36416.pdf

Cheers,


Efficient cardinality of set overlap relation

Consider the following problem. We are given $n$ sets $S_1,\ldots,S_n \subseteq \{1,\ldots,\log n\}$, and have to decide whether there are two disjoint sets among them. This problem is known as Orthogonal Vectors (OV), and it is conjectured that it cannot be solved in time $O(n^{2-\epsilon})$ for any $\epsilon>0$ (on a RAM machine). See for example Chen and Williams, An Equivalence Class for Orthogonal Vectors.