Is this passage from the textbook Artificial Intelligence: A Modern Approach incorrect?

Yes.  You are right.  That looks like an error in the textbook.  Check their errata, or send the authors a note to let them know.


"Flow layouts" inside a GUI -- how do I come up with a good algorithm?

I've encountered variations of this problem several times doing GUI layout work. Your question about "What should I optimize?" is key to answering your question. Until you've decided that you really can't create a better algorithm.

More than likely you'd like to consider the size-ratios. Each child will have likely a minimum size, possibly a maximum in each dimension, and a preferred ratio, or range of acceptable ratios. You can use this basic data to make a guess as to what the layout should be. Now, for the resulting layout of each child you need a way to produce the preference score.

Now you simply have an optimization problem: maximize the total score of all the children. You can also include global scoring attributes, like the parent size (to cover your second problem).  Some layouts you can also reject if they produce invalid results (parent too wide, child not acceptable).

Depending on how many children you have, and how optimal your layout needs to be, will determine how good your algorithm needs to be. For a very simple greedy approach you can simply do line-based. For example, just consider two lines at a time, the current line, and the next line. You should be able to come up with a list of items that easily have enough space on this line, and some that maybe don't. Then just try a few combinations of those trailing components (this line or next) and find a maximum score.


Number of planar graphs, given an embedding

Pach and Wenger proved in their paper Embedding planar graphs at fixed vertex locations that if $p_1,\ldots,p_n$ are $n$ different points on the plane, then every planar graph on $n$ vertices $v_1,\ldots,v_n$ has a planar embedding in which $v_i$ is found at position $p_i$.


Is there an algorithm to compute the shortest Hamiltonian path in an directed graph from one point to another in polynomial time?

Here's a small hint.

Let $G$ be a directed graph with unit weights, and $u$ and $v$ be two vertices.  Suppose that I could solve SHP in polynomial time, say, $O(n^c)$.

Now, say that I would like to solve Hamiltonian Path on a directed graph.  Let me spend $O(n^2)$ time to "guess" your vertices $u$ and $v$, and for each of them run your algorithm for SHP.  Then, I would in $O(n^{c+2})$ time have either found a Hamiltonian path in $G$, or conclude that $G$ is not Hamiltonian.

That would mean that P = NP.

Now, this doesn't prove that your problem in NP-complete.  For that, you need to come up with a reduction.  But it does tell you that you should probably not spend too much time looking for a polynomial time algorithm.


Can anyone find a mapping from the set of all possible string to the natural numbers?

Just pretend that your alphabet $S = \{0, \dots, s\}$ for some $s$ and then a string in $S^*$ is just a natural number written out in base $s+1$. There's the slight wrinkle that $0$, $00$, $000$, etc. are all representations of zero, but that's easily fixed by associating the string $x$ with the number whose base-$(s+1)$ representation is $1x$ (i.e., $x$ with a $1$ stuck on the front).


Can most programs (except the IO part) be re-written as a sequence of matrix operations?

If you regard the output of a program as a function of its input then matrices can be used to represent some programs, namely those where the output is a linear function of the input. So a program that takes two arguments $a$ and $b$ and returns $a+b$ and $a-b$ could be represented by the matrix

$\begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

But most programs are not linear functions. For example, if the program instead returns $a^2+b^2$ and $a^2-b^2$ how will you represent that as a matrix ?


What is the complexity class of solving hash decision problems?

It's in NP.  In particular, it is easy to provide a witness for a yes answer (the witness is such a value $p$) and given a witness, you can verify the yes answer in polynomial time.

As you say, it's not in P if the cryptographic hash function is cryptographically secure.

I don't think it's likely to be NP-complete, but at the moment I can't articulate a specific reason why I think that.

(If you have a one-way permutation, then it's in NP $\cap$ coNP, so unlikely to be NP-complete... but that doesn't apply to your question.)


"Real World" Applications of an Efficient Root Finder

Sure.  If this works for any function $f$ that can be computed efficiently, such an algorithm would let you solve any NP problem.

Let $g:\{0,1\}^n \to \{0,1\}$ be an arbitrary function that is efficiently computable.  When $x$ is an integer, define $f(x) = g(x_1,\dots,x_n)$ where $x_1\cdots x_n$ is the binary representation of $x$; when $x$ is not an integer, define $f(x)$ to linearly interpolate between $f(\lfloor x \rfloor)$ and $f(\lceil x \rceil)$, i.e.,

$$f(x) = f(\lfloor x \rfloor) + (f(\lceil x \rceil) - f(\lfloor x \rfloor))(x - \lfloor x \rfloor).$$

Then if we apply your algorithm to $f$, we find an efficient way to compute $x_1,\dots,x_n$ such that $g(x_1,\dots,x_n)=0$.  This in turn lets you efficiently solve any NP problem.

For instance, you could break the RSA cryptosystem efficiently, you could mint Bitcoin coins efficiently, you could solve optimization and operations research problems efficiently, and so on.

If this is restricted to only $f$ that are low degree polynomials, we already know of algorithms to solve the problem, so it likely would not represent an advance over the state of the art and likely wouldn't have much of an impact in practice, unless your method was significantly more efficient than existing methods.


Multiplying intervals in Two's complement

If $0 \leq a,b,c,d$ then $[a,b] [c,d] = [ac,bd]$. The trouble begins when numbers can be negative. If $a,b<0$ then $[a,0][b,0]=[0,ab]$. If $a<0<b$ then $[a,0][0,b] = [ab,0]$. And so on. To consider intervals straddling $0$, partition them into their positive and negative parts.

Summarizing, I wouldn't say that it is "impossible" to find an algorithm for multiplying intervals, only that you have to consider numerous cases. Good luck.


$\mathsf{SPP}$ is a class of languages, so we can ask whether a language is in $\mathsf{SPP}$, not some input in $\Sigma^*$. The function $f$ is fixed before seeing the inputs, as it defines the language. You don't look at the input and then ask if there exists some function.

Think of it this way, $\mathsf{SPP}$ is the class of languages decidable by a certain class of nondeteministic polynomial time machines, namely those for which the difference between the number of accepting and rejecting paths takes values in $\{0,1\}$ (for all inputs). Note that for a general NP machine, given input $x$ this difference can take values in $\{0,1,...,2^{poly(|x|)}\}$. Given such a machine $M$, the associated $\mathsf{SPP}$ language is the set of all inputs for which the difference is $1$.


route and/or packing optimization algorithm

This specific problem seems to be an variation of minimizing the makespan in the job shop scheduling problem. Essentially, your couriers are modeled as 'workers' that need to process certain 'tasks', which are the delivery requests. We look for an assignment of tasks to workers that minimizes the time until the last worker is finished, the makespan of the assignment.

The current problem is slightly different from the basic version, as it assumes all workers are equally skilled, but here some workers can process faster, as they can carry more items.

The job shop scheduling problem is an NP-complete problem, which means that we do not expect to solve this problem exactly in polynomial time.

One option is to model this problem and various extensions as an (mixed) integer linear program, but this generally means you either have an exponential time algorithm or have no guarantees over the quality of your result.

A better idea for this specific problem is to use an approximation algorithm for the job shop scheduling problem. These approximation algorithms run in polynomial time and although they do not guarantee an optimal solution, they can give you an upper bound on the quality of the solution (e.g. The solution given will be at most twice the size of the optimal solution). There is extensive literature about this problem, so where to start mostly depends on the type of solution you're looking for.


By definition it's enough to show existence of $c>0$, and, also existence of $N \in \mathbb{N}$, for which $f(n) \geqslant c g(n)$, when $n \gt N$. Of course, if it's possible to find $c$, then proof is also done.
In case of $(n + a)^b = \Omega(n^b)$, assuming $a,b>0$, then choice $c=N=1$ fulfills definition, as we have $(n + a)^b \geqslant  n^b$.
BTW, holds also $(n + a)^b = O(n^b)$, so $(n + a)^b = \Theta(n^b)$.


Is the number of operators always one less than the number of values in an arithmetic Reverse Polish Notation expression with only binary operators?

RPN expressions have stack semantics: a value pushes a number onto the stack, whereas a binary operator pops two values and pushes one back, for a net loss of one element. At the start of an expression the stack is empty, and at the end there is exactly one value – the result.

Now let $V$ be the number of values in the expression, and $B$ be the number of binary operators. Then at the end of the expression, the stack contains $V-B$ values. Since there should be exactly one value remaining, we conclude that $V-B = 1$, or $B = V-1$.

Another way to see this is using structural induction. As you mention, every expression is either a value or is obtained from two expressions combined using a binary operator. Let's prove by induction on the number of values and operators appearing in the expression that $V = B+1$ (in the terminology of the preceding section).

When the expression consists of just a value, $B=0$ and $V=1$, so $V = B+1$. When the expression consists of a binary operator together with two other expressions $E_1,E_2$, we have $V = V(E_1)+V(E_2)$ and $B = B(E_1)+B(E_2)+1$ (I hope the notation is clear). By induction, $V(E_1) = B(E_1)+1$ and $V(E_2) = B(E_2)+1$, so
$$ V = V(E_1) + V(E_2) = B(E_1) + 1 + B(E_2) + 1 = B + 1. $$


Create cfg and npda/pda for Language {ww}

Short answer: $L$ is not context-free, so there is no CFG/PDA.


Word addressing means that, the number of lines in the address bus in the processor is lesser than the number of bits in the word itself.

Lets say we have a 4 byte word. (32 bit address space)

If this machine is byte addressable, then the address bus of the CPU will have 32 lines, which enables it to access each byte in memory.

If this machine is word addressable, then the address bus of the CPU will have 30 lines ($32 - log_{2}4 =30$), which enables it to access memory ONLY in words/chunks of 4 bytes and that too from addresses which are a multiple of the wordsize.

Now if you ask the CPU to fetch a byte from a particular address, it will first drop the 2 least significant bits(by drop i mean overwrite them with 0's) of the address, fetch a word from the resulting address and return a byte using the 2 least significant bits as an offset within the fetched word.

This causes memory access time to increase, since the CPU has to spend more time modifying the address and processing the fetched word. But it also helps reduce hardware cost since the complexity of the circuits is reduced due to the reduction in address bus lines.

However, this overhead never arises in a byte addressable machine, hence 'byte extracting' is easier.


Cardinality of sets and strings -> confused

You are confusing the size of a set of things and the size of the things the set contains.
The empty set contains nothing. Its size (or cardinality of you want to be sesquipedalian) is 0.
A set of containing one thing has size 1. It doesn't matter whether the one thing is an elephant, a flea, or a string. If there is one thing, the cardinality is 1. That thing could even be a set, even the empty set. The empty set is a thing which contains nothing but it is not nothing. It is a thing, so it can be the element of another set.
A string is not a set, even though it consists of elements of a set of letters. It differs from a set in that its elements are ordered, and therefore might repeat. When we count the size, we count each repeated element too. But both a string and a set can be empty. The empty set has size 0 but it's also one thing. The empty string has size 0, and it is also a thing. (A different thing).
So,
$$\begin{align}\mid\{\}\mid&=0\\
\mid\{\{\}\}\mid&=1\\
\mid\{“”\}\mid&=1\\
\mid\{“”, \{\}\}\mid&=2\\
\end{align}$$
We usually talk about the length of a string (or other sequence) rather than its cardinality, but the two concepts are shown with the same operator (the pair of vertical bars above, also used for "absolute value"), because they are easily related. In fact, we can think of a string (or sequence) as a set of mappings, each integer in a contiguous finite range is mapped to a single character (or element of the sequence). Even though the two characters are the same, the mappings in $\{<1\to a>, <2\to a>\}$ differ (because the integers differ), and the two mappings clearly denote the string $aa$. The cardinality of the set of mappings is 2, just as is the length of the string.
The empty string corresponds to an empty set of mappings (as one might expect), so its cardinality is 0. (As we saw above, this is different from the cardinality of a set containing the empty string.)

Finally, your question about the pumping lemma is a different confusion, but still a confusion having to do with emptiness.
The pumping lemma states that $|y|>0$, so it is clear that $y$ cannot be  $\epsilon$. But it allows you to pump $y^i$ for any non-negative $i$. There is no contradiction here. $y^0 = \epsilon$ for any $y$, by definition. So the pumping lemma lets you produce a string where $y$ has been replaced with $\epsilon$ (in other words, deleted). That has nothing to do with the fact that the $y$ being eliminated actually existed in the original string. (Or perhaps it does, since eliminating nothing is a no-op.)


Number of nodes of given height in binary heap

Suppose towards a contradiction that your heap $H$ contains at least $\lceil n/2^{h+1} \rceil + 1$ nodes of height $h$, for some choice of $h$.

At least $\lceil n/2^{h+1} \rceil$ of these nodes are the roots of a complete binary subtree of the heap. Therefore each of these subtrees contains $\sum_{i=0}^h 2^i = 2^{h+1}-1$ nodes.

The subtree of $H$ rooted in any of the remaining nodes of height $h$, contains at least $1$ vertex (stronger lower bounds are possible, but this is all we need).

Since the subset of nodes having height at least $h$ in $H$ induces a binary tree $T$ whose leaves are the nodes of height exactly $h$ in $H$, we know that $T'$ must have at least $\lceil n/2^{h+1} \rceil + 1 - 1$ internal nodes.
This means that the number of nodes of height larger than $h$ in $H$ is at least $\lceil n/2^{h+1} \rceil$.

Then, the total number $n$ of nodes in $T$ must be at least:

$$
\begin{align*}
n \ge \lceil n/2^{h+1} \rceil  \cdot (2^{h+1}-1) + \lceil n/2^{h+1} \rceil + 1 =
\lceil n/2^{h+1} \rceil  \cdot 2^{h+1} + 1
\ge n + 1.
\end{align*}
$$

This is a contradiction.


Generating all factorials up to $n$: faster than naive approach?


Sampling from specific random distribution on sets

I have a suggestion for an algorithm that might get close to what you want:

Pick $m$ from the distribution $\mu$ (which I will describe below).

Choose $S$ uniformly at random from all sets containing exactly $k-1$ integers in $[m+1,\dots,\min(m+w,n))$.

Add $m$ to $S$.  Output $S$.

So, how do we pick the distribution $\mu$ to make this algorithm pretty good?  I'll describe how, using linear programming.
Let $\mu_i$ denote the probability of $i$ according to the distribution $\mu$.  Then, we have
$$\begin{align*}
\Pr[x \in S]
&= \sum_m \Pr[x \in S \mid m] \Pr[m]\\
&= \mu_x + \sum_{m=x-w+1}^{x-1} {k-1 \over \min(w-1,n-m-1)} \cdot \mu_m.
\end{align*}$$
Notice that this is linear in the $\mu_i$'s.  Now, let's treat the $\mu_i$'s as variables to be solved for.  Introduce the linear inequalities
$$\left| \Pr[x \in S] - {k \over n}\right| \le t,$$
where $t$ is another variable.  Also add the equality $\mu_1 + \dots + \mu_{n-k}=1$ and $\mu_{n-k+1}=\cdots=\mu_{n-1}=0$ and the inequalities $\mu_i > 0$ for all $i$.  We'll try to minimize $t$ subject to all of these inequalities.  These are linear inequalities in the variables $\mu_0,\dots,\mu_{n-w},t$, so you can find a solution in polynomial time using linear programming.  That gives you a distribution $\mu$ to use in the algorithm above.
This comes close to meeting your requirements.  It ensures the set $S$ output by the algorithm meets your conditions 1, 2, and 3.  It gets close to having $\Pr[x \in S] = k/n$; this is not exactly true, but it will be approximately true; and you can measure how large the error is when you solve the linear program, by inspecting the value of $t$.  Also, due to the inequality $\mu_i > 0$, every possible set has a non-zero probability of occurring.  Of course, this is only a heuristic, and it probably is not the maximum-entropy distribution, so you'll have to decide whether it is good enough for your needs.
You mention that you are dealing with a very large value of $n$.  Given that, an additional heuristic would be to assume that $\mu_i$ is constant for all $i \in [3w,n-4w)$.  Intuitively, the endpoints are the problem cases, and there is a loose symmetry among the middle values that makes it feel reasonable that they'll end up having about the same probability.  So, we can enforce the constraint $\mu_{3w} = \mu_{3w+1} = \cdots = \mu_{n-4w-1}$, by replacing $\mu_i$ with $\mu_{3w}$ for all $i \in [3w,n-4w)$.  Now there are only about $6w$ variables, namely, $\mu_1,\dots,\mu_{3w},\mu_{n-4w},\dots,\mu_{n-w}$ and $t$.
Note that it is easy to express $\Pr[x \in S]$ as a linear sum of the $\mu_i$ variables; this sum can be computed in $O(w)$ time.  So, we end up with a linear program in about $6w$ variables, so you can apply a LP solver, and the resulting system will have $O(w)$ variables and inequalities instead of $O(n)$ variables and inequalities, so the LP solver should be a lot faster.


Proving the regularity of a certain language

It is a trick question. You can find a simpler form to describe the language.


Communication complexity of comparing sets, for Bitcoin

One possibly better approach would be to use a Merkle tree, or some other hierarchical data structure like that.  If there's a large set of transactions that the sender can identify as probably already known to the recipient, then this might save a significant amount of data transfer.

Build a binary tree, where each leaf corresponds to a single transaction, and where each internal node has two children.  Now each leaf node will be labelled with 20 bytes, namely, the hash of the transaction.  Each internal node will be labelled with 20 bytes, namely, the hash of the concatenation of the labels on its two children.  For example, for each $i$, we might have an internal node at height $i$ that covers the first $2^i$ leaves, with a complete binary tree hanging underneath it (along with a bunch of other internal nodes).

The two parties can then compare their Merkle trees via some interactive protocol.  Note that if Alice and Bob established that they both have the same label for some node of their tree, they don't need to examine anything under that node; they know the subtree rooted at that node is the same for both of them.  If they have a different label for some node of their trees, then they can recurse and compare their children.

You can probably choose the structure of Merkle tree to take advantage of the probability distribution on where differences are most likely to appear.  You can also vary the branching factor.  This gives you a space of possible trees, with a range of tradeoffs between the typical number of rounds of interaction vs the typical amount of data that must be communicated.  You might be able to choose a parameter setting that is optimal in your setting.

Also, as another optimization, Alice can start by sending Bob the value of some fixed set of her nodes.  Notice that your example of sending a list of hashes corresponds to Alice proactively sending the value of all of the leaves.  However we might be able to do better by taking advantage of interaction: e.g., if Alice expects that one of her subtrees is probably shared by Bob, she can send just the label on the root of that subtree, and not send anything under that node (e.g., not the hashes of any of the transactions).  If she is right and Bob does have that transaction, neither has to do any other work.  If she is wrong, then some further interaction and additional data must be exchanged.

Many variations on this basic idea are probably possible.


What do you call a subtree covering a subset of contiguous leaves?

You seem to mean a subtree obtained by taking a certain node and all its successors.

In data structures, the implicit assumption usually is that we consider rooted (and often ordered) trees. Therefore, "subtree" is usually taken to mean what you intend; "subtree" as in graph-theoretic "subgraph" is rarely used (in my experience).

If you want to make very clear what you mean, you can write

  The subtree of $T$ which is rooted in $x \in T$.

A common notation for this tree is $T_x$.


Problems that are easy on bipartite but hard on general graphs

There are several well-known NP-complete problems that become solvable in polynomial-time for bipartite graphs. For example, 3-coloring is easy as bipartite graphs are precisely the 2-colorable graphs. Another example is independent set which is made easy by König's theorem.

Wikipedia also lists a problem that is NP-hard for general graphs but is trivially in P for bipartite graphs: the odd cycle transversal problem.


House painting problem where the house row is split and converged back

The problem you described can be solved in polynomial time using dynamic programming whenever the topology of the input houses is a tree (a path is just an even easier special case).

Unless $P=NP$, the problem is not solvable in polynomial time when the input instance is a general graph, since the $k$-coloring problem can be easily reduced to your problem.

However, in your particular case you are in luck since your input instances can always be decomposed in any of the following ways:

into $2$ paths by deleting two vertices.
into $2$ trees by deleting one vertex.

You can then guess the the color(s) of the deleted house(s) and update the cost matrix of their neighbors so that if a house $u$ is adjacent to a deleted house $v$ and $v$ is colored with color $c$, the cost of coloring $u$ with $c$ will be $+\infty$ (effectively ensuring that no optimal solution will color $u$ with $c$).

If $k$ is the number of colors, $n$ is the number of houses, and you delete $2$ vertices, solving your problem will take time $O(k^2 \cdot n k) = O(n k^3)$.

If you delete a single house and solve the problem on the resulting tree, you can reduce the time complexity to $O(k \cdot nk) = O(n k^2)$.

To solve the problem on trees in time $O(n k)$, root the input tree $T$ in an arbitrary vertex $r$ and let $C(u,c)$ be the cost of coloring vertex $u$ with color $c = \{1, \dots, k\}$.

Define $OPT[u,c]$ as the minimum cost needed to color the subtree of $T$ rooted in $u$ with the additional constraint that vertex $u$ must have a color different from $c$.

Then, if $u$ is a leaf of $T$, you have $OPT[u,c] = \min_{c' \in \{1, \dots, k\} \setminus c} C(u,c')$.
Otherwise, if $u$ is an internal vertex of $T$, let $v_1, \dots, v_h$ be its children. You have $OPT[u, c] = \min_{c' \in \{1, \dots, k\} \setminus c} \left( C(u, c') + \sum_{i=1}^h OPT[v_i, c'] \right)$.

The optimal solution is $\min\{ OPT[r, 1], OPT[r, 2] \}$ (since if $r$ is not colored with color $1$ in an optimal coloring then $OPT[r, 1]$ is exactly the minimum cost to color $T$, while if $r$ is colored with color $1$ then it is not colored with color $2$ and $OPT[r, 2]$ must be the minimum cost needed to color $T$).

A similar argument shows that, for each fixed vertex $u$, all supbroblems $OPT[u, c]$ can be solved in an overall time of $O(k)$ (there are only two interesting values of $c$). The time complexity follows.


Undecidable language and Turing Machines

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine.

You presume to know something about how the machine for $\overline{A}$ was built; don't, because you can't.

What's more, this construction (flipping accepting states) does not work for TMs that do not always halt, as any one for $A$ has to be.

Thus, a semi-decider for $\overline{A}$ has to look differently from what you describe.

Regarding the original problem you were given, it is a weird formulation to test your understanding of basic closure properties.

Hint: Assume there was a semi-decider for $\overline{A}$. What follows about $A$?


Graph edges are not "converted to function calls". DFS is a recursive function. When you call DFS on some start node, it looks at the adjacent vertices (vertices which are connected to this node via an edge) and recursively calls itself on one of them.
But since each node is only visited once in a DFS, the maximum stack size cannot be greater than the number of nodes.


Truth and lie in infomation theory: negative amount of information

How does information theory deal with truth?

It doesn't. It deals with messages drawn from probability distributions, not with knowledge.

  Does disinformation or lie have negative amount of bits of information?

No, because that's not what information theory is about.


The subset sum problem is even harder(NP-hard) for special groups which you can embed into $S_n$. See the paper you have linked in the problem description.

$\textbf{Observation:}$ $g$ can be writtens as combination of elements $\{g_1,\ldots,g_k\}$ if and only if $g \in \langle g_1,\ldots,g_k\rangle$. Under the assumption that each of $g_i$ can appears any number of times.

The complexity of the problem depends upon the input representation. There are two two most commonly used ways, Cayley table and generating set. For Cayley table see this paper for results. Read the CGM(Cayley membership problem) Link

$\textbf{CGM} $

$\textbf{Input :}$ A group $G$ by its Cayley table, $X \subseteq G$ and $t \in G$.

$\textbf{Output :}$ Does $t$ belong to the subgroup $\langle X \rangle$ generated by $X$?

In general problem is in Symmetric log space.

$\langle A \rangle$ means subgroup generated by $A$


What is the relationship between Turing Machines with a finite tape and Finite State Automata?

It depends what you mean by "finite tape". If you bound the length of the tape by some function of the input, then no - you can recognize non-regular languages. For example, consider LBAs.

But if you mean a bounded tape, where the tape has $k$ cells for some fixed $k$, then yes - you indeed get a model which is equivalent to DFAs.

To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.


Proving that a language is not in P using diagonalization

The idea (which doesn't quite work) is that given that $E'_1 \in P$, $M^*$ runs in time at most $2^n$ on an input of length $n$ (that's not quite true). Given that, if $M^*$ rejects $M^*$ then by the definition of $E'_1$, $M^*$ accepts input $M^*$ after at most $2^{|M^*|}$ steps, which is a contradiction.

The other direction, which you were happy with, is problematic: if $M^*$ accepts $M^*$ then by the definition of $E'_1$, $M^*$ does not accept input $M^*$ after at most $2^{|M^*|}$ steps. That's not a contradiction since our assumption that the running time of $M^*$ is $2^n$ was wrong - perhaps it's $2^{|M^*|} n$. So you need to be more subtle - presumably Papadimitriou addresses this.


Turing machine that can move right only $O(1)$ steps beyond input

Your machine uses $n + k = O(n)$ space. As such, it can be simulated by a linear bounded automaton. The latter is known to be weaker than a general Turing machine. For example, it cannot solve the halting problem for machines using $n^2$ space, a problem that Turing machines are able to solve.


What do the commas separating atomic events in a Relational Calculus formula means?

The notation is defined on page 17 and 18. The authors define a couple notations and state that they will "freely switch back and forth" between them.  This example doesn't seem super-consistent, I'd expect $Q(x,x'):\!\!-\,R(x),S(x,y),S(x',y),R(x')$ rather than an equals sign, but presumably it means $Q(x,x') = \exists y.R(x)\land S(x,y) \land S(x',y)\land R(x')$.

It doesn't really make sense to talk about natural joins in this context, as those rely on named attributes/columns. But yes, this query includes (equi-)joins. To be clear, the comma stands for conjunction.  Any joining is implicit in duplicate uses of a variable. In particular, if all variables were used only once in the right hand side, then there would be no equi-joins, even implicitly.  In SQL, the query would look something like:

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
WHERE S1.Field1 IN (SELECT Field1 FROM R)
  AND S2.Field1 IN (SELECT Field1 FROM R)

or to be more systematic,

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1
INNER JOIN S AS S2 ON S1.Field2 = S2.Field2
INNER JOIN R AS R1 ON R1.Field1 = S1.Field1
INNER JOIN R AS R2 ON R2.Field1 = S2.Field1

or going a different direction,

CREATE VIEW Q
AS
SELECT DISTINCT S1.Field1, S2.Field1 AS Field2
FROM S AS S1, S AS S2, R AS R1, R AS R2
WHERE R1.Field1 = S1.Field1
  AND S1.Field2 = S2.Field2
  AND S2.Field1 = R2.Field1


Is the decision problem, for a Turing Machine are there any input strings rejected decidable?

Let us start by properly defining your language as say
$$L = \{\langle M \rangle \mid M \text{ rejects some input } x \in \Sigma^\ast\}$$
where $\langle \cdot \rangle$ denotes some suitable encoding over our alphabet $\Sigma$.
To reduce $L$ to the halting problem $\mathrm{Halt} = \{\langle M, w \rangle \mid M \text{ halts on } w\}$ we consider some $\mathrm{Halt}$ instance consisting of a TM $M$ and some input $w$ and define a new TM $M_w$ which always, no matter what input it is given, just simulates the behavior of $M$ on $w$ with the slight change that it rejects if $M$ accepts, i.e. $M_w$ rejects precisely if $M$ halts on $w$ and does not halt if $M$ does not halt on $w$.
Note that $M_w$ can be algorithmically constructed from $M$ and $w$.
We see that $\langle M, w \rangle \in \mathrm{Halt}$ if and only if $\langle M_w \rangle \in L$, i.e. we have shown that the halting problem reduces to $L$ and thus $L$ is undecidable.
However, $L$ is also recursively enumerable: Fix some ordering of $\Sigma^\ast$ and iteratively execute $M$ on the first $n$ strings of $\Sigma^\ast$ for $n$ steps.
If $M$ rejects some string in $\Sigma^\ast$, this procedure will detect it in finitely many steps, showing that $L$ is semi-decidable and hence recursively enumerable.


Is it possible to get Nth Fibonacci number in sublinear time?

Let's assume that you could store such large Fibonacci numbers. In that case, the  length of $n^{th}$ Fibonacci number is $\lfloor n \log_{10}\phi+1\rfloor$. That is the length of the $n^{th}$ Fibonacci number is $\Theta(n)$.

If you go by the naive method, then calculating the $n^{th}$ Fibonacci number would cost you $\Theta(n^2)$ time.

In comparison, matrix exponentiation will take $O(n^2\log n)$ time, assuming you use schoolbook long multiplication to multiply numbers.  (A slightly more refined analysis shows that it is in fact $\Theta(n^2)$, by summing a geometric series.) But if instead we use Karatsuba multiplication , the running time to compute the $n$th Fibonacci number using matrix exponentiation becomes $O(n^{1.585}\log n)$.  (Analogous to before, a slightly more refined analysis shows that the running time is in fact $\Theta(n^{1.585})$.) Thus, if you use sophisticated multiplication algorithms, matrix exponentiation would be better for large $n$ compared to the naive algorithm.

In short: which method is better depends on which multiplication algorithm used.


In pipelining (at least, in MIPS), why is the incremented program counter address saved in the IF/ID pipeline register?

beq doesn't contain the destination address in the instruction, but an offset relative to the location of the instruction. For example "branch if equal to the instruction 12 words ahead of the branch instruction". You cannot execute such an instruction if you don't know what the address of the branch instruction was.


Let $a_{N-1} \cdots a_0$ be the two's complement representation of the number $a$. The more general formula is:
$$a = -a_{N-1}2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i$$
(I am sure you can figure out how your formulas can be derived from this one.)

Why does this hold? For $a \ge 0$, $a_{N - 1} = 0$ and then the value of $a$ is simply the value of the binary representation $a_{N-2} \cdots a_0$. For $a < 0$, on the other hand, let $b = -a \ge 0$ have binary representation $b_{N-1} \cdots b_0$. Then
$$\sum_{i=0}^{N-1} a_i 2^i = \sum_{i=0}^{N-1} (1-b_i) 2^i + 1
= \sum_{i=0}^{N-1} 2^i - \sum_{i=0}^{N-1} b_i 2^i + 1  = 2^N - b$$
since the two's complement is defined as the complement of the representation $b_{N-1} \cdots b_0$, plus one, and $\sum_{i=0}^{N-1}2^i = 2^N - 1$. Since $a$ is negative, $a_{N-1} = 1$ and then:
$$a = -b
= -2^N + \sum_{i=0}^{N-1} a_i 2^i
= -2^N + 2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i
= -2^{N-1} + \sum_{i=0}^{N-2} a_i 2^i
$$

I have refrained from giving an explicit example as you had asked; I believe explaining why the formula works in the first place is far more instructive.


The function $\mathsf{int}$ actually doesn't change a binary number to its base 10 form. Rather, it takes a string encoding some number $n$ in binary, and outputs $n$. When we write the output, we use decimal (base 10), but the output is just a number. It's us who use base 10.

The language $L$ consists of all strings $\alpha\#\beta$, where $\alpha,\beta \in \{0,1\}^*$, such that

$\alpha$ encodes (in binary) an integer $a$ in the range $1$ to $|\beta|$, where $|\beta|$ is the length of $\beta$.
The $a$th bit of $\beta$ is $1$.

It's difficult to say what the $a$th bit of $\beta$ is, since there are several possible conventions:

The "first" bit could be bit number $0$ or bit number $1$; in this case it seems like the first bit should be bit number $1$.
We could be counting bits from the left or from the right; the usual convention is from the left, though if you think as a string as encoding a number, it is more natural to count from the right.

Assuming we are counting bits from the left and starting with $1$, $L$ consists of strings $\alpha\#b_1b_2\cdots b_n$ where $\alpha$ encodes a number $a$ in the range $1 \leq a \leq n$ and $b_a = 1$. This interpretation also matches your examples.


LET REC recursive expression static typing rule

It seems you discovered the difference between a set of typing rules and an algorithm for type inference.

Typing rules only define a relation among 1) a type environment, 2) a term, and 3) a type. Their purpose is only to precisely define a mathematical relation $\Gamma \vdash t: \tau$.

Once we have such definition, we do not automatically get a type checking algorithm. That is, in general, there is no algorithm described by the rules which, given $\Gamma,t,\tau$, is able to test whether $\Gamma \vdash t: \tau$ holds. (In some cases, such an algorithm could even fail to exist!)

Similarly, we do not automatically obtain a type inference algorithm, which given $\Gamma,t$ is able to find a related $\tau$ (when it exists).

The type checking/type inference algorithm must be devised independently.

Now, it is true that in many cases the algorithms can follow the rules quite closely. The rule for non-recursive LET you mention is one nice example, since it is clear how to turn it into an algorithm. For recursive LETs, we are not that lucky.

A typical strategy to type check/infer recursive LETs is to introduce a fresh type variable in the environment, and then perform type checking on the body while generating a set of constraints. For instance, consider this example

let-rec f (x: int) = 1 + f(x) in f(0)

We discover immediately that f : int -> ???. Let's introduce a fresh type variable R for the result, and say f : int -> R.

We then type check 1 + f(x) assuming the environment f: int -> R , x: int.
Here + is applied to arguments 1: int and f(x): R. Assuming + requires its arguments to be of the same type, this forces the constraint int = R.
If + also returns the same type, we obtain another constraint int = R (redundant, in this case).

Finally, we solve the constraints, discovering R = int.

Note that in the general case we might be less lucky, since more complex types could be involved.

let-rec f(x: int) = (2, fst(f(x-1)))

Here, we discover f: int -> R, then we see that R must be a pair type R = A*B, then A=int (because of the 2). Moreover, we get f(x-1):R so fst(f(x-1)): A, hence B=A. We conclude f: int->(int*int).

It is not trivial to generate these constraints, or to solve them (usually through a unification algorithm). In the scientific literature we can find several algorithms which perform this, but they are not obvious at first.


Proof that $\{⟨M⟩ ∣ L(M) \mbox{ is context-free} \}$ is not (co-)recursively enumerable

I think the question is how to show that $L$ is not r.e. One way to do that is to reduce the complement of the halting problem to $L$, because the complement of the halting problem is not r.e.

Here's a hint about one way to do that reduction: given $M$ and $x$, we want to make a language that is context free if and only if $M(x)$ does not halt. So start simulating $M$ on input $x$. As long as $M(x)$ does not halt, we make a language that looks like $\{ 0^n : n \in \mathbb{N}\}$. But if $M(x)$ does halt, we change the language we're generating after that point to be some r.e. but not context free language.


Complexity of shortest paths if paths have to use edges from different partitions

If it helps, the problem you are trying to solve is looking for a "rainbow path" between the two vertices.  It's a relatively new area of research, and there's now a book:

Rainbow Connections of Graphs
X. Li and Y. Sun
http://www.springer.com/la/book/9781461431183

Or here's an earlier paper:
G. Chartrand, G. L. Johns, K. A. McKeon, and P. Zhang. Rainbow connection
in graphs. Mathematica Bohemica, 133(1):85–98, 2008.

The result you're looking for is likely in one of those places, something they cite, or something that cites them.


Which is the fastest method for calculating exact square root of a integer of 200-500 digit number?

It seems a bit surprising that you did not find the Wikipedia article on integer square root where the Newton's algorithm is described in detail.

Here is the implementation in Python:

def integer_sqrt(n):
    """Compute the integer square root of n, or None if n is not a perfect square."""
    x = n // 2
    while True:
        y = (x + n // x) // 2
        if abs(x - y) < 2: break
        x = y
    return (x if x * x == n else None)

This takes about 0.018 seconds for a 1000 digit number on my MacBook Air. It's not clear why you're asking for the particular range between 200 and 500 digits, but I think you should be able to go on from here, especially if you take the time to read the Wikipedia page.

You may also be interested in the Rosetta Code integer roots page, where you can find fast implementations of integer root algorithms in many languages.

By the way, I just googled "integer square root" to find all of this, except I wrote the Python code.


The greatest fixed point cannot contain only the infinite lists, because it must contain all the elements of the least fixed point (and every other fixed point). Another way to see this is that just the infinite lists are not even a fixed point, since applying $F$ will add $\mathrm{Nil}$, which is not infinite.
However, adding the infinite lists is the right thing to do. I'm not familiar with the book you're reading at all, so I don't know exactly how this would be realized in its setting. For instance, I don't know what $\mathrm{Cons}$ and $\mathrm{Nil}$ are intended to be exactly as operations on $\mathcal{U}$ (or what $\mathcal U$ consists of). But the idea would likely be that $\mathcal U$ has both finite and infinite things built completely out of them, the least fixed point collects just the finite ones, and the greatest fixed point collects all of them.


Search on Conformant Problem: solution for subset of a belief state

'different path from the start state': The sensorless vacuum world is by definition a 'single-state problem', that is, all variables in the world are incorporated into a single state variable. In that case, history doesn't matter. If we are in state 5 by one path, the world is exactly as it would be if we had got there by another path.

For an example of something else represented as a single-state problem, consider chess: you might say history matters because whether you can castle, depends on whether the king has moved, not just the current board position. Okay so if we represent chess as a single-state problem, then the state would encode not only the current board position but also other relevant variables like whether the king has moved.

Subsets: if we know how to get to {5,7}, we don't need to be interested in {1,3,5,7}. Getting to {5,7} gives us all the same information plus more besides.


Would limiting the number of operations in a transaction prevent SQL injection?

It could help avoiding some attacks. However, allowing the adversary to inject a part of the SQL WHERE clause is already quite dangerous.

E.g. injection can change this

SELECT * WHERE name="username"

into

SELECT * WHERE name="Bah!" or true or "too easy!"="x"

The sane thing would be to avoid injection completely. Ideally, in a typed language, the type of a SQL query should NOT be a string, so to prevent concatenation with user data. It should be a query template, to be filled with a special function. Something like

query = new Query(...);
fill(query, { "username": username })

Type systems excel for imposing these constraints of the programs. On the other hand, their use require some thoughtful library design. Sometimes it feels simpler to provide a more low-level solution (like using strings for everything), which is also simpler to use, and possibly document the potential security issues "programmers: don't do this", which can then be ignored by busy programmers, which would often take the shortest path to their goals. Types here would simply block the quick path, forcing the programmers to separate the "query template" part from the "user data" part.

Some languages still use strings for templates, but at least encourage programmers to avoid concatenation, and favor some fill-like function.

fill("SELECT * WHERE name=@username", { "username": username })

The above is doable even in an untyped language.

Moral: let the library perform all the string-escaping for you. The library always checks for special characters, and handles them correctly. You likely won't cover all the tricky cases.

Don't try to patch against an attack by imposing restrictions on just that attack. Consider all the variants for that attack which can pass the restriction. If injection is the problem, prevent injection at the root.


What does it mean when a dot appears in a logic gate other than the NOT gate? (in logic diagrams)

This is a NOR gate. You can implement a NOR gate using a combination of a OR and a NOT gate. However, in MOSFET implementation or other technologies (i.e. electrical hardware architecture), we can build a NOR gate directly and more efficiently (i.e. more efficient than using a OR and a NOT gate). That's why we use NOR as well.


Show that RP is closed under concatenation

Do the following $poly(|x|)$ times:

  Check for every possible (contiguous) partition of the input string $x = x_1x_2$ and apply the $\mathrm{RP}$ machine to each of $x_i$ if the answer is $\mathrm{YES}\:\mathrm{YES}$ outputs $\mathrm{YES}$ and halt.

If after polynomially many times, still no definite $\mathrm{YES}$ answer has been put down, output $\mathrm{NO}$ with a little bit of fear as it is always like so with $\mathrm{RP}$ algorithms.


Run-time analysis of distributed network decomposition algorithm

Calculus: any local minimum of the function $f(x)$ must be a point $x$ that satisfies $f'(x)=0$, where $f'(x)$ is the first derivative of $f(x)$.  So, take the derivative, set it to zero, and find all solutions.  Each solution is a candidate for the minimum.  You then need to check each candidate to see which makes $f(x)$ smallest.  You'll also need to check the "endpoints", e.g., the smallest and largest possible value for $x$ need to be added as candidates.

You can do the same for functions of two variables, and for asymptotics.


Expressing pseudo-polynomial runtime solely in terms of the input size

You are correct that the running time is $O(n^2 2^n)$, but according to the definition of big O, it is not the case that $n^2 2^n = O(2^n)$, since $n^2 2^n$ grows faster than $2^n$. What is true is that for every $\epsilon > 0$, $n^2 2^n = O((2+\epsilon)^n)$.

Often it is convenient to hide such "small" factors, and write $O(n^2 2^n) = \tilde{O}(2^n)$. The usual definition of $\tilde{O}(\cdot)$ is this: $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log g(n))^k)$. In practice this is almost always used when $g(n)$ is either a polynomial or an exponential. When $g(n)$ is a polynomial, $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n)(\log n)^k)$, and we say that $\tilde{O}$ hides polylogarithmic factors. When $g(n)$ is exponential (that is, $g(n) = e^{An^B}$ for some $A,B>0$), $f(n) = \tilde{O}(g(n))$ if for some constant $k$, $f(n) = O(g(n) n^k)$, and we say that $\tilde{O}$ hides polynomial factors.


I'm frankly not even sure whether the above equation is meant to involve a multiplication.

No, not at all. We have nesting here:

$\max_{X \in \mathcal{X}}\ ( \min_{x \in X} x)$

is the largest minimum of all $X$. Similarly -- but the other way around -- for $\min \max$. This is very similar to nested quantifiers $\forall$ and $\exists$.

Let, for instance, $\mathcal{X} = \{ \{1,2\}, \{3,4\} \}$. Then, the following equalities hold:

$\min_{X \in \mathcal{X}} \min_{x \in X} x = 1$.
$\min_{X \in \mathcal{X}} \max_{x \in X} x = 2$.
$\max_{X \in \mathcal{X}} \min_{x \in X} x = 3$.
$\max_{X \in \mathcal{X}} \max_{x \in X} x = 4$.

Play around with the example by adding more sets to $\mathcal{X}$, more values to the individual sets, and quantify over $f(x)$ instead of just $x$ for different $f$, in order to get a feeling for this.

If you are inclined to algorithmic thinking, do a quick implementation; you'll see how these operators nest more clearly with types, and examples are faster to compute. For instance, the second example would be

Xs.map { X => X.max }.min


Is the following intuition valid for understanding $k$-wise independent hash functions?

Your intuition is exactly right.  Yes, that's equivalent to choosing a random polynomial over $\mathbb{F}_p$.  The reason why it works is exactly the interpolation theorem for finite fields.

$k$-wise independent basically means "it behaves like a perfect hash function, if you only feed it $k$ inputs" or "it behaves like a perfect hash function, as far as correlations between up to $k$ different hash values appear"; and the interpolation theorem then ensures that this level of perfection is achieved for the construction you outline.

It can be a bit tricky to explain this intuition to students who aren't familiar with anything from number theory, group theory, or finite fields.  One approach is to explain the intuition of the interpolation theorem over the real numbers, and then just give a statement that "something similar happens when you work modulo $p$ a prime", without trying to prove it.  That's not perfect, though.

Another approach is to not try to teach this topic, at this point in their education.  While I was taught universal hashing in my undergraduate algorithms course, I've gradually come to the opinion that the topic is better to omit from the course: it's not important enough, and it relies too much on mathematical background and intuition that students don't have.  Why isn't it important?  Well, most students won't become theorists.  For students who will eventually become practitioners, they probably won't ever need universal hash functions.  Instead, ordinary hash functions are often so good that as a first approximation you can just model them as if they were universal (as a heuristic), without making a big deal about it, and do your probability calculations from there.  This is enough to let you analyze uses of hash functions in a way that's accurate enough for practical/engineering purposes.  And, given that, it's not clear that we need to show them constructions that provably achieve something that ordinary hash functions already heuristically achieve pretty well.  That's just a personal opinion, though.


How many iterations does the Bellman-Ford algorithm need for directed and undirected graphs

The Bellman-Ford algorithm does not work on undirected graphs with negative weights, because $(u,v)$ and $(v,u)$ are not allowed on the same path, but the Bellman-Ford algorithm does not handle this constraint. In fact, if the weight of $(u,v)$ is negative, $(u,v)$ and $(v,u)$ form a negative cycle.

If your weights are all non-negative (which is possibly your case according to your comment), the Bellman-Ford algorithm can work on undirected graph. The reason why it requires only $n-1$ iterations is explained in D.W.'s answer. However, you may want to take the advantage of non-negative weights and use some more efficient algorithm (like Dijkstra's algorithm).

Otherwise you can use the technique of T-joins or perfect matching.


Proving that the language SPACE TMSAT is PSPACE-complete?

To prove that a problem $P$ is PSPACE-complete, you need to do two things:

Show that $P$ can be computed in PSPACE.
Show that every problem $Q \in $PSPACE reduces to $P$, in the sense that there exists a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

As mentioned by dkuper, you forgot about the first part. Your argument for the second part (PSPACE-hardness) unfortunately does not constitute a proof. You need to follow the definition: given an arbitrary $Q \in $PSPACE, produce a polytime function $f$ such that $f(x) \in P$ iff $x \in Q$.

Apart from not being a proof, your argument is also not convincing: there could be some trick that avoids simulating $M$. Such tricks are behind results such as L=SL or NL=coNL in complexity theory. For example, the second result states that given a non-deterministic Turing machine $M$ that runs in logarithmic space, there is a  ways to decide non-deterministically in logarithmic space whether a given input is not accepted by $M$. The obvious way to do this is to run all possible execution paths of $M$, but since $M$ could make polynomially many non-deterministic decisions, that would require polynomial space (we need to keep track of all these decisions so that we can run through all of them). Yet there is a trick that enables us to do it non-deterministically using only logarithmic space.

Hint for the second part: Given $Q$, consider a Turing machine $M$ that computes $Q$ in space $O(n^k)$ for some $k$.


What does sublinear space mean for Turing machines?

When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space consumption on the work tape. For palindromes, with space $O(\log n)$ on the work tape we can implement FOR loops that go over the input, comparing matching characters on both ends. Each index takes $O(\log n)$ space to store.


A Good Resource for Christofides' Heuristic

In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen.

We denote the sum of costs of a tour or of similar objects by $w(\cdot)$. Fix some optimal TSP tour $H$.

The starting point of the algorithm is a minimum spanning tree $T$. Why do we want a minimum spanning tree? Suppose that instead of a TSP tour, we're interested in a TSP path. A TSP path is a spanning tree, and while it is difficult to find an optimal TSP path, it's easy to find a minimal spanning tree. In the case of a TSP tour, we have $w(T) \leq w(H)$ as well.

If $T$ happens to be a path then, with some luck, we can get a good tour by completing it into a cycle. However, this need not be the case, and $T$ can be a complicated tree. Here we use a trick: Euler proved that every graph with even degrees can be traversed by an Eulerian circuit. While we wanted a tour and not just any circuit, this happens not to matter as we will see below.

How do we make $T$ into a graph with even degrees? The obstructions are the vertices with odd degree, so we'd like to pair them (there must be an even number of them since the sum of degrees in a graph is always even) as cheaply as possible. This is the minimum-weight matching you mentioned. We complete $T$ into an even-degree graph $T'$ by adding a matching $M$ on the odd-degree vertices, which is just a set of edges connecting pairs of odd-degree vertices. For obvious reasons, we want $M$ to have as minimal weight as possible, and such a matching can be found effectively. (As a special case, if $T$ is a path then $M$ connectes its two endpoints, and $T'$ is just a cycle.)

All vertices in $T'$ have even degree, so we can find an Eulerian tour $E$ working its way over all edges of $T'$. However, we wanted a Hamilton cycle (another name for a TSP tour). The idea now is to follow the Eulerian tour. Whenever we're supposed to visit a vertex we have already encountered, we just "skip" this edge. Eventually the tour will reach a new vertex, and then we just connect the previous vertex with the new one. The triangle inequality shows that the resulting TSP tour has weight at most $w(T') = w(T) + w(M)$.

Here is an example: suppose the Eulerian tour starts $a,b,c,a,d$. The constructed TSP tour will start $a,b,c,d$. The cost of the Eulerian tour is $w(a,b)+w(b,c)+w(c,a)+w(a,d)+\cdots$. The cost of the TSP tour is $w(a,b)+w(b,c)+w(c,d)+\cdots$. The triangle inequality shows that $w(c,d) \leq w(c,a)+w(a,d)$, i.e. if we take a detour from $c$ to $d$ via $a$, that can't be shorter than going straight from $c$ to $d$.

We already know that $w(T) \leq w(H)$. What about $w(M)$? Let $v_1,\ldots,v_{2k}$ be the set odd-degree vertices in $T$, in the order in which they appear in $H$ (starting at an arbitrary vertex and an arbitrary orientation). One possible way to match them is $M_1 = (v_1,v_2),(v_3,v_4),\ldots,(v_{2k-1},v_{2k})$. Another possible way is $M_2 = (v_2,v_3),(v_4,v_5),\ldots,(v_{2k-2},v_{2k-1}),(v_{2k},v_1)$. The triangle inequality (again) shows that the edge $(v_i,v_{i+1})$ costs at most as much as the entire stretch of $H$ from $v_i$ to $v_{i+1}$. Now imagine taking $M_1$ and $M_2$, and replacing each edge with the corresponding stretch of $H$. The result is all of $H$, and so $w(M_1) + w(M_2) \leq w(H)$. Since $M$ has minimum weight, $w(M) \leq w(M_1),w(M_2)$ and so $w(M) \leq w(H)/2$. Therefore $w(T) + w(M) \leq (3/2) w(H)$.


Maximum flow with Edmonds–Karp algorithm

I'm sure you have a misunderstanding.  Try simulating the Edmonds-Karp algorithm by hand on the first example, then edit the question to show the residual graph you've got after it finishes.  I'm sure you'll find there remains an augmenting path from $s$ to $t$ in the residual graph.  If you don't draw the residual graph explicitly, you might fail to notice the path -- you can't do this in your head without drawing the graph on paper.

Many students get tripped up by the fact that there might be an augmenting path in the residual graph that looks like it goes "backwards" in the original graph; that's OK, and it still counts as an augmenting graph.


Efficient algorithm for finding maximum subset of intersecting rectangles

You need a sweep line and an interval tree (modified so that it reports a number instead of intervals). I assume this is a course book problem and you are familiar with its background.

Move the sweep line bottom to top, stop at each horizontal segment. If the segment is the bottom side of a rectangle, insert it as an interval into the interval tree and remove it when the sweep line hits the top side of that rectangle. At each step you can query the number of rectangles containing a point on the sweep line. There are $O(n)$ stops for sweep line, each one adds $O(\log n)$ for interval operations, so it is $O(n\log n)$ in total. The only remaining issue is to keep track of the maximum covered point in $O(1)$ at each step. You should be able to complete this solution.


What does the processor do while waiting for a main memory fetch

Memory latency is one of the fundamental problems studied in computer architecture research.

Speculative Execution

Speculative execution with out-of-order instruction issue is often able to find useful work to do to fill the latency during an L1 cache hit, but usually runs out of useful work after 10 or 20 cycles or so.  There have been several attempts to increase the amount of work that can be done during a long-latency miss.  One idea was to try to do value prediction (Lipasti, Wilkerson and Shen, (ASPLOS-VII):138-147, 1996).  This idea was very fashionable in academic architecture research circles for a while but seems not to work in practice.  A last-gasp attempt to save value prediction from the dustbin of history was runahead execution (Mutlu, Stark, Wilkerson, and Patt (HPCA-9):129, 2003).  In runahead execution you recognize that your value predictions are going to be wrong, but speculatively execute anyway and then throw out all the work based on the prediction, on the theory that you'll at least start some prefetches for what would otherwise be L2 cache misses.  It turns out that runahead wastes so much energy that it just isn't worth it.

A final approach in this vein which may be getting some traction in industry involves creating enormously long reorder buffers.  Instructions are executed speculatively based on branch prediction, but no value prediction is done.  Instead all the instructions that are dependent on a long-latency load miss sit and wait in the reorder buffer.  But since the reorder buffer is so large you can keep fetching instructions if the branch predictor is doing a decent job you will sometimes be able to find useful work much later in the instruction stream.  An influential research paper in this area was Continual Flow Pipelines (Srinivasan, Rajwar, Akkary, Gandhi, and Upton (ASPLOS-XI):107-119, 2004).  (Despite the fact that the authors are all from Intel, I believe the idea got more traction at AMD.)

Multi-threading

Using multiple threads for latency tolerance has a much longer history, with much greater success in industry.  All the successful versions use hardware support for multithreading.  The simplest (and most successful) version of this is what is often called FGMT (fine grained multi-threading) or interleaved multi-threading.  Each hardware core supports multiple thread contexts (a context is essentially the register state, including registers like the instruction pointer and any implicit flags registers).  In a fine-grained multi-threading processor each thread is processed in-order.  The processor keeps track of which threads are stalled on a long-latency load miss and which are ready for their next instruction and it uses a simple FIFO scheduling strategy on each cycle to choose which ready thread to execute that cycle.  An early example of this on a large scale was Burton Smith's HEP processors (Burton Smith went on to architect the Tera supercomputer, which was also a fine-grained multi-threading processor).  But the idea goes much further back, into the 1960s, I think.

FGMT is particularly effective on streaming workloads.  All modern GPUs (graphics processing units) are multicore where each core is FGMT, and the concept is also widely used in other computing domains.  Sun's T1 was also multicore FMGT, and so is Intel's Xeon Phi (the processor that is often still called "MIC" and used to be called "Larabee").

The idea of Simultaneous Multithreading (Tullsen, Eggers, and Levy, (ISCA-22):392-403, 1995) combines hardware multi-threading with speculative execution.  The processor has multiple thread contexts, but each thread is executed speculatively and out-of-order.  A more sophisticated scheduler can then use various heuristics to fetch from the thread that is most likely to have useful work (Malik, Agarwal, Dhar, and Frank, (HPCA-14:50-61), 2008).  A certain large semiconductor company started using the term hyperthreading for simultaneous multithreading, and that name seems to be the one most widely used these days.

Low-level microarchitectural concerns

I realized after rereading your comments that you are also interested in the signalling that goes on between processor and memory.  Modern caches usually allow multiple misses to be simultaneously outstanding.  This is called a Lockup-free cache (Kroft, (ISCA-8):81-87, 1981).  (But the paper is hard to find online, and somewhat hard to read.  Short answer: there's a lot of book-keeping but you just deal with it.  The hardware book-keeping structure is called a MSHR (miss information/status holding register), which is the name Kroft gave it in his 1981 paper.)


Assigning all nodes in a tree a parent and children

The tree in your diagram is undirected. Undirected trees don't have a uniquely determined root because the edge $xy$ just means that nodes $x$ and $y$ are related: it doesn't specify that one is the parent of the other.

If you're told to make a particular node the root, you can do so by directing all of the edges away from the root, which you can do by depth-first search (or breadth-first search, or any other enumeration procedure).

Conversely, if the edges are directed, so $xy$ means "$x$ is the parent of $y$" (or vice-versa, if you want to adopt the opposite convention), then you can find the root by starting at any node and navigating to the parent until you find a node without a parent. Since the root is the unique node without a parent, you're done.  You might also want to check that the graph really is a tree, i.e., that it is connected and acyclic.


Maximum sum subset of an array with an extra condition

Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $[1, n], [n+1, 2n] \ldots [(t-1)n+1, tn]$ we can't take more than $k$ elements, so the number of taken elements won't be larger than $t\cdot k$. Let's call the indices of taken elements in the given array $x_1, x_2 \ldots x_{tn}$. It's easy to notice that $x_i + n \le x_{i+k}$, because there can't be more than $k$ elements in any window of size $n$.

With this knowledge we are ready to construct dynamic programming solution, which would choose in parallel indices for every segment $[x_1 \ldots x_k], [x_{k+1} \ldots x_{2k}] \ldots [x_{(t-1)k+1} \ldots x_{tk}]$ separately.

$$dp[k+1][k+1][k+1]...(t\,times)[tn]$$
We would iterate trough positions $i$ from $1$ to $tn$ and every time decide whether we want to take one more element in the first segment from the position $i$, in the second segment from the position $i+n$, in the third segment from the position $i+2n$ etc. Bear in mind that at any point any segment cannot have more chosen elements than one of its preceding segments.

For $t = 3$:
$$dp[a][b][c][i] = max(dp[a][b][c][i-1], dp[a-1][b][c][i-1] + A[i], dp[a][b-1][c][i-1] + A[n + i], dp[a][b][c-1][i-1] + A[2n + i], dp[a-1][b-1][c][i-1] + A[i] + A[n+i] \ldots)$$
There are in total $3^t$ different combinations of taking elements from $i$-th position and it can be easily fixed in code using additional $3^t$ states.
if $a \le b \le c$ is not met:
$$dp[a][b][c][i] = -inf$$

Result of the given task is stored in one of $dp[x][0][0][tn], dp[k][x][0], dp[k][k][x]$ states for any $x$ depending on how many elements does the optimal solution use.

So overall time complexity is $O(tn(k+1)^t3^t)$ and space complexity is $O(tn(k+1)^t)$.


Applying Master Theorem to: T(n) = T(n - 2) + n^2

Think about what the derivative of T is. If the difference between T (n) and T (n-2) is $n^2$ then the derivative T' (n) is about $n^2 / 2$ and T (n) is about $2/3 · n^3$.


Why do AlphaGo and AlphaGo Zero include board history in the input features

The primary reason for including a history of states is likely indeed the ko rule. Even if having a long history will often be redundant, it's unlikely to hurt either (except that it might take some computation time... but that doesn't appear to be a major concern throughout the entirety of the papers).

I imagine that having a history of states can also help the Neural Network to more easily "focus" on important areas of the board during training (maybe only in the beginning of the training process, maybe for a longer time). You're right that, from a game-theoretic point of view, the current game state should be sufficient (ignoring rare cases). However, the learned components of AlphaGo Zero are not optimal in a game-theoretic sense early on in training (and likely still aren't after training either). Architectural choices in the Neural Network that may be redundant in a game-theoretic sense may still be beneficial for more rapid learning.

For example, in early stages of learning when learned components are still performing poorly, I imagine a useful heuristic may be to pay more "attention" to areas of the board where moves have recently been made; these are more likely to be important areas of the board than some different area of the board where nothing is going on (especially for an amateur-level component in the beginning of a learning process). Such areas of the board can easily be identified by subtracting game states in the recent history from each other.

I would not be surprised if this indeed ends up happening to some extent during the learning process. Stochastic Gradient Descent tends to, intuitively, take the path of "least resistance" and greedily optimizes parameters wherever it happens to notice some correlation between inputs and outputs. Of course this whole argument is rather handwavy, and it also may not at all be happening... I suppose the main point is what I put in boldface above. Neural Network-based components are not optimal in a game-theoretic sense, and they're also trained using algorithms (SGD-style) that may take suboptimal paths to global minima or not even find a global minimum at all. Modifications that would not be necessary for an "optimal" solution may still help to more easily or more quickly find good solutions.

David Silver, one of the first authors on both of the AlphaGo papers, describes a similar hypothesis to what I described as "focus" (more commonly described as "attention") here (emphasis mine):

  Actually, the representation would probably work well with other choices than 8 planes! But we use a stacked history of observations for three reasons: 1. it is consistent with common input representations in other domains (e.g. Atari), 2. we need some history to represent ko, 3. it is useful to have some history to have an idea of where the opponent played recently - these can act as a kind of attention mechanism (i.e. focus on where my opponent thinks is important).


Which kind of interrupt has the highest priority on 8086 processors?

The Intel manual for 8086 on page 2-23's diagram and also in the text says that internally generated interrupts are processed before hardware. It says in particular an overflow is processed as part of the instruction that generated the over flow, and hardware interrupts aren't checked until instructions are complete.  So overflow is the answer.


A 4-bit combinatorial circuit that outputs 1 when integer greater than 7 and is odd number

You've got the answer!

The number is eight or higher if the first bit is set. The number is odd if the last bit is set. So the answer is simply those two bits ANDed together. The two middle bits don't matter, you don't need to bother with them.


No, because A TM has 3 possibilities: run forever, accept, or reject. So the language of a TM is recursively enumerable as the TM M either accepts some input x, which means x is in L(M), or otherwise rejects or runs forever.

A language can be non-recursively enumerable, but the language of a concrete TM is always recursively enumerable.


How to find max number with a single-tape turing machine?

There are many ways to tackle this. This is just one suggestion. I assume you need a single-tape machine, and that you actually need to write it down formally, so you need a very simple solution, not something like "just compare the numbers".

Start by finding $\max\{x_1,x_2\}$, and replacing $x_1,x_2$ with this new number. To do this, you can take to new symbols $X,Y$, and erase one letter from each number using one of $X,Y$. After one of the numbers is erased, you remain with the second number. You can then erase the smaller number, and restore the bigger one to $1$'s.

Then, simply repeat the process until you are left with a single number.
It requires several states, but it shouldn't be too huge.


Can the same node appear twice in a tree?

A tree is defined to be a set of nodes, with a parent-child relationship that satisfies certain properties.  Thus, it doesn't make sense to ask whether a node can "appear" twice.

In your code snippet, you have constructed a DAG, not a tree.


Randomly select a uniform subsample from a nonuniform dataset

One approach would be to weight each timestamp with the time since the previous timestamp.  In other words, sort the timestamps in increasing order and then let the timestamps be $t_1,t_2,\dots$.  Now, weight the timestamp $t_i$ with weight proportional to $t_i-t_{i-1}$.  Finally, sample from the timestamps, choosing each possible timestamp with a probability proportional to its weight.  This will ensure that the selected timestamps are distributed uniformly across time.

You can also look at variants of this, where you do some kind of smoothing.  For instance, given a timestamp $t_i$, you can look at the 5 previous timestamps, compute the average duration between them, and choose a weight based on that; this amounts to choosing $t_i$ with probability proportional to $t_i - t_{i-5}$.  Or, you can choose a fixed duration $d$, and choose a timestamp $t_i$ with probability that is proportional to the number of events that occur in the window $(t_i-d,t_i]$ (i.e., proportional to $|\{j : t_i-d < t_j \le t_i\}|$).  The latter is similar to your histogramming idea, so might be a bad choice -- the problem is that you have to choose a fixed duration $d$, which might be problematic.  So try my other suggestions.

There's no way in general to choose a sample that is simultaneously uniform in both dimensions.  For instance, suppose your timestamps are evenly spaced through time, where the earliest 80% have phase 0 and the latest 20% have phase 1; then there's no distribution on timestamps that is simultaneously uniformly distributed in time and uniformly distributed in phase.
However, you can choose one sample that is uniform in one dimension, and uniform in another dimension.


Union of finite and non-regular language

Hint 1: Try to prove the contrapositive, namely: if $C\cup B$ is regular and $B$ is finite, then $C$ is regular.

Hint 2: Use closure properties of regular languages.


Examples of Context-sensitive grammars which produces non-indexed language

If you settle for a noncontracting (or monotonic) grammar instead:

$S\to DTA \mid ab$ $~~~~~$ the last $A$ is an end-marker for the last $ab^n$, $n=1$ separate.

$T\to DTa \mid Da$ $~~~~~$ number of $D$'s equals the number of $a$'s ($A$ counts as $a$)

$Da \to abD$ $~~~~~$ every $a$ gets an extra $b$

$Db \to bD$ $~~~~~$ $D$ moves over $b$'s

$DA \to Ab$ $~~~~~$ and $D$ disappears at the last block of $ab^n$

$A \to a$ $~~~~~$ finally end-marker $A$ is changed into $a$ (if we do this too soon, the $D$'s will not disappear, and the dirivation is not valid)

Example of building word $abbbabbbabbb$ ($n=3$) (added by @Andremoniy):

1) $S\Rightarrow DTA\Rightarrow DDTaA\Rightarrow DDDaaA$ - "inflate" string $n$ times;

2) $\Rightarrow DDabDaA\Rightarrow DabDbDaA\Rightarrow abDbDbDaA\Rightarrow abbDDbDaA\Rightarrow abbbDDDaA\Rightarrow \dots$ - we built 1st subword $abbb$, move on

3) $\Rightarrow abbbDDabDA\Rightarrow abbbDabDbDA\Rightarrow abbbabDbDbDA\Rightarrow abbbabbbDDDA\Rightarrow\dots$ - two subwords $abbbabbb$ are built, move on

4) $\Rightarrow abbbabbbDDAb\Rightarrow abbbabbbDAbb\Rightarrow abbbabbbAbbb\Rightarrow abbbabbbabbb$


How to prove that existence of one-way functions implies P≠NP?

Suppose that P=NP, and that $f\colon \{0,1\}^* \to \{0,1\}^*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \in \{0,1\}^n$ such that $y = f(z)$ in polynomial time (in $n$).
Using an NP oracle, we determine whether there exists $z$ such that $z_1 = 1$ and $y = f(z)$. If so, we set $w_1 = 1$, and otherwise, we set $w_1 = 0$. Using an NP oracle, we determine whether there exists $z$ such that $z_1 = w_1$, $z_2 = 1$, and $y = f(z)$. We set $w_2$ accordingly. Continuing in this way, we eventually found $z$ such that $y = f(z)$. Since we assumed that P=NP, this algorithm runs in polynomial time.


[...] it says that Map() function emits <"hello", 1> every time it sees hello where the reduce function counts the number of instances "hello" occurs

Not quite: It appears the mapper reads each file, counts the number of times a word appears, and outputs a single (word, count) pair per file, rather than per occurrence of the word. The reduce step then sums these. ("hello", 1) indicates that "hello" appeared once in a given file, ("hello", 3) indicates three appearances in a file, etc.

In the example for the reduce step, it appears four files were mapped, and that "hello" appeared 3 times in the first, 5 in the second, etc.

  Also, why do you need MapReduce to do this?

Via wiki MapReduce is "for processing parallelizable problems across huge datasets using a large number of computers[.]" Meaning, if your task is to count the number of times "hello" appears in four small documents, you likely don't need MapReduce. But if your task is to count the appearances of all words that appear in a large set of documents, then the only way to accomplish this is a practically useful time may require distributing across multiple processors.


does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

Let us denote by $L_S(P)$ the set of numbers in $P$ for $P \in S$, and similarly by $L_M(P)$ the set of numbers in $P$ for $P \in M$.

Consider the following program $P \in S$. It interprets as input as a pair of integers $(x,y)$, runs the $x$'th Turing machine on the empty input for $y$ steps, returns $x$ if the machine halts, and returns some fixed $C$ if $x$ doesn't halt, where $C$ is the index of a halting Turing machine. Thus $L_S(P)$ is the set of indices of Turing machines which halt on the empty input. It is well-known that this language cannot be computed by an $M$-program, that is, $L_S(P) \neq L_M(Q)$ for all $Q \in M$.

More generally, a non-empty language is of the form $L_S(P)$ iff it is r.e., whereas a language is of the form $L_M(Q)$ iff it is recursive.


There are systemic approaches to find the separating words (a.k.a. distinguishers).

However, for small instances of regular languages, I prefer to use plain argument in plain English sometimes. Let me use your case 1) as an example, where you have got all the equivalent classes correctly.

$L$ contains words that start and end with $aa$.
$S_1$ is the empty word.
$S_2$ is the word $a$.
$S_3$ are the words that do not start with $aa$.
$S_4$ are the words that start with $aa$ and end with $aa$.
$S_5$ are the words that start with $aa$ but do not end with $a$.
$S_6$ are the words that start with $aa$ and end with $a$ but not $aa$.

What kind of words can be attached to each group of words to make them in $L$?

$S_1$ + $L$
$S_2$ + words that start with $a$ and end with $aa$.
$S_3$ won't work
$S_4$ + $a$ or words that end with $aa$.
$S_5$ + words that end with $aa$.
$S_6$ + words that end with $a$.

Now that we know these completion groups of words, it is easy to find the separating words.

For example, $S_1$ and $S_2$. We need a word that is in $L$ or that starts with $a$ and ends with $aa$, but not both. The word $abaa$ will do.

For example, $S_5$ and $S_6$. We need a word that ends with $aa$ or that ends with $a$ but not both. The word $a$ will do.


Number of buckets for bucket sort (most significant bits)

The code you found is unfortunately written and explained in a very confusing way, most notably in a way that, in my humble opinion, misses the entire point of Bucketsort.

Let $A$ be an array of $n$ elements, taken from the ordered set $(S, \le)$. Bucketsort is a sorting algorithm that sorts $A$ in linear time with probability $1$, subject to the hypothesis that the statistical distribution of the elements of $A$ over $S$ is known in advance.

For the sake of simplicity, we will assume $S$ to be the real interval $[0, 1)$ and the distribution of $A$ to be uniform over $[0, 1)$. Our second assumption is without loss of generality. In fact, should we be provided with a different probability density function $\rho$, we could simply replace each $x \in A$ with:

$$
x' =\int_{0}^x \rho(z) dz
$$

An analogous argument holds for different choices of $S$.

Bucketsort works as follows:

Split $[0, 1)$ in $n$ consecutive intervals, where $n = |A|$, such that the $i$-th interval is $\left[ \frac{i-1}{n}, \frac{i}{n} \right)$
Create $n$ empty lists $L_1, L_2, \dots, L_n$
For each element $x$ of $A$, add $x$ to the list corresponding to the interval in which it falls
Sort each list individually, then return the concatenation $L_1 \circ L_2 \circ \dots \circ L_n$

Correctness is obvious, but complexity isn't. The crucial hypothesis is that, by assumption, we are sorting elements uniformly distributed over $[0, 1)$. Therefore, if $n$ grows large, as it is the case in the usual asymptotic setting, at the end of our third step, each of the lists will contain a constant number of elements with probability $1$; if that weren't the case, the elements wouldn't be uniformly distributed after all. Also observe that "with probability $1$" is not the same as "certainly", although it's as close as it gets.

The choice of exactly $n$ buckets is due to the fact that we want our last step to take linear time; but that can only be achieved if each list contains a constant amount of elements. We could have chosen just as well to use $n/c$ buckets for any $c \in \Theta(1)$, but we couldn't have started with $ k \in o(n)$ buckets; each of them would have contained $n/k \in \omega(1)$ elements. The total cost of sorting them would have been:

$$
k \left ( \frac{n}{k} \log \frac{n}{k} \right ) = n \log \omega(1) \in \omega(n)
$$


Updating maximum sum subrectangle in a sparse matrix when one element is changed

Yes, absolutely.  There is a straightforward way to do what you want, if you work through the details of the algorithm given at the link in your question.  The trick is to use persistent data structures, to avoid re-computing data multiple times.

The algorithm given at your link builds a one-dimensional array A[] for each i,j (where $1\le i \le j \le m$), where A[k] = sum{B[i..j,k]}.  So, let's keep a copy of each of those arrays.  That can be done by using a persistent data structure for the array, say, a persistent balanced binary tree.  In this way, the output of the algorithm shown there is $m(m-1)/2$ 1-D arrays, one for each i,j.

Now let's say that the entry B[i*,k] gets modified in the matrix B.  Obviously, this affects the entry A[k] in each of the arrays for i,j, where i <= i* <= j.  That's at most $O(m^2)$ of the 1-D arrays.  And, we can go update that one entry of those arrays in $O(m^2)$ time.  In fact, for a sparse matrix, the running time is even less: it is something like the square of the number of non-zero entries in the k-th column of the matrix B.


Z is not the array of misclassified points.  Try working through an example, and be careful and precise when making statements like that; while you can talk about which points are classified by a particular classifier, that will depend on the classifier.  So, when there are multiple classifiers floating around (or multiple training sets floating around), you need to specify which classifier you are referring to.  I suspect this is what is tripping you up: something that is misclassified with one training set might be correctly classified with another training set.

The key guarantee of this procedure is: if you use Z as your training set for a nearest-neighbor classifier, then this NN classifier will have 100% accuracy.  Try working through an example to see why.  (It iteratively grows the training set as needed to ensure that every point will be classified correctly by that NN classifier.)

As always, when you are confused, start by working through a small example with a few points (two, three, four), simulating the algorithm by hand, with pencil and paper.  That will often be very effective at building intuition -- and in this case it should be sufficient to understand what is going on.


How are partial measurements performed on a N qubit quantum circuit?

To measure a single qubit you:

Split the amplitude vector into "target qubit is Off" and "target qubit is On" parts.
Weigh up the parts. Add up the squared magnitudes of the amplitudes within each part. This gives you the probability of each.
Randomly pick one of the parts. (Or keep tracking both. Just make sure you never interfere parts from one with the other anymore.)
Renormalize the part(s). Divide by the squared-magnitude-sum, so the result totals to 100% again.

You'll probably find the calculations a lot easier if you do one operation at a time instead of a whole column at a time.

Also, you'll probably find my quantum circuit simulator Quirk helpful. It lets you drop state displays into the middle of circuits. Useful for checking your work. Here's your circuit in Quirk, with various displays sprinkled in:

The vector entries are not in quite the same order, but they agree with your results.

As you can see, the top measurement results are 50/50 random and the third qubit ends up pointing right (i.e. in the state $|0\rangle - |1\rangle$ regardless of the measurement outcome). (Trying to factor out a qubit often makes states easier to understand.)

Basically what has happened is easier to explain if you think in terms of the X gate as an X-axis control. Given the state of the third qubit during the CCNot, that "control" is satisfied. So really it's like the controls on the top two wires are a controlled-Z. This entangles the top two qubits.


How can I show that this language is context sensitive?

In the same way that DFAs are the counterparts for regular expressions and PDAs are the counterparts for context free languages , the counterpart for context sensitive languages are LBAs (linear bounded Automaton)
That is to say that a language is context sensitive iff some LBA recognises it
But what are LBAs ?
Hopefully you have an idea about what Turing Machines are , an LBA is basically a Turing machine with limited memory , unlike Turing Machines which can access the entire infinite tape , the LBAs computation is restricted to the part of the tape which contains the input , thus the head can only operate in the part of the tape containing the input (hence bounded) , an Alternative less stricter definition is that only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head (hence linear) , in this way you can imagine the LBA as having a tape of length kn , where n is size of input and k is a constant associated with the machine
Now can we use an LBA to recognise L ?
Let M be an LBA :
M on input w :

Read the first symbol make sure it is an a , else reject ( since n≥1 we can't accept the empty string)

Read the entire string and make sure it follows the right order as , then bs then cs then ds else reject

move the head to the left end of the tape then start crossing an a then a b then a c then a d

Repeat 3 till all as are crossed , when crossing symbols if M finds that w fell short of some symbol (ex: all bs are crossed but we need to cross a b) reject

after all as are crossed read the entire input if there remain any uncrossed symbols reject

else Accept

Clearly M is an LBA that recognises L , thus L is a context sensitive language
Notice how M uses only finite memory , in this example using only the portion of the tape where the input is written is enough to recognise L


There's no such thing as "an authorized CS reference", since nobody has the authority to declare how tree levels should be numbered.

The "height" of a vertex is its distance from the root (or distance plus one; see another question about the definition) so it probably makes sense to start at the top in most cases.  But you should use whichever numbering is most convenient in your situation.


That syntax is actually rather questionable formally, since it treats the big-O as a function, which it is not. But with a bit of slop the rule to interpret these is rather simple. The big-O stands for some function with the asymptotic behaviour given by the big-O.

I'll start with the full syntax of the big-O notation:

$$ f(n) = O(g(n)) $$

means that

$$ \exists C~\exists n_0~\forall n > n_0: f(n) \leq Cg(n). $$

So when we write "complexity is $O(n)$", we are really saying complexity is $c(n)$ for which $c(n) = O(n)$.

Alternatively we can say $O(g(n))$ is a set of functions defined as

$$ O(g(n)) = \{ f(n) | \exists C~\exists n_0~\forall n>n_0: f(n) \leq Cg(n) \}. $$

And write $f(n) \in O(g(n))$ instead. While this definition is more logical, it seems to be less used in textbooks.

Now if we say that complexity is $2^{O(n)}$, we can't expand it simply as $c(n) = 2^{O(n)}$, because we didn't define that. So instead we replace the big-O with a function that conforms to the big-O. Like this:

$$ c(n) = 2^{f(n)},\ f(n) = O(n) $$

And you can expand any other expression containing big-O. The approach applies to any expression having big-O as subexpression, so $O(n)^n$ is just

$$ c(n) = f(n)^n,\ f(n) = O(n) $$

In the set notation it makes even more sense, because

$$ g(F) = \{ g \circ f | f \ in F \} $$

where $g$ is a function and $f$ is a set of functions with one argument is the only logical definition of expression involving set of functions. So than:

$$ 2^{O(n)} = \{ 2^{f(n)} | f(n) \in O(n) \} $$

and

$$ O(n)^n = \{ f(n)^n | f(n) \in O(n) \}. $$

As for $O(\epsilon^{1/2^n})$, that's just standard big-O notation:

$$ f(n) = O(\epsilon^{1/2^n}) $$
$$ \exists C~\exists n_o~\forall n>n_0: f(n) < C\epsilon^{1/2^n} $$

(which tends to $1$ as $n$ tends to $\infty$). The $\epsilon$ would usually be some tunable parameter in the algorithm.


Probability of Success in Slotted Medium Access

There is a clear explanation given in these lecture notes MIT course Digital communication systems (read by H. Balakrishnan and G. Verghese).
The specific part that you require is this>

If each node sends with probability $p$, then the probability that exactly one node sends in any given slot is $Np(1 − p)^{N−1}$.
The reason is that the probability that a specific node sends in the time slot is $p$, and for its transmission to be successful, all the other nodes should not send. That combined probability is $p(1 − p)^{N−1}$. Now, we can pick the successfully transmitting node in $N$ ways, so the probability of exactly one node sending in a slot is $Np(1 − p)^{N−1}$.


How to properly compare performance of a prototype against a baseline

The general answer is of course: "It depends on the problem and the final utilization of your software".

The first question you should answer is what makes a given version query time so variable ? Is it query dependent ? Does the software have some buffering between queries ? Maybe a ressource variable availability ?

Generally the performance of an algorithm is evaluated considering the worst query possible. Let's take an example, you need an algorithm to find where a function change of sign:

You may loop on all points one by one or do a binary search. The former would sometimes performs faster if the searched point is one of the first. Nevertheless, in worst case it has to analyse all points whereas the latter finds the solution in logarithmic time.

Now if you have a timeout, the main metric you have is how many timeouts gets each solution. Maybe you even can identify what queries lead to timeout for each algorithm. In my opinion, there is no sense to compare average query time if some algorithm gets timeout more often.


What would be acceptable size of list for O(n!) algorithm

It depends a bit on the constants hidden in the $O$, so no general answer is possible. In my experience you can aim for the low teens. 13! is about six billion. A computer can do about a billion things in a second, so a runtime of a couple of minutes seems reasonable if you only want to enumerate permutations. 15! is already more than a thousand times bigger, so most likely whatever you want to do will take too long.

On my machine counting to 11! in Python takes 14 seconds and counting to 12! takes two and a half minutes. Counting to 13! would hence take about half an hour. Counting to 15! would take about a week.


Conversion of fractional part of a hexadecimal number to binary

Here is how to convert the fractional part from hexadecimal to binary:
$$
(0.25)_{16} = \frac{2}{16} + \frac{5}{16^2} =
\frac{0 \cdot 8 + 0 \cdot 4 + 1 \cdot 2 + 0 \cdot 1}{16} +
\frac{0 \cdot 8 + 1 \cdot 4 + 0 \cdot 2 + 1 \cdot 1}{16^2} = \\
\frac{0}{2} + \frac{0}{4} + \frac{1}{8} + \frac{0}{16} + \frac{0}{32} + \frac{1}{64} + \frac{0}{128} + \frac{1}{256} = (0.00100101)_2
$$
As you can see, we simply replace $2$ with its base 2 representation, and then adjoin the base 2 representation of $5$. I included this calculation to show why this works.
Note also that $(0.25)_{16} \neq 1/4$.


if $L_1$ and $L_2$ are languages over the same alphabet and $L_1 \cap L_2$ is context free, at least one of them must be context free

One way to deal with this kind of problems is to check some easy and extreme cases. Also, you would like to have a few concrete instances of the concepts involved. You should try to construct simple counterexamples with the instances. If you have found just one counterexample, great, you have found the answer. If you cannot found counterexamples by various constructions, you might have gained some understanding why it might be correct. You may have to repeat a few times.

What are some instances of non-context-free languages? Here is one. $\{0^{n^2}\mid n\ge1\}$. Or another one $\{1^{n^2}\mid n\ge 1\}$. Or another one $\{0^{n^2+1}\mid n\ge1\}$. How about their intersections?

In general, a condition that stipulates the type of the intersection of two languages is a very weak restriction to each of the languages. There are a lot of room for each of them to vary without changing their intersection.

Interested readers can enjoy the following simple exercises. $L_1$ and $L_2$ are are assumed to be over the same alphabet for all exercises.

Exercise 1. If $L_1 \cap L_2$ is finite, must at least one of them be finite?

Exercise 2. If $L_1 \cap L_2$ is regular, must at least one of them be regular?

Exercise 3. If $L_1 \cap L_2$ is context sensitive, must at least one of them be context sensitive?

Exercise 4. If $L_1 \cap L_2$ is decidable, must at least one of them be decidable?

Exercise 5. Raise a similar question.


Hint on median of two sorted lists, logarithmic time

Hint: Given any element, you can determine its relative position (in the sorted merged array) in time $O(\log m + \log n)$ using binary search. Use this primitive together with binary search to determine the median.


Reduce our problem to a known np-complete problem

The hint tells you pretty much everything:

Consider an arbitrary graph $G_{2}$ on $n$ vertices.
Also per the suggestion of the hint, let $G_1$ be the complete graph on $k$ vertices, for some $k \le n$.

Is $G_{1}$ is isomorphic to a subgraph of $G_{2}$?

If yes, what does that tell you about $G_{2}$?
How can you use that to solve the max-clique problem?


How to prove this isomorphism-related graph problem is NP-complete?

Here's a hint:  Consider Vertex Cover, which is NP-complete.  If $G = (V,E)$ has a vertex cover of size $k$, then you can remove $k$ vertices from $G$ to obtain $G'$ such that $G'$ is an edgeless graph on $n-k$ vertices.

Edit:  The correct reduction (by using Vertex Cover) shows the problem to be NP-hard.  Given the correct witnesses, you can easily show that it is in NP.


In order to prove that $\log(n^2+1) \in \Theta(\log n)$ according to your definition, you have to produce $a,b,n_0$ such that $a \log n \leq \log(n^2+1) \leq b\log n$ for all $n \geq n_0$. This is not what you did. What you have shown is some other inequality.

To help you in future such questions, here is a complete proof. We choose $a = 2$, $b = 3$, and $n_0 = 2$. So we have to show that for $n \geq 2$,
$$
2\log n \leq \log(n^2+1) \leq 3\log n.
$$

The first inequality follows from
$$
\log(n^2+1) \geq \log(n^2) = 2\log n.
$$
You did that part correctly.

The second inequality follows from
$$
\log(n^2+1) \leq \log(n^2+n^2) = \log(2n^2) \leq \log(n^3) = 3\log n.
$$
This is the part you did incorrectly.


Connecting The Informal and Formal Definitions of Decidable With Each Other

The author himself wrote informally speaking, the second is not a definition in the same sense of the first.

Intuitively, since a recursive function is defined by either $\mu$-recursion or composition of simpler functions, the existence of a total recursive function provides an effective method to compute the answer.

The informal part of the above reasoning is that we didn't really define what we mean by "effective method".

The usual formalization involves the definition of a computational model, which provides a rigorous framework for the notion of algorithm. Once you have done that, you can prove the equivalence in a mathematical sense.


SLR(1) Table construction, FIRST and FOLLOWS

In SLR(1) parser you need to compute only the follows of non-terminal symbols. When you have to put a reduce in the table, you look at the follows of the head of the production, and then put the production only in columns(correspond to terminals) that are in the follows.


Why does the cumulative order in which nodes are first visited with Iterative deepening is effectively breadth-first

What this statement means is that if you list the order in which vertices are "discovered" (first visited) in iterative deepening DFS, then it will be the same order in which vertices are discovered in BFS.


How asymptotically bad is naive shuffling?

We will show by induction that the permutation $\rho_n = (2,3,4,\ldots, n,1)$ is an example with $C(\rho_n) = 2^{n-1}$. If this is the worst case, as it is for the first few $n$ (see the notes for OEIS sequence A192053), then $m(n) \approx (2/e)^{n}$. So the normalized min, like the normalized max, is 'exponentially bad'.

The base case is easy. For the induction step, we need a lemma:

Lemma: In any path from $(2,3,4, \ldots, n, 1)$ to $(1,2,3, \ldots, n)$, either the first move swaps positions $1$ and $n$, or the last move swaps positions $1$ and $n$.

Proof Sketch: Suppose not. Consider the first move that involves the $n$'th position. Assume that it is the $i$'th move, $i\neq 1$ and $i \neq n$. This move must place the item $1$ in the $i$'th place. Now consider the next move that touches the item $1$. Assume this move is the $j$'th move. This move must swap $i$ and $j$, moving the item $1$ into the $j$'th place, with $i < j$. A similar argument says that the item $1$ can only subsequently be moved to the right. But the item $1$ needs to end up in the first place, a contradiction. $\square$

Now, if the first move swaps the positions $1$ and $n$, the remaining moves must take the permutation $(1, 3,4,5, \ldots, n,2)$ to $(1,2,3,4, \ldots, n)$. If the remaining moves don't touch the first position, then this is the permutation $\rho_{n-1}$ in positions $2 \ldots n$, and we know by induction that there are $C(\rho_{n-1})=2^{n-2}$ paths that do this. An argument similar to the proof of the Lemma says that there is no path that touches the first position, as the item $1$ must then end up in the incorrect position.

If the last move swaps the positions $1$ and $n$, the first $n-1$ moves must take the permutation $(2,3,4,\ldots, n,1)$ to the permutation $(n,2, 3,4, \ldots, n-1, 1)$. Again, if these moves don't touch the last position, then this is the permutation $\rho_{n-1}$, and by induction there are $C(\rho_{n-1})=2^{n-2}$ paths that do it. And again, if one of the first $n-1$ moves here touches the last position, the item $1$ can never end up in the correct place.

Thus, $C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$.