Rule of thumb to know if a problem could be NP-complete

This is my personal approach to determine whether a problem (i.e. a language $L$) is NP-complete or not. If both these conditions are verified:

I feel that testing if an instance $I$ is in $L$ implies that I need to check all combinations of some sort
and that there is no way to split such a combination into two smaller ones

then $L$ may very well be NP-hard.

For example for the subset sum problem, I have to list all subsets of $S$ and check if there is one whose sum is zero. Can I split $S$ into two smaller subsets $S_1$ and $S_2$ on which I will check a similar property? Humm... not really. Maybe if I checked for all combination of $S_1$ and $S_2$ but that would be really long...

Usually the ability to break into smaller pieces is a good indicator for a problem to be in P. This is the divide and conquer approach. For example to find the shortest path between two points, you can use the property that if the shortest path from $A$ to $C$ go through $B$ then it is not longer than the shortest path from $A$ to $B$ plus the shortest from $B$ to $C$.

Quite frankly this approach is very basic: I try to find a (polynomial) algorithm for the given problem. If I can't find one then the problem becomes "hard" in my point of view. Then comes all the NP-completeness reasoning: will I be able to encode an existing NP-complete problem into this one? (And since this is usually much harder, I try once more to find a polynomial algorithm..)

I suspect that this is the usual way of thinking. However it remains quite hard to apply on unknown problems. I personally remember being surprised by one of the first examples of NP-completeness I was told: the clique problem. It seemed so simple to check! So I suppose that experience has a lot to do with it. Also intuition can be useless sometimes. I remember being told several times two almost identical problems but one was in P and the other one with a small variation was NP-complete.

I am yet to find a good example (I need help here), but this is like the post correspondence problem: this is an undecidable problem but some variants are decidable.


Is there an algorithm for checking if a string is a catenation of palindromes?

Assuming you want disjoint palindromes, this is known as the PALSTAR problem, and there is a linear time algorithm by Zvi Galil and Joel Seiferas. A Linear-Time On-Line Recognition Algorithm for ``Palstar'.

You can find an explanation of the algorithm in the book here: Text Algorithms  (look at linked page and the preceding pages).

If you are ok with a quadratic time algorithm, straight-forward dynamic programming seems to work.

Given a string $s[1,\dots n]$, we maintain an array telling us whether $s[1,\dots j]$ can be decomposed into palindromes.

We also maintain an 2D table which tells us whether $s[i, \dots j]$ is a palindrome or not. This we can construct in $O(n^2)$ time by choosing a center and moving two pointers outwards, checking for palindromes with that center. Do this for each possible center: $\Theta(n)$ centers, each taking $O(n)$ time.

Now, you can check $s[1, \dots j+1]$ whether can be decomposed into palindromes, by checking for each $1 \le i \le j-1$ whether $s[1,\dots i]$ can be decomposed, and  if $s[i+1,\dots, j+1]$ is a palindrome (using the above 2D table). This yields a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

The space usage can be brought down to $O(n)$, if you use Manacher's on-line algorithm to compute whether $s[i+1,\dots j+1]$ is a palindrome (as $i$ goes from $j-1$ to $1$), basically getting rid of the 2D table.


What is intractable or not inherently depends on what the underlying computational model is as well as what your conventions are. By far, the most widely used notion is based on the Cobham-Edmonds thesis, which states that, for any given machine model for which time (or any equivalent thereof) is a valid resource, the tractable problems are those that can be solved in polynomial time. In this sense, tractability quite certainly has a formal definition.

This means that, if you are using run-of-the-mill TMs, then the class of tractable problems is $\mathbf{P}$. If you use probabilistic TMs (with two-sided error), it would then be $\mathbf{BPP}$. If you use quantum circuits, $\mathbf{QBP}$. For ATMs, $\mathbf{PSPACE}$—and so on.

  Are there problems/contexts which could be described as being on the border, meaning that they're really not easily fitting in any of the 2 categories (tractable/intractable) ?

The way tractability is usually understood, this is impossible. There is a well-defined set of tractable problems. Using standard logic, a problem is either in that set or it isn't. You could identify some problems as more difficult than others, but that is a different concept altogether since it would produce a whole spectrum of hardness (and, hence, is not quite captured by the aforementioned notion of tractability). What would rather fit that notion is time complexity itself; after all, it allows you to express a problem's hardness based on the time resources (as a function on $\mathbb{R}_0$) needed to solve it. (And, as we know, most such functions can be compared using, for instance, asymptotic analysis.)

TL;DR: Intractability is a discrete concept; time complexity is a continuous one (or as continuous as it can be in the set of (computable) $\mathbb{N} \to \mathbb{R}_0$ functions).


Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered

Your grammar generates $\Sigma^*$, where $\Sigma = \{a,b,c\}$.


Showing that tournament sort requrires O(n log n) comparisons

Initially you place the elements you want to sort in the leaves of the tournament tree. Then you fill all the internal nodes with the bigger of the two elements in their respective children. This takes $n-1$ comparisons.

After that, you have the largest element in the root. So you can remove it and place it in the output. Now all the comparisons where this element was involved have to be redone. This is one comparison per level of the tree, making $(\log n) -1$ comparisons (-1, since on the lowest level, there is only one candidate element left, so you don't need to compare.)

Now the second largest element is at the top and you can repeat the procedure. And so on. In the end you will have made up to $\log n$, i.e. $O(\log n)$ comparisons for each of the $n$ elements.

Summing up, we have $n-1 + n\cdot O(\log n)$ comparisons. By the rules of $O$-notation, that is in $O(n\log n)$.


Ways to perform "batch" Approximate Member Queries efficiently

If the query results are mostly false, the answer will be returned in $O(1)$ on average. (In traditional Bloom filters, negative results are faster than positive ones.)

This might be slow, however, since the lookups are random and have bad cache behavior. There are a few ways to fix this.

I'd suggest:

Use a blocked bloom filter (from Cache-, Hash- and Space-Efficient Bloom Filters) in which each item is mapped to a single cache-line-sized Bloom filter.
With the hash function that is used to map each item to a cache-line-sized Bloom filter, sort your queries in hash-value order.
Do the queries as usual, but in order.

Another approach is:

Use a split bloom filter, in which instead of setting $k$ values from a single array on each insert, set one value from each of $k$ arrays on insert.
After doing the inserts, use your first hash function to sort the values you wish to query in hash value order.
Query the first of your $k$ arrays for these values. Only a constant fraction will remain - $O(m)$ will be eliminated.
Take the remainder and repeat the last two steps, but using the second hash function, and the second bit array. Repeat $k$ times.

Sorting is expensive in internal memory, but it might be cheaper than all the random accesses. It depends on your machine and your data sizes.


Here is how you encode the input:

Weight and value of item 1.
Weight and value of item 2.
...
Weight and value of item $n$.
$W$.

Suppose that the weight and value are integers, are at most $M$, and both are encoded in binary, as is $W$. Then the length of the encoding is
$$
\Omega(n + \log W), O(n\log M + \log W).
$$
Hopefully this clarifies the difference between $n$ and $W$.


Reconstructing a screen of permuted pixels

One approach is to exploit fact that if two pixels are adjacent, then their intensities will be highly correlated: the intensity of the first pixel (as a time series) will be highly correlated to the intensity of the second pixel (as a time series).

In other words, let $I(p,t)$ denote the intensity of pixel $p$ at time $t$.  Then you can compute a correlation coefficient between $p,q$ as

$$C(p,q) = \sum_t I(p,t) I(q,t).$$

(Detail: you probably actually want to use the normalized correlation coefficient, as explained at bottom.)

For each pair of pixels $p,q$, compute $C(p,q)$, the correlation between these two pixels.

Next, for each pixel $p$, you could identify the four other pixels $p_1,\dots,p_4$ that have the highest correlation to $p$ (i.e., that maximize $C(p,p_i)$).  A reasonable heuristic would be to assume that those are the four neighbors of $p$.  Do this for every pixel.

Now you have a pretty good guess at which pairs of pixels are adjacent.  At this point, you several options.  One approach would be to pick a random pixel, then start trying to expand outward from there: find its four neighbors, then find their neighbors, and so on.

At each step you will need to decide how to orient the neighbors.  Here a plausible heuristic might be: the distance between two pixels $p,q$ in the original image is likely to be related to the correlation $C(p,q)$: larger $C(p,q)$ is associated with pixels that are further apart.  Thus, given a pixel $p$ and its four neighbors $p_1,p_2,p_3,p_4$, I expect you can tell which pairs of those neighbors are on opposite sides of $p$ vs which pairs are kitty-corner to each other (as opposite pixels are at distance 2 apart while kitty-corner pixels are at distance 2).  You probably won't be able to tell which is up and which is right, so just make an arbitrary guess; later you can have a human tell you whether the picture appears to be reflected.

So now suppose that you've mapped some pixels to their original locations, and you want to add one more to the set.  You can get at most three candidates for what it might be, then use the distance heuristic to form a guess about which of the three this is.

Continue this process until you've mapped out a guess at how to reconstruct a large patch of the original image.  Now have a human look at the unpermuted video (unscrambled using your guess at the mapping for those pixels).  If you're lucky, most of that will be correct.  A human should be able to tell you whether this looks correct, and identify the region that appears to be correct.

So, you have a process that given a starting pixel, finds a region surrounding it that appears to have been correctly unscrambled.  Repeat from multiple starting pixels until you have a large collection of such regions.  Now fitting those regions together is basically just a jigsaw puzzle, so should be solvable.

I would expect that the longer the image is, the more effective this will be -- the fewer mistakes this approach will make, and the larger these regions will be and the easier the jigsaw reconstruction process will be.

But the only way to find out for sure is to test this.  Ultimately, this is probably not a question that can be answered by proving a theorem, as the effectiveness of the technique depends on empirical facts about the properties of typical videos.

Footnote: In computer vision applications, it is usually more effective to use the normalized correlation coefficient (NCC).  So, I recommend that you use NCC for this.  The NCC is essentially

$$C(p,q) = \sum_t {(I(p,t) - \mu(p)) (I(q,t) - \mu(q) \over \sigma(p) \sigma(q)},$$

where

$$\begin{align*}
\mu(p) &= {1 \over m} \sum_t I(p,t)\\
\sigma(p) &= {1 \over m-1} \sum_t (I(p,t) - \mu(p))^2
\end{align*}$$

What's the running time of this approach?  The most expensive part is to compute the correlation between every pair of pixels.  Naively, this takes $O(n^2 m)$ time.

However, if computation time is at a premium, it might be possible to speed that up using locality-sensitive hashing or K-D trees to find pairs of pixels for which $C(p,q)$ is larger than some threshold.

If you're looking for research literature on this problem, I would look into video descrambling.  Some video scrambling methods (e.g., for copy protection or cheap video "encryption") permute the pixels, basically along the lines you outlined.  I think there might be work in the research literature on descrambling such videos; a literature search might turn up something useful.


Can we split a vector into positive and negative parts in LP?

Unfortunately, in the general case, no.

Consider if we had a single variable $x$, one can then write out $x = x_+ - x_i$, and have that $x_+, x_- \geq 0$.

The problem is that one can increase both $x_+$ and $x_-$ by any value $\Delta$ and the value for $x$ stays the same. There isn't any convex way to enforce that one of the values is 0. $\min\{x_+, x_-\} = 0$ is non-convex. One can understand that trying to enforce this is non-convex, by considering two axes, one for $x_+$ and the other for $x_-$. Requiring that one of them be 0, is equivalent to enforcing that the solution must lie on an axis - any penalty incurred where they are both non-zero (e.g. $\min\{x_+, x_i\}$, or $x_+ x_-$), then implies non-convexity.

One may be able to deal with this in an acceptable way by applying an $\ell_1$ penalty of $c(x_+ + x_-)$ for some small constant $c$ which doesn't cause too much distortion to the objective.

Of course, if the number of variables for which one wants to apply this is small enough, one can always consider solving all the different options explicitly (i.e., $x_+ \geq 0, x_- = 0$, $x_- \geq 0, x_+ = 0$), but this will only work for a very small number of variables.

Otherwise, one needs to resort to non-convex optimization techniques, which of course aren't guaranteed to find a global minimum.


A "system freeze" is normally due to the system running out of some resource and spending it's limited resources left trying frantically to fix up the mess. I.e., too much CPU load, has no processing power left for the user. Memory overload, keeps trying to free memory and gets nowhere, no time left for the user (and no memory to load programs).

It might also be a deadlock (some tasks inside the system are holding resources others require, and are waiting for still others to be released, but that will never happen as everybody is waiting for somebody else's resources).


Is there a name for "yield first result parallel map"?

You might be able to achieve this in a system for distributed promises / distributed futures.

Some systems will have an operation any that does what you want: if p1,p2,..,pn are promises, then any(p1,p2,..,pn) returns a new promise q that resolves as soon as any of the promises p1,..,pn do.  In other words, once the first promise resolves, q immediately resolves (with that value), without waiting for any of the other promises to resolve.  See, e.g., promise.any in Javascript Q, Promise.any in Bluebird or Promise.any? in Concurrent Ruby.

That said, this is only half the story.  When one promise resolves, what happens to the other promises?  Do they keep executing or get terminated?  The answer will probably depend on the specific system.  If you're unlucky, all the other computations keep running, eventually the other promises resolve, and then their result is just thrown away.  That'd be a waste.

However, if you're lucky -- if the system supports it, and the underlying scheduler is smart enough -- then perhaps the scheduler will terminate the computations associated with the other promises as soon as it is known that they are not needed.  How could that be implemented?  One way is that the implementation of any might cancel all of the other promises as soon as one of them resolves.  The system could be designed to propagate cancellation transitively, and the scheduler could be implemented to terminate any in-progress computation that exists solely to resolve a promise that has subsequently been cancelled.

Ultimately, it's likely to be system-dependent whether the other computations are terminated or not in this situation, and you might need to test individual systems to determine whether they do what you want.


Show that the equivalence problem for deterministic Turing machines and its complement is not semi-decidable

I think an easier way to approach this is by reducing from
$$ALL_{TM}=\{\langle M \rangle: M \text{ is a DTM and } L(M)=\Sigma^*\}$$

Showing that $ALL_{TM}$ is not in in RE nor coRE a standard exercise, and you can find the solution e.g. here

Then, we can reduce from $ALL_{TM}$ to $EQ_{TM}$ as follows: given input $\langle{M\rangle}$ for $ALL_{TM}$, we output $\langle{M,T\rangle}$ where $T$ is a fixed TM that accepts every input immediately. Thus, $L(T)=\Sigma^*$, and we have that $L(M)=L(T)$ iff $L(M)=\Sigma^*$, so the reduction is correct.


Validity of CTL formula $s_0 \models EG\ AF\ p$ in given model

You're correct. Another way to see would be to consider the de-morgan equivalent: $\neg (AF~EG~\neg p)$. To show this invalid, we can show its negation $AF~EG~\neg p$ is valid, which is easier: The formula $AF~EG~\neg p$ says on all paths starting at $s_0$, we eventually get to a state such that there is a path where $\neg p$ holds forever. And indeed that is true in the path $s_0 \rightarrow s_0 \rightarrow\ldots~.$ Since we established the negation, your original formula is invalid as you yourself concluded.

Thinking about CTL can be tricky. A good way is to always double-check using a CTL model checker, like the following:

MODULE main()
  VAR
    state: {s0, s1, s2, s3};

  ASSIGN
    init(state) := s0;
    next(state) := case
                     state = s0: {s0, s1, s3};
                     state = s1: s2;
                     state = s2: s1;
                     state = s3: s2;
                   esac;

  DEFINE
    p := (state = s1) | (state = s3);
    r := (state = s0) | (state = s1) | (state = s2);
    q := (state = s2) | (state = s3);
    t := (state = s1);

  SPEC EG AF p;

Using nuSMV (http://nusmv.fbk.eu/), I get:

-- specification EG (AF p)  is false
-- as demonstrated by the following execution sequence
Trace Description: CTL Counterexample
Trace Type: Counterexample
  -> State: 1.1 <-
    state = s0
    t = FALSE
    q = FALSE
    r = TRUE
    p = FALSE

Which is NuSMV's way of saying you can simply stay in the starting state and it would be a counter-example to your property.


Checking whether a number is a square or higher power modulo n

Recognizing squares

No.  As far as we know, there is no efficient algorithm to tell whether $x$ is a square modulo $n$, if the factorization of $n$ is not known.

This is the  quadratic residuosity problem; see Wikipedia for an overview.  The conjecture is that the quadratic residuosity problem is as hard as factoring (i.e., the best algorithm is to first factor $n$).  In fact, some cryptosystems have been built whose security rests on this assumption.

The best we can do is to use the Jacobi symbol.  If the Jacobi symbol $\left(\frac{x}{n}\right)$ is $-1$, then $x$ is certainly not a square modulo $n$.  However, if $\left(\frac{x}{n}\right)=+1$, then $x$ might or might not be a square.  In particular, if $n$ is the product of $k$ large, distinct primes, then about $1/2^k$ of all numbers modulo $n$ are squares; about $1/2$ have Jacobi symbol $+1$; so about $1/2^{k-1}$ of all numbers with Jacobi symbol $+1$ are squares, and the remaining are non-squares.  Thus, the Jacobi symbol is not enough to determine whether $x$ is a square modulo $n$.

When $n$ has known factorization

If the factorization of $n$ is known, then you can easily determine whether $x$ is a square modulo $n$ or not by using the Chinese remainder theorem.  Similarly for higher powers; again, use the Chinese remainder theorem; then check whether $x^{(p^e-p^{e-1})/k} \equiv 1 \pmod{p^e}$, for each prime $p^e$ dividing $n$.

(You might also like the following post, which discusses not only how to detect whether it is a $k$th power but whether you can compute the $k$th root, when working modulo a prime $p$: https://crypto.stackexchange.com/q/6518/351.  If the factorization of $n$ is known, this will determine when you can compute $k$th roots modulo $n$.)

So, in the rest of this answer, I'm assuming the factorization of $n$ is unknown, and $n$ is hard to factor.

Recognizing higher powers

What if we want to test whether $x$ is a $k$th power modulo $n$?  Here things bifurcate, according to whether $k$ is relatively prime to $\varphi(n)$ or not.

If $k$ is relatively prime to $\varphi(n)$, then every number $x$ that is relatively prime to $n$ is a $k$th power modulo $n$.  This follows from the fact that $(x^j)^k \equiv = x \pmod n$, where $j \equiv k^{-1} \pmod n$.  (The case where $x$ is not relatively prime to $n$ is easy to handle: you compute $d=\gcd(x,n)$ and split the problem into one of determining whether $x$ is a $k$th power modulo $d$ and whether $x$ is a $k$th power modulo $n/d$.)

If $k$ divides $\varphi(n)$, then we are in a situation analogous to that of detecting squares.  This is only case where I'm not 100% certain about the answer, and I don't know whether it has been studied or not.  (I would conjecture that detecting $k$th powers modulo $n$ is probably also hard if $n$ is hard to factor, but I have no proof.)

If $k$ is not relatively prime to $\varphi(n)$ but does not divide $\varphi(n)$, let $k'= \gcd(k,\varphi(n))$.  Then the question of whether $x$ is a $k$th power reduces to the question of whether $x$ is a $k'$th power, which is discussed above.


Regularity of a language contains more 1's than 0's

Treat the characters of the string as integers and add them up. The number you get is the number of ones in the string. If that number is more than half the length of the string, then there are more ones than zeros.

In my opinion, that's not a good way to specify the language. It's clever and correct but, honestly, if somebody has to ask a Stack Exchange question about the way you chose to write "More ones than zeros", then you made it way too hard to understand.


You are missing a proof that $L_H$ is semi-decidable.

Here are two ways to prove that $S$ is semi-decidable.

First method. The following predicate is decidable: "$M$ reaches state $q$ after running on $x$ for $t$ steps". Hence the following is semi-decidable: "there exist $x,t$ such that $M$ reaches state $q$ after running on $x$ for $t$ steps".

Second method. On input $M$ and $q$, simulate $M$ on all possible inputs (by dovetailing); output $\langle M,q \rangle$ for each state $q$ reached by each of these simulations.


Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$

You're looking at an implicit conflict in your grammar. Given
\begin{align*}
S &\to Aa \mid b A c \mid Bc \mid bBa \\
A &\to d \\
B &\to d,
\end{align*}
we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.

Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.

This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}_n (\alpha) \cap {\rm first}_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.

Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \{d\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before:
\begin{align}
S &\to da \mid bdc \mid dc \mid bda \\
&\Rightarrow ({\rm left ~ factoring}) \\
S &\to d X \mid bd X \\
X &\to a \mid c
\end{align}

Computing the 1-lookahead predictive table results in
$$
\begin{array}{ccccc}
& a & b & c & d \\
S & & \to bdX && \to dX\\
X & \to a & & \to c
\end{array}
$$

which corresponds to the algorithm

function parseS(words):
  if next word is b:
    // -> bdX
    consume b; consume d; parseX(rest)
  else if next word is d:
    // -> dX
    consume d; parseX(rest)
  else: error

function parseX(words):
  if next word is a: consume a
  else if next word is c: consume c
  else: error


What is the complexity of this subset merge algorithm?

EDIT:
Since your new algorithm is slightly different, I present a new complexity analysis.
I change the notation slightly of power-sets $P_a$ and $P_b$ to $P_1$ and $P_2$. Your algorithm generates a power-set $P = P(S_1 \cup S_2 \cup \cdots \cup S_n)$ where $P(S_i)=P_i$ given the power-sets $P_1, P_2, ..., P_n$.
In the body of the loop it performs the merge of two subsets $P_1$ and $P_2$.

What is the complexity of $\mathtt{merge}(P_1, P_2)$?

Define $|a|=\mathtt{len}(a)$ for a list $a$. The complexity of $\mathtt{set}(a) \mid \mathtt{set}(b)$ is $\mathcal{O}(|a|+|b|)$ according to Python Wiki for the union of two sets. The conversion $\mathtt{list}(\mathtt{set}(a) \mid \mathtt{set}(b))$ is asymptotically not worse than $\mathcal{O}(|a|+|b|)$, I guess it is either linear or sublinear depending how python implements it. Appending is constant, but since you are appending the whole list it is linear in terms of one list element as the whole list object will need to be copied in the memory, again $\mathcal{O}(|a|+|b|)$ . Thus the complexity of the loop body in a merge function is at most $\mathcal{O}(3(|a|+|b|)$ which is asymptotically equivalent to $\mathcal{O}(|a|+|b|)$.

The loop body in a merge function will be executed $|P_1||P_2|$ times. Thus the overall complexity of the merge function is $\mathcal{O}(|P_1||P_2|(|a|+|b|))$. Notice $a$, $b$ are elements of power-sets. Thus their lengths follow a binomial distribution. Therefore on average $|a|=0.5\log_2(|P_1|)$ and $|b|=0.5\log_2(|P_2|)$. This gives us

\begin{align}
\mathcal{O}(|P_1||P_2|(|a|+|b|))&=\mathcal{O}(|P_1||P_2|(0.5\log_2(|P_1|)+0.5\log_2(|P_2|))\\
&=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1|)+\log_2(|P_2|))\\
&=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1||P_2|))\\
&=\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|))
\end{align}
for the complexity of a merge algorithm for two power-sets $P_1$ and $P_2$.

Notice that the merge of $P_i$ and $P_{i+1}$ replaces $P_{i+1}$ for a power-set $\mathtt{merge}(P_{i}$,$P_{i+1})$ which is of length $2^{\log_2|P_i|+\log_2|P_{i+1}|}=|P_i||P_{i+1}|$.

After the first the first execution of the loop body in the main algorithm you will have executed $\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|))$ steps. $P_2$ has changed to $P_2'$ with the length $|P_1||P_2|$. After the second execution you will get another $\mathcal{O}(|P_2'||P_3|\log_2(|P_2'||P_3|))$ steps which is $\mathcal{O}(|P_1||P_2||P_3|\log_2(|P_1||P_2||P_3|))$ And then by the induction you finally get the complexity of the last step of the loop
\begin{align}
\mathcal{O}(|P_1||P_2|\cdots|P_n|\log_2(|P_1||P_2|\cdots|P_n|))&=\mathcal{O}(\Pi_{i=1}^n|P_i|\log_2(\Pi_{i=1}^n|P_i|))\\
&=\mathcal{O}(\Pi_{i=1}^n|P_i|\Sigma_{i=1}^n\log_2|P_i|).
\end{align}

The complexity of the whole program is the sum of these complexities.


Why we treat sentence letter $Q$ as conclusion in one form and premise in other?

I completely agree with others that the terms "premise" and "conclusion" don't apply to things that aren't implications. By analogy, in $P\land Q$, $P$ and $Q$ are called "conjuncts", but it would make no sense to ask what the conjuncts of $P\to Q$ are.

However, there is terminology that could make sense of the connection that is more commonly used in type theory than logic but is just as applicable to logic. We can talk about "positive" and "negative" positions. In $P\to Q$, the premise, $P$, is in negative position and the conclusion is in positive position. These senses "multiply" in that in $(R\to S)\to Q$, $S$ is in negative position, but $R$ is in positive position (because it's in a negative position within a formula that is itself in negative position). Since $\neg P\equiv (P\to \bot)$, ($\bot$ is the always false formula) negation effectively swaps negative and positive. In $P\land Q$ and $P\lor Q$, both positions are positive. (The general intuition is that propositions in positive positions are possibly asserted, while propositions in negative position are possibly being assumed. They might not actually be asserted/assumed, e.g. in $P\lor Q$.)

This positive/negative notion can be a quick sanity check for equivalences and can help guide proof search. (Negative propositions will likely need to be assumed at some point and positive ones proven. Also, particularly for purely logical theorems, you are often trying to bring negative and positive occurrences together, e.g. as in $P\to P$.) For your equivalence $$P\to Q \equiv \neg (P\land\neg Q)$$ we can see on the right-hand side that $P$ occurs in a positive position within a formula in negative position and so is negative, while $Q$ occurs in negative position within a formula in negative position and so is positive. This matches the left hand side.


It sounds like you are trying to generate a synthetic data set, by artificially adding fake drift.

This is a bad idea.  Don't do this.

If you manage to find some algorithm that works well on your synthetic data set, then all you will know is that your algorithm works on a fake data set -- but you'll have no idea whether it is useful in practice.

Instead, I suggest that you try to find some real-world data sets that contain concept drift, and use them to work with.  If you're not sure how to do that, you might not be ready to do research in this area yet: you might want to spend some time talking to your advisor/mentor, or spend a bunch of quality time in the library reading papers in the literature that talk about the concept drift problem.


Is the dynamic programming pairwise alignment algorithm considered greedy?

No. Rather, the DP algorithm for pairwise sequence alignment1 is an instance of backtracking. What makes it superior to naïve exhaustive search is that

it abandons potential solutions as soon as it can prove that it is going to be sub-optimal (each field in the DP matrix considers only the optimal previous sub-alignment), and
it computes partial results only once and reuses them — that’s the “dynamic programming” aspect of it.

There are other, greedy algorithms for pairwise sequence alignment. These will first find so-called perfect “seed matches” between a query and a database, and then extend those outwards using one of several strategies. They thus explore locally optimal solutions but aren’t (in general) guaranteed to find a global optimum. This is for instance what the BLAST algorithm is doing.

1 By which I’m assuming you mean the Needleman–Wunsch or Smith–Waterman algorithm or some minor variation.


If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$

Using the definition of reduction,
$x\in L_1\iff f(x)\in L \iff x\in L_2$
And thus $L_1=L_2$.


Is 95% of code really non-semantic fluff?

First, note the IT World article grossly simplifies the paper. (This is partly inevitable — if you could summarize the paper in a few accessible paragraph, it wouldn't be a research paper). The 5% figure comes from a particular measure, but the paper considers multiple measures. That being said, I don't think the measures considered in the paper are particularly appropriate.

Let me summarize my understanding of the paper (I've skimmed it, I haven't read it in detail, so I may have made some mistakes or missed important points).

The paper seeks to measure the information density in source code. More precisely, they divide the source code into meaningful units (methods in Java), and they quantify how methods differ from each other, the idea being that if two methods aren't seen to differ then having those two methods instead of just one is content-free overhead (“chaff”).

To extract meaning from source code, they erase distinctions that they consider meaningless. They cut the code of a method into words (which they choose to be lexer tokens), then apply an abstraction function $a$ to each word (in other words, they consider words modulo an equivalence relation: $u \equiv v$ iff $a(u) = a(v)$). The abstraction function is the lexicon. I'll call the set of abstractions of the words in a method ($A(u_1\dots u_n) = \{a(u_i) \mid i \in [1,n]\}$ where $u_1 \ldots u_n$ are the tokens of a method) its abstraction set.

The choice of lexicon is crucial to the measure. At one extreme, you could stick all tokens into the same equivalence class ($\forall u, a(u) = \top$), and then every non-empty method would have the same minset. At another extreme, you could put all tokens in a separate equivalence class ($\forall u, a(u) = u$), and then the minset of a method would only ignore whitespace, comments, the amount of repetition of each token, and the order of token.

The minset of a method in a corpus captures how its set of words differ. A corpus is a set of abstraction sets for all the methods of a set of programs. The minset of a set $S$ in a corpus $C$ is a subset of $S$ (i.e. a subset of the set of words in a method) is a subset $S^* \subseteq S$ such that $S^*$ is not a subset of another element of $C$, and which is maximal under these constraints. Intuitively, anything you add to the minset will not help to distinguish that set from other elements of the corpus.

The 5% figure comes from a fine-grained lexicon where the equivalence between tokens is the trivial one ($u \equiv v$ iff $u = v$). The conclusion is that methods in a typical program are 95% similar.

I don't think the conclusions are particularly relevant for several reasons. The minset measure has major flaws.

If a corpus consists of a single method, then if I understand the definition correctly, its minset will be a singleton (it could be any element, the minset computation is non-deterministic). This shows that there is the correlation between the size of the minset and the complexity of the semantics that the code implements is dependent on the corpus. In order to be meaningful, the corpus has to include all the programs that one would possibly want to write, not just all the programs that were uploaded to a particular repository.

As seen above, the minset measure is also very sensitive to the choice of words and abstraction. To give an extreme example, consider binary code split into bytes, or Turing tarpit languages with a minimal set of primitives and no variables. These will have a very small lexicon, but the ways in which the primitives are combined are highly relevant to the semantics of the program. Even if we don't get into “exotic” languages, consider something like numerical code (built on top of a couple of dozen primitives like add, multiple, while, …), or symbolic processing (built on top of a few primitives like let-rec, cons, fold, …). These tend to express a lot of different behavior by combining a few primitives in rich way. The order and structure of the arrangement of primitives matters a lot, the semantics of a program is not given by the mere set of primitives that it uses.

The paper fundamentally lacks any justification for calling information that isn't captured in the minset “non-semantic” or “chaff”. Their analysis is very sensitive to language syntax and the intuitions are clearly wrong in common examples. The conclusion in the ITworld article is chosen for being sensational, not because it's a realistic measure of the semantic content of code.


Reference asking : High Performance Computer Architecture

This is a pretty good book: Mike Johnson, Superscalar Microprocessor Design, Prentice-Hall, 1991, ISBN 0-13-875634-1.
Having said that, some of the original references are quite readable. For example:

Robert Tomasulo, An Efficient Algorithm for Exploiting Multiple Arithmetic Units
Lynn Conway et al, Dynamic Instruction Scheduling


Is unrestricted grammar equivalent to deterministic Turing machine?

Such a grammar system is Turing-complete.  I can encode a tag system, and tag systems are known to be Turing-complete.


Compression of a text that contains only the 5 first letters of the alphabet?

If you look at the algorithm for creating Huffman trees/codes, you will see that while it uses frequencies, any weight works. You can always rescale (by dividing by the sum of all weights), if you wish.

If your problem does not contain any weights but only a relative order, you can not build a Huffman tree; you don't know where in the order the inner nodes you create go. Ask your teacher.


Graph "coloring" problem minimal number, each edge has a colored end

A valid coloring exists iff the graph is bipartite. In that case, you can divide it into its connected components. Suppose that the $i$th connected component has $x_i$ vertices on one side, and $y_i$ on the other side. Which side would you color $a$?


They are the same.

In the first definition, we identify $\mathbb{F}_2$ with elements $\{0,1\}$, with $+$ defined to be addition modulo 2 and $\times$ defined to be multiplication modulo 2.
In the second definition, we identify $\mathbb{F}_2$ with elements $\{1,-1\}$ and $+$ defined to be multiplication modulo 2 and $\times$ defined as $x \times y = \max(x,y)$.

Both representations of $\mathbb{F}_2$ are isomorphic.

Degree is defined as usual for the polynomial ring $\mathbb{F}_2[x_1,\dots,x_n]$; see your favorite math textbook for the formal definition.  Do note that $f$ is a multivariate polynomials, not a univariate polynomial.

The "integer coefficients of magnitude at most $d$" is weird and doesn't belong.  The definition would make more sense with that phrase omitted.  Pedantically speaking, that phrase makes no sense, as a polynomial over $\mathbb{F}_2$ by definition has coefficients in $\mathbb{F}_2$, so it makes no sense to speak of them as "integers", and they don't have a magnitude.  (Alternatively, if we interpret it loosely/informally, that phrase becomes redundant and dead and ultimately has no effect.)


Rod Cutting without using dynamic approach

In recrsv_top_down, declare result = -1000 as a local variable.


Are there subexponential-time algorithms for NP-complete problems?

Depends on what you mean by subexponential. Below I explain a few meanings of "subexponential" and what happens in each case. Each of these classes is contained in the classes below it.

I. $2^{n^{o(1)}}$
If by subexpoential you mean $2^{n^{o(1)}}$, then a conjecture in complexity theory called ETH (Exponential Time Hypothesis) implies that no $\mathsf{NP}$-hard problem can have an algorithm with running-time $2^{n^{o(1)}}$.
Note that this class is closed under composition with polynomials. If we have a subexponential time algorithm for any $\mathsf{NP}$-hard problem, we can combine it with a polynomial-time reduction from SAT to it obtain a subexponential algorithm for 3SAT which would violate ETH.
II. $\bigcap_{0 < \epsilon} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for all $0 < \epsilon$
The situation is similar to the previous one.
It is closed under polynomials so no $\mathsf{NP}$-hard problem can be solved in this time without violating ETH.

III. $\bigcup_{\epsilon < 1} 2^{O(n^\epsilon)}$, i.e. $2^{O(n^\epsilon)}$ for some $\epsilon < 1$
If by subexponential you mean $2^{O(n^\epsilon)}$ for some $\epsilon<1$ then the answer is yes, there are provably such problems.
Take an $\mathsf{NP}$-complete problem like SAT. It has a brute-force algorithm that runs in time $2^{O(n)}$. Now consider the padded version of SAT by adding a string of size $n^k$ to the inputs:
$$SAT' = \{\langle \varphi,w\rangle \mid \varphi\in SAT \text{ and } |w|=|\varphi|^k \}$$
Now this problem is $\mathsf{NP}$-hard and can be solved in time $2^{O(n^\frac{1}{k})}$.
IV. $2^{o(n)}$
This contains the previous class, the answer is similar.
V. $\bigcap_{0 < \epsilon}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for all $\epsilon>0$
This contains the previous class, the answer is similar.
VI. $\bigcup_{\epsilon < 1}2^{\epsilon n}$, i.e. $2^{\epsilon n}$ for some $\epsilon<1$
This contains the previous class, the answer is similar.

What does subexponential mean?
"Above polynomial" is not an upper-bound but a lower-bound and is referred to as superpolynomial.
Functions like $n^{\lg n}$ are called quasipolynomial, and as the name indicates are almost polynomial and far from being exponential, subexponential is usually used to refer a much larger class of functions with much faster growth rates.
As the name indicates, "subexponential" means slower than exponential. By exponential we usually mean functions in class $2^{\Theta(n)}$, or in the nicer class $2^{n^{\Theta(1)}}$ (which is closed under composition with polynomials).
Subexponetial should be close to these but smaller.
There are different ways to do this and there is not a standard meaning.
We can replace $\Theta$ by $o$ in the two definitions of exponential and obtain I and IV. The nice thing about them is that they are uniformly defined (no quantifier over $\epsilon$). We can replace $\Theta$ with a multiplicative coefficient $\epsilon$ for all $\epsilon>0$, we get II and V. Their are close to I and IV but nonuniformly defined. The last option is to replace $\Theta$ with a multiplicative constant $\epsilon$ for some $\epsilon<1$. This gives II and VI.
Which one should be called subexponential is arguable. Usually people use the one they need in their work and refer to it as subexponential.
I is my personal preference, it is a nice class: it is closed under composition with polynomials and it is uniformly defined. It is similar to $\mathsf{Exp}$ which uses $2^{n^{O(1)}}$.
II is seems to be used in the definition of the complexity class $\mathsf{SubExp}$.
III is used for algorithmic upper-bounds, like those mentioned in Pal's answer.
IV is also common.
V is used to state the ETH conjecture.
Intersections (II and V) are not that useful for algorithmic upper-bounds, their main use seems to be complexity theory.
In practice, you will not see a difference between I and II or between IV and V. IMHO the later three definition (IV, V, VI) are too sensitive, they might be useful for particular problems, but they are not robust which decreases their usefulness as classes. Robustness and nice closure properties are part of the reason why famous complexity classes like $\mathsf{L}$, $\mathsf{P}$, $\mathsf{NP}$, $\mathsf{PSpace}$, and $\mathsf{Exp}$ are interesting.
Summary
IMHO, the main definitions are I and III. We already have subexponential algorithms for $\mathsf{NP}$-hard problems in the sense of III and we cannot have them in the sense of I without violating ETH.


A complicated variant of Weighted Median problem

A tip: this problem becomes much easier if you sort the $x$'s into increasing order.  (If you sort by the $w$'s, your life will be much much harder.)

More precisely, you should sort the entries so the $x$-values are in increasing order, resolving ties so the $w$-values are in increasing order.  This amounts to lexicographic order on $(x,w)$.  This way, if $i<j$, then $x_i\le x_j$ and either $x_i<x_j$ or $w_i\le w_j$.

Once the elements are sorted in this way, you can solve this problem with a linear scan.

Just scan from left to right (i.e., from $i=1$ to $n$), keeping track of the sum of the weights seen so far (i.e., $w_1+w_2+\dots+w_i$).  When this sum transitions from less than $1/2$ to greater than $1/2$, you've found the weighted median.  At the very end, if there are multiple elements with the same $x$-value as the one you found, scan leftwards to find the first element with the same $x$-value as the one you initially found.

Running time: $O(n \lg n)$.  It takes $O(n \lg n)$ time to sort, plus $O(n)$ time for the linear scan.  No need for fancy dynamic programming.

My thanks to Dukeling for helpful comments and corrections!


By dynamic I presume you mean either:
int* array = malloc(sizeof(int)*col*rows);
or
int* array = new int[rows][col]();
In which case its fairly simple:
void sort(int* array, int size)
{
    int temp, idx, kdx;
    for(idx = 0; idx < size; idx++)
    {
        for(kdx = 0; kdx < size; kdx++)
        {
            if(array[kdx] > array[kdx+1])
            {
                temp = array[kdx + 1];
                array[kdx + 1] = array[kdx];
                array[kdx] = temp;
            }
        }
    }
}

//in main or wherever
int* array = malloc(sizeof(int)*col*rows);
random(array, col*rows);
sort(array, col*rows);
free(array);

Although that is a very sloooooowwwwww sorting operation. How about researching logsort or quicksort?


Why is the start symbol "not allowed" on the right hand side in Chomsky normal form?

Recall that in Chomsky normal form, we are allowed productions of three forms:

Productions of the form $A \to a$.
Productions of the form $A \to BC$.
The production $S \to \epsilon$.

We have to allow the production $S \to \epsilon$, since otherwise it will be impossible to generate the empty string.

Suppose for a moment that the production $S \to \epsilon$ is absent. Then we have the following very useful property:

  If $A \Rightarrow^* w$ then $w \neq \epsilon$.

This comes up in some proofs of the pumping lemma, for example.

If we have the rule $S \to \epsilon$, then we no longer have the property above. However, a similar property holds:

  If $A \Rightarrow^* w$ and $A \neq S$ then $w \neq \epsilon$.

This is due to our insistence of not having $S$ on the right-hand side of productions; otherwise we might have rules like $A \to SS$ and then derivations like $A \Rightarrow SS \Rightarrow^* \epsilon$.

If the rule $S \to \epsilon$ is absent, then there is no reason to disallow $S$ on the right-hand side of productions. Indeed, some authors allow $S$ on the right-hand side of productions as long as the production $S \to \epsilon$ is absent.


The number of connected components in the context of cyclomatic complexity

When they say connected component, they mean a weakly connected component. Take a look at the third formula they provide in the Wiki.

For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is M = E − N + 2.

This implies that for $P > 1$ is used for multiple programs. In other words, it is used for programs with multiple start points with distinct end points.
So for the first formula, it takes in consideration of multiple programs, subroutines, or methods that are completely disconnected from each other (i.e. they do not call upon or interfere with each other) in a single program control graph.
The following is an example where the first formula would be applied. Here $M = 9 - 8 + 2*2 = 5$.


There are two possible bugs in this proof:

When you say "decider" - you mean a deterministic TM. In this case, the best translation (to our knowledge) from an NP machine to a deterministic machine may yield a machine that runs in exponential time, so after complementing you will have a decider for the complement in exponential time, proving that $co-NP\subseteq EXP$ (or, after some optimization, $co-NP\subseteq PSPACE$).
When you say "decider" you mean a nondeterministic TM. In this case, flipping the answer will not necessarily complement the language. Indeed, the language of the flipped machine will be all the words for which there exists a rejecting run of $M$ on $w$


Finding two store typings that make the same store valid (lambda-calculus with references)

The store $\mu$ indicates the type of what is stored in the reference. If $\Sigma(\ell) = T$ then the expression $!\ell$ has the type $T$, and the expression $\ell$ has the type $\mathsf{Ref}(T)$.

If all you need is for $\lambda x:\mathsf{Unit}. (!\ell)(x)$ to be well-typed, then $\ell$ must be a reference to a function whose argument type is $\mathsf{Unit}$, with no constraint on the return type.


Why is it necessary to use binary numbers in logspace?

The "usual" encoding of numbers is binary. Binary can mean two things:

Encoding a number in the range $0,\ldots,2^n - 1$ using $n$ bits.
Encoding an arbitrary natural number.

In the latter case, the "width" or "length" of the number is not known in advance, and so some special encoding has to be used. An especially simple one encodes a number $b_0 \ldots b_{n-1}$ as
$$ 1b_0 1b_1 \ldots 1b_{n-1} 0. $$
This is known as a self-delimiting encoding. If you allow the input alphabet to be larger, then you can use a non-binary character as a separator instead, which is a popular convention.

We are more used to decimal numbers rather than binary numbers. In terms of encoding length, the two differ by a multiplicative constant, so binary encoding and decimal encoding are equivalent for most purposes. Binary encoding is used since sometimes we imagine the input encoded as a string over $\{0,1\}$ (this is the case when we talk about circuits, for example).

The other option is unary encoding, in which the number $n$ is encoded by $1^n 0$ (that is, $n$ times the bit 1 followed by the bit 0).

Encoding $n$ takes $n+1$ bits in unary, but only $\Theta(\log n)$ bits in binary. This can make a huge difference in complexity theory, since the running time is measured in the size of the input. For many problems, however, the number parameters pale in length compared to other inputs (say an input graph), and so the exact encoding used is not important.

Here is an example in which encoding is important. Many cryptographic algorithms include a subroutine that accepts $n$ and outputs a key of length $n$. If the input is encoded in binary then its length is $\Theta(\log n)$, and so the subroutine must run in exponential time (since the output is of length $n$). If the input is encoded in unary then there is no such restriction. This is why in such algorithms, $n$ must be encoded in unary.

In other cases, encoding an input parameter in unary might make the problem too easy, and so it is important to encode it succinctly. Unfortunately, I can't think of any such problem right now, since as stated before, usually the number parameters are dwarfed in length by other inputs.


Why is the vulnerable time in pure aloha twice the frame time?

This is because in pure ALOHA, even if a bit of a frame collides with a bit of another frame, both the frames get discarded. Also, in pure ALOHA, a station doesn't listen to the medium before transmitting. So, it has no way of knowing that another frame was already underway. If another frame was indeed underway already, then the newly transmitted frame becomes vulnerable. That is why it is called "vulnerable time". It equals twice of the frame time because it counts the time in which the transmission of another frame should start so as to make the current frame vulnerable. This time interval includes:

the frame time because if transmission of another frame were started in the frame time of the current frame, collision would occur.

a time interval (equal to the frame time) before the frame time because if transmission of another frame were started in this time interval, collision would still occur.

My question is what kind of problem will be created if vulnerable time was equal to frame time?

If the vulnerable time were equal to frame time, any frame (say A) transmitted prior to the considered frame (say B) could be transmitted within the frame time of the considered frame (B), resulting in a collision.
Suppose a sender X starts transmitting at time instant '0' and finishes at instant 't'. Then any other sender Y should start at or after instant 't' and continue till instant '2t' (because if Y start its transmission even a tiny amount of time before 't', there will be collision). Here, the vulnarable time for the frame transmitted by Y is the sum of its own frame time (i.e. 't' to '2t') and another time duration (i.e. '0' to 't'), effectively being '0' to '2t'. This is the time interval during which no sender should send on the channel to ensure that the frame sent by Y doesn't collide.


Dependency on adjacent blocks decreases as block count increases

The more blocks there are, and the longer each block is, the smaller the dependency between blocks.

There are two tendencies. Let us explain one by one.

(Tendency of more blocks) Assume the block size does not change. The more blocks there are in a string, the smaller the dependency between blocks.

Suppose the block size is greater than 10. Suppose there are $N$ blocks. Since each block depends only two other blocks, the previous block and the next block, the total number of (unordered) dependent pairs of blocks is $N-1$ as each block is dependent on its next block except that there is no next block to the last block. There are $N(N-1)/2$ (unordered) pairs of blocks in total. The ratio of dependent pairs to all pairs, $\dfrac{N-1}{N(N-1)/2}=\dfrac 2N$ becomes smaller and smaller and can be arbitrarily close to 0 when $N$ goes bigger and bigger. That is one way in which we can understand the meaning of tendency of more blocks.

If the block size is not greater than 10, we can argue similarly since each block will depends on at most previous $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks and next $\lceil\dfrac {10}{\text{block size}}\rceil$ blocks.

(Tendency of longer blocks) The larger each block size is, the smaller the dependency between adjacent blocks.

Consider two adjacent blocks $B$ and $C$ with $C$ following $B$. Let us consider the ordered pairs of letters where the first letter is in $B$ and the second letter is in $C$. Since every letter does not depend on any letter that is more than 10 letters away, there are at most $1+2+\cdots+10=55$ such pairs in which the two letters are dependent. As the block size $S$ goes bigger and bigger, the number of all possible pairs $S\times S$ becomes bigger and bigger quadratically. However, the number of dependent pairs stays at 55 once the block size is no less than 10. Hence the ratio of dependent pairs to all pairs becomes smaller and smaller. This is one way how we can understand the meaning of tendency of longer blocks.

If we agree that the nearer the letters, the stronger the dependency between them, then we can see that the dependency between adjacent blocks becomes smaller and smaller when the block size grows bigger and bigger even if we do not require the block sizes are no less than 10.

The above explanation follows roughly the same style as the original text. To be more precise, we should define the correlation of two blocks in mathematical terms and we should show how the ordered dependent pairs of letters from two blocks contribute/determine to the correlation of two blocks. That will not be an easy undertaking to be done rigorously. However, it is, I believe, intuitively clear that ratio of dependent pairs from two blocks to the total pairs is in proportional (not necessarily linearly) to the dependency of the two blocks, as long as the latter is defined reasonably. So the above explanation should convince you the correctness of the quoted conclusion. After all, that quoted conclusion is supposed to be easy and intuitive to understand.

  Given some block, I can't see how block count decreases dependency on two blocks adjacent to it.

If "block count" means the number of letters in a block,  then "larger block count decreases dependency between the given block and either of the two blocks adjacent to it" is the tendency of more blocks as I have explained in the above.

If we consider "block count" as the number of blocks, then "larger block count" does not decreases dependency between the given block and either of the two blocks adjacent to it, as you believed.


How to generate a grammer from this language?

Start with $i+j=k+\ell$. If $i\ge \ell$, say $=\ell+m$, then also $k=j+m$ and we can write strings in the form $a^\ell a^m b^j c^j c^m d^\ell$. Those can be generated by a grammar, you can use the basic toolbox.

Similarly when $i\le \ell$.


How to get this upper bound on worst-case heaps?

In Heap sort we use a data structure which is a binary tree, and it is nearly complete. So, height is bounded by
 where n is the no. of nodes. In comparison to root, height of left and right subtree can differ by 1 at max.

Now, Imagine a tree T, and also assume left subtree height = h+1 and right subtree height = h

What is worst case in max_heapify() ? Worst case is when , we end up doing more comparision and swaps while trying to gain heap property.

If the recursive max_heapify algorithm runs and it recursively goes to the longest path, then we can say : a possible worst case.

Well, all the longest paths are in the left sub-tree (because height is h+1 ).

So, to get more longest paths we need to have make left subtree completely full. Since left subtree is of height h+1 , it will have  leaf nodes and  longest paths from root. This is the maximum possible number of longest paths ( of h+1 height ) in T, such that while max_heapify()  is running in a recursive way, it may traverse to the bottom of the left subtree. And we maximize such longest paths by considering left subtree as FULL to make the possibility of deep traversing more frequent in max_heapify() function.

Below is tree structure in worst case situation :

From the above figure assume yellow and red portions has x nodes each. Red portion is total right subtree and yellow portion is excluding the last level of left subtree. Both red and yellow sections now have height h.

How many nodes we have to add ( or attach or pad ) in the bottom layer of yellow portion to make the left subtree completely full  as well as of height h+1 ?

Well, bottom layer of yellow portion has  nodes and we now add 2 children to each of these nodes, => total x ( ) nodes have been added. Why adding, just to make left subtree of height h+1 and full to meet worst case criteria.

OK !! DONE !! .. now , count how many nodes overall...

total =

And left subtree contains 2x nodes = 2n/3 nodes.

So, for worst case one of the subtree should have 2n/3 nodes.

More in the following links :
https://stackoverflow.com/questions/9099110/worst-case-in-max-heapify-how-do-you-get-2n-3

https://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure


How can I show that a language is Turing-recognizable and decidable?

A language is Turing decidable if you can write a C program (replace C with your favorite programming language) that outputs YES if the input belongs to the language and outputs NO otherwise. It is Turing recognizable if in the latter case the C program simply never halts.


What is the smallest $n$ such that $BB(n) > $Graham's number?

If I recall correctly it started with $n = 64$, then $n = 25$ shortly after that with $n=23$, $n = 22$ and now $n = 19$.


What would you call an algorithm that finds $R$ % of the time the optimal solution to an NP-hard problem?

The idea you mention is covered in complexity theory by probabilistic classes.

The computational model they refer to is the probabilistic Turing machine, i.e. a Turing machine equipped with an additional read only tape that at the beginning of the computation contains an infinite sequence of symbols, independently chosen at random with uniform probability from the machine alphabet. Or, equivalently, a Turing machine that can flip a fair coin and read the answer in constant time.

Observe that due to the way that our computational model works, two executions on the same instance may give two different answers; for instance, one could define a machine that flips a coin and returns YES on heads and NO on tails.

We are interested in both the asymptotic worst-case running time and the probability that the answer given is actually correct. In literature, a vast amount of different classes are analyzed, they differ depending on various constraints that they impose on the solver.

Perhaps the most interesting of such classes, both from a theoretical and practical point of view is $\mathcal{BPP}$, defined as the class of languages decidable in polynomial time by a probabilistic Turing machine that, whether the answer is YES or NO, is guaranteed to give a correct answer with probability at least $2/3$. Notably, it is an open problem whether or not $\mathcal{P} = \mathcal{BPP}$.

A full discussion of probabilistic complexity theory would be too lengthy for SE, although there are plenty of sources available in both electronic and dead-tree form.


Given a TM $T$, consider the machine $T'$ which, on input $w$, simulates $T$ on $w$ and enters a special state $q$ if and only if has determined that $T$ accepts $w$. Note you can easily guarantee $T'$ never enters $q$ prior to $T$ accepting $w$. Moreover, you can make sure that, once $T'$ enters $q$, it starts to cycle between all its states indefinitely. (For instance, have $T'$ write a special tape symbol so it knows it is supposed to do so.)

For an arbitrary $T$, producing the description of $T'$ is computable. I'll leave it to you to fill in the gaps so this is a full-fledged reduction.

As a rule of thumb, these exercises can usually be solved by producing description of machines (in this case, $T'$) which encode the answer to the original problem ($A_{\mathrm{TM}}$) in their own behavior. In this particular case, the idea is to establish the equivalence between $T'$ entering all its states and $T$ accepting $w$.


What are the differences between search problems, optimization problems, and decision problems?

A decision problem has this form:

Input: $x$
Output: "Yes" if $\phi(x)$ holds, "No" otherwise

A search problem has this form:

Input $x$
Output: $y$ such that $\psi(x,y)$ holds, if such a $y$ exists. "No" otherwise.

Finally, an optimization problem has this form:

Input $x$
Output: $y$ such that $f(x,y)$ is the minimum possible, i.e. $f(x,y) = \min_{y'} f(x,y')$

Here $\phi$ and $\psi$ are some boolean properties, and $f$ is some natural number function of $x$ and $y$.


How does MIPS ( or any other multi-byte word arch ) fetch a word?

MIPS can load a 32-bit (4-byte) word in a single instruction (load word, LW). The fact that each byte of the word is individually addressable doesn't affect this.  Effectively, the instruction says "Read the four bytes beginning at this address", not "Read the byte at this address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address.  Increment the address by one.  Read the byte at that address."

By way of an analogy, you can photocopy any two facing pages of a book simultaneously, even though each has its own number.


Correctness of Linearizability vs Sequential consistency in replication

A Sequential Consistent (SC) system should behave as if there is just a single copy of the data.
So lets try to determine a possible memory order for your scenario:
1:client2:read(y=0)
2:client2:read(x=0)
3:client1:write(x=1)
4:client1:write(y=2)

This is valid according to SC. Keep in mind that the real time order of requests, doesn't need to preserved. So perhaps the client2.read(x=1) happened later than the client1.write(x=1), it can be ordered in the memory order before the write.
Lets change the example a bit to make it more interesting:
1:client1:write(x=1)
2:client1:write(y=2)
3:client2:read(y=2)
4:client2:read(x=0)

This example isn't SC because the read of x=0, doesn't see the most recent write before it in the memory order. It should have seen x=1. And this is the consequence of the lack of coherence (so what you could get with replicas being out of sync).


What are "state registers" and "code registers"?

While I've not heard those exact terms, my guess would be that "code registers" are the registers that code you would write set. For example, on an Intel x86 platform, that would be the general purpose registers like the AX, BX, CX, etc. and EAX, EBX, ECX, etc. registers. These are registers that you can either use directly if you're writing assembly code, or that are used by the code generated by your compiler.

Meanwhile, the computer also has a set of registers for its own use. Things like the program counter (or instruction pointer) register which points to the next instruction to execute in memory. They can also indicate statuses; things like carry registers that indicate whether there was a carry out of an addition between 2 other registers. (For example if you add 1 to MAX_INT, you'll generate a 1-bit carry that the registers can't hold.)

Each processor is different. The 6502 had 2 registers (labeled X and Y) and an accumulator as general purpose (or code) registers. Then it has one status register that held 7 bits of status flags, a stack pointer, and a program counter, which would be "state registers".


Why does a reduction from a P-problem to an NP-complete problem not show that P=NP?

Part 1 shows how to solve BoxDepth using MaxClique.

Part 2 shows how to solve BoxDepth directly.

None of the parts says anything about solving MaxClique.


How to reconcile the different definitions of asynchrony?

The unifying definition is that one part of the system triggers an event in another part of the system, and the triggerer does not know when the event will take place.
To put it another way: in a synchronous system, you know when things (will) happen. In an asynchronous system, you don't know when things (will) happen.
In event-based programming, a thread creates another thread, and then it has no control over when the thread will do its job. For example, with AJAX, the new theard performs an HTTP request, and the original thread continues executing without knowing when the HTTP response comes back.
In communication over an asynchronous channel, the sender of a message does not know or care when the recipient will be available receive the message.
In an asynchronous distributed system, the sender of a message does not know when (or possibly even whether) the recipient will receive the message and potentially reply to it.


Efficient (sublinear) approximation algorithms for matrix-vector multiplication?

One approach is to treat each component of the result as a separate approximation problem. In this case, we can assume that $A$ is a row vector, so really the problem is to approximate a dot product $\sum_{i=1}^p a_ix_i$, or equivalently, to approximate the mean of the terms, $\frac1p\sum_{i=1}^p a_ix_i$.

This can be done by selecting a random sample of the indices $1,\dots,p$, and taking the mean of $a_ix_i$ over the sample, and constructing the $z$ confidence interval, a standard statistical procedure. In order to apply a Central Limit Theorem type of result to show that this gives asymptotically correct confidence intervals, we would need some mild assumptions on the entries of $A$ and $x$ to ensure that, roughly speaking, the mean cannot be dominated by outliers in a small proportion of entries. If you had upper and lower bounds on the entries of $A$ and $x$, for instance, then you could use Hoeffding's inequality to bound the probability of the estimate exceeding a given margin of error.

Of course, this approach gives only a probabilistic approximation method; it cannot guarantee accuracy with 100% certainty. But this is not of practical significance, as long as the error probabilities can be made sufficiently low. And in any case, it's not too hard to show that there cannot exist a deterministic approximation algorithm running in sublinear time, so probabilistic approximation is all that we could ask for in this case.

If a separate confidence interval for each component is not a desirable form for the output, then the approach could probably be adapted to instead give a margin of error for the norm of the error vector (e.g., with respect to the $\ell^1$, $\ell^2$, or $\ell^\infty$ norms).


"Best algorithm" is a fuzzy term. The algorithm which is best for some particular case can very well be absolutely worst for another, similar problem. Problems differ in details (and not-so-details), in size, in available resources, sometimes an exact solution is essential, other times a rough approximation is good enough. And there are literally thousands of algorithms, with new ones added each day.


How to properly describe this behavior (in terms of time complexity)

You're interested in asymptotic behavior as $x$ increases without bound.

$O(.35 \times 2^y)$ is still $O(2^y)$.


An algorithm must have a finite description, whereas a deterministic process according to your definition can use an infinite lookup table. For example there is a deterministic process that solves the halting problem for Turing machines, but there is no such algorithm.


Proving a solution for the $n$-Queens Puzzle

Consider $i < j$ between 0 and $ n-1$. Of course, the first coordinate can’t be same for any two queens, hence they aren’t in same row.

Now, suppose, for the sake of contradiction, they lie on the same column. Then, $2(i-j) = nk$  for some natural $k$. Now, as n doesn’t contain 2 as it’s divisor, $k$ must be even. So, either $k$ is 0, which is not possible because that will contradict our assumption that $i$ and $j$ are not equal, or $k\geq 2$. In the latter case, $LHS = 2(i-j) < 2(n-1) < 2n \leq nk$, and hence $LHS \ne RHS$. Hence, we conclude that our assumption must have been incorrect and two queens positioned in this manner can’t lie on same column.

You still need to figure out the diagonal case.


Are synchronous message sends a subset of async. ones?

There are several possible semantics for asynchronous message passing, so there isn't a single answer to this question. It depends how the scheduler works.

From a theoretical perspective, the simplest model (for some version of simple) is to not have a scheduler. Once a message has been emitted, it may be received at any time when the receiver is ready. All the parts of the system work in parallel. This is the principle of process calculi, of which there is a rich theory.

The notion of synchronicity then depends on what the continuation of a send operation is. In the pi calculus, which is arguably the most important model of concurrency, sending is a synchronous operation, with a continuation. $\bar a\langle x\rangle.P$ (“send $x$ on $a$ then do $P$”) blocks until some other part of the system is ready to receive a message on $a$. An asynchronous send operation is represented by doing the send in parallel with something else:

asyncSend(target=a, message=x);
stuff();

is represented by $(\bar a\langle x\rangle. 0) \mid \mathtt{stuff}$ (send $x$ on $a$, then do nothing; all of this in parallel with stuff).

The join calculus is another process calculus inspired from the pi-calculus. It defines both asynchronous and synchronous messages. Synchronous messages act like function calls — they're remote procedure calls. Asynchronous messages have no continuation: once the order to send the message has been given, the message will sit around until it gets received; the only way to know that the message has been received is to take action on the receiver. The snippet above is represented by $a\langle x\rangle \mid \mathtt{stuff}$. The notation $a\langle x\rangle$ means “send $x$ asynchronously on $a$”; there's no continuation for the send operation: $\color{red}{a\langle x\rangle; Z}$ is not even syntactically valid. A synchronous call can be encoded with asynchronous calls by having the receiver reply. If the receiver sends an acknowledgement:
$$ a\langle x\rangle \mapsto  \mathtt{ack}\langle\rangle \mid \ldots$$
then the sender can wait for this acknowledgement:
$$ a\langle x\rangle \mid (\mathtt{ack}\langle\rangle \mapsto \ldots) $$
models

syncSend(target=a, message=x);
...

In the join calculus, synchronous and asynchronous operations are distinguished in the syntax. Therefore there's no possibility of “getting messed up”.

The mess comes from trying to force concurrent behavior into a sequential framework. Since you mention object oriented languages (which have absolutely nothing to do whatsoever about asynchronous message passing), you're probably thinking of implementations of these concepts in languages like Java and C#. I'm not familiar with those libraries, but as far as I know, they introduce additional complications by forcing the programmer to be explicit about threads. Threads are not a natural concept in process calculi: if things happen in a certain order, it's because of how the information is propagated, not because the language describes how a scheduler will do its job. A call like asyncSend may have additional constraints on when it takes place relative to other things that are going on in the same thread. If there is some constraint between an asynchronous send and a subsequent synchronous send, that's a limitation of the library which defines when the asynchronous send may take place. A true asynchronous send would not have such a constraint.


Are probabilisitc algorithms deterministic?

A probabilistic algorithm is one which has access to the output of a random source during its computation. It might be the case that although the algorithm uses randomness, the output is deterministic, i.e. for every possible random string obtained from the source the output is the same (you can always just ignore the source and act solely on the input).

Note that when you're dealing with probabilistic algorithms, your output becomes a random variable. The output can be deterministic in the sense that it is always the same, or can take some value with probability 1 (which is a weaker statement).


Showing that an algorithm is 2-approximation

The place to start is at the simplest case: $k = 2$. Suppose that the points in $S$ are $x,y$. Consider some optimal solution of value $1$. We consider two cases.

$x,y$ belong to the same cluster. Thus $d(x,y) \leq 1$. Since $y$ is the farthest point from $x$, all other points are at distance at most $1$ from $x$, and in particular at distance at most $1$ from $\{x,y\}$. This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base (either $x$ or $y$), and so the diameter of each cluster is at most $2$.
$x,y$ belong to different clusters. In this case, since the optimal solution has value $1$, each point other than $x,y$ is within distance $1$ of either $x$ or $y$ (the one which shares cluster with it). This means that in the clusters generated by the algorithm, each point is at distance at most $1$ from its base, and so again the diameter of each cluster is at most $2$.

See if you can generalize these ideas for $k > 2$.


$\omega$-string avoiding a set of substrings

If every $\omega$-string contains a substring in $S$, then we say that $S$ is unavoidable or a universal hitting set (UHS). There is a classical algorithm for detecting whether a set of substrings is unavoidable, described for example in Lothaire's Algebraic combinatorics on words, Section 1.6.
Construct a graph $G$ as follows. The vertices are all prefixes of strings in $S$. For every prefix $p$ and symbol $\sigma$, we connect $p$ to the longest suffix of $p\sigma$ appearing in the graph. The set $S$ is unavoidable iff every cycle in $G$ passes through a vertex corresponding to a word in $S$.
To see this, suppose first that every cycle in $G$ passes through a vertex corresponding to a word in $S$. Consider some $\omega$-word $w$. Starting at the vertex $\epsilon$, "read" the symbols of $w$ one by one. Eventually you will hit a cycle (since $G$ is finite). By assumption, this cycle contains a vertex $v$ in $S$, and so $w$ contains $v$. In the other direction, tracing an $S$-less cycle (replacing each edge by the symbol $\sigma$ used to create it) results in a periodic $\omega$-word which avoids $S$.


Color coding to get an FPT algoirthm for k disjoint triangles

The dynamic programming algorithm goes over all subsets of $[3k]$ whose size is a multiple of 3, in nondecreasing order of size. For each such non-empty subset, it goes over all $O(n^3)$ triplets of vertices, and for each one, it performs a single table look-up. Therefore the running time is $O^*(2^{3k} n^3)$, where $O^*$ hides $\operatorname{poly}(k)$ factors which are needed to manipulate indices.


Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate:

Stage 1: Calculate $M^2$

Stage 2: Calculate $M^3 = M^2 * M$ and $M^4 = M^2 * M^2$

Stage 3: Calculate $M^7 = M^4 * M^3$ and $M^8 = M^4 * M^4$

Stage 4: Calculate $M^{15} = M^8 * M^7$

This is one multiplication more than calculating $M^5$ in three multiplications and raising $M^5$ to the third power in another two multiplications, but should be faster if you have two processors. For arbitrary high powers, you will need more processors.

If you use a brute force algorithm for the multiplication, multiplying row by column, you may save some time by calculating one row of a product, then immediately using that row for the next product. This would help in the calculation of $M^3$ where we can start calculating $M^3$ as soon as the first row of $M^2$ has been calculated; it wouldn't be that helpful with $M^4$ since we need both rows and columns of $M^2$. For large powers, you could probably arrange which powers to calculate.

And after posting this it becomes obvious that you can use multiple processors very easily: You start by calculating the first row of $M^2 = M * M$. When you have that row, you have all the information you need to calculate the first row of $M^3 = M^2 * M$, so you calculate the second row of $M^2$ and the first row of $M^3$ in parallel. Then you can calculate the third row of $M^2$, the second row of $M^3$, and the first row of $M^4$ in parallel and so on.

This will do a lot more operations than necessary (for example, 14 matrix multiplications for $M^{15}$ instead of the minimal 5 or the 6 of the four-stage method). If the power is not large compared to the number of processors this will still be faster. But calculating $M^{1000}$ with four processors using this method will be inefficient; doing this in an optimal way would be an interesting problem.

Combining approaches: Using four processors for example, you can calculate AB, ABC, ABCD and ABCDE almost in parallel by calculating each product one row at a time. This allows calculate all four of $M^2$ to $M^5$ using four processors in about the same time as one product with one processor.

Given these four results and the original M, you can calculate four of the matrices $M^6$ to $M^{25}$ in the same time again, provided the matrices are at most five powers apart from each other. So each power up to $M^{25}$ can be calculated in about twice the time of a single processor matrix product.

With these matrices calculated, all matrices up to $M^{108}$ and some more up to $M^{125}$ can be calculated in three times the time of a single matrix product if four processors are available. With k processors this should go up to at least the power $k (k+1)^2$.


Example 1.
The empty language is recognizable and its complement (the language containing all the words) is also recognizable.
Example 2.
Any regular language is recognizable and, since regular languages are closed under complement, its complement is also recognizable.
Example 3.
The language $H = \{ \langle T, x \rangle : T \mbox{ is a Turing Machine}, x \in \{0,1\}^*, T(x) \mbox{ halts}\}$ is recognizable.
In order to recognize $H$ it suffices to build a Turing machine $M$ that checks if  $T$ is a valid description of a Turing machine, simulates $T$ on $x$ until $T(x)$ halts (possibly forever), and accepts.
The complement $\overline{H}$ of $H$, however, is not recognizable as if it was recognizable a Turing machine $M'$ for $\overline{H}$, together with $M$, would allow to solve the Halting problem. To do so simply simulate in parallel $M$ and $M'$ until one of them accepts.


Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?

Yes, your understanding is correct.  That's exactly the role the hash function plays.

A pair of keys $x,y$ might collide with one hash function, but not with another.  For any fixed set of keys, the expected number of collisions is small.  Moreover, for any fixed set of keys, the probability of having a large number of collisions is very small.  That's why we can say that the average-case running time is good, and why there's only a tiny probability that the running time is high.

To put it another way: Since the adversary doesn't know what hash function we will be using, he can't craft inputs (a set of keys) that will trigger worst-case behavior.  The randomization ensures we only need to worry about average-case behavior (the adversary has no way to force us into the kind of situation that would trigger worst-case behavior).  And, hash tables have excellent average-case running time.


NP-hardness of finding a subset of vertices in a vertex-weighted graph

The problem is polynomial-time solvable, suggested in Lemma 1 of the paper Computational Complexity of Some Maximum Average Weight Problems with Precedence
Constraints.

Basically the idea is to write a linear program on variables $x_i\in[0,1]$, where $x_u-x_v\leq 0$ if $(u,v)\in E$. The signed adjacency matrix is totally unimodular, so we can compute the integral optimum.


Origin of the terms "safety" and "liveness" for concurrent algorithm properties?

Lamport commented on his paper "Proving the Correctness of Multiprocess Programs" as follows:

  This paper introduced the concepts of safety and liveness as the proper generalizations of partial correctness and termination to concurrent programs. It also introduced the terms "safety" and "liveness" for those classes of properties. I stole those terms from Petri nets, where they have similar but formally very different meanings. (Safety of a Petri net is a particular safety property; liveness of a Petri net is not a liveness property.)

This can be seen as a claim that he (Lamport) has introduced the terms.


"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.


Selecting elements from two arrays to get a target sum

Here is an algorithm using dynamic programming. Let us define the function $C:V\times \mathbb{N} \rightarrow \mathbb{N}$ as $C(i, s) = r$, if using only the first $i$ indices we can achieve a sum of at least $r$ in B, when having a sum at list $s$ in $A$. This means $C(i, s) = r$ if there is an index set $I \subseteq [i]$, such that $\sum_{j \in I} A[j] \geq s$ and $\sum_{j \in [i] \setminus I} B[j] \geq r$. If $s$ is greater than the sum of the first $i$ elements in $A$, then set $C(i, s) = -\infty$ It is easy to build the transitions of the dynamic programming as follows. For each $i$ and $s$:
$$C(i+1, s) = \max\{C(i+1,s), C(i, s) + B[i]\}$$
$$C(i+1, s+A[i]) = \max\{C(i+1, s+A[i]), C(i, s) \}$$
The output is yes, if there is $s \geq k$ such that $C(n+1, s)\geq k$.

The correctness is pretty straight forward. The running time can be bounded in $O(nk)$.

On the other hand, this problem is NP-hard. It is easy to reduce the set partitioning problem to this problem. In the set partitioning problem, given a set of integers, you are asked to partition the set into two subsets having equal sums. Let $S$ be an instance of the set partitioning problem and $s$ be the sum of elements in $S$. Set $A = B = S$ and $k = s/2$. The correctness of the reduction is quite straight forward. That is why a pseudo polynomial algorithm (polinomial in the value of the input instead of its size) is the best we can hope for.


Not respecting the 3rd rule of a LL(1) grammar

Something like the following:

$\begin{align}
  S &\to A a \\
  A &\to a \mid \epsilon
\end{align}$


Explanation of proof of why connectedness is not conjunctively local of any order $k$

The predicate $\varphi_0$ depends on at most $k$ points. There are $k+1$ middle squares. So $\varphi_0$ cannot depend on all of them. That is, there is a middle square that $\varphi_0$ does not depend on. Therefore, if we add that square, the value of $\varphi_0$ doesn't change, and so $\psi$ is still 0, even though the figure is now connected.


Can a finite automaton have more than one regular expression?

There are multiple ways of writing the same expression, then I guess yes, it can be represented by many expressions.

For example, look at this DFA (with the initial state being final)

-->(a)________
    ^         |
    |         |
    |         V
    '--------(b)

the regular expression for it can take infinite forms, such as

$(ab)^*\;$ or $\;(ab)^*(ab)^*\;$ or $\;(ab)^*(ab)^*(ab)^*\;$ ...

If you consider different forms of the same expression, then it can be represented by lots of regexs, otherwise is just 1.


Would it be possible for a new technology to make RAM obsolete?

There is nothing special about RAM. Before electronic computers were invented, mechanical data sorters and tabulators used punched cards as their main (and only) memory. Early electronic computers used many different technologies for their main memory, including vacuum tubes, acoustic delay lines filled with mercury, the screen of a cathode ray tube and tiny rings of magnetic material looped around wires. If a memory technology was developed that was just as reliable as solid-state RAM and at the same time significantly faster and/or cheaper then it could certainly replace RAM and make it obsolete.


Comparing asymptotic complexity of functions $\log{n}$, $(\log{n})^c$ and $\sqrt{n}$

for any $c>1,\epsilon>0$,
$$\lim_{n\to\infty} \frac{(\log n)^c}{n^\epsilon} = 0$$

This means that $\log n=o( (\log n)^c)$ and $(\log n)^c = o(n^\epsilon)$. In particular, for $\epsilon =0.5$, $(\log n)^c = o(\sqrt{n})$.

See Reference answers to frequently asked questions


For dynamic programming problems, how do we know the subproblems will share subproblems?

The answer is - you don't.  Not in advance.  There are no guarantees and there is no silver bullet process.
Instead, dynamic programming is a way of thinking about a problem, a framework for approaching a problem.  You typically won't know whether that approach will be successful or not in advance.
Dynamic programming basically amounts to finding a recursive algorithm for the problem, and then speeding it up with memoization.  You'll have to try different recursive algorithms (different ways of decomposing into subproblems) and see, for each candidate, if it has the properties that are needed to apply these ideas successfully.  You usually won't know in advance whether any particular decomposition into subproblems will be successful.   You might be able to tell whether those subproblems will be "overlapping", but not whether it'll lead to a useful dynamic programming algorithm.  It's partly an art, where experience helps give you some intuitions for what kinds of subproblems might be useful in any particular situation.
I encourage reading What is dynamic programming about?, When can I use dynamic programming to reduce the time complexity of my recursive algorithm?, and Deciding on Sub-Problems for Dynamic Programming to get a sense of this perspective.
Personal opinion: I personally don't find "overlapping subproblems" as a very helpful way to think about dynamic programming.  I encourage you to use whatever works for you, but that one never worked very well for me.  If you want to understand it, think about algorithms that work on an array $A[1..n]$.  Divide-and-conquer will work on some subarrays, say $A[1..n/2],A[n/2+1..n],\ldots$, but no pair of those have a partial overlap.  Dynamic programming may work on all subarrays, say $A[i..j]$ for all $i<j$, and there are pairs of those that partly overlap (e.g., $A[3..5]$ overlaps with $A[4..9]$).  That's what is meant by "overlapping subproblems", and that is one distinction between dynamic programming vs divide-and-conquer.  That said, I don't find that a very helpful characterization, personally -- and especially, I don't find it helpful at designing an algorithm (it might be more helpful once I already have an algorithm and am wondering whether I should call it divide-and-conquer vs dynamic programming, but at that point I often don't care too much what we call it).


How to resize a large, distributed hash table?

Yes, after storing many items in a distributed hash table spread over a hundred computers, if hypothetically we used the sort of hash function popular for in-RAM hash table, adding another computer would cause every item to be re-hashed and nearly every item to move from one computer to another, which could take days.

So instead we use special hash functions specifically designed for DHT applications, which allow us to add computers and more-or-less immediately start using them and only re-arrange a few items. (Ideally, with around 100 computers, about 1 percent of the items in each and every computer already in the DHT would move to the new computer).
Confusingly, some people use "consistent hashing" to refer to any such system where relatively few items are re-shuffled when a new computer is added or removed from the system, although most use "consistent hashing" to refer to the one particular such system described below.

I now know of 4 different hash algorithms solve the distributed hash table problem, all of them (coincidentally?) published in 2001.
(Are there others?)

rendezvous hashing, also called highest random weight hashing (HRW):
A client with a list of computers Cj looks up some key K by giving each computer a score Sj = hash( K | Cj ).
The key, value pair K,V is stored on the computer with the highest score.
(For two-failure-tolerant systems, the key,value pair K,V is stored on the three computers with the highest scores).
consistent hashing:
A client with a list of computers Cj maps each computer to a location on the the edge of a circle. The client looks up some key K by starting at the point where K maps onto the circle, and walking clockwise until it hits a computer. (Each computer is actually mapped to many "replica" points on the edge of the circle). (For two-failure-tolerant systems, the key,value pair K,V should be stored on the first three different computers it walks across).
The "distance" walked is d = (unsigned int)(hash(K) - hash(Cj)).
In some implementations, such as Chord and Pastry, none of the computers nor the client really knows all of the computers in the DHT. The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer either responds with the (key, value) data item if it has it, or with a list of other, closer computers.
content addressable network (CAN) has some similarities to consistent hashing, except instead of a one-dimensional circle-edge, it uses a multi-dimensional torus.
Kademlia algorithm:
A client that only knows about a few of the computers in the DHT looks up some key K by finding the computers that are "close" to the key, where the "distance" is calculated as d = hash(Cj) XOR hash(K). (This abstract "distance" function is completely uncorrelated with the real, physical distance in miles between servers). The client sends a request to a few of the closest computers ''that it knows'', asking about the key. Each such computer consults its tables and reply with a list of the closest computers to the desired key ''that it knows''. The client sends a request to a few of those ever-closer computers, asking about that key, and repeats that process until no new nodes are returned that are closer than the best previous results. (For two-failure-tolerant systems, the key,value pair K,V should be stored on the three "closest" computers to that key K).

There is one additional technique often used to make adding a new computer to a DHT appear "instantaneous": indirection.
Immediately after adding a new computer to a DHT system, most items should remain in the same place, but there are typically lots of items that need to move from each old computer to the new computer -- it may take a day before all those items are moved, typically as a low-priority "background task".
Long before all those items are moved, each old computer sends a brief summary of those items to the new computer, and when some client asks the new computer for some particular item, the new computer either (a) admits to the client it doesn't have that file yet, and tells the client which one of the old computers still has that item, or (b) bumps up the priority of moving that item to a "foreground task", possibly streaming each block of that item to the client as soon as it is received from the old computer.


Are there any efficient algorithems to find packets similarities in a list?

There are many possible approaches for measuring document similarity:

edit distance
shingling
Jaccard similarity
TF-IDF and cosine similarity
https://stackoverflow.com/q/101569/781723
https://stackoverflow.com/q/8897593/781723
https://stackoverflow.com/q/29842137/781723

I suggest you think more about what metric makes sense for you, and review the literature on information retrieval and natural language processing to see what metrics have been used in other contexts.


Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying "run $M$ on all words from $\Sigma^n$" does make sense. But we need to be somewhat careful about the details here.

We could run $M$ on all $w \in \Sigma^*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there is a first word for which we learn that $M$ halts on it. But "first" here refers to our particular simulation, and to how long $M$ takes on the various words. This will generally not be the lexicographically first word; so this is not doing the job.

We could run $M$ on the words $w \in \Sigma^*$ in lexicographic order. But now, if $M$ doesn't halt on $0^n$, we never proceed beyond this particular simulation.

To prove that the function is indeed non-computable, mirror the proof of Rice' theorem.


First, "has no occurence of 123".

So the string can start with any number of 2s and 3s.
Then it has 0, 1 or more components that start with 1, and followed by any number of 2s and 3s other than 23. So the 1 is followed by nothing, a single 2, 22 and any number of 2s and 3s, or 3 and any number of 2s and 3s.

Each of these components could contain three or four consecutive 2s. Four consecutive 2s are not allowed, three consecutive 2s may only happen once. So for each of those components add things to not allow three 2s in a row, or to allow three but not four 2s in a row. And then the language is any number of components with no three 2s, optionally followed by a component with three 2s and any number of components with no three 2s.

It's a bit complicated, but not too bad.

So make regular expressions for "lead_2" = "any number of 2s and 3s, but no three 2s in a row", "lead_3" = "any number of 2s and 3s, with 222 once but not twice, and no 2222", "follow_2" = "1, followed by lead_2 not starting with 23", "follow_3" = "1, followed by lead_3 not starting with 23", and the whole language is

lead_2 (follow_2)* or
lead_2 (follow_2)* follow_3 (follow_2)* or
lead_3 (follow_2)*


Complexity of matrix inverse via Gaussian elimination

No, it's not true.  You can use Gaussian elimination to invert a matrix in $O(n^3)$ time, but there are other algorithms that are even faster.  The complexity of a problem is the running time of the fastest algorithm for that problem.  Therefore, it is not correct that the complexity of matrix inversion is $\Theta(n^3)$.

See https://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency, https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm, https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra, https://scicomp.stackexchange.com/q/22105/4274, Complexity class of Matrix Inversion.


Determining initial and final states from FA diagram

In your diagrams, a triangle points at the initial state, and double circles indicate final states. Inside the circles you can find the state names, such as x1.