Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially

The correctness proof of the Bellman–Ford algorithm relies on the following lemma (compare Wikipedia):

  After $i$ iterations, $d[v]$ is at most the distance of the shortest path of length $i$ from the source vertex to $v$.

Indeed, if we perform all updates at a specific iteration in parallel, then $d[v]$ equals the distance of the shortest path of length $i$. When we perform the updates sequentially we might get lucky, and this depends on the order of vertices in the path.

This shows that in general you cannot stop Bellman–Ford early in the way you envision.


Confused about proof that $\log(n!) = \Theta(n \log n)$

Consider the sum $S = \log(1) + \dots + \log(n)$.  We're going to break it into two parts: $S=T+U$, where

\begin{align*}
T &= \log(1) + \log(2) + \dots + \log(n/2)\\
U &= \log(n/2+1) + \dots + \log(n-1) + \log(n).
\end{align*}

Basically, $T$ has the first $n/2$ terms of $S$, and $U$ has the remaining $n/2$ terms.

Now we'll lower-bound each of them.  Start with $T$.  Each term in $T$ is at least $\log(1)$, so we get

$$T \ge \log(1) + \log(1) + \dots + \log(1) = 0 + 0 + \dots 0,$$

so $T \ge 0$.  Next look at $U$.  Each term in $U$ is at least $\log(n/2)$, so we get

$$U \ge \log(n/2) + \log(n/2) + \dots + \log(n/2) = (n/2) \times \log(n/2).$$

Now $S = T+U$, so plugging in the lower bounds obtained above, it follows that

$$S =T+U\ge 0 + (n/2) \times \log(n/2).$$

This is exactly the result you wanted to prove.  Also, $(n/2) \times \log(n/2)$ is $\Omega(n \log n)$, so this proves that the sum $S$ is $\Omega(n \log n)$.


What to do with empty set during NFA to DFA conversion?

Creating a new sink state is perfectly fine. The empty set is also a subset of all states.

In most DFA diagrams this state is omitted for simplicity.


You're trying to compute something called the arrangement of the line segments.  The arrangement is a planar straight-line graph whose vertices are either endpoints or intersection points of line segments.  The vertices partition the lines segments into smaller segments, which are the edges of the arrangement.  Finally, the vertices and edges partition the plane into several components; these are the faces of the arrangement.

Suppose you are given $n$ line segments, and $k$ pairs of those line segments intersect.  (You don't know $k$ in advance.)  The intersection points can be computed in $O((n+k)\log n)$ time using the Bentley-Ottmann sweep-line algorithm.  (The running time can be reduced to $O(n\log n + I)$ using a more complicated algorithm, where $I\le k$ is the number of intersection points, but the additional effort is probably not worth it.)  The algorithm can be modified to report, for each intersection point, which segments intersect at that point.  Then it is simply a matter of careful bookkeeping to construct a standard data structure that represents the arrangement.

A few caveats to keep in mind:

The faces of the arrangement are not necessarily simple polygons.  If the union of the line segments is connected, each bounded face is a weakly simple polygon, but a single edge can be incident to the face no both sides.  If the union of the segments is disconnected, then faces can have holes, which are either trees or weakly simple polygons.
Most textbook (and Wikipedia) descriptions of the Bentley-Ottmann algorithm assume that the input segments are in general position.  In this context, "general position" means that at most two segments intersect at any point; no segment endpoint lies on another segment (in particular, the intersection of two segments is either empty or a single point); and no two endpoints have the same $x$-coordinate.  In practice, however, this assumption does not hold.  As usual in computational geometry, handling degenerate cases correctly and robustly is the most difficult part of implementing the algorithm.  (What does your implementation do when the input contains 42 copies of the segment [(0,0),(1,1)], 17 copies of the segment [(0,0),(2,2)], and 9 copies of the zero-length segment [(1,1),(1,1)]?)
For small numbers of segments (at most a few dozen), it's probably faster to use a brute-force $O(n^2)$-time algorithm to compute the intersection points.


Instead of a general "formula", you should try to work out from principles first, at least in the beginning. You can see that the number of executions are:

$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1$$

We try solving them one step at a time. The innermost (right-most) summation can be solved as:

$$\sum\limits_{k=j}^{i} 1 = i - j + 1$$ (how many times will the loop execute from $j$ to $i$, inclusive).

Going on to the next level, by substituting the above result, we get:
$$\sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1 = \sum\limits_{j=1}^{i} (i - j + 1) = i\sum\limits_{j=1}^{i} 1 -\sum\limits_{j=1}^{i}j + \sum\limits_{j=1}^{i}1$$
$$ = i^2 - \frac{i(i+1)}{2} + i = \frac{i(i+1)}{2}$$

Notice that when summation is over the variable $j$, $i$ behaves like a constant, and so could be taken out of the summation.

The above expression gives the number of times the inner two loops are executed for every value $i$ that the outer loop takes. Solving the outermost summation with this expression ($i$ runs from $1$ to $n$), we have:

$$\sum\limits_{i=1}^{n}\frac{i(i+1)}{2} = \frac{1}{2}\sum\limits_{i=1}^{n}i^2 + \frac{1}{2}\sum\limits_{i=1}^{n}i$$
$$ = \frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6} + \frac{1}{2}\cdot\frac{n(n+1)}{2}$$
$$ = \frac{n(n+1)(n+2)}{6}$$

This will also be the value of the variable s in your pseudocode. I suggest that you should approach these kind of questions from the basics, and revise the summation rules. There are no general formulas or multiplication factors for some arbitrary nesting of loops. You might even want to go along these lines to again derive your result for the first two loops only.


Understanding hashtable performance in the worst-case

The load factor denotes the average expected length of a chain, therefore it is interesting for an average case analysis, not the worst case analysis. That's why on average you expect needing constant time for search operations.

In the worst case however, all your elements hash to the same location and are part of one long chain of size n. Then, it depends on the data structure used to implement the chaining. If you choose a sorted array, you can do binary search and the worst case complexity for search is O(log n). If you choose an unsorted list, you have a worst case of O(n) for search. Depending on your choice of data structure, the performance (worst and average case) of insert, delete and search changes.

According to Coding-Geek.com, Java 7's HashMap implementation uses a linked list (unsorted), but Java 8 uses a balanced binary tree instead. Of course, insert/delete/search in a balanced tree of size n has complexity O(log n).


It is decidable whether a pushdown automaton will accept a word?

Pushdown automata are nondeterministic, and there is no a priori bound on the length of computation (imagine $\epsilon$-transitions that add and remove the same element from the stack). Therefore it's not clear how to perform your simulation.

Fortunately, we know how to convert a pushdown automaton to an equivalent context-free grammar, and the latter have parsing algorithms such as CYK. Using these algorithms, we can dedice whether a given pushdown automaton accepts a word by first converting the automaton into a context-free grammar.


Data structure with Median, Min, Max, Delete in $O(1)$ amortized-time

It should be possible with everything O (1) amortized if the insertions and deletions are random: If there are n items, try to keep track of the sqrt (n) smallest items, largest items, and items around the median.

If you insert or remove an item within the smallest, largest or median items, that's $O(n^{1/2})$ because you need to insert or remove one of $n^{1/2}$ elements, and happens with probability $O(1/n^{1/2})$, so total O (1).

Whenever you insert or remove one of the elements before the median elements, the range of the "median" elements shifts. When the items that were supposed to be around the median don't contain the median element anymore, you need to find elements around the median again, which should happen in O (n). If insertion / deletions are random, then I think the balance shifts by $n^{1/2}$ only after a large number of insertions / deletions. You'll have to check the maths.

And of course all this only works if insertions / deletions are random. Otherwise you need something significantly more clever.

PS. D.W.'s comment indicates (unless I'm very wrong) that if you can find the median and insert items in O (f(n)) amortized in the worst case, then you can sort an array in O (n·f(n)), which means f(n) cannot be better than log n asymptotically in the worst case.


Language of a Turing Machine that runs its input on two other Turing Machines

You're right: it might happen that $M_1$ might run forever on input $x$, so you'd never get to the "run $M_2$ on $x$" part. This problem goes away if $M_1$ and $M_2$ were deciders, i.e., if they are guaranteed to halt on any input in either an accept state or a reject state. In that case we would have $L(M)=L(M_1)\cup L(M_2)$ and would have proven that decidable (aka recursive) languages are closed under union.

All is not lost, though, to show that this holds for more general languages. Suppose that we know that we have languages $L_1,L_2$ such that there are TMs $M_1, M_2$ with $L_1=L(M_1)$ and $L_2=L(M_2)$. Then we can make a TM $M$ such that $L(M) = L_1\cup L_2$ by a very useful technique known as dovetailing, like this

M(x) =
   repeat
      run M_1(x) for one move (beyond any that have been made already)
      if M_1 accepts
         return accept
      run M_2(x) for one move (ditto)
      if M_2 accepts
         return accept
   // end repeat

If either $M_1$ or $M_2$ accepts $x$ then it will do so in some finite number of moves, and that's all we need for $M$ to accept $x$. So for this machine, we'll have $L(M)=L(M_1)\cup L(M_2)$, exactly as needed.


Find non-smooth function that meets conditions

As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that

$T(n)$ is non-decreasing.
$T(2^k) = 2^{2^k}$.
$T(n)$ is not $O(2^n)$.

To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.

  (a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.

  (b) Show that it satisfies the third condition as well.

  (c) For which functions $f(n)$ does this construction work?


minimum vertex set removal for edge-free graph

The problem you describe is called minimum vertex cover. It is a well-known NP-complete problem, so there is no known algorithm that will always be fast (as in polynomial runtime) and give the optimal solution. However, fast approximation solutions are known, as well as algorithms that, while slow in the worst case on general graphs, are fast on significant classes of graphs. See the linked Wikipedia article for details and links to even more details.


Adder circuit with sign bit (not twos complement)

This is called "sign-magnitide" or "signed-magnitude" representation. A Google search for "sign-magnitude adder" gives lots of useful results. I know this doesn't answer your question directly (I don't have enough reputation to simply comment your post), but you will find the answer there.

As for only having AND and XOR, this is the classic result that any logic gate can be constructed from AND and NOT. Note that XOR(1,a) = NOT(a). Now you have NAND and NXOR. NOR(a,b) = AND(NOT(a),NOT(b)). Now you have OR by negating NOR. All other gates can be constructed by negating inputs of these gates.


Distinction between statements, declarations, and expressions in formal grammar

These are informal terms. For example, in the C language:

Statements are things like x = 3;.
Declarations are things like int x;.
Expressions are things like x * y.

So declarations are a particular type of statements, and expressions appear in statements.

A better formulation of the statement you quoted would be:

  Nonterminal symbols represent syntactic entities such as statements, declarations, or expressions.


The easiest way to prove some problem is in $\mathsf{NP}$ is using the certificate definiiton of $\mathsf{NP}$ mentioned in other answers. The nondeterministic definition of $\mathsf{NP}$ is usually not very useful for showing a problem belongs to $\mathsf{NP}$. Intuitively, a problem is in $\mathsf{NP}$ iff we have an efficient (polynomial time) verification algorithm with polynomial size certificates/proofs.

For example, if you want to check if a given number $m$ is composite,
the following works:

Format of certificates: certificates are a pair numbers $(a, b)$,
Verification algorithm: a certificate $(a,b)$ is accepted iff $1<a,b<m$ and $ab=m$.

If a number is composite then there is a pair of number $(a,b)$ which satisfies the condition and has size $O(\lg m)$. It is important that the certificate has polynomial size in the size of input (here the size of input is $\lg m$).

If a number is not composite there are no such pairs.

Note that we fix a particular certificate verifier for all inputs. You cannot change the verification algorithm from one input to another one.

A more challenging question is to show that primeness is also in $\mathsf{NP}$, i.e. there are polynomial size primality certificates.


What are some uses of the Thue-Morse sequence in computer science?

I don't know if this counts as an application but at least it shows up. When using a polynomial rolling hash, it's tempting to do it modulo $2^{32}$ or $2^{64}$ (depending on the word size of the computer) since on most modern architectures addition and multiplication of integers just handle overflows this way, saving time. This method will fail often on Thue-Morse-like strings (like ABBABAAB...), as explained here. I remember not understanding the factorization of $T$ a few years ago, the key is the recurrence relation $t_{2n} = t_n$, $t_{2n+1} = 1-t_n$

Alternative explanation of the factorization: from the "append the negated sequence" definition one can directly see $\Pi_n (1-x^{2^n})$ , since each each term does exactly that.


The difference between a sequence and a set

Your question uses a number of words, such as "logic" that might require clarification. In order to answer I should start with some preliminary definitions.

Consider a universe of objects. The objects have different properties. We do not know yet if each object can be identified. We say that all objects that share a certain property form a set (this statement is related to the notion of specification in Set Theory).

For instance in order to have a set of all sand particles you do not need to be able to identify each particle of sand. You just need to be able to distinguish them from objects that are not sand particles.

So a set is either an empty set or a set of all objects in our universe that share some common property. Two sets $A$ and $B$ are considered equal if an element $x$ belongs to $A$ if and only if $x$ belongs to $B$. (this statement is known as extensionality). It follows that removal of duplicates does not change a set.

In order to define a sequence we need to introduce natural numbers into our universe. Now a sequence is a mapping from the set of natural numbers into a set of objects. That is each number is associated with a unique object.
(You need to be able to identify individual objects in order to define a sequence).

A sequence can also be considered as a set where each element has a special form. For example a sequence A, B, C, B, ... can be represented as a set

   { {1,{A}}, {2,{B}}, {3,{C}}, {4,{B}}, ... }

Example

Now here is an example where a sequence can be used as opposed to a set. Suppose our universe consists of colored grains of sand. Assume each grain is either green or red. Then we could have only four different sets in our universe:

  {}, {G}, {R}, {G, R}

and many higher order sets, such as

  {{G}}, {G,{R}}, ... etc.

However we could form many infinite sequences without using higher-order sets:

  R, G, G, R, G, R, R, G, ....

Programming

In programming languages some basic data structures, such as arrays or lists are sequences, that is you can refer to an element by its sequence number. Using such structures to model sets requires additional processing: identifying duplicates and keeping them in a sorted state.

A natural data structure to model sets is a hash table. This model handles duplicates efficiently, however computing a hash table that represents a union of two hash tables may have complexity proportional to the size of the hash tables.

Hope this clarifies the difference between sequences and sets.


Why is this pushdown automaton for some palindromes right?

PDAs are nondeterministic. Although you have found a valid computation which does not lead to an accept state, a PDA is said to accept its input if there is some valid computation which does lead to an accept state.

In this case (input $111$), an accepting computation is:

$q_1 \to q_2$, stack: $[\$]$
$q_2 \to q_2$, stack: $[\$, 1]$
$q_2 \to q_3$, stack: $[\$, 1]$
$q_3 \to q_3$, stack: $[\$]$
$q_3 \to q_4$, stack: $[]$


One approach is to apply Procrustes analysis to superimpose the shapes, then use the sum of the squares distances between each pair of corresponding points (i.e., a L2 norm).  This is apparently sometimes called Procrustes distance.  Here you will use the set of "corners" of the shape as your set of points.

One disadvantage of this approach is that it is not robust in case one or a few points are deleted: maybe shape $S_2$ is the same as shape $S_1$ except that it is missing a single point.  If you want to be robust to this kind of situation, you could combine RANSAC with Procrustes distance.  Pick a random sample of 3 consecutive points from $S_1$, and 3 consecutive points from $S_2$; use Procrustes analysis to find the best map $M$ to superimpose those points; apply $M$ to $S_1$ to get $M(S_1)$, and use some kind of edit distance to measure the similarity between the vector of points of $M(S_1)$ and vector of points of $S_2$ (you might assign a large cost $c_\text{del}$ to deleting a point, a large cost $c_\text{ins}$ to inserting a point, and make the cost of matching a point $p$ to a point $q$ be the squared distance $||p-q||^2$ between the two points, then apply standard dynamic programming algorithms to compute the edit distance).  Now repeatedly apply this sampling procedure.  Keep the best map $M$ you find, where you can determine what you consider best (e.g., the lowest edit distance; or some other metric).

There are probably many other possible distances.  For instance, instead of the sum of squared distances, another possibility is to compute $\theta_i$ (the angle between $p_i,p_{i+1},p_{i+2}$ from the first shape) and $\theta'_i$ (the angle between $q_i,q_{i+1},q_{i+2}$ from the second shape), then some norm on these angles: e.g., $\sum_i (\theta_i - \theta'_i)^2$.  This too could be made robust to a few mismatched points using RANSAC.  There isn't enough information in the question to select between these, so without more knowledge, the best I can suggest is to simply try these on a set of examples and see which one seems to give results that most closely match what you are looking for.

None of this will work if your shapes $S_1$ and $S_2$ look "similar" but they have a very different number of points.  For instance, you mention the case where $S_1$ is a perfect square (with crisp edges where the angle between all 4 pairs of 3 points is exactly 90 degrees) made out of 20 points total and $S_2$ is a user-drawn square consisting of 300 points without crisp corners and no 3 consecutive points which align at 90 degree angle.  The methods above will not work at all for that kind of situation.

Incidentally, you mention the issue of shapes that can be drawn in one vs those that cannot.  I think your representation of a shape as a vector of points implicitly assumes that the shape can be drawn in one stroke (since the points appear in the vector in the order that they're visited by the stroke, and each point is assumed to be connected to the one after it), so if you want to deal with shapes that cannot be drawn in a single stroke, you'll probably need to find a different representation of the shape.


Finding a solution to the following conditions?

There are infinitely many sequences starting $4,6,10,16,24$. If I understand you correctly, this sequence was generating according to the rule $a_n = a_{n-1} + 2n$ with the initial value $a_0 = 4$. In that case, you have
$$
a_n = a_0 + \sum_{k=1}^n (2k) = a_0 + 2 \frac{n(n+1)}{2} = n^2 + n + 4.
$$


Minimum amount of swaps needed to sort a stack

Your problem is known as Pancake sorting and it is not true that $f(n) < n$. The minimum number of swaps is between $\frac{15n}{14}$ and $\frac{18n}{11}$.

Currently we know empirically that $P_{17} = 19$, which is the Pancake number, giving lower bound of 19 flips in the stack of 17 elements.

The sequence is known as AA058986.


Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)

One way to solve this exercise is to notice that there are at least $k$ numbers of the form $a + b \sqrt{2}$ smaller than $\lfloor \sqrt{k} \rfloor + \lfloor \sqrt{k} \rfloor \sqrt{2}$ (namely, those with $0 \leq a,b \leq \sqrt{k}$). Conversely, every such number of the form $a + b \sqrt{2}$ must have $a,b \leq (1 + \sqrt{2})\sqrt{k}$. Therefore we could simply take all $O(k)$ values of the form $a+b\sqrt{2}$ with $a,b \leq (1+\sqrt{2})\sqrt{k}$, find the $k$th smallest in time $O(k)$, and then go over the list in $O(k)$ and output the $k$ smallest elements. The entire algorithm runs in time $O(k)$ (ignoring the cost of arithmetic operations).

This algorithm needs to compare two numbers of the form $a + b\sqrt{2}$. This can be done as follows. Suppose we want to determine whether $a + b \sqrt{2} \leq c + d \sqrt{2}$. If $a = c$ then this happens iff $b \leq d$, and similarly if $b = d$ then this happens iff $a \leq c$. Suppose, without loss of generality, that $d > b$. If also $c > a$ then $a + b \sqrt{2} < c + d \sqrt{2}$, so suppose that $a > c$. Then
$$
a + b \sqrt{2} \leq c + d \sqrt{2} \Leftrightarrow
a-c \leq (d-b) \sqrt{2} \Leftrightarrow
\frac{a-c}{d-b} \leq \sqrt{2} \Leftrightarrow \\
\left(\frac{a-c}{d-b}\right)^2 \leq 2 \Leftrightarrow
(a-c)^2 \leq 2(d-b)^2.
$$

What would happen to this approach if we replaced $\sqrt{2}$ by, say, 2? Then there are only $O(\sqrt{k})$ numbers smaller than $\lfloor \sqrt{k} \rfloor + 2\lfloor \sqrt{k} \rfloor$, since not all combinations of the form $a + 2b$ for $0 \leq a,b \leq \sqrt{k}$ are distinct. Indeed, we need to take the upper bound on $a,b$ to be linear in $k$ in order to find the $k$ smallest values of the form $a + 2b$. So the irrationality of $\sqrt{2}$ does make a big difference for the algorithm.


This is algorithm called bucket sort, integer sort, counting sort, or Pigeonhole sort (naming is a bit inconsistent across sources and/or different names refer to slight variations of the same idea).

Its time complexity is $O(m)$ (assuming distinct values) where $m$ is the largest among the $n$ integers you are trying to sort. Your algorithm takes $O(n)$ time as long as $m=O(n)$, for example if you know you that you want to sort a large-enough subset of the integers from $1$ to $n$.

If the integers are not distinct, you can replace booleans with counters to obtain an algorithm with complexity $O(m + n)$. In general, you can sort arbitrary items with integer keys by keeping an array of lists, where the $i$-th list will contain all items with key $i$. The output is just concatenation of these lists (and hence this sorting algorithm is stable as long as you append new elements at the end of the lists).

If you apply the above (stable) algorithm multiple times on your input, where the $j$-th execution sorts the integers w.r.t. the $j$-th least significant digit you obtain Radix Sort.

For example, in base $10$, you'd need $\lceil \log_{10} m \rceil$ iterations, thus obtaining an algorithm with time complexity $O( n \log m )$, which is in $O(n \log n)$ even when $m$ is exponentially larger in $n$ (on a unit-cost RAM machine). For a general base $b$, the time needed would be $O((b+n) \log_b m) = O((b+n) \frac{\log m}{\log b})$, which is optimized (in an asymptotic sense) by choosing $b = \Theta(n)$, resulting in a time complexity of $O(n \frac{\log m}{\log n})$.


How to categorize an undirected triangular graph with top, bottom, and intertwining paths

Your algorithm relies on some properties of the input graph for its correctness. You should isolate these properties, and then you will know how to name your program.

The most likely answer is that your algorithms works on DAGs oriented source-to-sink, as you and David mention. However, there are many possible variants:

Your algorithm might rely on the DAG having a single source.
Your algorithm might rely on the outdegree being at most 2 or perhaps exactly 0 or 2.
Your algorithm might work on every (possibly connected) graph, implicitly considering say the BFS tree (or forest) of the graph, from a given starting node.

Only you can tell which of these is correct for your algorithm.


Is there any proof that quantum computers are more efficient than classical computers?

Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.


Why is dominating set in $W[2]$, but independent set in $W[1]$

For deciding the independent or dominating set problem, it is not sufficient to guess the set. One must also verify that the guessed set indeed is an independent or a dominating set.

In the case of independent set, once the machine has guessed the set and stored it in the first $k$ cells of the tape, it checks for all pairs of guessed vertices whether they are indeed not equal and do not form an edge. There are $k\choose 2$ such pairs, so the overall running time is $O(k^2)$. Thus the reduction from independend set to short NTM acceptance is a parameterized reduction. The number of steps in the verification phase only depends on the parameter.

In the case of dominating set, one needs to checks whether all vertices are dominated. While above, we only had $k\choose 2$ pairs, now we have to deal with $n$ vertices. Which does not only depend on the parameter. (The way the multitape NTM solves this is by spending one tape per vertex.)

Of course, the above is only intended to give some intuition about why dominating set is not in W[1]. It does not give a proof. That would be way out of scope...

(For the sake of the casual reader, let me clarify that the NTMs above are not machines that solve the independent or dominating set problem. There is a reduction involved that converts instances of these problems into machines. Thus, a single such machine solves only a single instance of the problem, not the general problem.)


This is a large topic, often called "geometric shape matching." Here is one survey that can lead to many specific algorithms:

  H. Alt and L. J. Guibas. Discrete geometric shapes: Matching, interpolation, and approximation. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 121–153. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. doi:10.1016/B978-044482537-7/50004-8

If you have difficulty accessing that chapter, an earlier draft of the survey
is here: PDF download.


What is the purpose of ϵ-transitions in PDA?

Yes, you could substitute the red transition for the black one below and have an equivalent PDA. With the black one, you allow the possibility that when reading $\mathtt{b}$s, you make a nondeterministic switch to the state where you expect to see a $\mathtt{c}$. If you do, it's as if you followed the red transition. In other words, either PDA will accept a string in $A$.

By the way, you could do a similar thing between the first and the second states of the upper branch.

The moral is that here are many roads to the top of the mountain, grasshopper.


Understanding Wirth's symbol table entry

Pretty much, yes. The list of variable names form a linked list, and the fields within a record are basically a nested symbol table.


How do I build a left derivation tree from an expression including right-to-left associativity?

In a leftmost derivation, you always expand the leftmost non-terminal, by definition. The question is, what do you expand it to, since you usually have more than one choice.


If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

It's important to first understand how $\delta(S_l)$ changes. When $l = 0$, $S_l$ contains all vertices, and when $l = 1$, $S_l$ contains no vertices. In either case, there is no edge going between $S_l$ and $\overline{S_l}$, so $\delta(S_l) = 0$.

For values of $l$ between $0$ and $1$, $\delta(S_l)$ contains exactly the edges with one endpoint in $S_l$ and one endpoint in $\overline{S_l}$. In particular, if we define

$$f_{ij}(l) =\left\{
 \begin{array}{ll}
  1  & \mbox{if } l \mbox{ is between } x_i \mbox{ and } x_j \\
  0 & \mbox{otherwise.}
 \end{array}
\right.$$

then we have $$|\delta(S_l)| = \sum_{(i, j) \in \delta(S_l)} 1 = \sum_{\substack{(i,j) \in E \\ i \in S_l \\ j \not\in S_l}} 1 = \sum_{(i, j) \in E} f_{ij}(l).$$

Now let's consider one particular edge, from $u$ to $v$. Because $f_{uv}(\cdot)$ is just $0$ everywhere except for on one interval where it takes on the value $1$, the value of $\int_0^1 f_{uv}(l)\,\mathrm{d}l$ is just the length of the interval on which $f_{uv}(l) = 1$, that is, $|x_u - x_v|$. So

$$\sum_{(u, v) \in E} |x_u - x_v| = \sum_{(u, v) \in E} \int_0^1 f_{uv}(l)\,\mathrm{d}l = \int_0^1 \sum_{(u, v) \in E} f_{uv}(l)\,\mathrm{d}l = \int_0^1 |\delta(S_l)|\,\mathrm{d}l.$$


Until quantifier of Computation Tree Logic

$pUq$, as is, is not a well-formulated CTL (or more generally - CTL*) formula. A CTL* formula is a state formula, which starts with has a path quantifier ($A$ or $E$).

$pUq$ is a path formula, which means it refers to a single (linear) computation. A computation satisfies $pUq$ if $p$ holds in every state until $q$ holds (and $q$ must hold at some state).

Translating to CTL, you can talk about two different formulas: $ApUq$ and $EpUq$. The former is true in a state if every path starting from this state satisfies $pUq$. The latter is true in a state if there exists such a path starting from that state.

Does that clear things up?


What is the time complexity of the original Otsu's method?

The algorithm can certainly be implemented in $O(LN)$ time, as  you say.
It is not hard to optimize it to run in $O(N+L^2)$ time.  Simply form a histogram of pixel intensities (count of the number of pixels of each intensity).  Then you can compute each variance in $O(L)$ time, rather than $O(N)$ time.
You can improve it further to run in $O(N+L)$ time.  Suppose we have computed the sum of values below the threshold and sum of squared values below the threshold; and the same for those above the threshold.  That is enough to compute the standard deviations.  Then, when we bump up the threshold by one, it is possible to update those four sums in $O(1)$ time.  As a result, it takes $O(N)$ time to build the histogram, then $O(L)$ time to compute the score for the first threshold, then $O(1)$ time for each subsequent threshold, and there are $L$ candidate thresholds, for a total of $O(N+L)$ time.
In practice the difference between $O(N+L^2)$ vs $O(N+L)$ might be unimportant, as for 8-bit images, $L \le 256$.


Extension of Tarski's result on the decidability of reals

I doubt there's a proof you can cite, since the result is obvious. The "features" you're adding are first-order definable, and first-order logic is closed under substitution.


Sorry, I found out the answer myself. It is 1000 000 manitssa and 0000 exponent.
for mantissa, 1.000 0000 = -128 *power(2,-7).

for exponent, 0000 = 0.
So, result= -128 * power(2,-7)


Linear/affine lifetimes without subtyping

Linear and affine typing systems have been developed in the context of linear logic and process calculi. Most developments of such types do not use subtyping. The system in (1) is pioneering for its use of linearity, as are (2, 3) which introduced session types which are heavily based on linearity. See also the CSTheory Stackexchange thread Determinism and pi-calculus for some other (related) typing systems that make heavy use of linearity and affinity. While all this work is for process calculi, note that sequential behaviour is a well-behaved special case of concurrency and affinity in Rust is closely related (the same) as affinity in process theory.

 N. Kobayashi, B. C. Pierce, D. N. Turner, Linearity and the Pi-Calculus.

 K. Takeuchi, K. Honda, M. Kubo, An Interaction-based Language and its Typing System.

 K. Honda, V. T. Vasconcelos, M. Kubo, Language Primitives and Type Disciplines for Structured Communication-based Programming.


Counting the number of satisfied models - given mathematical constraints

I know of two reasonable approaches.

Approach #1: Count the number of integer points inside a convex polytope.

The set of linear inequalities you provided, together with the inequalities $0 \le a,b,c,d \le 1$, defines a convex polytope.  Now, you want to count the number of integer points that fall within this polytope.

There are standard algorithms for doing that, which you could apply directly.  If you search on "counting integer points in polytope" or "counting lattice points in polytope" you'll find many research papers.  See, e.g., https://cstheory.stackexchange.com/q/22280/5038, Finding all solutions to an integer linear programming (ILP) problem.

Approach #2: Convert to CNF, then use a #SAT solver.

You can always convert your constraints to a CNF formula.  Each linear inequality can be converted to a set of CNF clauses.  A linear inequality of the form $x_i + \dots + x_j \ge 1$ corresponds immediately to the CNF clause $(x_i \lor \dots \lor x_j)$.  For a more general linear inequality of the form $x_i + \dots + x_j \ge c$, you want to express the constraint that at least $c$ out of the $k$ variables $x_i,\dots,x_j$ are true.  There are many standard ways of encoding that.  See https://cstheory.stackexchange.com/q/23771/5038, Reduce the following problem to SAT, Encoding 1-out-of-n constraint for SAT solvers,

(One approach is to convert a Boolean circuit that computes $x_i + \dots + x_j$ and compares it to $c$, then convert the Boolean circuit to CNF using the Tseitin transform.  You can create such a Boolean circuit by using standard adder and comparator circuits.  However, there are many other ways as well.)

Once you have a CNF formula that is equivalent to the set of constraints, then you can use any off-the-shelf #SAT solver to count the number of solutions to that CNF formula.

It's hard to say which of these two approaches will work better;  you might need to try them both on the kinds of instances you're dealing with, to know for sure.  I'd expect that if you have linear inequalities of the form $x_i + \dots + x_j \ge c$ where $c$ is large, then Approach #1 may be superior; but if $c$ is typically small, then Approach #2 may be superior.


How many ways to express N as sum of 2, 3 and 5?

It looks like you're missing some considerations with respect to the base cases. Since you're starting your for loop at i = 5, you should have base cases set for i = 0, 1, 2, 3, 4. f[0] = 1 since there's 1 way to choose a set of numbers that sums to 0 — choose nothing. f[1] = 0 since there's no way to make 1 out of 2, 3, and 5. f[2] and f[3] are both equal to 1 because they are in your set. Finally, f[4] = 1, since 2+2 = 4. This gives output f[7] = 5, as shown in your example cases.

For the "harder version", I suggest you look up the coin change problem. The problem formulation is essentially the same — how many ways are there to make up a given sum using a set of coins? The basic idea, and the one that prevents doubly counting permutations of the same solution, is that for each coin or value, you consider whether or not you wish to include it in the current solution set. If so, you get closer to the sum, and you can choose to reuse the same coin/value. If not, the value of your solution stays the same, but you never use that coin/value again in that solution. The final number of ways is just the sum of these two possibilities. Note that this method does have a time complexity of $O(mn)$.

Additional Links

https://www.geeksforgeeks.org/coin-change-dp-7/


A general algorithm is to compute the SHA256 hash of each file, then sort the hashes and look for duplicates.  After sorting any duplicates that may exist will be consecutive.  For all practical purposes, you can assume that two files will be identical if and only if their SHA256 hash is the same.

If you're asking how to do this from the command line or looking for a product recommendation, take a look at this:

https://unix.stackexchange.com/q/71176/9812
https://superuser.com/q/8223/93541
https://superuser.com/q/46690/93541


Asymptotic growth rate of $f(n)$ and $f(n+1)$

Imagine any continuous, monotonically non-decreasing function $f$ such that $f(n) = n!$ for all non-negative integers $n$. Then $f(n+1) = (n+1)! = (n+1)n! = (n+1)f(n)$. Since there is no constant $c$ such that $n+1<c$, it follows that it is not true that $f(n+1) = \Theta(f(n))$. QED.


Algorithms to convert 2D videos to 3D ones

Sure, there are many algorithms for this:

Some works, which directly work on H264 domain, such as:

  Real-Time 2D to 3D Conversion from H.264
  Video Compression, Nir Shabat, Gil Shabat and Amir Averbuch
  http://www.cs.tau.ac.il/~amir1/PS/3d.pdf

Some deep learning methods already exist on the topic:
http://homes.cs.washington.edu/~jxie/pdf/deep3d.pdf
(this is the review version of the paper, so I could not cite)
There are many other works which use images in many ways to create 3D:

http://live.ece.utexas.edu/publications/2011/cao_mag_2011.pdf

https://people.mpi-inf.mpg.de/~pdidyk/papers/2D-to-3D/2D-to-3D.pdf


Fundamentally, yes. Prediction can be used to compress, and compression is a form of prediction. More generally, any learned pattern can be used to compress and vice versa.
This rabbit hole goes a lot deeper, for example I'd suggest A Tutorial Introduction to the Minimum Description Length Principle as a thorough introduction into trying to learn and choose models using compression.


Mastermind (board game) - Five-guess algorithm

The text you quoted seems clear as it is.  But I'll try to elaborate on step 3, since you asked:

Let $S$ denote the set of possible secrets (given responses to moves you've made so far).  Given a candidate guess $g$, you run over all possibilities $s \in S$ and calculate the response that you'd get if you guessed $g$ and the secret was $s$ (the number of black pegs and the number of white pegs); this is "the colored/white score".  Now, for each colored/white score that could be received, if you were to get that score, you could eliminate some possibilities from $S$ as incompatible with that colored/white score; the "goodness" of a colored/white score is the number of possibilities eliminated.  The "helpfulness" of a candidate guess $g$ is the minimum of the "goodness" of all the colored/white scores you could possibly get, in response to $g$.  Select the guess $g$ with highest "helpfulness".

In other words, let $R(g,s)$ denote the number of black pegs and number of white pegs you'd get if the secret were $s$ and you guessed $g$ (this is what your quote calls the "colored/white score").  Let $Z(g) = \{R(g,s) : s\in S\}$, so that $Z(g)$ denotes the set of "colored/white scores" you could possibly get if you made guess $g$ (given that the secret $s$ has to be one of the possibilities in $S$).   Now, if you have a "colored/white score" $z$ where $z \in Z(g)$, let

$$G(g,z) = |\{ s \in S : R(g,s) \ne z\}|,$$

so that $G(g,z)$ is the "goodness" of getting a "colored/white score" $z$ in response to guess $g$.  Also, let

$$H(g) = \min \{G(g,z) : z \in Z(g)\},$$

so that $H(g)$ denotes the "helpfulness" of a candidate guess $g$.

Now step 3 says: you should play the guess $g$ that maximizes $H(g)$.


There is no decision problem that is (unconditionally) known to be in $coNP \setminus NP$.  If we had a decision problem that we could prove is in $coNP$ and could prove is not in $NP$, then we would have proven that $NP \ne coNP$, from which it follows that $P \ne NP$.  In other words, if we knew of such a problem, a proof that is in $coNP \setminus NP$ would provide a proof that $P \ne NP$.  But of course we don't know of any proof that $P \ne NP$; that is a famous open question.

For similar reasons, there is no decision problem that is known to be in $NP \setminus coNP$.

The closest we have is the following: we know of decision problems that are in $NP \setminus coNP$, if $NP \ne coNP$.  For instance, if $NP \ne coNP$, then SAT is in $NP \setminus coNP$.  (You can replace SAT with any other problem that is known to be NP-complete.)  It is widely conjectured that $NP \ne coNP$, so SAT is a good candidate for such a  problem -- but we don't know any proof that $NP \ne coNP$ (that's another famous open problem).

We can also say that if $NP = coNP$, then there is no decision problem in $NP \setminus coNP$.  From this plus the above discussion, we obtain the following useful fact:

  There is a problem in $NP \setminus coNP$ if and only if $NP \ne coNP$.  If there is any problem in $NP \setminus coNP$, then SAT is one such problem.

The same remains valid if you replace SAT with any other NP-complete problem.  Symmetrically, we also know:

  There is a problem in $coNP \setminus NP$ if and only if $NP \ne coNP$.  If there is any problem in $coNP \setminus NP$, then TAUTOLOGY is one such problem.

You can replace TAUTOLOGY with any other problem known to be coNP-complete.

So, this is pretty much a complete characterization of those classes, up to our lack of knowledge whether $NP=coNP$ or not.


Not sure how to interpret the question: how to find egg-breaking height

In this task, the resources that you care about are not running time, but rather the number of throws and the number of eggs broken (in the worst case). Here is an example. Suppose that $N = 2$. An optimal algorithm, which throws at most two eggs and breaks at most one egg, goes as follows:

Throw an egg from floor 1. If it breaks, the answer is $F=1$. Otherwise, continue.
Throw an egg from floor 2. If it breaks, the answer is $F=2$. Otherwise, the answer is $F=3$.

(If $F=3$ is not a possibility, then we need only one throw.)

In this way, we can determine $F$ using at most $\sim N$ throws and one broken egg. There is a way to improve the number of throws to only $\sim \log N$, at the cost of potentially breaking up to $\sim \log N$ eggs.


Mapping Reductions to Complement of A$_{TM}$

Let's take $L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$, that is, all the machines that accept no word (i.e., whose language is empty).

Now we show the reduction $\overline{A_{TM}} \le L_\emptyset$. The reduction is done by taking an input $(\langle M \rangle,w)$ of $\overline{A_{TM}}$ and converting it into an input ${\langle \tilde M \rangle}$ for $L_\emptyset$ such that

$$(\langle M \rangle,w) \in \overline{A_{TM}} \quad\text{  iff  }\quad \langle \tilde M \rangle \in L_{\emptyset}$$

Given $(\langle M \rangle,w)$ we can construct $\tilde M$ in th following way. $\tilde M$ on input y does the following:

deletes the tape
writes $w$ on the tape
runs $M$ on $w$, and performs the same (if $M$ accepts, $\tilde M$ accepts as well).

Convince yourself it is possible to construct the coding of $\tilde M$ from the coding of $M$ and from $w$. Now let's verify that this reduction is valid:

If $(\langle M \rangle,w) \in \overline{A_{TM}}$ then $M$ either rejects or doesn't halt. If so, then also $\tilde M$ doesn't accept $y$, for any input $y$. This means $L(\tilde M) = \emptyset$ thus $\langle \tilde M \rangle \in L_{\emptyset}$.
If $(\langle M \rangle,w) \notin \overline{A_{TM}}$ then $M$ accepts $w$, thus $\tilde M$ accepts $y$ (for every $y$). It follows that $L(\tilde M)=\Sigma^*$ which implies that $\langle \tilde M \rangle \notin L_{\emptyset}$.

The "iff" condition holds and we successfully mapped an input of $\overline{A_{TM}}$ into an input of $L_\emptyset$. In this case we say we reduced $\overline{A_{TM}}$ to $L_\emptyset$. That is, if we can solve $L_\emptyset$, we can also solve $\overline{A_{TM}}$ by first converting the input and then running the algorithm that solves $L_\emptyset$ on the converted input.


Computer Vision - What is spatial histogram/pyramid feature?

Spatial histogram.  A simple histogram is obtained by taking a region of an image, assigning a label to each pixel (somehow; via some mapping function), and then computing a histogram of the labels.  The histogram counts, for each possible label, how many pixels received that label.  You obtain a feature vector: a vector of counts, one count per possible label.

Such a histogram doesn't capture any information about where the labels appear.  A spatial histogram addresses that shortcoming by dividing the image up into several smaller patches, computing a histogram for each patch, and concatenating those histograms.  For instance, you could take a 32x32 image and break it up into sixteen 8x8 patches, compute a histogram for each patch, and concatenate them to get a feature vector.

You still have to choose an appropriate matching.  You might choose a texture descriptor, or just the pixel RGB value (quantized appropriately), or something about the direction of the gradient (quantized), or something else.  For more about spatial histograms, see also http://www.answers.opencv.org/question/7207/spatial-histogram/ and the following paper:

Hongming Zhang, Wen Gao, Xilin Chen, Debin Zhao.  Object detection using spatial histogram features.  Image and Vision Computing, vol 24 no 4, April 2006.

Pyramid.  A pyramid allows you to do something at multiple scales.  You start with a 32x32 image and compute a feature vector for it.  Then, you rescale the image down to a 16x16 image and compute a feature vector for it.  Then you rescale down to a 8x8 image and compute a feature vector for that.  And so on.  Finally, you concatenate all of those feature vectors.  This allows you to capture both coarse features (from the highly downscaled images) as well as fine features (from the large images).

For more about pyramids, see https://en.wikipedia.org/wiki/Pyramid_%28image_processing%29.


How to analyze the Steiner tree problem?

Short answer:  You are given a graph with some special vertices, and are asked to connected them using as few (or cheap) edges as possible.  By connecting them, we mean that you will use only those edges.

More formally, you are given a graph $G = (V,E)$ and a set $S \subseteq V$ of vertices.  These vertices are often refered to as terminals.  You are also given some number $k \in \mathbb{N}$.

I ask you now:  Can you find a set of edges $F \subseteq E$ such that (a) $|F| \leq k$ and (b) in the graph $G' = (V, F)$, $S$ belongs to the same connected component.

Now, if such a set $F$ exists and you take a subset minimal $F'$, the graph $G' = (V,F')$ is a forest, and the component containing $S$ is called a Steiner tree.

This is the unweighted decision version.  It is not hard to come up with the optimization or weighted version.  The weights are on the edges.

Edit:  When it comes to your next question, I would go for Vertex Cover.  Hint: Subdivide every edge and make the new vertices the terminals.  Then the number of edges in a Steiner tree is some function of the $E$ and the number of vertices in the vertex cover in the original graph.

And to show that the problem is in NP should be quite easy.


Prove that it is undecidable whether a given LBA accepts a regular set

Thanks to @YuvalFilmus I managed to reduce the Halting problem to the given problem. We design an LBA B, that given an instance of the Halting problem, $\langle M,x\rangle$, accepts the valid computation histories of M on x. If M doesn't halt on x, $L(B)=\phi$ which is regular. However, if M does halt $L(B)=VAL-COMPS(M,x)$ which is not regular(not even CFL). Techinically, I have reduced the complement of the Halting problem, but as we know that it is also not decidable, so it's fine.


Undecidability in the context of modern programming languages

Short answer: No.

Undecidability is a property of problems, not of programs. What is undecidable is however to check if some given program ever halts on any input. This problem has the program as input.

If you fix a program, then it may be decidable to check if the program halts for some input. This problem has the program input as input. In particular, for programs such as yours that always terminate, the termination problem is decidable, meaning there exists an algorithm for it: it just outputs "yes".

Note that the term "undecidability" only has a meaning in environments that allow arbitrary memory size and arbitrary input size. The Python language may fit to this definition, but the interpreter your are using certainly doesn't.


Resolution and incomplete Knowledge Base

The theory is not inconsistent and trivially admits two different models :

a first one in which dave is rich but not poor;
a second one in which dave is poor but not rich.

You're maybe confusing the "empty clause" which contains no literal, thus being always false, with the "true clause" which contains both a literal and its negation, thus being always true. Applying resolution leads to the "true clause" resolvent, not the "empty clause".


How to find sets of polynomially bounded numbers whose subset sums are different?

There are many functions that satisfy your condition. Here are a few.

$a_i=1+c^{-i}$, for some constant $c\ge 2$.
$a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer between 1 and $p_i-1$.
$a_i =1+\alpha^i/\lceil\alpha^i\rceil$, for any positive transdental number $\alpha$. For example, you can take $\alpha = \pi$ or $\alpha=e$ or $\alpha=0.110001000000000000000001\cdots$, an Liouville number. (Yuval's method)
$a_i=c_1b_i+c_0$, where $b_i>0$ is such a function and $c_1, c_0$ are positive constant.
One can choose random numbers between a positive constant $c_0$ and 1, which should satisfy the requirement with probability one. The issue then is how to select/implement a random number generator and detect the outliers, which may or may not be trivial. (Yuval's method)

For the first three methods, the constant 1 can be replaced by some kind of polynomial of $n$. For example, a nonzero polynomial of $n$ with nonnegative integer coefficients.

These functions should get you going. If you find more ways, you can update this answer.


Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions

Subproblem 1: Find the number of possible paths from $[i,j]$ to $[k,\ell]$ for all $i,k \in \{0,\dotsc,m-1\}$ and $j,k \in \{0,\dotsc,n-1\}$. Store them in a table $A$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $A[i][j][k][\ell]$ stores the number of possible paths from $[i,j]$ to $[k,\ell]$. You can construct this table since this is similar to the second variant of your problem while considering the restrictions.
Subproblem 2: Find the number of possible paths from $[i,j]$ to $[k,\ell]$ that does not goes through the entries: $[k,0], \dotsc, [k,\ell-1]$, for all $i,k \in \{0,\dotsc,m-1\}$ and $j,k \in \{0,\dotsc,n-1\}$. Store them in a table $T$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $T[i][j][k][\ell]$ stores the number of possible paths from $[i,j]$ to $[k,\ell]$ that does not pass through the entries: $[k,0], \dotsc,[k,\ell-1]$. You can construct this table from the entries of the previous table $A$ but it will require some more work.
Main Problem: Suppose the row vector is $(r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$. Here, I am assuming the $0$ based indexing. In other words, if $r_{i_{j}} = 4$, it means it is the fifth row. For sake of better understanding of the solution, let me add $r_{i_{0}} = 0$ at the beginning of this row vector. Now, the row vector is $(r_{i_{0}},r_{i_{1}},r_{i_{2}},\dotsc,r_{i_{p}})$.
Now, we define a table $R$ of size  $(p+1)$ x $n$ such that $R[t][j]$ denote the number of possible paths from $[r_{i_{t}},j]$ (for valid $r_{i_{t}}$ and $j$) to the $[0,n-1]$ that goes through the row vector $(r_{i_{t+1}},\dotsc,r_{i_{p}})$
Output: The algorithm should output $R[0][0]$ since it denote the number of possible paths from $[0,0]$ to the $[0,n-1]$ that goes through the row vector $(r_{i_{1}},\dotsc,r_{i_{p}})$
Induction Step:
$$R[t][j] = \sum_{\ell = 0}^{\ell = n-1} \Big( T[r_{i_{t}}][j][r_{i_{t+1}}][\ell] \Big)\cdot \Big(R[t+1][\ell] \Big) $$
Base Step: When $t$ becomes equal to $p$, we get $R[p][j]$, which denote the number of possible paths from $[r_{i_{p}},j]$ to $[0,n-1]$ that does not goes through any row vector.
$$R[p][j] = A[r_{i_{p}}][j][0][n-1] \quad \textrm{ for all valid $j \in \{0,\dotsc,n-1\}$}$$

Since you just asked for hints, this is more than sufficient.


Your problem is a slightly more general version of computing the vertex-connectivity of a graph. If all weights are equal, then it is equivalent to the vertex-connectivity problem.

The problem can be solved in polynomial time with network flow, yes; but you'll need to invoke a network flow subroutine several times; just one invocation won't be enough.

The simplest approach is the following. Consider all pairs $s$, $t$ of nodes in the graph. For each such pair, we are going to compute the minimum cost, call it $c_{st}$, of separating that pair, that is, the weight of a minimum vertex-weighted $s$-$t$ cut. Then the set you look for will be the set achieving the minimum cost $c_{st}$ over all pairs $s$, $t$.

For a given pair $s$, $t$, the minimum weight cut can be computed with network flow by first replacing every edge $\{u,v\}$ with a directed pair of edges $(u,v)$, $(v,u)$. Then you need to expand your graph by splitting every vertex $v$ into a pair $(v^-, v^+)$. An arc $(u,v)$ is replaced by an arc $(u^+, v^-)$ and an arc $(v,u)$ is replaced by an arc $(v^+, u^-)$. Moreover you add arcs $(v^-, v^+)$ with capacity equal to the weight of $v$; all other arcs have unbound capacity ($\infty$). This complication is necessary to properly model the vertex removal costs. After creating this new instance, you just call the network flow subroutine with source $s^+$ and sink $t^-$. The amount of flow shipped from the source in the solution will tell you $c_{st}$. (To find the set of vertices disconnecting $s$ from $t$, look for all vertices $v$ such that $v^-$ is reachable from $s^+$ in the residual flow network while $v^+$ is not.)

All in all, you need to call the network flow subroutine $n(n-1)/2 = O(n^2)$ times. In fact, there is also a less intuitive but somewhat faster algorithm that allows you to call the network flow subroutine $m$ times instead of $n^2$, where $m$ is the number of edges. This could be much better if the graph if sparse. See the reference below for more details about this faster version.

You can also substantially reduce the time complexity if you know for sure some vertex $s$ that is not going to be one of the nodes that will be removed from the graph. Then you can just try all other nodes $t$ and follow the same strategy as above, only this time you will need to invoke $n-1$ times the network flow subroutine, because $s$ is fixed.

Reference: A. Schrijver, Combinatorial Optimization, Section 15.2. Springer, 2004.


What is so special about a majority and why is it the key for Paxos to work? (Paxos made simple)

Let's assume there were more than 1 Majority. Then at least 1 acceptor would contribute to all majorities. This mandates, however, that this acceptor accepts at least 2 different values, a behaviour ruled out by assumption.


Show that the following algorithm doesn't always find the optimal matching

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal even on graphs with maximum degree 3.


Is there an efficient test for if an NFA accepts a subset of another NFA?

The problem of deciding language containment in NFAs is $PSPACE$-complete. To prove this, it is easy to reduce from the universaility problem for NFAs (testing whether $L(A)=\Sigma^*$)
So, in a way, you have to determinize, but you may do so on-the-fly.

Your observation about co-NP is wrong (but nice). Such a witness can indeed be checked in polynomial time in the witness, but the shortest witness itself may be exponential in the length of the input. Since $PSPACE=co-PSPACE$, then deciding non-containment is also $PSPACE$-complete.

To state things more carefully, deciding whether $L(A)\subseteq L(B)$ is $PSPACE$ in the size of $B$ (since only $B$ needs to be complemented), and $NLOGSPACE$ in the size of $A$.


Graph of size n with girth >2k and minimum degree more than n^1/k

Suppose that $G'$ has girth more than $2k$. Pick an arbitrary node $v$. The node $v$ has $N_1 > \lceil n^{1/k} \rceil$ neighbors. Each neighbor of $v$ has more than $\lceil n^{1/k} \rceil$ neighbors, and at least $\lceil n^{1/k} \rceil$ of them are different from $v$. The neighbors of different neighbors are all different, since otherwise $G'$ would have a 4-cycle. Denoting by $N_2$ the number of nodes at distance 2 from $v$, we have $N_2 \geq \lceil n^{1/k} \rceil N_1$. Continuing this way, we have $N_\ell \geq \lceil n^{1/k} \rceil N_{\ell-1}$ for all $\ell \leq k$ (here you use the lower bound on the girth; details left to you). In total, we get $N_k > \lceil n^{1/k} \rceil^k \geq n$, which is impossible.


Sequential subsequence removal with arbitrary predicate

Set threshold to, say 30 (arbitrary value greater than noise in the plot) and start from left to right, if value is greater than threshold, keep it as run - collect data to temporary array, if values drop below threshold then discard data and create new array for another run.

This will cut 5 bars and discard data between, if you want to keep data, you have to decide the shape (divide evenly between bars, keep it to left or to right).
It may happen that data drops below threshold in the bar (not visible in plot), then keep counter of dropped values, if it is small, add them to last run.


How can I represent a set of graphs for learning purposes?

I don't think that paper is suitable for what you want to do.  That paper generates an embedding of nodes: given a graph $G$ and a node $v$ in $G$, it outputs an embedding of $v$ (a representation of some properties of $v$).  You want an embedding of the entire graph: given a graph $G$, you want to compute an embedding of $G$ (a representation of the entire graph $G$).

So, I suspect you'll need to consider a different approach.  A usual starting point would be to do exactly what @Juho recommended: brainstorm some features that might be relevant (e.g., number of nodes, average degree), then map the graph to a feature vector (a list of the values of these features), and use the feature vector as your representation of the graph.  More sophisticated methods are possible as well, but I'd recommend you start with the simple approach before diving into more complex methods, especially if you are not very experienced in this field.


Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$

Your observation is correct. More specifically, we have the following proposition.

(Asymptotic behavior of a kind of linear recurrence) Suppose $T(n)\ge0$ is defined for all $n$ greater than some constant.
$$T(n) = T(c_1n+h_1(x)) + T(c_2n+h_2(n)) + ...+ T(c_kn+h_k(n)) + c n$$
where $c_1, c_2, ..., c_k, c$ are positive constants smaller than 1 and $h_1, h_2, ..., h_k$ are functions bounded by a constant. There are three cases.

If  $c_1 + c_2 + ...+ c_k < 1$, then  $T(n) = \Theta({n})$.
If  $c_1 + c_2 + ...+ c_k = 1$, then  $T(n) = \Theta(n\log n)$.
If  $c_1 + c_2 + ...+ c_k > 1$, then  $T(n) = \Theta(n^p)$, where $p$ satisfies $\sum_{1 \le i \le k} {c_i}^{p} = 1$.

Note that $h_i(n)$ represents a small perturbation in the index of $T$. Since $\lfloor c_{i}x\rfloor =c_{i}x+(\lfloor c_{i}x\rfloor -c_{i}x)$ and that the absolute value of $\lfloor c_{i}x\rfloor -c_{i}x$ is always between 0 and 1, $h_{i}(n)$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function.
For example, $T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lfloor\frac{n}{4}\rfloor) + T(\lceil\frac{n}{8}\rceil) + n$ and $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n$ will have the same asymptotic behavior. Because of this same asymptotic behavior, recurrence relations might be written sloppily from time to time when only their asymptotic behavior are the only concern, such as possibly the case of the current question.

The above proposition is just a special case of the more general situation handled by the Akra-Bazzi method, also explained here.

The question has provided examples for the first two cases of the proposition.

Here is an example of the third case. Let $$T(n)= T(\lfloor\frac12n\rfloor) + T(\lfloor\frac23n\rfloor) + T(\lfloor\frac56n\rfloor)+2019n$$ and $T(1)=0$. Since $(\frac12)^3+(\frac23)^3+(\frac56)^3=1$, we conclude that $T(n)=\Theta(n^3)$.

Exercise. How about $T(1)=1$ and $T(n)= T(\lceil\frac27n\rceil) + T(\lceil\frac37n\rceil) + T(\lceil\frac67n\rceil)+2018n$?


Expected maximum bin load, for balls in bins with equal number of balls and bins

The correct approximation here is Poisson. The occupancy of each bin is distributed roughly $P(1)$ (Poisson with expectation $1$), and tail bounds for Poisson random variables show that with probability $1-1/n^2$ (say), the variable is at most $O(\log n/\log\log n)$. A union bound shows that with high probability, all bins contain at most $O(\log n/\log\log n)$ balls.

A good resource on balls and bins is "Balls into Bins" – A Simple and Tight
Analysis by Raab and Steger. They use elementary methods to a range of $m$ (balls) and $n$ (bins) that covers the classical case $m = n$.


How is out-of-order instruction execution related to superscalar execution?

Superscalar execution means that some instructions execute simultaneously.  Since the instructions under superscalar execution aren't executing in-order, supserscalar execution is one form of out-of-order execution.


How fast can we identifiy almost-duplicates in a list of strings?

Comparing two strings

Algorithms for computing the Levenshtein edit distance between a pair of strings can be found in the Wikipedia page on the edit distance.  As that page explains, the running time for computing the edit distance between two strings of length $M$ is $O(M^2)$ time and $O(M)$ space.  If you only care about whether the edit distance is $\le T$ or $>T$, then the running time can be reduced to $O(MT)$ time and $O(M)$ space.

Algorithms for computing the (full) Damerau-Levenshtein distance are linked to on the corresponding Wikipedia page.  As Wikipedia explains, the (full) Damerau-Levenshtein distance can be computed in $O(M^2)$ time and $O(M^2)$ space; the algorithm is found in the Lowrance and Wagner paper cited there, or in Appendix A of the Bard paper cited there.

Wikipedia also shows how to compute what is known as restricted Damerau-Levenshtein edit distance; that is considerably easier than computing the full Damerau-Levenshtein distance, and the restricted Damerau-Levenshtein edit distance can be computed using a simple modification to the standard dynamic programming algorithm for the Levenshtein edit distance.  The running time is $O(M^2)$, and it can be reduced to $O(MT)$ time if you only care about whether the distance is $\le T$ or $>T$.

Wikipedia also claims that for spelling correction and typo detection in natural language, the restricted Damerau-Levenshtein edit distance rarely differs from the full Damerau-Levenshtein distance, so you might as well use the restricted distance as it is easier to understand and implement.  I have no personal knowledge of this; just passing along what is claimed in Wikipedia.

I recommend reading Appendix A of the Bard paper cited at Wikipedia for further implementation details.

Comparing all pairs: naive computation of pairwise distances

Therefore, the naive algorithm of computing the edit distance between each pair of strings will take $O(N^2 MT)$ time and $O(M)$ space.

However, for real-world problems of the sort you mentioned, this naive algorithm is typically not optimal.  If $T$ is fairly small, there are much better algorithms; the best algorithm depends heavily on $T$.  But since you haven't specified $T$ in your question, you haven't provided us enough information to suggest a specific algorithm.

Comparing all pairs: better data structures

A related problem is: given the set of $N$ strings, compute a data structure that allows us to quickly find the closest one in the set to any given string (under edit distance as our measure of "closeness").  There is lots of theoretical work on this problem, e.g., using BK-trees, Levenshtein automata, and many other techniques.  See especially Efficient map data structure supporting approximate lookup and  https://cstheory.stackexchange.com/q/4165/5038 for an entry into the literature.

In your case, this might be overkill, though.

The case where $T=1$: sorting

In the special case where $T=1$, there is a clean algorithm.  In other words, we want to consider two strings $X,Y$ if their edit distance is $1$ (i.e., $X$ can be transformed into $Y$ with a single insertion, deletion, or substitution, transposition).

Notice that if $d(X,Y)=1$, then the single difference must appear in either the first half of the string or in the last half of the string.  In other words, either the first half of $X$ matches the first half of $Y$ (they have a long matching prefix), or the second half of $X$ matches the second half of $Y$ (they have a long matching suffix).

This immediately suggests a nice two-stage algorithm:

Sort the entire list of strings.  For each string $X$, enumerate all other strings $Y$ that agree with $Y$ in its first half and check whether any of them are at edit distance $1$ from $X$.  This can be done through a linear scan of a short contiguous stretch of the sorted list, and the start and end of that stretch can be found quickly with binary search.
Next, reverse all the strings and do the same thing again.

(Note that you need to be a little bit careful about the definition of "half" above, to take into account that $X,Y$ might differ in their length.  However these pesky details can be easily worked out with a little bit of care.)

The space requirement is $O(N)$.  Sorting takes $O(N \lg N)$ time.  If you're lucky and the strings are fairly random, then hopefully each string will have only a small number of other candidates that match in the first half or last half.  If this is the case, the running time might be in the vicinity $O(N \lg N)$.

Does this generalize to $T>1$?  Maybe, but it gets messier.

One way to try to generalize is to split the string into $T+1$ equal-length segments, and note that if $d(X,Y)\le T$, then there must be some segment where they match.  However, this runs into messy details because the length of $X$ might differ from the length of $Y$. Therefore, if $T>1$, I don't recommend this approach.

Another way to try to generalize is to break each string down into different fields: say the street address, the city, the country, the postal code.  Now if two addresses $X,Y$ have edit distance $\le 2$, then either (a) some field of $X$ is at edit distance $2$ from $Y$, and all other fields match exactly, or (b) there are two fields where they have edit distance $1$, and all other fields match exactly.  You can find all matches of type (a) by, for each field, building a hashtable keyed on everything but that field; now any two strings that match will be mapped to the same hash bucket, so you just need to solve the problem separately for each bucket.  You can also find all matches of type (b) similarly.  This might be more promising, depending upon the structure of your problem.

Pragmatics

In practice, there are some techniques that I suspect will probably be helpful.  One is to try to use spell-correction on each field of the address first, and then use the spell-corrected addresses to look for duplicates (confirming them by reference to the original value).

Another possible heuristic might be to map each address to geographical coordinates on the sphere, and look for pairs of addresses that are locally very near each other.  This won't detect typos in (say) the country or state, but it might be helpful in detecting typos in (say) street address, by reducing the set of pairwise comparisons you need to make.

Other resources

You might also like to look into the literature on how to build fast spell checkers, as that is a closely related problem.  Take a look at Peter Norvig's article on that problem: http://norvig.com/spell-correct.html


Finding an isomorphism between finite automata

Here's a simpler approach to testing whether two descriptions of regular languages $L_1, L_2$ are descriptions of the same language ($L_1 = L_2$).

Compute the complement of $L_2$, denoted $\overline{L_2}$. If it's represented as a DFA, this can be done in polynomial time (linear I believe).
Compute the intersection of the automata, $L_1 \cap \overline{L_2} $. If they're both DFAs, then this is can be done in quadratic time and space.

If the intersection is null, then you know there's no word in $L_1$ which is not in $L_2$, meaning that $L_1 \subseteq L_2$.

Perform the same test with $L_1$ and $L_2$ interchanged. If $L_1 \subseteq L_2$ and $L_2 \subseteq L_1$, then the langauges are equal, meaning the minimal DFAs are isomorphic. If your input DFAs are known to be minimal, this will test for isomorphism.


Yes and no.

Yes, you could structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects or higher-order functions as parameters).

Felleisen defines a notion of "macro expressiveness" in his 1991 paper On the expressive power of programming languages. Basically, a programming language feature that is macro-expressible is one that can be expressed by a localized and delimited syntactic transformation. With this notion you can partially compare the "expressive power" of different language features: a language feature is at least as expressive as another feature if the second feature is macro-expressible in a language with the first feature (relative to a common base language).

If a feature is not macro expressible relative some language, that means to implement it requires non-local (often global) transformations. This may be done in a brute-force way as a transformation of the whole program, but it also could be done by having a bunch of smaller macros that coordinate to maintain invariants. Either way, the point is if I want to extend your language with a macro of my own creation that operates at the "base" level (machine code in your idea), then my macros need to maintain all the invariants your macros rely upon or else I'll break the "high-level language". It's possible that these invariants are too constraining for what I want to do. If I proceed anyway, rewriting parts of the language so its compatible with my new macros, the end result is that I haven't extended your language at all, I've made a new, incompatible language. It's quite likely that I will either not be able to use your language's existing standard library or that I will need to reimplement it so that it takes advantage of the new features. Even if I can make something that's compatible with the old language, if what I'm doing is not macro-expressible in terms of the "high-level language" (which presumably it isn't or else I wouldn't be accessing the base language) then my macros are going to have their own invariants that need to be maintained across usages and/or will be making assumptions about the low-level details. Now imagine I'm not making an application but a library. Now imagine you want to use my library and another library that has its own set of macros and invariants but don't know about each other.

I've discussed this quite extensively at LtU. See this comment thread and the comment threads it references. I even briefly touch on the thought experiment of assembly + macros in this comment (from 2006). This comment (a bit into one of the threads referenced by the first comment) may be a relatively coherent explanation with examples.

In a nutshell, separately adding two features which are not macro-expressible to a common language will typically produce two incompatible languages. The less expressive the common language is, the more often this will occur.


Why is static-single assignment preferred over continuation passing style in many industry-used compilers?

I imagine many compiler implementers for typical imperative languages simply weren't that familiar with CPS and CPS-based compilation techniques. In the functional programming community both CPS and CPS-based compilation are very well-known techniques - the latter from Guy Steele's work. Nevertheless, even in the FP community, most compilers don't use CPS-based techniques for compilation unless the language itself supports control operators like call/cc.  Something more like Administrative Normal Form (ANF) (sometimes also referred to as Monadic Normal Form which is intimately related for reasons that will become clear) is used which has an even tighter relationship to SSA than CPS does.

If I remember correctly, administrative normal form gets its name from the fact that CPS-based compilation can lead to beta-redexes in the intermediate code that didn't correspond to anything in the source code. These were referred to as "administrative redexes". These could reduced at compile-time, but there was a good amount of research on performing a CPS transform that would output code without the administrative redexes in the first place. The goal then was to produce output in a normal form where all "administrative" redexes were reduced, and this was the origin of Administrative Normal Form. It didn't take long to realize there wasn't a whole lot of benefit to viewing this as a(n optimization of a) two-step process: CPS-transform, reduce administrative redexes. In particular, administrative normal form looks rather like monadic-style as practiced (by hand) most notably in Haskell. The CPS transform can be understood as a conversion to monadic-style where you just happen to be using the CPS monad (so there's really multiple ways to "convert" to monadic-style corresponding to different evaluation orders). In general, though, you could be using a quite different monad, and so conversion to monadic-style and thus administrative normal form isn't really related to CPS in particular.

Nevertheless, there were some benefits to CPS versus ANF. In particular, there were certain optimizations that you could do in CPS with just standard optimizations, such as beta reducing, that required (seemingly) ad-hoc rules for ANF. From the monadic perspective, these rules correspond to commuting conversions. The upshot is now there is a theory that can explain what rules should be added and why. A recent paper gives a (new and) pretty clear description of this (from a logical perspective) and its related work section serves as a brief but decent survey of and references into the literature on the topics I mention.

The problem with CPS is tied to one of its main benefits. CPS transforming allows you to implement control operators like call/cc, but this means every non-local function call in the CPS intermediate code has to be treated as potentially performing control effects. If your language includes control operators, then this is just as it should be (though even then most functions probably aren't doing any control shenanigans). If your language doesn't include control operators, then there are global invariants on the use of continuations that are not evident locally. This means there are optimizations that are unsound to perform on general CPS code that would be sound to perform on this particularly well-behaved use of CPS. One way this manifests is in the change in precision of data and control flow analyses. (CPS transforming helps in some ways, hurts in others, though the ways it helps are mostly due to duplication rather than the CPS aspect itself.)1 You could, of course, add rules and adjust analyses to compensate for this (i.e. to exploit the global invariants), but then you've partially defeated one of the major benefits of CPS-based compilation which is that many (seemingly) special-purpose, ad-hoc optimizations become special-cases of general-purpose optimization (particularly beta reduction).

Ultimately, unless your language has control operators, there is usually not much reason to use a CPS-based compilation scheme. Once you compensate for the issues I mentioned above, you've typically eliminated the benefits of CPS-based compilation and produced something equivalent to not using CPS. At that point, CPS is just making convoluted looking intermediate code for not much benefit. An argument for CPS-based compilation from 2007 addresses some of these issues and presents some other benefits using a different form of CPS conversion. The things that paper brings up are covered in part by the (2017) paper I mentioned before.

1 Doesn't the equivalence between SSA and CPS make this more or less impossible? No. One of the first things the paper introducing this equivalence states is that the equivalence does not work for arbitrary CPS code, but it does work for the output of a CPS transform (which they define) for a language without control operators.


For a binary tree of n nodes, there is a subtree with n/3 to 2n/3 nodes

$\DeclareMathOperator\s{size}\def\f#1{\lfloor#1\rfloor}\def\c#1{\lceil#1\rceil}$As already pointed out by gnasher729, the statement is not literally true when $n\equiv1\pmod3$: if $n=3k+1$, there are binary trees of size $n$ whose all subtrees have size either $\le k<n/3$ or $\ge2k+1>2n/3$.
A version suitable for all $n$ can be proved as follows. Let $\s(u)$ denote the size of the subtree rooted at $u$.

Lemma 1: If $1\le s\le n$, then every binary tree of size $n$ has a node $u$ such that $s\le\s(u)\le2s-1$.

Proof: Let $u$ be a node with $\s(u)\ge s$ such that $\s(u)$ is minimal possible. By minimality, the child subtrees of $u$ have size $\le s-1$ each, hence $\s(u)\le2(s-1)+1=2s-1$. QED
Balancing $\s(u)$ and its complement, we obtain the following.

Corollary 2: In every binary tree of size $n>1$,

there is a node $u$ such that $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$, and

there is a node $u$ such that $\c{n/3}\le\s(u)\le\f{(2n+1)/3}$.

Proof: Using Lemma 1 with $s=\f{(n+1)/3}$, we have $2s-1\le\f{(2n+2)/3}-1=\f{(2n-1)/3}$. Likewise, $2\c{n/3}-1=2\f{(n+2)/3}-1\le\f{(2n+4)/3}-1=\f{(2n+1)/3}$. QED
We can also reformulate it as follows:

Corollary 3: Every binary tree of size $n>1$ has a subtree such that both the subtree and its complement have sizes between $\f{(n+1)/3}$ and $\f{(2n+1)/3}$.

Proof: Taking $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}$ by Corollary 2, the complement of the subtree rooted at $u$ has size between $n-\f{(2n-1)/3}=\c{(n+1)/3}=\f{n/3}+1$ and $n-\f{(n+1)/3}=\c{(2n-1)/3}=\f{(2n+1)/3}$. QED
Using Corollary 2, the simple bound $n/3\le\s(u)<2n/3$ works if $n\equiv0,2\pmod3$. It also works for all $n$ if the tree is full:

Corollary 4: Every binary tree of size $n>1$ such that all nodes have $0$ or $2$ children has a node $u$ such that $n/3\le\s(u)<2n/3$.

Proof: In this case, the size of every subtree (including $n$ itself) is odd. By Corollary 2, there is $u$ with $\f{(n+1)/3}\le\s(u)\le\f{(2n-1)/3}<2n/3$. If $\f{(n+1)/3}\ge n/3$, we are done. The remaining case is that $\f{(n+1)/3}=(n-1)/3$. But here $n-1$ is even, hence $(n-1)/3$ is also even, while $\s(u)$ is odd. Thus $\s(u)\ge1+(n-1)/3>n/3$. QED


That inequality is not defined for $\alpha = 0, 1, 2$. For $\alpha > 2$ you have:
$$
\frac{1}{\alpha-2}  - \frac{1}{\alpha-1} -  \frac{1}{\alpha} =
\frac{\alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2)}{\alpha(\alpha-1)(\alpha-2)}
$$
Clearly the denominator is always positive. Regarding the numerator:
$$
\alpha(\alpha-1)-\alpha(\alpha-2)-(\alpha-1)(\alpha-2) =
\alpha(\alpha-1-\alpha+2) - (\alpha-1)(\alpha-2) =\\
\alpha - (\alpha-1)(\alpha-2) =
\alpha - \alpha^2 + 2\alpha  + \alpha  -2=
-\alpha^2 + 4\alpha - 2,
$$
which is negative as soon as $\alpha \ge 4$. In fact, your inequality is only true for $\alpha=3$.


What does it mean to logically imply another predicate?

$F_1$ says for all $x$, there exists a y such that $P(x)$ implies $Q(y)$.

$F_2$ says for there exists a $x$, for all $y$ such that $P(x)$ implies $Q(y)$.

$F_3$ says that for all $x$, if $P(x)$ holds, then there exists a $y$ such that $Q(y)$.

$F_4$ says that there exists a $x$, such that if $P(x)$, then for all $y$, $Q(y)$ holds.

The first one means that for all values of $x$, there exists some value of y such that the $P(x)$ implies $Q(y)$.

The second one says that there exists a common $x$ for all $y$ such that $P(x)$ implies $Q(y)$.

Both of them aren't the same, which is what you have pointed out too and you can solve the rest of them in the same way.

Also, a good way would be to some concrete example and see if it holds or not. It makes the intuition a bit easier.

EDIT: If you want more help with logical implications, there's a book called How To Prove It by Daniel Velleman whose first two chapters deal with logic, which is a good read.


Would a polynomial-time algorithm for an NP-hard problem implies that P=NP?

Your conclusion is correct: Since an NP-complete problem exists that can be reduced to your NP-hard problem, if you should be able to solve your NP-hard problem in polynomial time the NP-complete problem would be in P, hence P=NP.


Domain and range of recursive functions are recursively enumerable

The first proof looks ok. (Actually, it depends on the definition you use for RE. Some authors define RE iff it's the domain of a recursive function, making the exercise trivial.)

For the second, here's a hint. Given $x$ you want to check whether $f(0)=x$ or $f(1)=x$ or ... If all of these are false, we can diverge (we must diverge, actually), but if any of these is true, we must halt. We can not proceed with a simple infinite iteration, since $f(1)$ might diverge and $f(2)$ might return $x$, and if so we need to detect that and halt anyway.

So, we need to evaluate in parallel all these programs, so that even if one of them diverges does not stop the evaluation of the others.

Think of a fair scheduler among infinitely many processes. Think about running a program for only a given number of steps. Think about doves and their tails. ;-)


Is there a clear line between algorithmic problem and an algorithmic problem instance?

Yes, there is a clear distinction. A problem is a general computational task; an instance is an input to that task.

The confusion in your examples is because you need to make a decision about what the task is and, correspondingly, what the input is. For any fixed domain $D$ and fixed comparison relation $\sqsubseteq$ on that domain, sorting elements of $D$ according to $\sqsubseteq$ is a problem. The instances of this problem are sequences of elements of $D$. For example, the problem of sorting natural numbers according to $\leq$ is a problem, whose instances are sequences of natural numbers. The problem of sorting natural numbers according to $\geq$ is a different problem, though its instances are also sequences of natural numbers.

Alternatively, one could make the comparison operator a part of the input. Now, the problem is to sort elements of some fixed domain $D$ using the given comparison operator, and an instance consists of a sequence of elements of $D$ and a comparison operator. However, it's not clear how you'd specify the comparison operator, which is a binary relation on $D$, which could be an infinite amount of data. One option might be to have a list of allowed choices so, e.g., choice 1 means sort according to $\leq$, choice 2 means sort according to $\geq$, etc.


What is the connection between combinatorial circuits and finite state automata?

You can associate with a combinatorial circuit with $n$ inputs and a single output the language consisting of the $n$-bit strings on which the circuit outputs $1$. This language is finite and so, in particular, regular. This is not particularly enlightening, however.

Combinatorial circuits have a fixed number of inputs. In contrast, finite automata get as input a word of unbounded length. The goals of circuits and automata are thus rather different – circuits attempt to solve a finite problem efficiently, whereas automata attempt to solve an infinite problem. Every finite problem can be computed by some circuit, and so the challenge is to come up with a small circuit that computes it. In contrast, not all infinite problems can be solved by a given type of automata.

The more interesting relation between circuits and automata is that of translation. Given a language $L$ of binary words, let us denote by $L_n$ its restriction to inputs of length $n$. A well-known result is the following:

  If $L$ can be solved in polynomial time, then there is a polynomial $p(n)$ so that for every $n$, the finite language $L_n$ can be computed by a circuit of size $p(n)$.

Therefore one way to show that $L$ cannot be solved in polynomial time is to show that the finite languages $L_n$ cannot be computed by polynomial size circuits.

The circuits produced by the translation alluded to above are related to each other, in the sense that they can all be generated by a program which on input $n$ outputs the circuit $C_n$ for the fragment $L_n$. Such a family of circuits is known as a uniform family of circuits. When comparing the strength of circuits and automata, the correct comparison is between uniform families of circuits and automata. For example, we can strengthen the result above to an equivalence:

  A language is in polynomial time iff its finite restrictions can be computed by a uniform family of polynomial size circuits.

Thus uniform polynomial size circuits have exactly the same power as polynomial time computation. Uniform circuits often appear in practice – a good example is circuits for doing arithmetic, from whose structure their uniformity is apparent. Non-uniform circuits – ones which cannot be produced uniformly – can have unlimited power. For example, non-uniform circuits can solve the halting problem in its unary formulation, $$\{ 1^n : \text{ the $n$th Turing machine halts on the empty tape} \}.$$

Nevertheless, it is believed that even non-uniform polynomial size circuits cannot solve NP-hard problems, a conjecture known as $\mathsf{NP} \neq \mathsf{P/poly}$. At some point in time this looked like a promising avenue for proving $\mathsf{P} \neq \mathsf{NP}$, though at the moment this point of view seems naive.


If $A \cap B$ or $A \cup B$ or $A \times B$ is recursively enumerable is it true to say that both $A$ and $B$ are recursively enumerable?

Notice that $\mathsf{RE}$ is not closed under complementation. Therefore there exists an $A\in\mathsf{RE}$ such that $B=A^c\notin\mathsf{RE}$, while $A\cap B$ and $A\cup B$ are trivially recursively enumerable.

However, when $A\times B\in\mathsf{RE}$, there is a Turing machine $\mathcal{M}$ accepts $(x,y)$ iff $x\in A$ and $y\in B$. Therefore $\mathcal{M}(x,y_0)$ for fixed $y_0\in B$ accepts the language $A$, and hence $A\in\mathsf{RE}$. For $B$ it is the same.

Update: I notice that I missed something in the case of $A\times B$. The conclusion holds only when both $A,B$ are not empty, since otherwise $A\times B=\varnothing\in\mathsf{RE}$ whatever the other one is.


Why do we believe that PSPACE ≠ EXPTIME?

Let's refresh the definitions.

PSPACE is the class of problems that can be solved on a deterministic Turing machine with polynomial space bounds: that is, for each such problem, there is a machine that decides the problem using at most $p(n)$ tape cells when its input has length $n$, for some polynomial $p$.
EXP is the class of problems that can be solved on a deterministic Turing machine with exponential time bounds: for each such problem, there is a machine that decides the problem using at most $2^{p(n)}$ steps when its input has length $n$, for some polynomial $p$.

First, we should say that these two classes might be equal. They seem more likely to be different but classes sometimes turn out to be the same: for example, in 2004, Reingold proved that symmetric logspace is the same as ordinary logspace; in 1987, Immerman and Szelepcsényi independently proved that NL$\;=\;$co-NL (and, in fact, that NSPACE[$f(n)$]$\;=\;$co-NSPACE[$f(n)$] for any $f(n)\geq \log n$).

But, at the moment, most people believe that PSPACE and EXP are different.  Why?
Let's look at what we can do in the two complexity classes.  Consider a problem in PSPACE.  We're allowed to use $p(n)$ tape cells to solve an input of length $n$ but it's hard to compare that against EXP, which is specified by a time bound.

How much time can we use for a PSPACE problem? If we only write to $p(n)$ tape cells, there are $2^{p(n)}$ different strings that could appear on the tape, assuming a binary alphabet. The tape head could be in any of $p(n)$ different places and the Turing machine could be in one of $k$ different states. So the total number of configurations is $T(n) = k\,p(n)\,2^{p(n)}\!$.  By the pigeonhole principle, if we run for $T(n)+1$ steps, we must visit a configuration twice but, since the machine is deterministic, that means it will loop around and visit that same configuration infinitely often, i.e., it won't halt.  Since part of the definition of being in PSPACE is that you have to decide the problem, any machine that doesn't terminate doesn't solve a PSPACE problem.  In other words, PSPACE is the class of problems that are decidable using at most $p(n)$ space and at most $k\,p(n)\,2^{p(n)}$ time, which is at most $2^{q(n)}$ for some polynomial $q$. So we've shown that PSPACE$\;\subseteq\;$EXP.

And how much space can we use for an EXP problem? Well, we're allowed $2^{p(n)}$ steps and the head of a Turing machine can only move one position at each step. Since the head can't move more than $2^{p(n)}$ positions, we can only use that many tape cells.

That's what the difference is: although both PSPACE and EXP are problems that can be solved in exponential time, PSPACE is restricted to polynomial space use, whereas EXP can use exponential space. That already suggests that EXP ought to be more powerful.  For example, suppose you're trying to solve a problem about graphs.  In PSPACE, you can look at every subset of the vertices (it only takes $n$ bits to write down a subset).  You can use some working space to compute on each subset but, once you've finished working on a subset, you must erase that working space and re-use it for the next subset.  In EXP, on the other hand, you can not only look at every subset but you don't need to reuse your working space, so you can remember what you learnt about each one individually.  That seems like it should be more powerful.

Another intuition for why they should be different is that the time and space hierarchy theorems tell us that allowing even a tiny bit more space or time strictly increases what you can compute. The hierarchy theorems only let you compare like with like (e.g., they show that PSPACE$\;\subsetneq\;$EXPSPACE and P$\;\subsetneq\;$EXP) so they don't directly apply to PSPACE vs EXP but they do give us a strong intuition that more resource means that more problems become solvable.


Finding the $k$th largest element in an unsorted array

Yes, there is. Selection algorithm. There are two versions: running in worst-case linear time, and in expected linear time (see Cormen's chapter 9).
You can also implement this algorithm to run in sublinear time using data structures.


Difference between selecting a large pool of individuals for reproduction, and selecting two parents specifically

The approach defined in 1 is known as Elitism approach or Elitism based selection, which is usually done by selecting the fittest individuals. link1 and link2.

The approach defined in 2 is commonly known as crossover where 2 individuals are repeatedly selected via different algorithms like Tournament selection, Roulette wheel, etc. until the max population is reached.


Language with $\log\log n$ space complexity?

I found the answer below in lecture notes of Muli Safra.

Consider the language consisting of the following strings:
$$
\begin{align*}
& 0 \$ 1 \$ \\
& 00 \$ 01 \$ 10 \$ 11 \$ \\
& 000 \$ 001 \$ 010 \$ 011 \$
  100 \$ 101 \$ 110 \$ 111 \$ \\
&\ldots
\end{align*}
$$
This language can be recognized in space $O(\log\log n)$. For each $m$ which is smaller than the width of the first block, we check that the $m$ least significant bits form a counter modulo $m$ starting at $0$ and ending at $2^m-1$. We stop when $m$ is the width of the first block.

Since this language clearly isn't regular, it requires space $\log\log n$ (see for example these lecture notes by Hansen). We conclude that the language requires space $\Theta(\log\log n)$.


Trouble understanding theory for error detection and correction in repetition code

Question 1: Suppose $k$ is fixed. Then, if any group of repeated $k$ bits is flipped, the error is not detected, so we need $k \ge m + 1$. On the other hand, if $k = m + 1$, then any combination of $m$ errors will be detected because at least $k$ bits must be flipped (i.e, the whole group of $k$ repetitions) in order to arrive at a valid code word.
Question 2: The reasoning is similar. One bit errors can be fixed because of the parity bit. Two bit errors cannot because flipping the parity bit and any other repetition bit yields a word $w'$ with Hamming distance $2$ from the original code word $w$; from it, flipping the other two repetition bits yields a valid code word $w''$ which also has Hamming distance $2$ to $w'$, so the error cannot be corrected. The argument for identifying up to three errors is similar: at least four bits must be flipped to arrive at $w''$ from $w$ (as before), and anything less than that will not yield a valid code word.


Isoecursive Types When to Fold and Unfold

As you've stated, the type of IntObject is mu X. {val: int, add: (X -> X)}. fold and unfold witness the isomorphism between a recursive type and its body, i.e. in this case between mu X. {val: int, add: (X -> X)} and {val: int, add: ((mu X. {val: int, add: (X -> X)) -> (mu X. {val: int, add: (X -> X)))}. Letting Y stand for mu X. {val: int, add: (X -> X)}, this can be more compactly written unfold : Y ~= {val: int, add: (Y -> Y)} with fold going the other direction.

You need unfold whenever you want to access any fields/methods. mu X. {val: int, add: (X -> X)} doesn't have any fields; {val: int, add: (Y -> Y)} does. Dually, whenever you want to make an IntObject, you need to use fold. A value of type {val: int, add: (Y -> Y)} is not an IntObject, but fold can inject that value into the type IntObject. In particular, any time you new up an IntObject, i.e. invoke the constructor to create an object.

Basically, your IntObject(i) "really means" something like

let self = fold({val: i, add: \other -> IntObject.add(self, other)}) in self

Similarly, your add method would look like:

def add(self, other):
    return IntObject(unfold(self).val + unfold(other).val)

where we'd use the definition of IntObject just mentioned above.


How can I treat a problem like a search problem in AI?

To treat it as a search problem, you should have a decision tree in mind. In your example, the each node's degree would be the total combination of possible movements for each car (except for the combination in which all cars stay put). Then, each edge of the decision tree would represent a transition from one timestep to the next and each node would represent the positions of all the vehicles at that timestep. One can use the current depth of the tree during the search process to track the current timestep. Using this setup, there are many possible tree search algorithms that may suffice for your problem.


I have not fully understood the algorithm, as it didnt state what $w$ is.

Although, the language $L$ is decidable:

Build the TM for the following algorithm: (assuming input of form $<M,t>$)

For every $w\in\Sigma^*$ with $|w|\le t$:

Emulate $M$ on $w$ for $t$ steps. If $M$ did not halt in that time, reject.

If for all such $w$, $M$ halted within $t$ steps - accept.

This algorithm always halts - as there are a finite number of $w$ with $|w|\le t$ (and it does not simulate $M$ for more than $t$ steps)

The algorithm is right:

If $<M,t>\in L$ then $M$ will halt within $t$ steps on every $w$ we will check, therefore the algorithm will accept.
If $<M,t>\notin L$, then there is some $w\in\Sigma^*$ where $M$ doesnt halt on him within $t$ steps. Notice, that if we define $\hat w=w_{1,...,t}$ to be the first $t$ letters of $w$, then also $M$ wouldnt halt on $\hat w$ within $t$ steps, as if it would have been - then $M$ didnt read move its head right more that $t$ times - and therefore for every $y\in\Sigma^*$, $M$ halts on $\hat wy$ within $t$ and specifically $w$ too. The algorithm can find the $\hat w$ (since $|\hat w|=t$) and will reject because of it.


Algorithm for finding 2 missing items in a stream of integers

Suppose that $x + y = A$ and $x^2 + y^2 = B$. Then
$$ xy = \frac{(x+y)^2 - (x^2+y^2)}{2} = \frac{A^2-B}{2}. $$
Consider now the polynomial
$$ (t-x)(t-y) = t^2 - (x+y)t + xy = t^2-At + \frac{A^2-B}{2}. $$
The polynomial on the right has the two roots $x,y$.

If $x + y = z + w$ and $x^2 + y^2 = z^2 + w^2$ then both $x,y$ and $z,w$ are the two roots of the same polynomial, and so $\{x,y\} = \{z,w\}$.