Where in the toolchain does formal specification come in?

Tests can be written based on either a formal spec or an informal spec.

Verification always requires a formal specification.  Formal verification might be manual or automated, or some combination of the two; it depends what techniques you use.  Typically, it's hard to do completely automatic verification -- it's more usual that verification systems automate part of the verification task, but require some assistance from the programmer (e.g., to specify invariants or prove lemmas that are hard for the automated system to prove).  See https://en.wikipedia.org/wiki/Formal_verification for an overview; there are also textbooks that give an overview of formal verification.  I suggest reading some standard references on formal verification: they will probably answer a lot of questions you might have.

There's nothing that says you have to have an informal spec, a formal spec, and a program.  You could have just a formal spec and a program.

It is often helpful to have specifications at multiple levels of abstraction/granularity, with theorems relating them.  Higher-level specs may be easier to understand and specify properties about the whole system or properties we ultimately care about, but may be difficult to prove directly; lower-level specs may be more detailed and harder to work with or understand, but may have a more direct mapping to the program and might facilitate proof/verification.

Higher-level specs might be formal, or in some cases they might be less formal.


Sharp concentration for selection via random partitioning?

It's not true that the algorithm runs in linear time with high probability. Considering only the first round, the running time is at least $\Theta(n)$ times a $G(1/2)$ random variable. Let $p(n) \longrightarrow 0$ be the allowed failure probability. Since $\Pr[G(1/2) \geq \log_2 p(n)^{-1}] = p(n)$, the running time is at least $\Omega(n \log_2 p(n)^{-1}) = \omega(n)$.

(There is some cheating involved, since the length of the first round isn't really $G(1/2)$. More careful analysis might or might not validate this answer.)

Edit: Grübel and Rosler proved that the expected number of comparisons divided by $n$ tends (in some sense) to some limit distribution, which is unbounded. See for example Grübel's paper "Hoare's selection algorithm: a Markov chain approach", which references their original paper.


Structure for getting $| \{ a,b \} \subset S : a+b \le d|$ in O(1)

It is on the right direction to try some kind of tree augmented with a global counter that stores the number of all unordered pairs of nodes $\{u,v\}$ such that $v.value+u.value \le d$.

The kind of tree you are looking for is a balanced (binary) search tree. Being balanced such as an AVL tree, it supports insertion, deletion and lookup of a number with $O(\log|S|)$ time.  Being sorted as well, it can also update that global counter in $O(\log|S|)$ time if we can maintain some extra information on each node of the tree.

What should be those extra information? One approach is that each node $v$
will have a member $lcount$ that stores the number of nodes in its left subtree as well as a member $rcount$ that stores the number of nodes in its right subtree.

To simplify the explanation, let us use AVL tree. We will assume all values are distinct; otherwise, we can add a duplicity counter to each node.

Each insertion or deletion involves at most two tree rotations. Each rotation changes the edges between at most several nodes. So we can update all $lcount$ and $rcount$ in $O(\log|S|)$ time.

Before the insertion of node $n$, we should compute the number of nodes whose values are not greater than $d - n.value$, which is one plus the number of nodes to the left of the node $m$, whose value is the greatest but no greater than $d-n.value$. With the insertion of $n$, we will keep the global_counter intact if there is no such node $m$. Otherwise, letting $ancestor$ be $m$, we will do the following.

while ancestor is not null:
  if anc.value < m.value:
    global_counter := global_counter + ancestor.lcount + 1
  ancestor := ancestor.parent

The case of deletion is similar to the case of insertion.

Further explanation will be omitted.

Thanks to OP, who contributed to this answer.


"Breadth course" problem – find maximum independent set given all maximal cliques

This is an instance of bipartite matching.   You have one left-vertex for each course, one right-vertex for each category, and an edge between each course and each category it can be used for.  Now you want to find a maximum matching in this bipartite graph.  There exist standard polynomial-time algorithms for finding a maximum matching in a bipartite graph.


CURE algorithm: what does moving the representative points towards the centroid do?

If I'm understanding your question correctly, you are interested in why the representative points are chosen as such, why they are merged and why this works. I'll first go over some background for CURE, then I focus on this particular question.

Background: why CURE?

I think we should start with the intention of CURE. To see that, we look at slide 14:

Here, CURE is compared with BIRCH and MST. We see that BIRCH succeeds in identifying the top ellipsoid pair as different, but fails to detect the large disk as a single cluster. BIRCH seems to only support same-sized clusters, So BIRCH doesn't make some clusters big enough and others too big. MST successfully classifies the disk as a single cluster, but fails to separate the ellipsoids on top. MST makes the clusters too big.

So, BIRCH is an attempt at trying to 'hit' the sweet spot between BIRCH and MST, in the hope of creating better clusters. In this example, it seems to be working pretty well.

Alright, back to the main question, why are the representative points handled as such? Suppose CURE would output the BIRCH result as an intermediate step. It then looks at the representative points of the light-blue and black half-disks. As the representative points are close, CURE would decide to merge these two half-disks into a full disk, which is good.

Okay, that's nice and all, but what prevents CURE from merging the two ellipsoids above, as BIRCH does? CURE doesn't do this (or is at least unlikely to do so), as the representation points are well scattered. This means that it is only likely that two clusters that are touching each-other on a location with high density get merged (as otherwise many representatives being close has low probability). As the two ellipsoids only touch each-other at points with low density, CURE (with carefully chosen parameters, no doubt) detects them as different.

How to merge?

We've seen that CURE sometimes has to merge two smaller clusters into a bigger one. The question is how to handle the representative points. The simplest way to do this is to simply add them to the new cluster. But this isn't a good idea. For their original clusters, the representation points were well scattered. But if we simply use the same points for our merged cluster, this is no longer the case.

To see this, consider the example of the two half-disks in the clustering provided by BIRCH. Suppose that the representation points form the outline of a half-disk slightly smaller than the ones given. Now, if we merge the clusters, the representation points lie a bit far away from the center. They are no longer well scattered.

This is a problem, because if there were another disk-like cluster nearby ('connected by a chain of outliers', as the authors would say), the fact that the representation points are too far to the edge of our newly merged disk means we're likely to put the two disks in a single cluster. Note that this process can occur many times at different hierarchical levels, so if we don't solve this, we won't get nice results.

So, the solution is to move the representation points a bit closer to the center, as this makes them more well-scattered and therefore decreases the probability that we make a bad merge.


It is possible to implement a *greater than* function using only addition, substractions and multiplications?

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.

Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x_1,\ldots,x_n$ in the following form:
$$
\sum_{t_1,\ldots,t_n \in GF(q)} f(t_1,\ldots,t_n) \prod_{i=1}^n \left(1-(x_i-t_i)^{q-1}\right).
$$
Since the dimension of the space of $n$-variate functions is $q^n$ and the number of monomials of individual degree at most $q-1$ is also $q^n$, we conclude that this representation is unique.


Prove that all non-recursive languages are infinite

First, not every infinite language is undecidable. Some infinite languages are very easy to decide. For example, the language of all words ($\Sigma^*$).

The converse is true, however: every undecidable language is infinite. In order to show this, we can simply show how to decide every finite language:

Consider a finite language $L=\{w_1,...,w_n\}$. In order to decide it, you can construct a TM $M$ that encodes in its states the words $w_1,...,w_n$. This is done as follows: the machine starts in $q_0$, which intuitively corresponds to the empty word $\epsilon$.

$M$ then reads an input letter. If there is no letter, meaning that the word is $\epsilon$, then $M$ either goes to $q_{acc}$ or $q_{rej}$, depending on whether or not $\epsilon\in L$. Now, if there is an input letter $\sigma$ on the tape, $M$ goes to a state that corresponds to $\sigma$. Then, again, it reads the tape. If there are no more letters, it either accepts or rejects, depending on whether $\sigma\in L$. Otherwise, it read the next input $\tau$ and moves to the state $\sigma\tau$, and so on, until the maximal length of a word in $L$ is reached, in which case $M$ rejects immediately.

So essentially, $M$ has a state for each word of length at most $k$, where $k$ is the maximal length of a word in $L$. Thus, $M$ can keep track of the word that was read so far, and decides if it needs to be accepted.


minimum number of states for the regular expression

We can summarize this unary language by the list of possible lengths of words:
$$
0,3,5,6,8,9,10,11,12,\ldots.
$$
Now let us look at (left) shifts of this list:
$$
0,3,5,6,8-\infty \\
2,4,5,7-\infty \\
1,3,4,6-\infty \\
0,2,3,5-\infty \\
1,2,4-\infty \\
0,1,3-\infty \\
0,2-\infty \\
1-\infty \\
0-\infty
$$
There are 9 different shifts, and so 9 different states in the minimal DFA. In this case, the minimal DFA is very simple: it has 9 states $s_0,\ldots,s_8$, with arrows $s_i \to s_{i+1}$ (for $i < 8$) and $s_8\to s_8$, starting state $s_0$, and accepting states $s_0,s_3,s_5,s_6,s_8$.

This sort of reasoning works for all unary languages, though sometimes the minimal DFA won't be a simple path. For languages of the form $(1^{n_1}+\cdots+1^{n_k})^*$, the minimal DFA is in fact always a path, and assuming (without loss of generality) that $\mathrm{gcd}(n_1,\ldots,n_k)=1$, the number of states exactly equals $2$ plus the maximal integer not representable as a sum of non-negative multiples of $n_1,\ldots,n_k$ (in our case, $7$).


Solving T(n) = 2T(n/2) + log n with the recurrence tree method

The non-recursive term of the recurrence relation is the work to merge solutions of subproblems. The level $k$ of your (binary) recurrence tree contains $2^k$ subproblems with size $\frac {n}{2^k}$, so you need at first to find the total work on the level $k$ and then to summarize this work over all the tree levels.

For example, if the work is constant $C$, then the total work on the level $k$ will be $2^k \cdot C$, and the total time $T(n)$ will be given by the following sum:

$$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$$

However, if the work logarithmically grows with the problem size you'll need to accurately compute the solution. The series would be like the following:

$$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$$

It'll be a quite complex sum:

$$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$$

I'll temporarily denote $m=\log_2{n}$ and simplify the summation above:

$$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Here I used a formula for the $\sum_{k=1}^{m}k2^k$ sum from the Wolfram|Alpha online symbolic algebra calculator. Then we need to replace $m$ back by $\log_2{n}$:

$$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$$
$$=2n-\log_2{n}-2=\Theta(n)$$

Q.E.D.


How to jump directly from level 0 to level 5 in a Gaussian pyramid without having the levels 1, 2, 3, and 4?

$w$ is effectively defined by $$g_l(i,j) = \sum_{m=-2}^2 \sum_{n=-2}^2 w(m,n) g_{l-1}(2i+m, 2j+n)$$ and $h_l$ by $$g_l(i,j) = \sum_{m=-M_l}^{M_l} \sum_{n=-M_l}^{M_l} h_l(m,n) g_0(i2^l+m, j2^l + n)$$
Some straightforward substitution of the second into the first gives
$$\sum_{m_l=-M_l}^{M_l} \sum_{n_l=-M_l}^{M_l} h_l(m_l,n_l) g_0(2^l i+m_l, 2^l j + n_l) = \\
\sum_{m=-2}^2 \sum_{n=-2}^2 w(m,n) \sum_{m'=-M_{l-1}}^{M_{l-1}} \sum_{n'=-M_{l-1}}^{M_{l-1}} h_{l-1}(m',n') g_0(2^l i+2^{l-1}m+m', 2^l j+2^{l-1}n + n')$$
We conclude firstly that
$M_l = 2^l + M_{l-1}$, and since $M_1 = 2$ (and $h_1 = w$), we have $M_l = 2^{l+1}-2$. Secondly, that

$$h_l(m_l, n_l) = \sum_{\substack{-2 \le m \le 2 \\ |m_l - 2^{l-1}m| \le M_{l-1}}} \sum_{\substack{-2 \le n \le 2 \\ |n_l - 2^{l-1}n| \le M_{l-1}}} w(m,n) h_{l-1}(m_l - 2^{l-1}m, n_l - 2^{l-1}n)$$
by identification of weights of the same pixel of $g_0$.


If two languages $A$, $B$ are complements of each other, then their disjoint union $A \uplus B$ must be the set of all strings $\Sigma^{\ast}$ over the given alphabet $\Sigma$. That is, every string in $\Sigma^{\ast}$ has to be in $A$ or $B$ but not both. So if we want to show that $L_{1} \neq \overline{L_{2}}$, all we have to do is find a string that is either in both or neither.

In this case it's fairly trivial. All strings in $L_{1}$ and $L_{2}$ have a $c$ in them, so pick any string that doesn't have a $c$ it in. For example $\varepsilon$, it's in neither $L_{1}$ nor $L_{2}$.

A construction for a PDA for $L_{1}$ is given here.

As for proving $L_{2}$ is not context free, everything you need is here.


Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$?

Since you already implemented IDA$^*$ you certainly understand why it expands more nodes than A$^*$, i.e., it starts from the start state with a new depth-first traversal in each iteration. Note first that, the overall number of nodes visited by IDA$^*$, while necessarily larger than A$^*$ is not that much larger. The reason is that the number of nodes at each depth progresses according to a geometric series with factor $b$, the branching factor. As a result, the number of nodes at depth $d$, $b^d$, is much larger than the sum of all nodes expanded at the previous iterations, i.e., $b^d>\sum_{i=0}^{d-1}b^i$. From this difference, it turns out that IDA$^*$ requires $\frac{b}{b-1}$ additional expansions which is asymptotically optimal as the limit for large $b$ is 1. Concluding, for any algorithm visiting all nodes at depth $d$ is much more difficult than visiting all nodes at the preceding depths.

In case that you want to delve more into this issue, I strongly recommend you reading the original paper: Korf, Richard E. Depth-First iterative-deepening: An optimal admissible tree search. Artificial Intelligence (27), 97-109, 1985. See in particular Theorem 4.2:

  Depth-first iterative-deepening is asymptotically optimal among
  brute-force tree searches in terms of time, space, and length of
  solution.

Of course, it delivers optimal solutions so that it is admissible and hence, asymptotically optimal. It only practices depth-first traversals and therefore, it is asymptotically optimal in terms of space (requiring with a good implementation only $O(d)$).

As for the time, I already outlined the main theoretical reason but let me know highlight three main reasons why it is so fast in practice:

First of all, for almost all purposes, the overall running time of any algorithm is dominated by the time it takes to expand nodes (other operations are rather simple and atomic). It is indeed when expanding nodes that IDA$^*$ can be extraordinarily fast because:

1.1. IDA$^*$ is implemented recursively so that all you need is to take the state given as an argument and to generate a child at a time (for your specific case this simply means swapping the blank with an adjacent tile, that's only one statement!). However, for A$^*$ the expansion operation requires: first, popping a state from the queue, then generating all its children (i.e., moving the blank tile in all possible directions).

1.2. While the preceding operation makes some difference, the really important one is that A$^*$ requires sorting nodes in OPEN. Even if you do this with a 1-bucket (which would take $O(1)$), note that IDA$^*$ does not require to sort nodes at all, so that while A$^*$ takes time which is linear in the number of nodes expanded, IDA$^*$ takes none at all.
Thirdly, one of the contributions of best-first search algorithms (such as A$^*$) is that they avoid re-expanding nodes by using a CLOSED list (which in spite of its name is usually implemented as a set!!). IDA$^*$ does not have duplicate-detection mechanisms and hence, again, A$^*$ performs an extra operation which is not performed at all by IDA$^*$. If you want to know more about duplicate-detection in IDA$^*$ see: Reinefeld, A.; Marsland, T. Enhanced iterative-deepening search. IEEE Transactions on Pattern Analysis and Machine Intelligence (16) 7, 701-710, 1994.

The last point is truly relevant. In the case of the sliding-tile puzzle there are not many transpositions indeed and the shortest cycle consists of 12 moves, so that the number of re-expansions is not that large. Putting all these together, IDA$^*$ is a killer machine for all sizes of the sliding-tile puzzle.

However,, in spite of all its advantages, it might not be of practical interest in those applications that have a large number of transpositions. There have been various attempts to overcome this difficulty with limited success, see for example:

Dow, P. Alex; Korf, Richard E. Duplicate avoidance in depth-first search with applications to treewidth. International Joint Conference on Artificial Intelligence, 480-485, 2009.

Hope this helps,


How does the TLB identify a particular process?

In the most basic setup, the TLB doesn't determine that.  Instead, the TLB only maintains mappings for the pages that are accessible to the current process.  If process A is currently running, the TLB only contains mappings for the pages that are accessible to process A; so if page 2 belongs to process B, it won't be in the TLB.

Also, you should be aware that the TLB is a cache.  The definitive authoritative mappings are in the page table, and the page table contains mappings only for the process that is currently running.  The TLB is a cache of mappings found in the page table.  It gets filled in as you go.

When you change which process is running, you change the page table (since now you need a different set of mappings), and you clear the TLB (so you don't have any old mappings that are only relevant to the previous process).  Clearing the TLB is also called flushing the TLB.

I suggest reading a good OS textbook.  This information can be found in many places, so do a bit of research.  Also
https://en.wikipedia.org/wiki/Translation_lookaside_buffer may be helpful.

That describes the basic setup.  The disadvantage of the basic setup is that clearing the TLB is slow, which adds a lot of overhead every time you switch processes.  That slows things down.  Many modern processors have optimizations that reduce this overhead.

For instance, modern Intel TLBs have a process context ID (PCID); each TLB entry is tagged with the PCID of the process that the page mapping is for, and the processor will only use that TLB entry if its PCID matches the ID of the currently running process.  The processor fills the PCID when it creates the TLB entry from a register which the operating system must set to a unique value for each process.  You can read about that more by searching for PCID.

Arm processors have a somewhat similar feature called domains.  Each page table entry contains a domain field, which must be set by the operating system if it wants to use this feature.  The processor saves this value in the TLB entry.  On a context switch, the operating system updates a register containing the set of currently accessible domains.  A TLB entry is valid only if the corresponding domain is accessible.


Preamble
I'll use the following example to illustrate each statement. The graph below will be $GR$.

Below is the MST $M$ of $GR$. These are the bolded edges.

Statement One
The first statement is false if $A$ is an internal vertex of $M$. In that case, $M-\{A\}$ will result in a forest, which is not an MST.
Suppose we choose $A = d$, then $M-\{A\}$ will result in the following graph which is not a tree.

Statement Two
The second statement is true. It is pretty easy to see why $M-\{A\}$ in this case is still an MST.
Suppose we choose $A = a$ (our only choices are $\{a,g,i\}$), then $M-\{A\}$ (left) will result in the following tree. We can compare it to $GR-\{A\}$ (right) and see that it is an MST.

Statement Three
The third statement is true.
Formal Proof of Statement Three
Proof: Let $GR[T_1]$ and $GR[T_2]$ be induced subgraphs of $GR$ and $M_1'$ and $M_2'$ are their MSTs respectfully. Let $X$ be the set of edges that connect vertices of $T_1$ and $T_2$ in $GR$ (note $e \in X$).
To show $M_1$ and $M_2$ are MSTs, we must show is $M_1 = M_1'$ and $M_2 = M_2'$.
Let $w(M) = w(M_1) + w(e) + w(M_2)$ be the cost of the MST of $GR$.
Let $w(M_1')$ and $w(M_2')$ be the cost of the MST of $GR[T_1]$ and $GR[T_2]$.
Construct the graph $M' = M_1' \cup e \cup M_2'$. This graph is the MSTs of both induced graphs and a single edge that connects them. Note, we could use any edge from $X$, however for it to be a MST, we must select the minimum cost edge of $X$. So $w(M') = w(M_1') + w(e) + w(M_2')$.
Since $w(M_1')$, $w(e)$, and $w(M_2')$ are minimal, then $w(M')$ is minimal. Since $w(M')$ is minimal, then $w(M') = w(M)$. So,
\begin{align}
w(M_1') + w(e) + w(M_2') &= w(M') \\ &= w(M) \\ &= w(M_1) + w(e) + w(M_2).
\end{align}
So $w(M_1') = w(M_1)$ and $w(M_2') = w(M_2)$, thus $M_1' = M_1$ and $M_2' = M_2$. Hence, $M_1$ and $M_2$ are MSTs.
Intuition of Proof
I'll pick $e = \{c,d\}$ to be the edge with weight one for this example. Below is $M-\{e\}$

Let $M_1$ be the tree on the left and $M_2$ be the tree on the right. Then $T_1 = \{a,b,c\}$ is the vertex set of $M_1$ and $T_2 = \{d,e,f,g,h,i\}$ is the vertex set of $M_2$. We need to construct the induced subgraphs of $GR$ on $T_1$ and $T_2$, $GR[T_1]$ and $GR[T_2]$. Below on the left is $GR[T_1]$, and below on the right is $GR[T_2]$.

Now you can see the $M_1$ is the MST of $GR[T_1]$ (similarly for $M_2$).
In the proof, we abuse the fact that the MST of the induced subgraph and the original graph are minimal. We also use the fact that $M$ must contain $e$, the smallest edge that connects $M_1$ and $M_2$. We can conclude the only MST of the induced graphs is $M_1$ (for the left) and $M_2$ (for the right).
I hope this helps!


What is monograph and digraph in keyboard optimization problem?

The article uses monograph to refer to a single key, say "e", in a position on the keyboard. In the interest of efficiency, you'd want the frequently-used letters to be in locations where a model typist would have to expend the least motion to strike. A digraph, on the other hand, would be two keys which would be struck in sequence, like the "in" which I typed a few characters ago. In this case, we would be looking for a keyboard layout which minimized the effort depending not just on the absolute positions of the characters, but on the relative positions of the pairs.


The equational theory of regular languages has no finite set of axioms for general alphabets

For each $k > 0$, the equation
$$
 A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1})
$$
holds for regular languages over every alphabet, hence if for some alphabet we have a finite axiomatization, this equation is provable from it. Now as shown in A. Ginsburg, Algebraic Theory of Automata, the following infinite system of axioms is complete for unary regular languages.
\begin{align*}
 A + B & = B + A \\
 A + (B + C) & = (A + B) + C \\
 A + A & = A \\
 A + \emptyset & = A \\
 AB &= BA \\
 (AB)C & = A(BC) \\
 A1 & = A \\
 A \emptyset & = \emptyset \\
 (A+B)C & = AC + BC \\
 1^{\ast} & = 1, \emptyset^{\ast} = 1 \\
 (AB^{\ast})^{\ast} & = 1 + AA^{\ast}B^{\ast} \\
 (A + B)^{\ast} & = A^{\ast} B^{\ast} \\
  A^{\ast} & = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1}), \quad k > 0
\end{align*}
So we get a finite axiomatisation for unary languages, if we take but the last family of axioms, and all axioms from the finite axiom system for some alphabet that prove
$$
 A^{\ast} = (A^k)^{\ast}(1 + A + A^2 + \ldots + A^{k-1})
$$
for each $k > 0$. Then all of the above equations are derivable by this finite axiom system, and as the above one is complete, this finite axiom system would be complete, which is not possible. Hence there is no finite system of axioms for any alphabet.


Finishing degree requirements NP-complete: Choosing 1 element from each set avoiding conflicts

Assuming the sets $C_i$ are pairwise disjoint, this problem is very related to the independent set problem and is called maximum colored independent set (also called rainbow colored independent set). The problem goes as follows. Given a graph and a colouring function over the vertices of the graph. Find a maximum independent set with each vertex in the set having a different colour. The problem is NP-hard as well (try to reduce Independent set).

Assuming the sets are not disjoint the problem does not get easier since the version with disjoint sets is only a special case of this problem.


You seem to be confusing the definition of bisimilarity with an algorithm for finding a bisimulation.

In your examples, the states are indeed bisimilar, and the relation is the set
$$\{(A,A)\}$$
It is easy to verify that it satisfies the desired properties.

This means that the structures are indeed bisimilar.

What you were trying to do is to find an algorithm for constructing a bisimulation, given the two different structures. If you try to proceed by taking the initial states, and moving through paths, then you indeed encounter a problem with cycles. (By the way, if the structures were trees, or DAGs, then your approach would work).

This is why algorithms for finding bisimulations typically take a different approach -- namely refinement: you start with a naive relation (e.g., everybody is bisimilar to everybody), and whenever you find a mismatch, you refine your relation.

Take a look at the "fixpoint" definition of bisimilarity here, and try to extract an algorithm from it.


Has Anyone Actually Created a System that Writes Computer Programs from specification?

This is a very active research topic, very promising, though full
automation of program generation probably has intrinsic limitations (but are human beings any better?).
But the idea is still be very useful in assisting considerably the
creation of programs by mechanizing many steps, and by automatically
checking the correctness of the program generation.

It is strongly related to a result in logic, called the Curry-Howard
correspondance (or isomorphism), that shows that computer programs and
mathematical proofs are very similar.

So the idea is that the system will take your program specification as a
theorem to be proved. In the case of your example, it would be
something like (informally): "there is a set of all prime numbers smaller
than 10".

Then, you will attempt to prove that theorem, and existing systems
will assist you in doing the proof, automating some parts, possibly the whole proof, and making
sure you never make errors.

From that proof one can then extract a program
that actually computes the  wanted list of prime numbers that had been
initially specified.

Several systems were developed in the past to elucidate these ideas. One
of the better known was LCF by Robin Milner, who created the language
ML for that purpose. One of the currently most advanced systems is
Coq.

There are examples fully worked out, some of them quite complex. You may find some in the following article, though it is in no way simple reading and requires advanced knowledge of Logic.


Proving $L = \{0^i1^j0^i1^j\ |\ i+j > 0\}$ is not a context-free language

You do not need to express $i$ and $j$ in terms of $n$.

Now suppose $L$ were context-free; then there would exist an $n \geq 0$ such that for every $s \in L$ with $|s| \geq n$ there would be a partition of $s = uvwxy$ such that

$|vwx| \leq n$
$|vx| > 0$
$uv^iwx^iy \in L$ for all $i \geq 0$

Consider the example string $s = 0^n1^n0^n1^n$. Clearly, $s \in L$, and obviously $|s| \geq n$. You must now examine all the possible partitions of $s$ and show that none of them can satisfy all three of the above conditions.


I will give you some intuition how to build such NFA.

Because L is a regular language, then we can find deterministic finite automata F which accepts this language. Based on that we will build our NFA. Let's add epsilon transitions from all F's accepting states to new state which will be the only accepting state in our NFA. You can now prove, that such automata will accept L.


How to prove Shortest Common Superstring is NP-Hard

This article may help you.

Theorem 1 states that Hamilton path problem can be reduced to SCS even if all strings have fixed length $H \ge 3$.

For your case with strings of any length but fixed alphabet, this is also true, but the proof is more technical.


What does synchronous and asynchronous mean in computer science?

As Discrete lizard suggests, there is not some precise CS-wide definition for these terms. Generally, you should not expect terms and notation to always mean the same thing even within a single field.

Nevertheless, a vague general statement is that in "synchronous" systems, things "wait" for other things, while in "asynchronous" systems, things don't "wait".

That said, it's probably better to split this into two broad interpretations of this. There's "synchronous" in the sense of everything moving in lock-step (i.e. everyone "waits" for the next "round" or everyone "waits" on a "clock"). This interpretation is probably the closer of the two to the colloquial notion. This applies to synchronous circuits, Bulk Synchronous Processing, and synchronous data flow. A synchronous circuit has a clock signal and it executes in time with the clock. An asynchronous circuit allows each subcomponent to execute whenever it's ready. It requires careful timing to make sure all the inputs to each subcomponent are ready when that subcomponent is ready.

The other interpretation is blocking where one thing makes a request to another thing and then sits there waiting for the response. The "waiting for the response" aspect is what is called "blocking". Synchronous calls/messages would fall under this. The alternative is to send a message and then continue on without waiting for a response. Any response is either ignored or collected in a "mailbox" to be read at some later time. This is often handled by the framework you're using which will then dispatch events to which you register.

The Ptolemy Project is a fantastic resource for in-depth thoughts on different models of computing and their notion of time.


Proving simple bound on coupon collector

Divide the process into $n$ phases. The $m$th phase ($m=1,\ldots,n$) starts when the $(m-1)$st cell has been occupied, and ends when the $m$th cell has been occupied. The first phase takes time $1$. Suppose that the occupied cell is $i_1$. The second phase then takes expected time $1/(1-p_{i_1})$. Suppose that the occupied cell is $i_2$. The third phase then takes expected time $1/(1-p_{i_1}-p_{i_2})$. And so on. Overall, the expected time is
$$
1 + \frac{1}{1-p_{i_1}} + \frac{1}{1-p_{i_1}-p_{i_2}} + \cdots + \frac{1}{1-p_{i_1}-\cdots-p_{i_{n-1}}} = \\
\frac{1}{p_{i_1}+\cdots+p_{i_n}} + \frac{1}{p_{i_2}+\cdots+p_{i_n}} + \cdots + \frac{1}{p_{i_n}} \leq = \\
\frac{1}{np_1} + \frac{1}{(n-1)p_1} + \cdots + \frac{1}{p_1} = \\
\frac{H_n}{p_1} \leq \frac{\ln n + 1}{p_1}.
$$


To answer the question, there are two different manners to solve this.

By adding a dead state whenever you have an incomplete automata. By doing so, you will no longer have to worry about what to do if one automata has a transition from a specific state but not the other.
You can still do the intersection of the two without adding dead states.

In this example, if you are focusing on the state 1 and 3 with the symbol 'b' :
- From A1, you have no transition : δ(1,b) = ∅
- From A2, you have a transition : δ(3,b) = 4

Since one has a transition, but not the other, then the resulting automata will have the transition : δ(13,b) = ∅. Therefore, it is indeed acceptable to put ∅.


Are there complete problems for P and NP under other kinds of reductions?

Your questions contain a few incorrect or unclear phrases.  Neither “complexity class X has Y reduction” nor “we can use Y reduction for complexity class X” makes sense.  In addition, there are at least two definitions known under the name “polynomial-time reductions,” both of which are used to study NP-completeness: polynomial-time many-one reductions and polynomial-time Turing reductions.  But in this answer, I will ignore the difference between many-one reductions and Turing reductions, and I will focus only on the resource restrictions of reductions, because otherwise the answer will become too long and unfocused.

Now I will restate what you might want to ask, and answer them.

Are there any definitions of reductions with respect to which NP-completeness can be defined, other than polynomial-time reductions?  Are there any definitions of reductions with respect to which P-completeness can be defined, other than NC reductions and log-space reductions?

As Artem and Raphael said, you can define whatever you like.

Are there any definitions of reductions actually used to study NP-completeness in the literature, other than polynomial-time reductions?  Are there any definitions of reductions actually used to study P-completeness in the literature, other than NC reductions and log-space reductions?

Yes.  For example, Papadimitriou uses log-space reductions throughout his textbook [Pap94], including the definition of NP-completeness.  (Note: in [Pap94], the term “L-reduction” means something completely different from log-space reduction.)  As for P-completeness, NCk reductions are mentioned in [GHMRSS00].  This is a special case of NC reductions, and more general than log-space reductions for k≥2.

But are they really different notions, or just different definitions for the same notion?

Currently, no one knows.  For example, log-space reducibility and polynomial-time reducibility are equivalent if and only if L=P.

[GHMRSS00] Raymond Greenlaw, H. James Hoover, Satoru Miyano, Walter L. Ruzzo, Shuji Shiraishi, and Takayoshi Shoudai.  The Parallel Computation Project: Volumes I–III, 2000.  http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/

[Pap94] Christos H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.


Shortest path between two points with n hops

If vertices can be visited more than once, then yes: you can create $n+1$
copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each edge $uv$ in the original graph becoming the set of edges $u_iv_{i+1}$ for all $1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex $A_1$ and end vertex $B_{n+1}$.  Intuitively, each edge traversed in any path necessarily takes you to the next "level" of the graph.

If vertices cannot be visited more than once, then there's no known poly-time algorithm, since setting setting $n$ to one less than the number of vertices would solve the NP-hard Hamiltonian Path problem.  (Although the HP problem technically asks for any path that visits all vertices exactly once, a poly-time algorithm for the simple-paths version of your problem would nevertheless give you a poly-time algorithm for HP: just run it $O(n^2)$ times, one for each possible pair of start and end vertices.)


Example of graph with exponential many s-t minpaths and min cuts

I can offer an example for super-exponentially many shortest paths and super-polynomially many minimum cuts.

An example for many shortest s-t-paths you probably came up with is the layer graph, similar to the one here. Turns out we can use the same idea here -- all we have to do is use many layers so that there are many minimum cuts, and fiddle with the weights so that there have to be enough "inner" nodes in either partition.

Idea: Use a complete layer graph with $\sqrt{n}$ layers and $\sqrt{n}$ nodes in each layer. Add $s$ and $t$ and wire with the first resp. last layer; make the weights on these edges so large that the first layer has to be in the partition of $s$ (and the last in that of $t$) for every minimum cut.

The graphs look like this (unit weights on all unlabelled edges):

[source]

Now we can count.

The graph has $n + 2$ nodes and $(n+2)\sqrt{n} - n \in \Theta(n^{\frac{3}{2}})$ edges.
Every shortest s-t-path picks one node in every layer; hence, we get $\sqrt{n}^{\sqrt{n}}$ such paths.
No edge $(s,\_)$ or $(\_,t)$ is ever part of a minimum cut (each such edge has more weight than all others together). Convince yourself that all cuts constructed by fixing a column (but the first and the last), putting every node either left or right and using this as the "cut line", are minimal with weight $n$. We obtain $(\sqrt{n}-2) \cdot 2^{\sqrt{n}}$ many such cuts.

At least with layer graphs, I think the two quantities can not be exponential at the same time; one needs non-constant depth, the other linear width. I'm not sure if a similar argument carries over to general graphs.


You're looking for a maximum cut in the graph – maximizing the number of edges between the partitions minimizes the number within them.

Unfortunately, Max Cut is NP-hard on general graphs and also hard to approximate. There's a polynomial-time algorithm on planar graphs, if that's of any use to you.


If $x \in L$ then the probability that $(P,V)(x,r) = 1$ is positive, where $r$ is the randomness involved; the probability is over the choice of $r$. In particular, there is some $r$ such that $(P,V)(x,r) = 1$.

In contrast, when $x \notin L$, the probability that $(P,V)(x,r) = 0$. That is, there is no $r$ such that $(P,V)(x,r) = 1$.

States differently, when $x \in L$, there is some conversation for which the verifier outputs 1, whereas when $x \notin L$, there is no such conversation. Since the verifier runs in polytime, the conversation has polynomial length, and can be verified to be a valid conversation in polynomial time. This puts $L$ in NP.

What is the difference between IP* and IP? IP* has perfect soundness – when $x \notin L$, the probability of error is 0 – whereas IP has neither perfect soundness nor perfect completeness. This makes IP much stronger.


Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Yes, if you don't want an injective mapping: just assign to all strings value 0.
No, if you want an injective mapping:

Empty string must correspond to value $0$. Otherwise,
$$value(\epsilon) = value(\epsilon \cdot \epsilon) = 2 value(\epsilon),$$
- contradiction when $value(\epsilon)\ne 0$.

Let "0" correspond to value $a$ and "1" correspond to value $b$ ($a,b > 0$). Then
$$value(0^b) = b \cdot value(0) = ab = a \cdot value(1) = value(1^a)$$
- contradiction, since both $0^b$ and $1^a$ correspond to the same value.


Why is DFS not suited for shortest path problem?

TL;DR Depth First Search
I believe that Depth First search traverses the graph by recursively visiting the unseen vertices of the current vertex until they're exhausted.
for all vertices fresh = true
DFS(v):
   v.fresh = false
   for all the neighbors e of v:
      if e.fresh:
         DFS(e)

Now, weight on the other hand, is a restriction imposed on edges. Hence, the usage of Breadth First Search becomes handy. Because we traverse the graph based on layers or levels, where we're checking all the edges at a certain vertex.
Dijkstra's algorithm
Dijkstra's algorithm is pretty much tricky. You seen, the original paper does specify how prioritize to vertices based on the sum of the weight for each reached vertex.
But more importantly, it does not specify how to fulfill such a task. Indeed, the whole time complexity is dependent on the complexity of how we're prioritizing the vertices.
Prioritizing the vertices
Consider an abstract data type PriorityQueue, where it supports the following operations for an instance queue:

void add(item) to add an item to the instance queue
item get() to return and remove the current top priority from the instance queue.

Many data structures provide these elementary operations. But the bottleneck of the algorithm is to update the vertex's priority in case it was reached from a less weighted edge.
Consider an operation update(item,value) that reset the priority of the item to a certain value. There are many ways to extend PriorityQueue but all of them have different complexities.
Using Arrays
Arrays are finite contiguous chunks of memory, so we have

$O(1)$ to add() any item at the end, $O(n)$, otherwise since it involves swapping.
$O(n)$ to get() the current priority because we traverse the whole array.
$O(n)$ to update() any item for the same reason.

Using Heaps
Heaps are arrays that have a binary tree property, called the heap invariant which states the following

Every node is less than it's children (in the case of a MinHeap)

This provides $O(\log_2 n)$ to both add() and get() an item. But it costs $O(n)$ to update() any item's priority (since there is no order imposed on the children).
Using Binary Search Trees (Balanced)
It has the same costs as the heap does for both to add() and get() an item. But instead of $O(n)$ to update(), we have $O(\log_2 n)$. Since searching throughout the whole tree is logarethmic due to the following properties

Every node is greater than its left
Every node is less than or equals its right

Using Fibonacci heaps
Fibonacci heaps are an advanced data structure that is a forest of MinHeap trees.


Consider the intersection of your language with $ab^*c^*$.


Given the set of length of triangle, find the Maximum Area Triangle

There is an $O(n^2)$ algorithm. By Heron's formula, the area of a triangle whose sides have length $a$, $b$, and $c$ is $S = \frac{1}{4}\sqrt{4a^2b^2 - (a^2+b^2-c^2)^2}$. Thus if we fix $a$ and $b$, the area is maximized when $c$ is closest to $\sqrt{a^2+b^2}$. A simple approach is to try all $O(n^2)$ possible pairs of $a$ and $b$ and perform binary search for the best value of $c$. This approach yields an $O(n^2 \log n)$ algorithm.

To achieve $O(n^2)$, we first sort the lengths of line segments ($l_1, l_2,\ldots, l_n$) in non-decreasing order. Let $a = l_i$ and $b = l_j$ with $i < j$, and let $k$ be the position in which $l_k$ is closest to $\sqrt{l_i^2 + l_j^2}$. When $j$ runs from $i+1$ to $n$, $k$ also increases gradually to $n$. Thus finding $k$ has an $O(1)$ amortized run time, i.e., the whole algorithm takes $O(n^2)$.

Update 11/26/2013:

An easier $O(n \log n)$ algorithm is to sort $l_i$ in a non-decreasing order, and find  $3\leq k \leq n$ that maximizes the area of the triangle assembled from $l_{k-2}, l_{k-1}$, and $l_{k}$. It follows from the fact that if $i ,j < k$ then $S(l_i, l_j, l_k) \leq S(l_{k-2}, l_{k-1}, l_k)$ (can be proved by taking the derivative of $S$ and that $l_k$ is the length of the longest side).


Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis

Imagine you're playing a game, and are currently at state $S_{0}$. In order to win, you must reach the state $S_{finish}$.

In every turn, you can do one of $c$ moves. Your goal is to reach $S_{finish}$ in as little moves as possible; in other words, every move has a cost $1$.

To find the optimal path $P = \{S_{0}, S_1, S_2 \dots S_{finish}\} $, would be finding the set of moves $c_1 \dots c_n$ so that $P$ is minimum.

So what would a lower cost first algorithm do? the same thing a $BFS$ would do; in each turn $i$, search $S_i^1...S_i^c$ possible states that can be reached from the previous state $S_{i-1}$.

so, searching $n$ times, how many moves have you effectively searched?

$1$ in turn 1

$c + 1$ in turn 2

$c*c + c+1$ in turn 3

$=\sum_{i=0}^{n-1} c^i$ in turn $n$, which is exponential in $n$.

But its also exponential in terms of space. To search all the next states $S_{i+1}$, you must keep all your current states $S_i$ in your memory.

How many states $S_i$ are there? $c^i$ as shown above.

When your professor mentioned Dijkstra is polynomial in $V$, he meant on input size that is $V,E=n, O(n^2)$ respectively. However, when searching the optimal path to some wanted state, like in chess, the number of states (or $V$ essentially, if we suppose a state is a vertex), grows exponentially.


NL - iterating all edges of a graph in log space

There's absolutely no problem to iterate over all edges in a graph in logspace (even deterministic logspace!). The details depend on how the graph is encoded. For example, if the graph is encoded as an adjacency matrix, then you can simply go over all pairs of vertices.

However, this doesn't give an NL algorithm for clique. The problem is that you need to iterate on $k$-tuples of vertices, for non-constant $k$. This is something you cannot do in logspace.

NP is sometimes described in terms of witnesses. However, the "official" definitions is using nondeterministic Turing machines, which are allowed to have more than one correct move at any given point in time. The class of languages accepted by nondeterministic polytime Turing machines coincides with the class of languages which are given a polynomial size witness and can verify it in polynomial time. Unfortunately, there is no such alternative description for nondeterministic logspace Turing machines.


How to make NFA remember its first step?

NFAs have finite "memory", and you need to store one bit of information: whether the first symbol was ".

   Copy the automaton for tokens. If your string starts with ", move to one copy; if not, to the other. The first copy then requires a trailing " to accept, the second one does not.

 In general, you can implement any finitely-bounded counter like this: just copy all states as many times as you need.


Robustness of Turing Machines - 3 dimensional case

If you are not concerned with efficiency this trivial and time-wasting approach can also work (it only shows how it can be done without taking too much care of coordinate-mappings ... in other words the bad way to do it :-)).

Use the single tape to store a list of quadruples $...\#x,y,z,v\#...$.

Each quadruple holds the value $v$ stored on the 3D tape at point $(x,y,z)$. Initially the single tape is filled with a finite list of the non-blank values of the 3D tape along with their coordinates, and the head is on the left of the quadruple that represents the head position in the 3D tape.

Every step of the original 3D machine can be simulated in the following way:

apply the original transition, and update the value $v$ to $v'$ in $(x,y,z,v)$
now, suppose that the head must move to the adjacent 3D point $(x',y',z')$, then search in the tape from left to right for a quadruple that matches its coordinates;- if you find it, then move the head on it and go to (1);- if you don't find it, just append a new quadruple $(x',y',z',blank)$ to the end of the tape, move  the head on it and goto (1)

For every state of the original 3D machine you must have many states on the single tape machine in order to perform the operations at step 2 and at the same time keep track of the current state of the original machine.


Applying Shannon Entropy to data storage

No.  That is telling you the size of the file, i.e., that's a statement about its length, not its entropy.

Of course, the length gives an upper bound on the entropy, but it is not itself a value for the entropy.  The actual entropy could be smaller.

No, compressing the file does not tell you its entropy.  The length after compression is, on average, a reasonable upper bound for the entropy -- but the true entropy could be much smaller.

Beware that it only makes sense to talk about the entropy of a random process or the entropy of a distribution (e.g., the entropy of a process used to generate a file), not the entropy of a single file.  As an analogy, consider this old joke:

It doesn't make sense to say that "the number nine is random"; that's a property of the process used to generate the number, not the number itself.  You could get a 9 by rolling a ten-sided die (which is a random process), or you could get a 9 by writing the largest single-digit decimal number (that's not a random process).  Similarly, it doesn't make sense to ask what is the entropy of the number nine; that is not well-defined.  We can talk about the entropy of the random process that was used to generate it, though.

See a good textbook to learn more about the subject of entropy.


Finding a closed form for a discrete sum using generating functions

The term $t_N = {2 N - i \choose N} x^N$ of the sum is hypergoemtric ($t_{N+1}/t_N$ is a rational function of $N$) which means that the closed form of the sum can be found using Gosper's algorithm, if it exists and is hypergeometric.

When I run the algorithm with Mathematica it says
$$x^i \cdot {}_2F_1(\frac{i+1}{2}, \frac{i+2}{2}; i+1; 4 x)$$
where ${}_2F_1$ is the hypergeometric function. This means that a closed form of the kind you are expecting does not exist.

Supplemental:

Gosper's algorithm computes
$$\sum _{i=0}^n \binom{2 n-i}{n} 2^i = 4^n$$
and then
$$\sum _{n=0}^{\infty } x^n \sum _{i=0}^n \binom{2 n-i}{n} 2^i = \frac{1}{1 - 4 x}.$$


How to find vertices of bounded region made by intersection of lines

Finding the all the vertices for all of the bounding regions is roughly the same amount of work as creating a doubly connected edge list (DCEL) that represents your regions, so I will show how to construct a DCEL from a set of line segments. After that, finding all the boundary points for each region from a DCEL is a simple operation.

First, we find all line segment intersections between the segments we start with. This can be done efficiently with the standard sweepline algorithm for line segment intersection, which is described in various references, such as in these slides. This can be done in $O(n\log n + K)$ time, where $n$ is the number of line segments and $K$ the number of intersections between these lines.

For the next part, we construct a set of endpoints $P$ and a set of line segments $L$, where for each segment $l\in L$, we also store the pair of points $(p,q)$ from $P$ that are the endpoints of segment $l$. First, add all original line segments to $l$ and the corresponding endpoints to $P$.

Then, at every intersection point $p$, split the segments that intersect at that point into two segments 'separated' by $p$, store the point $p$ in the set $P$, remove the old segment from $L$ and add the new segments to $L$, setting their endpoints accordingly.

In the end, we have represented our regions with a graph $G=(P,L)$, where the vertex set $P$ are all points in our 2D space (including the intersection points) and the set of edges $L$ contains all segments connecting these points. Note that the graph $G$ doesn't have any crossing edges by construction, so it is planar.

From this planar graph, we can construct a DCEL, as shown in this answer, which is mostly bookkeeping.

In the DCEL, each region is associated with a representative half-edge. From that half-edge, we can find all half-edges that form the border of the region. Then, the vertices of the region are all vertices of those half-edges.

It is possible to skip the DCEL and find the vertices directly, but likely you need to do almost the same thing. The main advantage of using a DCEL as an intermediate step is that someone else already has made an algorithm to construct a DCEL.


Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

Fixed-size queues are often implemented using what some people call circular buffers. If you remove the protection against it being full, you get the desired behaviour.

Of course, no actual pushing will happen in the array -- that would be too expensive -- but it will look like it from the outside.


Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Here are some hints:

Flesh out your counterexample with quantifiers properly: "There exists a graph $G$, and a minimum spanning tree $T$ for $G$ with edge weights $w_1 \le w_2 \le \dots \le w_{n-1}$, and another spanning tree $T'$ of $G$ with edge weights $w'_1 \le w'_2 \le \dots \le w'_{n-1}$, and an integer $i$ obeying $1 \le i \le n-1$, such that $w'_i < w_i$".  In a situation like this, from the set of all such counterexamples ($(G, T, T', i)$ tuples), you are free to choose one having minimum possible $i$, and it's nearly always useful (and never harmful) to do so.
"I tried adding it to the tree $T$" -- you must first show that it is not already in $T$.  Here you can use minimality of $i$ for edges to the left, and the increasing weight order for edges to the right.
Let's add it to $T$, to make a graph I'll call $G_2$.  What noticeable feature does $G_2$ contain?
What simple modifications could you make to that feature in $G_2$ to turn it back into a tree?  Hint: With this particular feature, there will always be at least 3 ways to do this, and there could be as many as $n$.
Can you choose an option in the previous step that will lead to a tree that is strictly lighter than $T$, and thus a contradiction (since we assumed $T$ to be minimal)?


Can all NP-hard problems be reduced to one another?

The answer to your question is no. Take for example the $SAT$ problem and Halting problem. Both are NP- Hard but second can't be reduced to first.


Your language is not even decidable.
Given a Turing machine $T$, define $M_T$ as a Turing machine that simulates $T$ on an empty input, and then decides any $\mathsf{EXPSPACE}$-complete language $L_C$ of your choice (notice that the function $f(T) = M_T$ is computable).
Notice that the language $L(M_T)$ is $L_C \not\in \mathsf{NP}$ if $T$ halts and $\emptyset$ otherwise.
Suppose now that there exists a Turing machine $M^*$ that decides $L$.
Then, you could design a Turing machine that solves the halting problem. When given input $T$, this Turing machine behaves as follows: it computes $M_T$; it simulates $M^*$ with input $M_T$; it rejects if $M^*$ accepts, otherwise it accepts.
Notice that if $M^*$ accepts then you must have $L(M_T) = \emptyset$, showing that $T$ does not halt.
On the contrary, if $M^*$ rejects, then $L(M_T) \not\in \mathsf{NP}$ implying that $L(MT)=L_C$ and hence $T$ halts.


Minimum edge weight k-exact cover with triangle inequality

Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set form together an $r$-cut and are exactly the edges we do not count in our sum. Hence, instead of minimizing the sum of edges in the subgraphs induced by the sets of the partition, we can maximize the weights of edges having one end in a set of the partition and the other end in a different set.

Note that we are looking here at a special variation of maximum $k$-cut, where we require that all the subsets of the partition have equal sizes and hence the problems are not completely equivalent. However, it is not hard to reduce the maximum $k$-cut problem (let us call it for now maximum $s$-cut to avoid confusion) to your problem, where given an instance of the $s$-cut problem (with $N$ vertices), you can add $(s-1)N$ additional vertices to the graph and connect each of them with all vertices in the graph with edges of weight 0. Set $k = N$ (note that $n = sN$) and hence, we will have $r = s$. Each solution to your problem corresponds to a solution to the maximum cut problem with dummy vertices assigned arbitrarily to make the count consistent.

The maximum cut problem is APX-hard and hence does not admit PTAS (polynomial time approximation scheme) unless P=NP. Using the previous reduction, and since the maximum cut problem is a special case of the maximum $k$-cut problem, your problem is at least as hard as the maximum cut problem.


Every connected graph on more than 3 vertices has two vertices whose removal doesn't disconnect it

Prove that every undirected connected graph with |V | > 2 has at least
  two vertices such that if one or both are removed (along with their
  incident edges) the resulting graph is still connected.

If your graph is connected, then you always have a Spanning Tree, now you can reduce the problem to proving that Every Finite Non-Trivial Tree has at Least 2 Leaf Nodes.

  Describe an efficient algorithm to find two such vertices.

A very obvious way would be just to find 2 leaf nodes of your Spanning Tree.


Yes, they are stored on the same stack.  Yes, that sequence of code could cause problems.  It is up to the compiler (or the assembly language programmer) not to do that.

A compiler will typically ensure that the start of the function pushes some number of words (say $n$ words), and that the end of the function pops off exactly as much as was pushed -- no more, and no less.  As long as you do that, the return address will be left undisturbed and the RET will return back to right after the CALL.  If you don't follow that kind of convention, then all sorts of strange things can happen, exactly as you say -- so make sure you follow the convention.


Complexity of natural language processing problems

Maybe one should first define what is a natural language processing (NLP)
problem.

For example, Context-Free (CF) grammars and languages were introduced
by linguists (Chomsky type 2 language, work of Bar-Hillel and others).
Ambiguity is a major problem in Linguistics for real sentence
analysis, and in the formal study of CF grammars (ambiguity) and
languages (inherent ambiguity). Ambiguity of a grammar is only semi-decidable.

So I guess the problem of ambiguity should be an answer to your
question. Does it classify as a NLP problem?

Now if you take some modern formalizations of syntax, such as a CF
backbone with feature structures (i.e. structured attributes), you
quickly get Turing power (cf LFG which have been proved NP hard, or
even Turing complete, depending on variants). So , if you are not careful, you
have all the complexity problems you might dream about.

For more, you can also look at this question from SE-Linguistics:
"Does the P versus NP conjecture in computer science have any direct
relevance to linguistics?"

In my own answer, I actually criticize the meaningfulness of the
question, or at least of some of its interpretations. Many of the
problems that are considered in linguistics, regarding analysis of
sentences, for translation or other purposes, are small problem, to be
solved in a very short time. Some linguists might even dispute that
there is real recursion in language structure, since whatever
recursion there is is rarely very deep. Hence one might wonder about
the linguistic relevance of complexity analysis which is defined
asymptotically. The first question should be whether we ever get close
enough to the asymptote for asymptotic analysis to be meaningful.

However, this remark does not apply to some aspect of NLP, when
massive amount of data have to be processed. I know of at least two
cases:

data mining in large corpora.
the inverse problem of linguistics: analysis of large corpora to
mechanically extract the data characterizing a language, both
structurally and to produce extensive lists of constituents, such
as phonemes, vocabulary for various parts of speech (aka
preterminals), prefixes and suffixes, or inflection mechanisms, to
give a few examples.

I am no expert in data mining, and thus do not know whether it
actually raises complexity problems related to the size of the corpora
being processed. In that case, asymptotic complexity would indeed be
an issue. But if it is mostly composed of a large number of small
additive tasks, then it is more doubtful that asymptotic complexity
matters much. However, I would imagine that some data mining
techniques will work with correlations between independent documents,
and that should raise corpus dependent complexity issues.

In the case of the inverse problem of linguistics, the identification
of a language (which, I guess, could be considered a data mining
problem), we are indeed trying to extract information by correlating
all parts of large corpora. Then asymptotic complexity becomes
extremely relevant. I have unfortunately no specific problem in mind,
probably because such systems have a pragmatic aim, and people
developing them will tend to simply avoid any form of higher
complexity, quadratic being probably already beyond the available
resources. But a search of the literature would probably raise some
complexity issues.

Another point is that linguistics does not have clearcut laws like
physics. It is more a matter of being close enough to what might be
considered current linguistic consensus, since no two people speak
exactly the same language. Hence, good approximations are usually
sufficient when the aim is so elusive. The techniques I have seen were
mainly fix-point techniques to identify parameters by iterative
recomputation of some function based on the corpus structure, until
it no longer makes much difference (plus user input to weed out
remaining pathological cases).

Analysing properties of grammars and other formalized linguistic
structures may also be a source of high complexity problems, as
mentioned above for ambiguity, since natural language descriptions are usually large enough for asymptotic analysis to be meaningful.


What do "patterns, which separately match parts of a page" and "interactions between patterns" mean?

Simple patterns could mean regular expressions or extended regular expressions, each of which can be used to match parts of a page without considering the impact of other matches.

Interactions between patterns could mean the conditional probabilities among all findings, either the matched patterns or the unmatched patterns. Additionally, they could mean more complicated probabilistic or logical rules.

We could dive a lot deeper and wider into the subject of information extraction. However, the understanding as basic as the above should be suffice for a first-time reading.


Size of the universe for van Emde Boas Trees

This assumption makes the analysis easier. If the universe $\mathcal{U}$ is of size $2^{2^k}$ then every element in $\mathcal{U}$ can be represented by $2^k$ bits. Roughly speaking, when executing one of the vEB-tree operations you halve the "relevant bits" in every level of the recursion. So when you start with $2^k$ bits, then the recursion depth is $k$.

If your universe has a size not of the form $2^{2^k}$, then you have to use floor/ceiling in the analysis.


Does one add the number of operations or the complexity of each operation?

This is a good question! And the answer is, "it depends".

In any model of computation, some type of operation is considered "fundamental", and this operation is considered to run in $O(1)$. For example, some models consider multiplication to be fundamental. But others consider multiplication exponential in the number of bits.

No matter what, though, your algorithm is going to be doing $2^n$ decrement operations on the last element of the list, so it's always going to be $\Omega(2^n)$ (where the omega means "at least", as opposed to omicron's "at most").

  Is the complexity O(2**n) or is it O(1)*(2**(n+1)-2) reducing to constant time: O(1)?

I'm not sure I understand this part of the question. $O(1) \times (2^{n+1}-2)$ is $O(2^n)$, not $O(1)$.

However, your time complexity certainly isn't double-exponential. As you noted, you're doing $2^{n+1}-2$ decrement operations, so if you consider decrement to be constant, the total time is $O(2^{n+1}-2) = O(2^n)$.

Even if you did an additional $O(2^n)$ operation for each decrement, the time complexity would only be $O(2^n) \times O(2^n) = O(2^{2n})$.


If you're asking this question because you want something easier to implement than a Delaunay triangulation algorithm you're most likely out of luck.

You should also specify in what space you're operating. If you're working with $\mathbb N^2$ coordinates, you can possibly do it in $\mathcal O(n \log\log n)$ (with a randomized algorithm to generate the triangulation).

If you have $P\in \mathbb R^2$ your choices (ordered by difficulty of implementation from easiest to not-easiest) are:

Delaunay triangulation
WSPD based approaches (first find clusters on Quadtree of $P$, then build MSTs for each cluster and then connect clusters to get complete MST)
Improved version of Boruvka's algorithm: paper

The last one is also an improvement over the other two in higher dimensions. This answer is more or less a condensed version of the literature review of the linked paper.


My solution requires some kind of hack in the model, a Big-$M$ value, which is pretty common, but also a tolerance $\varepsilon$, which is not very desirable. I hope that I do not miss something easy here but reckon there is no way around it.

To model a condition of the form $(X \wedge Y) \to Z$ for binary $X, Y, Z$, you can use $$\tfrac12(X + Y) \leq Z + \tfrac12.$$
We can verify this by inserting: $X=Y=1$ yields to $1$ on the left hand side, thus, $Z$ has to be at least $\frac12$, and since it is binary, it must be $1$. If either $X$ or $Y$ is $0$ (or both), we have at most $\frac12$ on the left hand side and in this case $Z$ might be either $0$ or $1$.

We also need to transform the constraint $B \leq m$ as a binary variable in order to use the template above. This can be done by introducing a new binary variable $B'$ which must assume the vaue $1$ iff $B \leq m$. We also need a Big-$M$ value which must be greater than any value that $B$ can assume (note that for numerical reasons in practice, $M$ should be not too large). Moreover, we have $\varepsilon$, a small tolerance value to get a strict $>$-inequality (in practice you would choose the difference to the next greater number from $m$ that can be represented exactly on your machine). We now add the constraints $$B \leq m + (1-B')M\tag{1}$$ $$B \geq m + \varepsilon - B'M\tag{2}$$
$(1)$ guarantees that $B' = 0$ if $B > m$, $(2)$ guarantees that $B' = 1$ if $B \leq m$. We verify this again: If $B \leq M$, $(1)$ and $(2)$ can be satisfied with $B' = 1$, but not with $0$. If $B > m$, we need $B' = 0$ to satisfy $(1)$ and then $(2)$ is satisfied since $B$ is at least $\varepsilon$ larger than $m$.

Putting it all together, we obtain your constraint
$$
\tfrac12(A + B') \leq C + \tfrac12,\\
B \leq m + (1-B')M,\\
B \geq m + \varepsilon - B'M.
$$


Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

Some hints for you, so you can solve your own exercise:

If the graph has a negative-weight cycle, what is the proper answer?  Can you detect this situation?
If the minimum-weight cycle has positive weight (strictly greater than zero), how could you find it?  If you knew the distance between every pair of vertices, could you use that to help you find the minimum-weight cycle in this case?  Does that suggest an algorithm that could handle this case?
If the minimum-weight cycle has zero weight, can you detect this fact?  What could you do in this situation?


Find the nearest sum to a given number of two elements in sorted matrix

Try something like binary search since it is sorted
i.e. check a[n/2,n]+a [n/2 +1,1] if equal done
-smaller check the lower half
-greater check the upper half
(Keep the last checked value to compare how close with the next one)
Probably O ( log n2)


What constitutes one operation/cycle/move in the RAM model?

Complexity is usually defined using Turing machine model to avoid the issue of the amount of resources taken during a complicated operation like adding integers.

You can use different notation of complexity of a RAM machine and that depends on what you are trying to do. If you want to be able to compare it with standard complexity classes which are defined using Turing machines then you should assign to each operation an amount of resource usage that a Turing machine would require to simulate that operation. The answer also depends on what kind of operations your RAM machine supports.

The standard RAM model consists of a finite control where a program is stored, one or
more accumulator registers $Acc$, an instruction counter, and an infinite collection of
memory registers $R[0], R[1],\ldots$. The instruction can be divided to four categories:

flow-control: unconditional jump, Accept, Reject, Halt, conditional jumps
(the "conditions" are simple like $Acc = 0?$);
input/output: read, write;
data-transfer between accumulator and memory: load, save;
arithmetic: $Acc := 0$, add $R[i]$ to $Acc$;

Two more common costs are uniform and logarithmic. The two are related quadraticaly for the instruction set above (i.e. to convert the uniform to logarithmic you need to square the running time). Logarithmic means taking cost to be logarithm (i.e. the number of bits) of the inputs to the operation whereas uniform means that all operations are considered to take unit time.


In a NPDA if the stack is empty, where the start/end state are the same can you go again

There are several alternatives for the definition of a PDA, all of which are equivalent, in the sense that computationally they specify the same class of languages. To answer your question, you can perhaps take a look at the precise definition of PDAs you are working with.

For the following, with $X_\varepsilon$ I mean $X\cup\{\varepsilon\}$.

Some definitions use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma\to \mathcal{P}(Q\times\Gamma^*)$$ for the transition function, where $\Gamma$ is the stack alphabet. From this signature, it is evident that you need to have a symbol in the stack in order to move on. Of course, with this definition all PDAs are initialized with some initial symbol in the stack, before they start running. Otherwise, the PDA will never be able to make its first transition.

There are definitions, though, that use the signature $$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma^*)$$
or
$$\delta : Q\times\Sigma_\varepsilon\times\Gamma_\varepsilon\to \mathcal{P}(Q\times\Gamma_\varepsilon)$$
The difference of the two last signatures is in the number of stack symbols they are allowed to push with each transition. But both definitions allow no symbol $(\varepsilon)$ to be popped from the stack. So with these signatures, moves are allowed under empty stacks and the PDA is usually initialized with an empty stack.

From the PDA in the picture, it looks like you are using one of the two latter definitions or something similar, where a PDA is allowed to pop nothing from the stack. So, when you arrive again in $q_0$ with an empty stack (because you removed the last symbol $(\$)$ in it) you are allowed to move to state $q_1$ by reading nothing from the input string, popping nothing from the stack and pushing again the dollar symbol.


Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences

Yes.  This generalizes to any linear recurrence.  Suppose we have the linear recurrence

$$x_{n+1} = a_0 x_n + a_1 x_{n-1} + \dots + a_k x_{n-k}.$$

Define the column vector $v_n = (x_n,x_{n-1},\dots,x_{n-k})^\top$.  Then we have the equation

$$v_{n+1} = M v_n$$

where the matrix $M$ is given by

$$M = \begin{pmatrix}
a_0 &a_1 &a_2 &\dots &a_k\\
1 &0 &0 &\dots &0\\
0 &1 &0 &\dots &0\\
&&&\vdots\\
\end{pmatrix}.$$

It follows that

$$v_n = M^n v_0.$$

Therefore you can compute $v_n$ using $O(\log n)$ matrix multiplications, using a fast exponentiation algorithm for computing $M^n$.  This gives an efficient way to compute $x_n$: first compute $v_n$ using matrix exponentiation, then extract the first coefficient of $v_n$ to get $x_n$.

In fact, we can take this farther.  Suppose $M$ diagonalizes, say $M=PDP^{-1}$ where $D$ is a diagonal matrix.   Then

$$v_n = M^n v_0 = (PDP^{-1})^n v_0 = P D^n P^{-1} v_0,$$

so we don't need to perform matrix exponentiation; it suffices to exponentiate each of the diagonal entries of $D$.  In fact, expanding terms, you can get an algebraic closed-form expression for $x_n$.  If you apply this to the Fibonacci sequence, you get the closed-form expression in https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression (in terms of powers of $(1\pm \sqrt{5})/2$, because those are the elements of $D$); for a general sequence, you get a closed-form expression of the form

$$x_n = c_1 \lambda_1^n + \dots + c_k \lambda_k^n,$$

where $\lambda_1,\dots,\lambda_k$ are the diagonal entries of $D$ (i.e., the eigenvalues of $M$).  This also gives a potentially more efficient algorithm for computing $x_n$: instead of $O(\log n)$ multiplications of $k\times k$ matrices, we get $O(k \log n)$ operations on numbers.

If $M$ does not diagonalize, you may still be able to use the Jordan normal form of $M$.

See also https://en.wikipedia.org/wiki/Recurrence_relation#Solving_homogeneous_linear_recurrence_relations_with_constant_coefficients, which does something similar using the characteristic polynomial of the linear recurrence (which I think coincides with the characteristic polynomial of $M$, or something like that).


Is the language of words that contain a square regular or context-free?

A word is square-free if it contains no non-empty sub word of the form $y^2$. Your language consists of all words over $\{a,b\}$ which are not square-free. It is not difficult to enumerate (using exhaustive search) all square-free words over $\{a,b\}$:
$$
\epsilon, a, b, ab, ba, aba, bab.
$$
Since this list is finite, the language of square-free words over $\{a,b\}$ is trivially regular, and so is its complement.

In contrast, the language of square-free words over $\{a,b,c\}$ is not regular. This follows from the existence of an infinite square-free word $w$, which can be obtained from the Thue–Morse sequence.

Indeed, I claim that the set of prefixes of $w$ is pairwise inequivalent modulo your language. To see this, let $x,y$ be two such prefixes, say $x$ is a prefix of $y$. Then $y = xz$, and so $xz$ is square-free while $yz = xz^2$ isn’t.

Alternatively, we can apply the pumping lemma to the language of all square-free words over $\{a,b,c\}$. If the pumping length is $n$, take the prefix of $w$ of length $n$, and pump it up so that it contains a square. Similarly, since the Thue–Morse sequence is an infinite binary cube-free sequence, the language of cube-free words over $\{a,b\}$ is not regular.

The latter argument shows that the language of square-free words over $\{a,b,c\}$ and the language of cube-free words over $\{a,b\}$ are not context-free. This leaves the following questions open:

  Is the language of non-square-free words over $\{a,b,c\}$ context-free?
  Is the language of non-cube-free words over $\{a,b\}$ context-free?


How can I evaluate an algorithm for a NP-Hard problem?

It doesn't matter for what the algorithm is for, that is, you can analyze an algorithm for an easy problem (e.g. sorting) just like you would analyze an algorithm for a hard problem (e.g. 3-SAT). So the question does make sense.

Think about how your brute force method works. If you try all partitions of nodes, how many possible partitions are there? This is the way your analysis should work. Given that the problem is NP-hard, one should not expect a polynomial time algorithm though, but that's fine.


Should planar Euclidean graphs be planar straight-line graphs?

Fáry's theorem states that every planar graph can be drawn in such a way that its edges are (non-crossing) straight lines. Hence every planar graph is a planar straight-line graph.

However, this doesn't really have any bearing on the definition of Euclidean graph. According to the definition you link too, the edges need not be straight. A Euclidean graph is a planar graph in which the edge weights are their lengths in some specific (planar) embedding. In particular, a non-weighted graph isn't Euclidean any more than a cucumber.

Finally, the first graph in your question is planar – it's just that your specific embedding isn't a planar embedding.


Nobody said that $3/4$ was the optimal number. In fact, it seems like $2/3$ might be achievable. Starting at the root, consider a walk which always chooses the child with the larger subtree. Consider the first time that you reach a node whose subtree contains less than $2/3$ of the nodes. Its parent's subtree contains more than $2/3$ of the nodes, so the subtree rooted at its larger child contains at least $1/3$ of the nodes. So we have found a node whose subtree contains between $1/3$ and $2/3$ of the nodes.

Considering the tree with one root and two children, we see that we can't in general obtain a better balanced partition.


Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls to it to find the length of the Longest Common Subsequence of two sequences $A$ and $B$ ($\text{LCS}(A,B)$)? If so, how few calls can we query the LIS oracle in order to find the length of $\text{LCS(A,B)}$?

Well, we can find $\text{LCS}(A,B)$ without any call to the oracle since we can just run any algorithm that finds $\text{LCS}(A,B)$ such as brutal force or a solution by dynamic programming.

What you intended to ask was how much we can reduce the time-complexity of algorithms that find $\text{LCS}(A,B)$ if the oracle is available. The time-complexity will consist of two parts. One part comes from ordinary operations, and the other part comes from the calls to the oracle. There are two questions here.

Question one. Can we use less ordinary operations (asymptotically) with the availability of the oracle?

Question two.  If we can, how few calls to the oracle are needed to lower the complexity of the ordinary operations?

When one of $A$ and $B$ consists of distinct elements

Suppose the elements in $A$ are distinct. Here is an algorithm that employs the oracle. The idea of the algorithm is that if we regard the natural order of elements in $A$ according to the indices as defining a strictly increasing order, a common subsequence of $A$ and $B$ is exactly an increasing subsequence of $B$.

Keeping $A$ intact, sort $A$ into a new sequence $\alpha$.
Initialize a new sequence $I$.
For $i$ from 0 to size($B$) exclusive, try finding the index $j$ such that $A[j]$ is $B[i]$. If found, append $\alpha[j]$ to $I$.
Return the length that is returned by the oracle given sequence $I$.

There are two ways to implement step 2.

If the elements in $A$ and $B$ can be totally ordered, we can sorted the elements in $A$, keeping track of each element's index in $A$. Then a binary search can find that index $j$.
Construct a hash set whose elements are $(A[i],i)$ for all $i$, where the hash depends only on $A[i]$. Then we can use the hash set to find that index $j$.

So an answer to question one and two is that we can use a single call to the oracle to lower the complexity of the ordinary operations from $O(nm)$ to

$O(n\log n + m \log n)$ when $m\gg\log n$ or
$O(m)$ if the operation of finding an element in a hashset is considered $O(1)$.

Here $n$ is the number of distinct elements in one array and $m$ is the number of the elements in the other array.

When both $A$ and $B$ contain duplicate elements

It is not clear how we can take advantage of the oracle in order to reach a positive answer to question one. Instead, here is a conditional hardness result.

It is not possible to find $LCS(A,B)$ in time $O(n^{2 - \epsilon})$ for any positive constant $\epsilon$ where $n$ is the length of $A$ and $B$, if we can assume the strong exponential time hypothesis. This is shown in Tight Hardness Results for LCS and Other Sequence Similarity Measures by Amir Abboud, Arturs Backurs and Virginia Vassilevska Williams, 2015.


I'll describe what happens, and then describe why each router made the decisions that it made using the scenario from the question.

The starting situation is a steady-state where the routers $A$, $B$, and $C$ have the connectivity $$A\stackrel{1}{\to} B\stackrel{1}{\to} C$$
$B$ is connected to $C$ in one hop, $A$ is connected to $B$ in one hop, and $A$ knows that it is connected to $C$ via $B$ in two hops.

The connection from $B$ to $C$ goes down.
$B$ notices this and updates its distance information from $1$ to $\infty$.
Before $B$ notifies $A$ of the change, $A$ broadcasts an update saying that it has a route to $C$ in $2$ hops.
$B$ updates its routing table to record its belief that it can reach $C$ in $3$ hops via $A$.
$B$ broadcasts an update saying that it has a route to $C$ in $3$ hops.
$A$ updates its routing table to record its belief that it can reach $C$ in $4$ hops via $B$.
Et cetera.

From the comments, your issue is with step $6$. If $A$ already has a route to $C$ in $3$ hops, why wouldn't it just ignore the worse route via $B$ in $4$ hops and stay at $3$ hops? Well, the purpose of a router is to route messages. If I give $A$ a message to send to $C$, it needs to know who to send it to so that it eventually reaches $C$. $A$ knows that it will need to send to the message to $B$ for it to most efficiently reach $C$. In particular, $A$ knows that its distance estimate for a route to $C$ is based on the distance estimate of $B$. So if $B$ says that the distance has increased, $A$ knows that the distance has also increased for it (unless it can find a better route).

Of course, this is exactly what we want. Given the following connectivity diagram, if the connection marked by $(*)$ goes down, we want $A$ to start routing via $D$ ($3$ hops) rather than $B$ ($4$ hops) to send messages to $F$. That $B$ had a $2$ hop path in the past shouldn't matter. If $B$ loses all connectivity to $F$ (e.g. the connection between $B$ and $C$ also goes down), we certainly don't want to keep trying to route through $B$ just because it was the best route in the past.
$$\require{AMScd}
\begin{CD}
A @>>> @>>> B @>>> C \\
@VVV @. @V(*)VV @VVV \\
D @>>> E @>>> F @<<< G
\end{CD}$$

To put it a different way, we're talking about a dynamic version of the Bellman-Ford algorithm where edges can be added or removed in an online manner. Removing edges, in particular, makes the updates no longer monotonic. That is, we can no longer only keep the "best" routes we've ever heard, and we instead have to deal with potential "retractions".

Returning the the original, simpler scenario, the issue is when $B$ receives an update from $A$ that $A$ has a $2$ hop route to $C$, $B$ doesn't know that this information is dependent on $B$'s route to $C$. If $A$ had said that its route to $C$ was via $B$, then $B$ would have realized that this route was no longer useful and would not have updated its routing table in step 4. The split horizon modification solves this particular scenario by simply not having $A$ inform $B$ about any routes that $A$ can only reach (directly) through $B$, so step 3 never occurs as far as $B$ is concerned.


Help interpreting this deadlock question

Here is one bad scenario:

P0 obtains A and B.
P1 obtains D and E.
P2 obtains C and F.

At this point, we have reached deadlock, since P0 is waiting for P2 to release C, P1 is waiting for P0 to release B, and P2 is waiting P1 to release D.


Floating point normalised numbers in binary

I'm assuming you're talking about IEEE754. Unless I'm missing something, your book is wrong.

Every number in IEEE754 is represented as normalized (starting with a 1), unless your number is subnormal. A number is only subnormal if the mantissa is minimal (all zeroes). Since the first bit is the sign bit, $10$ could be the start of a subnormal number.

For example $10000000000000000000000000000001$ is the subnormal number $-2^{-149}$.


Finding one of 2/3 of all array elements in constant expected time

One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:

$$\begin{align}
P(\text{at least }1\; X) &= 1 - P(\text{all are } Y)\\
& = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\[0.5em]
& \geq 1 - 3^{-k}
\end{align}$$
This inequality holds as $n$ approaches $\infty$ for some constant $k$ because:
$$\lim_{n\to\infty} \frac{n/3 - k}{n - k} = \frac{1}{3}$$
Even for some small $k$ like 10, the probability of finding an index $i$ such that $A[i] = X$ is:
$$\begin{align}
P(\text{at least }1\; X) &\geq 1 - 3^{-10}\\
& \geq 0.99998
\end{align}$$


Finding a boolean submatrix isomorphic to a specific fixed set of other boolean matrices

The problem is NP-hard; it is at least as hard as the biclique problem.
If you can solve the problem for a single shaped box, you can solve for all boxes by just iterating over all the boxes.  So your problem reduces to:

Given a matrix $M$ and integers $h', w'$, find a $h'\times w'$ submatrix of $M$ that is all ones, or report that none exists.

This problem is NP-hard.  In particular, if we take any undirected bipartite graph $G$ with adjacency matrix $M$, then $M$ has an all-ones $k \times k$ submatrix if and only if $G$ has a $k$-biclique.  Testing for the presence of a $k$-biclique is NP-hard, so your problem must be, too.


Generating 3SAT circuit for Integer factorization example

First we reduce the task of factorization to finding any factor of $n$ (or showing that it's prime). Once we know how to do this, we divide $n$ by such an factor and repeat the process until all factors are broken down to primes, and this takes $O(\log n)$ steps.

Let $k=\lceil\log_2 n\rceil$ the number of bits in $n$.

Next, we design a binary multiplication circuit that accepts two $k$-bit numbers and produces $2k$-bit results. The size of the circuit is obviously polynomial in $k$.

To the output of the circuit we add a $2k$-bit comparator that returns true if the result is equal to $n$ and false otherwise. We also add comparators to the inputs that check that the inputs are $>1$. So the combined circuit takes two $k$-bit numbers and returns true if they're both $>1$ and their product is equal to $n$.

Such a circuit can be described by a propositional formula, so this way we convert it to SAT.

Finally, we convert it from SAT to 3-SAT by a standard procedure. The result will be a 3-SAT formula with $2k$ propositional variables. If it is satisfiable, the propositional variables will just encode two factors of $n$. If it's unsatisfiable it means that $n$ is prime.


Data points as outcomes of a random experiment

It is well known that

  Random variable is a function from sample space of a random experiment to ℝ.

Well-known, but false. Check out random variable on Wikipedia. We will not need the formal definition. Rather, a random variable is an object whose value is determined randomly. For example, consider a dice whose faces are labeled $a,b,c,d,e,f$. A dice throw is a random variable over $\{a,b,c,d,e,f\}$.

  1) Input to a random variable is an outcome of a random experiment. Then is it true that each data point is an outcome of a random experiment? If yes, then what may be that random experiment and who are running it?

I'm not sure what "input to a random variable is an outcome of a random experiment" means. In your case, here is what happens. You are interested in solving some learning problem, say digit recognition for concreteness. The process providing your samples goes like this:

choose a random person.
choose a random digit.
let the person draw that digit.
return the drawing as well as the digit.

As to who is running this experiment, it is the people who created the dataset.

  2) If dataset is a subset of or itself a sample space, then what is the reason for many statements stating every dataset has an underlying probability distribution? instead of saying that each dataset is a subset of a sample space of a random experiment?

The dataset is a bunch of samples drawn from the random experiment described above. It consists of $N$ pairs of drawings and digits.

  3) Output of a random variable is a real number. But in general parameter can be a vector of real number. How to understand it?

In this case the random variable ranges over pairs (drawing, digit).

There is a slightly different way of looking at the creation of a dataset. We are given a large dataset, which we randomly divide into training and test. The random experiment in this case corresponds to this random partition. But I think that it's more useful to think of both training and test to be coming from the same underlying random experiment, which corresponds to the process we are trying to learn.


The XOR cut-set structure, and combinatorial designs

You can use a linear code with distance $2k$ or so. The parity check matrix of the code has the property that the XOR of any set of at most $2k-1$ columns is non-zero. This means, in particular, that given the XOR of at most $k$ columns, you can determine (not necessarily efficiently) how many columns were XORed (since if you couldn't you would obtain a set of at most $2k-1$ columns which XORs to zero). The cost of this encoding is the number of rows of the parity check matrix. If you choose the parameters correctly and an efficiently decodable code (recall that the parity check matrix of a code is the generator matrix of its dual), then you probably obtain the conclusion stated in the remark.


Proving NP hardness of maximum sum of means of a partition into k sets

Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other.

Given two numbers $a<b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\lvert S_j\rvert$, swap $a$ and $b$.
Given $S_i,S_j$ where $|S_i|\ne 1$ and where all of the numbers in $S_i$ are greater than or equal to all of the numbers in $S_j$, move the smallest number in $S_i$ to $S_j$. (This move does not decrease the average of $S_i$, and does not decrease the average of $S_j$.)

An alternative correctness proof uses a linear relaxation. Let the numbers be $a_1\ge\cdots\ge a_n$ and consider the following linear program.

\begin{align}
&\text{maximize }\sum_{i=1}^na_ix_i\\
&\text{subject to}\\
&\sum_{i=1}^nx_i=k&(w)\\
&\forall i\in\{1,\ldots,n\},\quad-x_i\le\frac{-1}{n-(k-1)}&(y_i)\\
&\forall i\in\{1,\ldots,n\},\quad x_i\le1&(z_i)
\end{align}

Given a partition, for all $i\in\{1,\ldots,n\}$, we can set $x_i=1/\lvert S_j\rvert$, where $a_i\in S_j$. It follows that this program is in fact a relaxation. The proposed partition sets $x_1,\ldots,x_{k-1}=1$ and $x_k,\ldots,x_n=1/(n-(k-1))$.

Here is the dual program. By weak duality, feasible solutions of this program upperbound the objective value of the primal.

\begin{align}
&\text{minimize }kw+\sum_{i=1}^n\left(\frac{-y_i}{n-(k-1)}+z_i\right)\\
&\text{subject to}\\
&\forall i\in\{1,\ldots,n\},\quad w-y_i+z_i=a_i&(x_i)\\
&\forall i\in\{1,\ldots,n\},\quad y_i,z_i\ge0\\
\end{align}

Here is a feasible solution to the dual program whose objective value is equal to the previously proposed primal solution. It follows that both solutions are optimal.

\begin{align}
w&=a_k\\
y_i&=\begin{cases}a_k-a_i&\text{if }i\in\{k,\ldots,n\}\\0&\text{otherwise}\end{cases}\\
z_i&=\begin{cases}a_i-a_k&\text{if }i\in\{1,\:\ldots,\:k-1\}\\0&\text{otherwise}\end{cases}
\end{align}


Bellman Ford for directed graph G finds shortest paths within one iteration

If there's no negative cycle, this is true even without the constraint that all $v\in V(G)\backslash\{s\}$ are one edge distant from vertex $s$.

  Lemma. There exists a shortest path $e(v,1)e(v,2)\ldots$ (where $e(v,1),e(v,2),\ldots \in E(G)$) from $s$ to $v$ for each $v\in V(G)\backslash \{s\}$, such that for each $v_1,v_2\in V(G)\backslash \{s\}$, if there exists $i_1,i_2,j_1,j_2$ such that $e(v_1,i_1)=e(v_2,i_2)$, $e(v_1,j_1)=e(v_2,j_2)$ and $i_1<j_1$, then $i_2<j_2$.

Proof. Suppose there are such shortest paths corresponding to $v_1,\ldots,v_k$. Fix these paths and consider any shortest path $e(v_{k+1},1)e(v_{k+1},2)\ldots$ from $s$ to $v_{k+1}$. Let $i$ be the largest index such that $e(v_{k+1},i)$ appears in those fixed shortest paths corresponding to $v_1,\ldots,v_k$. Say $e(v_{k+1},i)=e(v,j)$ for some $v\in\{v_1,\ldots,v_k\}$ and some index $j$. Now consider the new path from $s$ to $v_{k+1}$: $e(v,1)\ldots e(v, j) e(v_{k+1},i+1)\ldots$ Note $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points (otherwise $e(v,1)e(v,2)\ldots$ is not the shortest path from $s$ to $v$), the new path is no longer than $e(v_{k+1},1)e(v_{k+1},2)\ldots$ Now regarding this new path as the shortest path corresoponding to $v_{k+1}$, we have proved there are shortest paths corresponding to $v_1,\ldots,v_{k+1}$ satisfying the conditions in the lemma. Furthermore, the lemma is proved by mathematical induction. $\blacksquare$

Due to the lemma, there exists a total order of edges that is consistent with the order of edges in each shortest path selected by the lemma. Apply the first iteration of Bellman-Ford algorithm according to this total order and consider a vertex $v\in V(G)\backslash \{s\}$. Recall that $e(v,1)\ldots e(v, j)$ must be a shortest path from $s$ to the vertex to which $e(v,j)$ points, so after dealing with $e(v,1)$, the minimum distance from $s$ to the vertex to which $e(v,1)$ points is computed correctly, and after dealing with $e(v,2)$, the minimum distance from $s$ to the vertex to which $e(v,2)$ points is computed correctly, and so on. Finally we can conclude the minimum distance from $s$ to $v$ is computed correctly. As a conclusion, one iteration corresponding to this total order is sufficient.


Why is the set of all regular expressions classified as context-free, instead of regular?

Going by the OP's comments, the real question here is not the one in the title, but "Why is the set of regular expressions a context-free (rather than regular) language?"

The reason is simply the occurrence of parentheses in more complex regular expressions like $(a+b)^*b(a+c)^*$. In order for such an expression to be well-formed, the parentheses must be balanced properly; this is one of the classical conditions which make a language non-regular (because a r.e. which begins with sufficiently many opening parentheses can always be pumped such that it becomes unbalanced).


It would imply that NP is in non-uniform ACC0. While in some circumstances non-uniformity can be removed, this one doesn't seem to be one of them, though you never know...


Performing semantic segmentation on images on word documents

There are many papers on document structure analysis.  I suggest you read them, rather than trying to reinvent the wheel.  As they say, a week in the lab can save a day in the library.

I think there may be some misconceptions.  The way we evaluate neural networks is by trying them on a representative workload to see how well they perform.  There are effectively no useful methods for performing a "comparative analysis".  When you ask "how should you..", the answer with neural networks is typically "whatever works".  There are no rules.  Often helpful advice is to look for papers that have addressed this problem before and see what they do.

A plausible approach is to just feed in the entire image as input to the network, with no pre-processing (other than the standard pre-processing for images, i.e., to normalize pixels to mean 0 and variance 0).

Labels are more challenging, and that depends on what task exactly that you want to solve.  Presumably, you need to manually label the images and then use those as your labels.

How would you train such a network?  The same way you train any other network: you construct a training set, choose a loss function, and then use an optimizer to minimize the loss on that training set.


As far as I understand your problem statement is as following:

  Given a Problem $A$ that has an answer $true$ if and only if both (some) conditions 1 or 2 are $false$.

We have a decision problem $A(w) = \overline{B(w)} \wedge \overline{C(w)}$, where $B$ and $C$ correspond to the conditions 1 and 2 respectively.

  Whether condition 2 is $true$ can be tested with certainty in polynomial time.

$C \in P$.

  Checking if condition 1 is $true$ on $A$ is an NPComplete problem (if we consider all possible instances of $A$).

$B \in NP$ and $B$ is $NP$-hard.

(Please, correct me if I misunderstood the problem statement)

So, let's rewrite the statement using the language notation: $L_B \in NP$, $L_C \in P$, and $L_A = \overline{L}_B \cap \overline{L}_C$.

By definition $L_A \in coNP$ if $\overline{L}_A \in NP$. But $\overline{L}_A = L_B \cup L_C$ (De Morgan law). Since we are given that $L_B \in NP$ and $L_C \in P$, $L_B \cup L_C$ is in $NP$ as well. So, $L_A$ is in $coNP$.

Now, take $\overline{L_C} = \emptyset$ which is clearly is in $P$, and so is $L_C = \Sigma^*$. For any $NP$-complete language $L_B$, $L_B \cup L_C = \Sigma^*$. But $\Sigma^*$ is not $coNP$-complete.