how to derive the complexity of the randomization solution to the majority element problem

Given an array of length $n$, which is promised to have an element $x$ which appears more than $n/2$ times, the goal is to find $x$. Note that $x$ is unique.

The randomized solution goes as follows:

Choose a random element $y$.
Check whether $y$ appears more than $n/2$ times, in time $O(n)$.
If so, return $y$.
Otherwise, go back to the first step.

Since $x$ occurs more than $n/2$ times, the probability to select it is more than $1/2$. Hence the probability that we didn't choose it in the first $t$ attempts is less than $2^t$.

In order to calculate the expected time complexity, let us calculate the expect number of attempts until $y = x$; the expected time complexity would be that multiplied by $O(n)$.

Let $E_t$ denote the event the we got to the $t$th round, that is, that the first $t-1$ attempts did not result in choosing $y = x$. Let $X_t$ be the indicator variable for $E_t$. The number of rounds is thus $X = \sum_{t=1}^\infty X_t$. Linearity of expectation shows that
$$ \mathbb{E}[X] = \sum_{t=1}^\infty \mathbb{E}[X_t] = \sum_{t=1}^\infty \Pr[E_t]. $$
We get to the $t$th round if we failed to find $x$ in the first $t-1$ rounds, so $\Pr[E_t] < 2^{-(t-1)}$. Therefore
$$
\mathbb{E}[X] < \sum_{t=1}^\infty 2^{-(t-1)} = \sum_{t=0}^\infty 2^{-t} = 2,
$$
using the formula for the sum of a geometric series. We conclude that the expected running time of the algorithm is at most $2 \cdot O(n) = O(n)$.

Another way to compute $\mathbb{E}[X]$ is using geometric random variables. Suppose that $x$ appears in $pn$ of the elements; so $p > 1/2$. The random variables $X$ has distribution $G(p)$, that is, geometric with success probability $p$, and so
$$ \mathbb{E}[X] = \frac{1}{1-p} < \frac{1}{1-1/2} = 2. $$

A more sophisticated way to express this is that $X$ is stochastically dominated by a $G(1/2)$ random variable, and so $\mathbb{E}[X] \leq \mathbb{E}[G(1/2)] = 2$.


Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible

Hint, a correct regular expression is $1^*(00^*11^*00^*11^*00^*11^*)^*0^*$.

There are 6 states, where $q_{0,1}$ is the initial state. Both $q_{0,1}$ and $q_{0,0}$ are accepting states.

$q_{0,1}$: the number of 01s is a multiple of 3 and it ends with 1. Or empty word.
$q_{0,0}$: the number of 01s is a multiple of 3 and it ends with 0.
$q_{1,1}$: the number of 01s is 1 plus a multiple of 3 and it ends with 1.
$q_{1,0}$: the number of 01s is 1 plus a multiple of 3 and it ends with 0.
$q_{2,1}$: the number of 01s is 2 plus a multiple of 3 and it ends with 1.
$q_{2,0}$: the number of 01s is 2 plus a multiple of 3 and it ends with 0.


Given $n$ persons, this question is about a sequence of unordered pair of persons, called a two-person schedule(TPS). A TPS is good if any of its initial contiguous subsequences satisfies the following two conditions.

(fairness requirement) Any person cannot appear two times more than any other person.
(non-repeating requirement) Any unordered pair of persons can appear at most once.

This question asks the best way to generate a good TPS that is as long as possible.
Let us define a perfect TPS as a TPS that satisfies the following requirement.

(inclusive requirement) Each unordered pair of persons is included.

It turns out that a good TPS of the longest length must be a perfect TPS.
In fact, if each unordered pair of person compete with each other, this question is none other than the round-robin tournament as explained by Wikipedia, which has complete solutions. Because of the durability and reliability of wikipedia as well as the size of the solutions, readers are encouraged to check the wikipedia item as well as the references listed thereof. Also there are plenty of resource on the web if you search for "round robin tournament scheduling", such as a nice explanation of Round Robin Tournament Schedule and Javascript code to schedule round robin tournament.
A program that produces Perfect TPS
You can play with a scheduling algorithm in this Javascript playground. Modify the number of persons as you want to on the last line of the code, document.writeln(JSON.stringify(robin(8))). Hit Run code button. You will see output like the following.
[[[1,8],[2,7],[3,6],[4,5]],[[1,7],[8,6],[2,5],[3,4]],[[1,6],[7,5],[8,4],[2,3]],[[1,5],[6,4],[7,3],[8,2]],[[1,4],[5,3],[6,2],[7,8]],[[1,3],[4,2],[5,8],[6,7]],[[1,2],[3,8],[4,7],[5,6]]]


Is $n^2 \log n$ in $O (n^2)$ am confused

$n^2\log(n)$ isn't $O(n^2)$. You need to have a constant $c$, so since $\log(n)$ tends to infinity, for any fixed $c$ you will choose, at some point $\log(n)$ will pass $c$, that is: $\forall n>n_0: c < \log(n)$ for some $n_0$. This directly means that $\forall n>n_0: cn^2  < n^2 \log(n)$ which means that $n^2 \log(n)$ is asymptotically bigger than $cn^2$.


Is finding Kth largest element using selection algorithm taking O(n) only if K is fixed?

There is no requirement that $k$ be constant, and those StackOverflow comments are misleading or simply incorrect.

Obviously $k \le n$ and so $k$ is $O(n)$. Your partial bubblesort algorithm is $O(kn)$ which is $O(n^2)$ unless $k$ is somehow restricted.

But the Quickselect algorithm is stochastic $O(n)$ and can be made worst-case $O(n)$ by using the median-of-medians algorithm to select the pivot. (Median-of-medians is too slow for practical use, but it proves that $O(n)$ is possible.) Quickselect does not require $k$ to be fixed.


Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1

No, your solution is wrong.  The expected number of collisions is not $n- E(\text{occupied locations})$, so you went wrong in the first step of your approach.  Try working through a small example or two and hopefully you will see why.

It's possible that your confusion has to do with how we count the number of collisions.  If items A,B,C all go into the same hash bucket, we consider that as 3 collisions: A,B are a collision, B,C are a collision, and A,C are a collision.


Relational Algebra: existential quantifiers

Let me concentrate, as you asked, on section $(\exists d)(\exists t)(\cdots)$.
In case when one part of conjuction is "not depend" on letter under existence quantifier, holds
$$(\exists d)(A \text{ and } B)\Leftrightarrow  (\exists d)(A) \text{ and } B$$
Where we assume $B$ does not containt letter $d$.
$$$$
In your case, for simplicity, let make following designations:
$$\begin{array}{l}
A(d) = \text{ DEPARTMENT(d) }\\
B(t) = \text{ DEPENDANT(t) } \\
C(d) = (\text{e.Ssn = d.Mgrssn})\\
E(t) = (\text{t.Essn = e.Ssn})
\end{array}$$
and assume, that $A,C$ doesn't depend on $t$ and $B,E$ doesn't depend on $d$. Then we have
$$(\exists d)(\exists t)\big(A(d) \text{ and } B(t)\text{ and } C(d) \text{ and } E(t)\big) \Leftrightarrow \\
\Leftrightarrow (\exists d)\big(A(d) \text{ and } C(d)\big) \text{ and } (\exists t) \big(B(t)\text{ and } E(t)\big)$$
So, you are right, they are equivalent in reviewed case.
Generally we cannot distribute existence quantifier  with respect to $\text{AND}$(conjunction) operation as shows example: take $A=$"$d$ is even" and $B=$"$d$ is odd". Then, of course, sentence "$(\exists d)(A) \text{ and } (\exists d)(B)$" is true, but sentence "$(\exists d)(A \text{ and } B)$" is false.


Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?

Your optimal alignment seems to be an optimal local alignment, the best substring match. Needleman-Wunsch is for global alignment. With the simple program by Eddy that you can find on the internet I have determined a global score of 0. This is better than the gobal score you get:  -5 (for 10 gaps and 5 matches).

Sequence X: GCATGCU
Sequence Y: GATTACA
Scoring system: 1 for match; -1 for mismatch; -1 for gap

Dynamic programming matrix:
             G    A    T    T    A    C    A
        0   -1   -2   -3   -4   -5   -6   -7
   G   -1    1    0   -1   -2   -3   -4   -5
   C   -2    0    0   -1   -2   -3   -2   -3
   A   -3   -1    1    0   -1   -1   -2   -1
   T   -4   -2    0    2    1    0   -1   -2
   G   -5   -3   -1    1    1    0   -1   -2
   C   -6   -4   -2    0    0    0    1    0
   U   -7   -5   -3   -1   -1   -1    0    0

Alignment:
X: GCA-TGCU
Y: G-ATTACA
Optimum alignment score: 0


Are joins/pullbacks of bloom filters possible?

Ok, so the short answer to this question seems to be a "yes, but it grows quickly in size". You can view the bloom filters for each tuple element as vectors of bits. In that case, their tensor product will be a "bloom filter" for the cartesian product, where projection can be done by taking partial traces.
The downside of this is that the number of bits grows exponentially with the size of the tuple. You can mitigate this by maintaining a list of bloom filters for all pairs of tuple elements instead, which is still useful for constraint propagation, and gives projection as the intersection of the projection of each pair filter.


Regular language concatenation with superset

Simply put, this statement of yours:

  On the other hand $\tilde{L}$ seems to contain strings E does not, i.e. those
  that are formed by concatenating non-empty string from both languages.

is wrong.

As you say, $E$ contains every string containing only symbols from $A$. Since $L$ also only contains strings with symbols from $A$, $\tilde{L}$ must as well. Concatenating strings that have symbols only from $A$ will just get you another string whose symbols only come from $A$.

Your statement is flipped; it is $E$ that contains strings that $\tilde{L}$ may not.


What is the relationship between minimum sized vertex covers and complete graphs?

The size of minimum vertex cover in a complete graph $K_n$ (on $n$ vertices for $n > 1$) is equal to $n-1$.

It is easier to understand using the fact that minimum vertex covers correspond to the complements of maximum independent vertex sets. In a complete graph $K_n$ the maximum independent set is clearly has only one vertex and so the size of a minimum vertex cover is equal to $|V| - \text{ size of maximum independent vertex set} = n-1$.


Error in solution in Types and Programming Languages?

If $power2~m~n$ stands for $m^n$, then it should be

$$power2=λm.λn.n~m$$

Let's try it on $0^1$:
$$
\begin{array}{ll}
& power2~c_0~c_1 \\
= & (λm.λn.n~m)~c_0~c_1 \\
\rightarrow & c_1~c_0 \\
= & (λs.λz.s~z)~c_0 \\
\rightarrow & λz.c_0~z \\
= & λz.(λs.λz.z)~z \\
\rightarrow & λs.λz.z \\
= & c_0
\end{array}
$$
Works fine.

Let's try it on $1^0$:
$$
\begin{array}{ll}
& power2~c_1~c_0 \\
= & (λm.λn.n~m)~c_1~c_0 \\
\rightarrow & c_0~c_1 \\
= & (λs.λz.z)~c_1 \\
\rightarrow & λz.z
\end{array}
$$

Wait, we should have got $c_1$.

Although syntactically $λz. z$ is different from it, but it has the same behavior as $c_1$.
In fact, you can use the function $equal$ (ex. 5.2.7) to prove it:
$$
equal = λm. λn.~and~(iszro~(m~prd~n))~~~(iszro~(n~prd~m))
$$

By the way, another form of the power function, given in the solution to this exercise have the arguments swapped:

$$power1 = λm. λn. m~(times~n)~c_1$$.


This tree traversal sounds similar to a Best-first traversal where the heuristic function is based on your weight function w. This strategy uses a priority queue (e.g. a heap, in this case a max heap).
Consider the following algorithm. $G=(V,E)$ is a graph with vertex set $V$ and edge set $E$, $w(j,t)$ is the weight function taking a vertex $j \in V$ and a timestep $t$, and $S \subseteq V$ is the list of start vertices (one in each connected component of $G$). $G$ is not necessarily connected.
BestFirstTraversal(G=(V,E), w(j,t), S)
    visited = []
    t = 0

    # from [0, t):   heap is the order in which the vertices are visited
    # from [t, end]: heap is a max heap
    heap = S  # from t to the end is max heap

    # loop until all vertices have been visited
    while len(visited) != |V| do
        u = heap[t]  # get the max element

        # do something with u

        append u to visited
        append neighbors of u (not in visited) to heap
        t = t+1

        heapify(heap[t:])  # based on w at step t
    end while
end

Let $n = |V|$ be the number of vertices.
Run Time: BestFirstTraversal runs in $O(n^2)$.
Notice $S$ is a list of vertices, one for each connected component of $G$. This is necessary because there must be a starting point for each connected component. If we started from a single node in a graph with more than one connected component, we would never be able to visit the other connected components. Thus the loop will visit each node in $G$ from one of the starting vertices.
Thus the while loop runs $n$ times. Appending neighbors and heapify takes up to $O(n)$ work. Hence, $n * (2 * O(n)) = O(n^2)$.
Note, heap will contain the order of the vertices visited at the end BestFirstTraversal.
Hope that helps!


Compression of Random Data is Impossible?

Here's the Kolmogorov complexity argument that @YuvalFilmus mentions in his answer.

Your input here is a sed script of some size plus an input file of some size.  Say the total size of the sed script plus the file is $n$ bits.

There can be only $2^n$ inputs of size $n$ bits.  Even if I let you have a sed script of less than $n$ bits (and don't charge you for telling me how long the input is) there can only be $2^{n+1}$ possible inputs.  But there are $2^{n+8}$ possible strings of length $n+8$ bits, so you can produce at most $1/128$th of the possible $2^{n+8}$ bit strings.  That's less than .01, so paying 50:1 my expected value for the bet would be positive (about 0.60).  (And that's only giving you 1 byte to play with.)

In short, random strings that are compressible at all must be extremely rare.

Why your scheme is broken

Your probability calculations look fine to me.  And the idea of a birthday attack is so appealingly clever, it took me quite a while to see the real problem.

Your basic scheme doesn't compress.

Suppose you find a 4-byte substring that doesn't occur in the original string, and an 8-byte substring that occurs twice in the original string.

Then you are going to produce a "compressed" string of length $n$ bytes - 8 bytes - 8 bytes + 4 bytes + 4 bytes, plus a sed replacement script which must be of length at least 4 bytes + 8 bytes.  Add that all together and we get $n+4$.

If the longer string is length $l$ and repeats $r$ times and the shorter string is of length $s$ then in general your scheme reduces the string length by

$$ (l-s) r - (l+s).$$
So $l=7$, $r=3$, $s=4$ "works" (saves 2 bytes), but the probability of finding a 7 byte substring that repeats 3 times is infinitesimal.


Can CFGs generate all languages? Are they (PDAs) finite or infinite state automata?

Since each context-free language can be described by a grammar, there are only countably many context-free languages (over a fixed alphabet). Therefore, "most" languages are not context-free. Examples of particular languages which are not context-free abound. Your language $\{ 1010^210^3\cdots 10^n : n \geq 1 \}$ is one such example. It can be proved to be non-context-free using the pumping lemma, for example.
Push-down automata have finitely many states, but an infinite stack. Although the stack is infinite, it can only be accessed in very specific ways, and this severely limits the power of the automaton. If we replace the stack with a queue, or add a second stack, then the automaton becomes much more powerful – equivalent to a Turing machine. But even such automata can only accept countably many languages. In particular, they cannot accept uncomputable languages such as that of the halting problem, as shown by Turing.


Analysis of brute force decoder in a $q$-ary erasure channel

To upper bound the first probability, we can assume without loss of generality that the sent codeword is the zero codeword. After deleting $|J|$ rows, we are left with a random $(n-|J|)\times k$ matrix $A$, and we want to bound the probability that its (right) kernel is non-trivial, that is, that there is a non-zero vector $x$ such that $Ax=0$. For any non-zero vector $x$, $Ax$ is a uniformly random vector (why?), and so the probability that $Ax=0$ is $q^{-(n-|J|)}$. Since there are $q^k-1$ many non-zero vectors $x$, the union bound shows that the probability that one of them satisfies $Ax=0$ is at most $q^k \cdot q^{-(n-|J|)}$. We can slightly improve on this by considering vectors up to scalar products, which reduces the probability by a factor of $q-1$.

The second half involves applying Chernoff's bound (also known as Hoeffding's bound) to show that it is unlikely that there are many erasures, and then applying the bound in the first half. Choose the threshold so that $q^{k-n+|J|} \leq q^{-\epsilon n}$.


First, be carefull, it might be that PSPACE ⊄ PSPACE-complete. If you suppose PSPACE ⊆ PSPACE-complete (thus PSPACE = PSPACE-complete since the other inclusion is true), then every problem of PSPACE is PSPACE-complete.
Thus, all problems of PSPACE can be reduced to some easy problem of P (which is also in PSPACE). This is very unlikely (but not (yet) proved true or false).

Now, let us consider the reduction you propose.

If I understood well, you want to take a formula of SAT. The reduction would be to take the same formula for QBF (with, I suppose, an existential quantifier for each variable, otherwise it would not be a valid QBF formula).

This is indeed a valid reduction, and the SAT formula would be satisfiable if and only if the QBF formula was true.

By doing so, you reduce SAT to QBF. This shows that QBF is at least as hard as SAT. Since SAT is NP-complete, this shows that QBF is NP-hard.

The reduction in the other way (taking a QBF formula and making a SAT formula) is not known. This is why we do not know whether NP=PSPACE or not.


Specify an upper bound of the size m of R with the big O notation

Are upper bound of the size m and runtime two different concept?

The concept is just upper bounding. It doesn't matter whether you're bounding the number of vertices in a graph, the number of steps a program takes to execute, or the number of elephants in India – it's just an upper bound.

Probably the first time most CS students see big-O notation is in the context of runtimes and it's a common mistake to assume that big-O somehow means runtime. But it doesn't. This is the same mistake as, "The first time I saw numbers, they referred to somebody's height. Therefore, numbers mean height."


solving large nonlinear systems in parallel

The main point of Krylov-Newton is that it does not require computing and storing the whole Jacobian matrix. It only requires the ability to apply the matrix to a vector.

The stardard approach is to do a little bit of pencil and paper work to figure out how to express the action of the derivative without actually computing and storing the whole matrix. If this is not possible, one can try to figure out a compressed representation of the matrix.

For problems where the matrices are dense, but the long range interactions are low rank (I think many radiative transfer problems would fall in this category..?), fast multipole or H-matrix type methods tend to be very effective.

It's difficult to give further advice without knowing more specifics of the problem.


It's up to you to decide. It's a pathological case which is quite similar to the empty graph (on zero vertices) — sometimes it makes sense to admit it, and sometimes not. It depends on the circumstances. The definition in Wikipedia is irrelevant here — there are many other similar definitions in the literature, that might disagree on this point.

I recommend the classic article Is the null-graph a pointless concept by Harary and Read.


Number of ways painting graph in two colors, such that two nodes of same color are linked by edge

Call a coloring where two nodes of same color must be linked by an edge (a.k.a. adjacent) attractive-coloring. The more common node coloring, where no two adjacent nodes are of the same color will be called repulsive-coloring.

Let $G$ be a given graph and $G'$ be the complement graph of $G$, i.e., $G'$ and $G$ are on the same nodes such that two distinct nodes of $G'$ are adjacent if and only if they are not adjacent in $G$.

An attractive-coloring of $G$ is an repulsive-coloring of $G'$ and vise versa. So the number of attractive-2-colorings of $G$ is the number of repulsive-2-colorings of $G'$. Note that a 1-coloring is considered a 2-coloring.

A graph can have a repulsive-2-coloring if and only if it is a bipartite graph. A connected bipartite graph has exactly two repulsive-2-coloring, i.e., assuming the two colors are red and black, we can color all nodes in one group red and all nodes in the other group black or the other way around.

Suppose the connected components of $G'$ are $C_1, C_2, \cdots, C_k$. If one of them is not bipartite, then there is no repulsive-2-coloring for that component and hence no repulsive-2-coloring for $G'$. If all of them are bipartite, then there are two repulsive-2-colorings for each of them and hence $2^k$ repulsive-2-colorings of $G'$.

Exercise (the well-known theorem on 2-colorable graphs). The (repulsively-)2-colorable graphs are exactly the bipartite graphs.


optimal lifted phylogenetic alignment - how to improve time complexity?

Consider a node $x$ with children $x_1,\ldots,x_d$, and denote by $N(v)$ the number of leaves in the subtree $T(v)$ rooted at $v$. We can implement the processing of $x$ as follows:

Go over $1 \leq i \leq d$:

Choose a leaf $f_i \in T(x_i)$ as the label of $x$ and $x_i$.

For all $j \neq i$, choose the leaf $f_j \in T(x_j)$ that minimizes $D(f_i,f_j) + d(x_j,f_j)$.

Store $d(x,f_i) = \sum_{j \neq i} [D(f_i,f_j) + d(x_j,f_j)]$.

The processing time of $x$ is proportional to
$$
\sum_{i=1}^d N(x_i) \times \sum_{j \neq i} N(x_j) = \left(\sum_{i=1}^d N(x_i)\right)^2 - \sum_{i=1}^d N(x_i)^2 = N(x)^2 - \sum_{i=1}^d N(x_i)^2.
$$
Summing over all nodes $x$ up to the root $r$, we see that the total processing time is proportional to $N(r)^2 = k^2$.


If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $.

It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a compressed trie the all the path of degree-1 nodes are merges to an edge, so you are done. For an uncompressed trie, I am afraid, you can have many degree-1 nodes. Say you have one letter $a_i$ that is very common and has a high probability of $1-\varepsilon$ and $\varepsilon\in \Omega(1/n^2)$. Then your trie contains many long degree-1 paths with high probability. In this case the you can have more than $O(n)$ interior nodes. Please do the computations by yourself (you might choose a smaller $\varepsilon$ if you like).


Is the Berman-Hartmanis Conjecture Solved?

The conjecture remains open. Also there is a proof that shows that if the conjecture is true, then P=/=NP. To my knowledge no one has proven the opposite, that if the converse is true then P=NP, to be true.


Hash tables - probing for collisions run time

The average number of positions addressed is
$$ \frac{1}{2} \left(1 + \frac{1}{1-\alpha}\right) $$
for linear probing and $1 + \alpha/2$ for chained hashing. Here $\alpha$ is the load factor. For each constant $\alpha$, this average is constant, but it depends on $\alpha$. The expression $1/(1-\alpha)$ blows up as the table gets full ($\alpha \to 1$), which is probably what is meant by the dependence is at least linear. The dependence is on the load factor rather than on the absolute number of elements in the table, which is not the deciding factor.

Usually, a linear dependence (not to be confused with the same terminology from linear algebra!) would be $\Theta(\alpha)$, at least linear would be $\Omega(\alpha)$, and more than linear $\omega(\alpha)$; but here $\alpha \to 1$ rather than $\alpha \to \infty$ so terminology is not standard. Perhaps the correct variable, which does go to $\infty$, is $1/(1-\alpha)$. In this case, we do have linear dependence for linear probing.


Why does packet delivery time only count transmission time once?

After the transmission time has passed, the last bit of the packet has just been put on the wire. That bit (just like all the others) will take an amount of time equal to the propagation delay to reach the receiver. When the last bit reaches the receiver, all the earlier bits will have reached it. So the total time taken is the transmission time plus the propagation delay.

It might be easier to visualize what's going on if you think about a train instead of a data packet. Imagine that we're standing by the track, some distance apart. We want to know how long it is from when the front of the train passes me (the time at which "I start sending the train to you") until the whole train has passed you (the time at which "you finish receiving the train"). This is equal to the time it takes the whole train to pass me (transmission time), plus the time it takes the back of the train to reach you (propagation delay). Or, if you prefer, it's equal to the time it takes the front of the train to reach you (propagation delay) plus the time it takes the rest of the train to pass you (transmission time).


Scheduling a sequence of queue operations that push and pop items at specified times

Initial Direction

Solving this problem is equivalent to solving a set of equations with constraints.

Denote the number of time units in an interval between consecutive input $t^{in}_i$/$t^{out}_i$ by $K_i$.

In the above example in the question there are three intervals:

|PUSH($T_2$) | PUSH($T_1$)|---------------|POP($T_1$)  |POP($T_2$)|

|---------------|---------------|---------------|---------------|---------------|

$K_1=0$.
$K_2=1$.
$K_3=0$.

The depth of the FIFO at the beginning and end of each such interval is the number of PUSHs minus POPs made before it, denote it by $d_i$.

In the above example:

$d_0=0$.
$d_1=1$.
$d_2=2$.
$d_3=1$.

Denote by $x_i\in \mathbb{N}\cup\{0\}$ the number of PNP assigned in interval $K_i$, then $x_i\leq K_i$.

In the above example:

$x_1\leq 0$.
$x_2\leq 1$.
$x_3\leq 0$.

Per data unit $T_i$ add an equation asserting it is available at the head of the FIFO at time $t^{out}_i$ by adding $d_i+x_{i+1}$ modulo the depth, $d_{i+1}$ of the FIFO per interval. In the above example:

For $T_1$: $(1+x_2)\bmod 2=0$.
For $T_2$: $((( (0+x_1)\bmod 1+x_2 ) \bmod 2)+x_3) \bmod 1 =0$.

And the solution is $x_1=0, x_2=1, x_3=0$ corresponding with the solution above.

But I'm not sure how to use this information to understand the complexity of the problem.


Finding the best N length combination between M items

This problem is similar to Knapsack Problem and it is NP-Complete. You may find its proof in here


According to these slides, deciding whether a single atom is generated by a Datalog program is EXPTIME-complete. There are several corresponding machine models, for example an EXPTIME Turing machine or an EXPTIME RAM machine.


You can use the pumping lemma to show that a language is not regular. Here, you're trying to prove that if $L_1$ is regular then $L_2$ is regular. The pumping lemma can't be used to prove this implication. It could be used to prove the contraposite (i.e. you might be able to prove that if $L_2$ is not regular, then $L_1$ is not regular by the pumping lemma). However, even assuming this can work (I haven't checked), it would be a lot more complicated than necessary for this result.

You write “what if $v$ is non-regular?” But this doesn't make sense: the concept of regularity applies to a language, not a word. For a given $u$, what language does $v$ have to belong to, in order for $uv$ to be in $L_2$?

If that's not enough of a hint, try reasoning with regular expressions. If $L_1$ is regular, then there is a regular expression that characterizes it. How can you use this regular expression to characterize $L_2$?


In Disjoint Sets, why do we make the smaller tree the subtree of the larger one?

Probably best explained with pictures. Say we have these two sets $A$ of height 2 and $B$ of height 3:

Now we have a choice when joining them:

Attach root of $B$ to root of $A$.
Attach root of $A$ to root of $B$.

Remember we are optimizing for look-up / $find()$. Let's see what happens in either case.

Attach root of $B$ to root of $A$.

We end up with this resulting set of height 4:

Attach root of $A$ to root of $B$.

We end up with this resulting set of height 3!

Wonderful! We've increased the size of the set without increasing the height. In this scenario our find will take at most 3 iterations, same as what we originally had because $B$ was of height 3 to begin with. In the other scenario we have at most 4 iterations because we've increased the height of the new set by 1. This is why it is always preferable to join the shorter tree to the taller one, because it will not increase the height of the taller tree (unless they are the same height). Thus, optimizing for look-up.


Evaluation metric for an ordering algorithm

One standard measure is the Kendall tau distance, which is the number of "inversions", i.e. positions $i < j$ such that $\pi(i) > \pi(j)$. It is also the number of transpositions $(k \; k+1)$ you need to apply to sort $\pi$, or vice versa, the number of such transpositions needed to generate $\pi$. (So it's the distance metric in the Cayley graph of $S_n$ with respect to the transpositions $(k \; k+1)$, which form a generating set.)


Approximately counting the number of marked elements in a list of n numbers

You calculate the average number of balls in a box (k / n), and the variance. From this you calculate the estimated number of balls and the variance when probing m random boxes. Convert variance to standard deviation. The number of balls will be normal distributed, and there is a simple formula for diverging by more than k standard deviations.


Principles of Programming Languages: Understanding Judgements

The --> is the relation that the judgement rules are defining. It's usually pronounced "steps to" or "reduces to". You can think of this relation as the analogue of "showing your work" in algebra:

(1 + 2) * 3 --> 3 * 3 --> 9

It's used as a way of specifying the semantics of a programming language through a binary relation on programs. These kinds of semantics are called small-step semantics. Within small-step semantics, there are approaches include reduction semantics and structural operational semantics. If the program is augmented first to a "configuration" that includes extra components like environments and stores, and the relation is on these configurations instead of just plain program terms, then it's called an abstract machine semantics.

Note: Sometimes you define multiple relations and build up more complicated relations out of them, so you have different arrows.

There are other kinds of operational semantics (eg big-step semantics) and there are other kinds of semantics besides operational semantics.


Time complexity of checking whether a string exists in a HashSet

You are right in that to check membership (or to retrieve) using a hash function, you also need to check that the retrieved element is equal to the element in question. For a string, you should assume that this takes time linear in the length.
Hence checking membership in a hash set is indeed expected $O(m)$.


Does P not NP imply NP COMPLETE disjoint from RP?

You have not accurately summarized the statement in Wikipedia.  The statement in Wikipedia also needs the extra assumption that $P=BPP$, which is widely conjectured but has not been proven to be true.
With that clarification, no reference is needed -- the reasoning is straightforward and already described on Wikipedia.  If $P=BPP$, then $P=RP=co-RP$ (since $BPP=co-BPP$ and $RP \subseteq BPP$ and $co-RP \subseteq BPP$).  If additionally $P \ne NP$, then it follows that $RP \ne NP$.
Yes, if $RP \ne NP$, then $NPC \cap RP = \emptyset$.


Info about dataset from which a Huffman tree was generated

My claim was not true. I've found counterexample on mathworld. If you look on the 4th level, you will see that 5th element is not in the correct position (if my statement were to be true).


Which closure properties are always valid between regular, context-free and non context-free languages?

I am afraid that there is no better general result than the obvious one.
Assume that $\mathcal K$ and $\mathcal L$ are two families of languages with $\mathcal K\subset \mathcal L$ such that $\mathcal L$ is closed under the operation $\circ$. Then for $K\in\mathcal K$ and $L\in \mathcal L$ we have $K\circ L\in \mathcal L$.
This is obvious, as both $K,L\in \mathcal L$. Usually we can choose simple examples that we can't do better. For instance, choose a "difficult" language in $\mathcal L$, so $L\in \mathcal L \setminus \mathcal K$. Then $L=\varnothing \cup L$, $L=\Sigma^*\cap L$, and $L=\{\lambda\}\cdot L$ show that we cannot do better than $\mathcal L$.


What is the time complexity of this algorithm?

In Python, range(0,n) iterates through the values 0, 1, 2, .., n-1 (but not n).  Therefore, your summation should have been

$$\sum_{i=0}^{n-1} \cdots$$

rather than

$$\sum_{i=1}^{n} \cdots$$

and similarly for the other sums as well.


Assembly language translation to machine code (process in "RAM")

In modern computers, assemblers do not deal directly with in-RAM machine code anymore. Their job is to translate the textual representation of the assembly language to opcode combinations, in a form that is not completely finished because exact addresses are not decided yet.

Both the tetx and its translation are stored in disk files, they only reside in RAM while translation takes place.

A next step is performed by another utility, the linker, which performs address assignments and creates another file, called the executable, and will also reside on disk.

When you want execution to take place, a third program called the loader will read the opcodes from disk and write them in RAM memory where it belongs. Then the loader will tell the operating system that a new task is ready for execution and eventually control will be passed to the program you have written and which is now loaded in RAM.

(This explanation is really simplified as there are many intervening steps and other goodies to consider.)


Doubt regarding strong component in a graph

Your question is a bit too broad. There can be a lot of properties $P$ such that if $H$ is a subgraph of $G$ and $P(H)$ holds then all vertices of $H$ are in the same strong component.

For example:

$P(H) = $ true iff H is a (directed) clique
$P(H) = $ true iff H contains only one vertex
$P(H) = $ true iff for every edge $(u,v)$ of $H$, $(v,u)$ is also in $H$.
$P(H) = $ true iff $H$ has $n>1$ vertices and more than $(n-1)^2$ edges.
...

You can prove that the last condition implies that the vertices of $H$ are in a strong component by induction on $n$.

If $n=2$ then the graph has more than $1^2 = 1$ edge, i.e., it has at least two edges. The claim trivially follows.

If $n>2$, then let $H'$ be any (not necessarily proper) subgraph of $H$ with $(n-1)^2+1$ edges. Pick a vertex $v$ of minimum degree in $H'$. The degree $\delta$ of $v$ is at most $\frac{(n-1)^2+1}{n}$. Therefore $H-v$ has $n-1$ vertices and at least $(n-1)^2 + 1 - \delta = \frac{n(n-1)^2+n - (n-1)^2 - 1}{n} > (n-2)^2$ edges. By inductive hypothesis $H-v$ is strongly connected. The claim follows since $\delta$ is at least $(n-1)^2 + 1 - (n-1)(n-2) = (n-1)(n-1 -n +2) = (n-1) + 1 = n$, showing that $v$ has at least one incoming and one outgoing edge.


Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

Both definitions are equivalent, and I think you have almost specified the reason behind it.
The below equivalence work in both ways.
From Definition 2:
"the chance of a collision between distinct keys $k$ and $l$" $\le$ $1/m$
$\Leftrightarrow$
{note that the "chance" here is about the process of picking $h$ from the class $\mathscr{H}$}
(Number of functions in the class where $k$ and $l$ collide) $/$ (Total functions in the class) $\le$ $1/m$
$|A|/|\mathscr{H}| \le 1/m$
$\Leftrightarrow$
$|A| \le |\mathscr{H}|/m$
(which is the wording used in Definition 1)


Optimization problem where penalty is sensitive to permutation

I will outline two different solution methods.  Either one will work -- pick whichever one you find easiest to understand and implement.

Dynamic programming

This can be solved using dynamic programming.  We'll fill in a one-dimensional table, so that $T[s]$ stores the penalty of the best (lowest-penalty) way to obtain a sum of exactly $s$.  Once we've filled in all of the entries, $T[20]$ will tell you the lowest penalty achievable for any combination that sums to 20.

So how do we fill in the table entries?  We can fill them in recursively:

$$T[s] = \min(T[s-1]+p(s-1,1), T[s-2]+p(s-2,2), \dots, T[s-5]+p(s-5,5))$$

where $p(s,k)$ is the penalty for adding the number $k$ when the intermediate sum is $s$.  In the question, you tell us that $p(s,k) = k$ for $0 \le s < 2$, $p(s,k) = 2k$ for $2 \le s < 6$, etc.

Also, we have the base cases $T[0] = 0$.  As a convention, we'll agree that $T[-1]=T[-2]=T[-3]=T[-4]=\infty$.  Then you can fill in $T[1],T[2],\dots,T[20]$ in that order, using the recursive formula above.

This will give you the penalty of the best way to achieve the sum $20$.  If you also want to output the specific combination that achieves that penalty, you can keep track of that with a small modification.  Basically, each time you fill in a $T[i]$ entry with some penalty value, on the side keep track of the combination that led to that penalty value.

Graph search

Construct a weighted directed graph, with vertices 0, 1, 2, .., 20.  Each vertex corresponds to a possible intermediate sum.  From each vertex (intermediate sum) $s$, add five outgoing edges, corresponding to the five possibilities for the number you add.  The length of the edge from $s$ to $s+i$ (for $i=1,2,\dots,5$) is the penalty for adding $i$ to an intermediate sum $s$, according to the rules described in your question.

Now find the shortest path from vertex 0 to vertex 20 in this graph.  That path will correspond to a combination of values that sum to 20, and the total length of that path will correspond to the penalty of that path.  The shortest path will correspond to the combination with lowest penalty.  You can use any standard algorithm for computing shortest paths in a graph, such as Dijkstra's algorithm.


Average number of comparisons in sorted insertion

Well, that would strongly depend on the algorithm that you use to find out where to insert the new element, and on the distribution of new elements.

Assuming that you do a linear search, and the new element could go to any position with the same probability, your result is close, but not quite exact. The new element can go into one of (n + 1) positions, not n. There may be up to n comparisons needed; n comparisons are needed both if the new element goes into the first array position, and if it goes into the second array position. So the result is

(1 + 2 + 3 + ... + (n-1) + n + n) / (n + 1) =

= (n (n+1) / 2 + n) / (n + 1)

= n (n + 3) / 2 / (n + 1)

= (n + 2 - 2 / (n + 1)) / 2 ≈ (n + 2) / 2,

which is just a tiny bit more than your answer (n + 1) / 2.


Modelling of minimal NOR-circuit problem with CP

This is a logic synthesis problem.  Specifically, without the "fan-out of 1" limitation, this looks like the circuit minimization problem.  Circuit minimization is $\Sigma_2^P$-complete, so you should not expect any efficient algorithm for it.  There are many algorithms in the literature that you can explore, including Karnaugh Maps, Quine-McCluskey, Espresso, and others.  I wouldn't consider constraint programming the obvious first way to approach this problem.

If you have a requirement to use constraint programming for some homework exercise, well, you should do  your own exercise, but here is a hint: you should be able to tell whether there exists a circuit of depth $d$ and width $w$ by building a $d \times w$ grid of NOR gates, then using decision variables to represent which edges are used to connect these gates.  How could you use that to solve the original problem?

Limiting fan-out to 1 seems unrealistic, as gnasher729 explains.


Looking for Methods in Computer Vision for Distinguishing Disappearing and Fading Objects

There are probably many possible approaches, but I'll suggest one candidate step-by-step approach that I think might work well, given the information shown in your question:

1. Find the times

As a first step, I suggest that you estimate $Ta1,Ta2,Tb1,Tb2,Tb3$.

The good thing is that $Ta1,Ta2$ will be the same for all pixels of object A, and $Tb1,Tb2,Tb3$ will be the same for all pixels of object B.  This means you only need to estimate 5 numbers, and you have an entire video to work with -- so you should have more than enough data to infer these 5 times.

One reasonable way to do this would be to do foreground-background segmentation to identify the foreground pixels, using the Running Gaussian Average with Selective Background Update method you already tried; as you said, this is already fairly accurate.  It won't need to be perfect -- just getting it approximately right should be enough for what I'm going to suggest.

When you've done that, pixels inferred to be foreground pixels will be a mixture of object A and object B (plus a little bit of error).  Now looking at just the inferred foreground pixels, you should be able to deduce $Ta1$, $Ta2$, $Tb1$, $Tb2$, $Tb3$.  For instance, at each time, compute the average pixel intensity over all foreground pixels, and graph this as a function of time.  You should find that this time series is roughly constant until $Ta1$, then has a large increase at $Ta1$, another large increase at $Tb1$, a big decrease at $Ta2$, and a smooth decrease from $Tb2$ to $Tb3$.  Each of those increases/decreases should be easily detectable in the signal.

For instance, you could take the first derivative of this time series (the average intensity of the foreground pixels) and look at its peaks.  You should find large positive peaks at $Ta1$ and $Tb1$ and a large negative peak at $Ta2$.  Apart from those three times, the first derivative should be close to zero for all time periods, except that it is a significant negative value from $Tb2$ and $Tb3$.  I suspect these two characteristics should be enough to identify $Ta1,Ta2,Tb1,Tb2,Tb3$.

If that's not accurate enough, there are alternative approaches; ask if you need them.  But I expect it will be relatively easy to implement this step and find the times $Ta1,Ta2,Tb1,Tb2,Tb3$.

2. Build a three-class classifier

Now that you know the times $Ta1,Ta2,Tb1,Tb2,Tb3$,
I suggest that as your next step you build a classifier that takes the time series for a particular pixel and classifies it as one of three classes: A (object A), B (object B), or Bg (background).

It will probably suffice to build a simple classifier by hand.  My guess is you probably won't need terribly sophisticated methods.  I'd suggest you identify a few features, and for each pixel, compute a feature vector (the values of those features, for that particular pixel).  There are some natural features you could use, for instance:

$\text{avg}([Ta1+\varepsilon,Ta1+2\varepsilon])-\text{avg}([Ta1-2\varepsilon,Ta1-\varepsilon])$, where $\text{avg}([t_1,t_2])$ is the average intensity of the pixel taken over times in the interval $[t_1,t_2]$.  This basically tells you how large a "jump" in the signal there is, at time $Ta1$; for A you expect it to be large, whereas it should be approximately zero for B and Bg.
$\text{avg}([Ta2+\varepsilon,Ta2+2\varepsilon])-\text{avg}([Ta2-2\varepsilon,Ta2-\varepsilon])$.  For $A$ you expect this to be very negative, whereas it should be approximately zero for B and Bg.
$\text{avg}([Tb1+\varepsilon,Tb1+2\varepsilon])-\text{avg}([Tb1-2\varepsilon,Tb1-\varepsilon])$.  For B you expect it to be large, whereas it should be approximately zero for A and Bg.
$\text{avg}([Tb3+\varepsilon,Tb1+3\varepsilon])-\text{avg}([Tb2-2\varepsilon,Tb2-\varepsilon])$.  For B you expect it to be very negative, whereas it should be approximately zero for A and Bg.  (unless $Ta1$ or $Ta2$ falls within the interval $[Tb2,Tb3]$, in which case you can also figure out what you expect it to be: very positive for A if $Ta1$ is in the interval but $Ta2$ isn't; very negative if $Ta2$ is in the interval but $Ta1$ isn't; or zero if they're both in the interval)
The fraction of the time points that your Running Gaussian Average with Selective Background Update method classifies the pixel as background.  For A and B we expect it to be small; for Bg we expect it to be large.

You might be able to build a classifier simply by setting thresholds for each of these features and using the result to select which object you have.

If that's not accurate enough, you could imagine training a classifier using some machine learning method (e.g., logistic regression, linear SVM, etc.).

Now apply this classifier to each pixel separately, to classify it as belonging to object A, object B, or the background.

3. Optional: Clean up the results

You could optionally clean up the results by using spatial locality: we expect object A to be a connected region in the image, and same for object B.  For instance, if a pixel belongs to object A, then that makes it incrementally a bit more likely that the neighboring pixels belong to object A.  Or, a more sophisticated version of this is: if two adjacent pixels have approximately the same color, then they're a bit more likely to belong to the same class; if they have very different colors, there are no restrictions (they might belong to the same class, or might belong to a different class; each is equally plausible).

There are methods to take this information into account.  For instance, suppose your classifier outputs not just its predicted class, but also a probability for each of the three classes (e.g., 90% chance this particular pixel is object A, 8% chance it is object B, 2% chance it is background).  Then you can combine this with a graph cut method to take into account spatial locality, i.e., to find a segmentation that both takes into account your classifier's predictions and also takes into account spatial locality.

This kind of post-processing might further enhance the accuracy of your method, by cleaning up the boundaries of the objects.


Closure properties of finite state transducers

It is probably a better idea first to concentrate on the complement, i.e., the equality language $\{ w\in \Sigma^* \mid T_1(w) = T_2(w) \}$.

Also, simple FST's will do, as even for morphisms $h_i: \{a,b\} \to \{1\}^*$, $\{ x\in \{a,b\}^* \mid h_1(x) = h_2(x) \}$ need not be regular.

And I want to add that it has been shown that $\Delta(T_1,T_2)$ is always context-free.


Understanding DIQKD protocol, a few questions

All of these are defined in page 2 of that paper.

1) A round is a single interaction with the device: Alice gives it an input, Bob gives is  an input, and the device outputs a bit to Alice and a bit to Bob.

2) While Alice's input is from the set $\{0,1,2\}$, the output she gets from the device, $a_i$, is a single bit. Then, the equation $a_i \oplus b_i = x_i \wedge y_i$ is on bits (the case of $x_i=2$ is treated separately). This equation is indeed the CHSH condition. If the bits where classical, the expected CHSH term is bounded by $2$, while if the system is quantum, values of up to $2\sqrt2$ are possible. By measuring the amount of times the equation holds you can estimate the value of the expected CHSH term, and if it is large enough, this implies the generation of "true" randomness.

There is a longer and more detailed version of that paper in
https://arxiv.org/abs/1210.1810


Are SAT problems with at most two false clauses NP-complete?

Yes.  You can solve this in polynomial time.  The same strategy as in Are SAT problems with at most one false clause NP-complete? works.

Let $\varphi$ denote the CNF formula you care about, and $n$ the number of variables in $\varphi$.  Let $A_{i,j}$ denote the number of truth assignments that do not satisfy clauses $i$ or $j$ of $\varphi$, let $A_i$ denote the number of truth assignments that do not satisfy clause $i$ but do satisfy all other clauses of $\varphi$, and let $A$ denote the number of truth assignments that satisfy all clauses of $\varphi$.

These three cases are mutually exclusive.  Therefore,

$$\sum_{i,j} A_{i,j} + \sum_i A_i + A = 2^n,$$

where $n$ counts the number of variables in the formula.  In other words,

$$A = 2^n - \sum_{i,j} A_{i,j} - \sum_i A_i.$$

You can compute $A_i$.  Let $S_i$ denote the set of variables mentioned in clause $i$.  There is only one assignment to the variables in $S_i$ that will make clause $i$ false, so substitute in those values for the variables in $S_i$ and simplify the formula; the result is a CNF formula $\varphi'$ where we are guaranteed that every assignment to the remaining $n-|S_i|$ variables satisfies at most one clause, so https://cs.stackexchange.com/a/115849/755 tells us how to count the number of satisfying assignments to $\varphi'$, say $n_i$.  Then $A_i = n_i$.

You can compute $A_{i,j}$.  It is either $2^{n-|S_i \cup S_j|}$ or $0$, depending on whether there is any variable $x_k$ such that both $x_k$ and $\neg x_k$ appear in those clauses $i$ and $j$ of $\varphi$.

Therefore, you can compute $A$, the number of assignments that satisfy the formula.  Now, if $A \ne 0$, then you know that the formula is satisfiable; if $A=0$, the formula is not satisfiable.


algorithms and the sequencing of numbers given a value

I don't see an algorithm in your answer. Also, I doubt that if you convert your sequence of steps into an algorithm, then it will produce the correct answer for $n=0,\ldots,5$.
From the given examples, you can see that the first number in the sequence is always $3n$, and from then on the numbers increase by $2$ each time (as you mention; but then in your "algorithm" they decrease by $2$ each time), and in total there are $2(n+1)$ of them (you can see this since the length of the sequence increases by $2$ each time).
How do we convert this into an algorithm? An algorithm is a recipe that prints the sequence for every value of $n$, not for the particular value $n=6$. Also, it should reproduce the given sequences for $n = 0,\ldots,5$.
Your question makes me doubt that the lecturer has explained the concept of "algorithm", so instead, try to write a function in your favorite programming languages that given $n$, prints the sequence corresponding to $n$. Code is just a formal way of presenting an algorithm.


I wouldn't say that code is a graph.  I would say that graphs are a convenient way to represent some aspects of graphs.

There is a sense in which every computation on your computer can be expressed as a state machine: if your computer has 8 billion bits of memory, then there are at most $2^{8,000,000}$ possible states, so it can be considered as a state machine on that state space.  However, that probably isn't a very useful point of view.  Instead, we usually model computers as Turing machines (or in another way), and those cannot be expressed as a finite state machine.

The question of whether all computations are graphs doesn't seem well-defined to me.  Presumably graphs can be used to represent some aspects of computations, but that doesn't mean the calculation is a graph (or that it is nothing more than a graph).


Is interaction more powerful than algorithms?

Turing machines can handle interaction just fine, using oracle tapes. It works are follows: from the point of view of a computer that handles interaction, the input of the operator is simply another sequence of bits that it sent into the computer from time to time. We all know that a lazy sysadmin could write a script to send the input to the program when it is requested, so that the sysadmin could go on break earlier.  The interaction machine has no way to know if there is really a live operator at the console, or if the input is being piped from another program.

Having all the interaction input prepared ahead of time is the same, in theoretical terms, as having all the input on a separate tape that is used by an oracle Turing machine. Whenever the computer would normally request interaction from the operator, the machine instead reads from the input tape. If the thing read from the tape seems invalid in some way, the Turing machine does exactly what the interaction machine would do on receiving that input.

I would guess that Wagner is aware of the ability to use oracle tapes to code input, so you have to take his comments with a grain of salt, or you have to ask what he actually means.  I believe that people who think about interaction are generally worried about two things:

"Real" computers do have interaction, but algorithms as defined by Turing don't. We can get around this by coding the input on oracle tapes, but this still does not match the way that real computers operate. It might be nice to study models of computation that are more closely aligned with real computers.
Oracle-based algorithms are not often considered in day-to-day computing because normal computers don't come with a magic "oracle" to supply data. But we might be able to actually just use a person as the oracle. If the person understands the data that is being requested, they may even be able to help the algorithm along, thus improving its performance. In other words a human may be able to provide a useful oracle tape rather than simply a random one, and in principle this might lead to faster or more powerful computing methods compared to non-oracle-based ones. A similar thing happens with randomized computing, after all, where the machine is given a sequence of random bits as an extra input.


Different decompositions of the string in the pumping lemma proof

Here is the statement of the pumping lemma:

  If $L$ is a regular language then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that (i) $|xy| \leq p$, (ii) $y \neq \epsilon$, (iii) for all $i \geq 0$, $xy^iz \in L$.

Here is the contrapositive, which is how you usually apply the lemma:

  Suppose that $L$ is a language such that for every $p$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w = xyz$ satisfying $|xy| \leq p$ and $y \neq \epsilon$, there exists $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

When you apply the lemma to show that a language is not regular, you have to consider all possible decompositions satisfying $|xy| \leq p$ and $y \neq \epsilon$. For each of them you need to find an $i$ such that $xy^iz \notin L$.


List count of occurrences pairs, triplets, etc. from sets

This is the itemset mining problem.  Use any standard algorithm for that problem.  Follow the links to learn more about standard algorithms for that task.


How do quantum computers find the global minimum?

Nope, that's not how quantum computing works.  That's actually a common misconception.  Sometimes people think that quantum computers work by trying all solutions in parallel and then selecting the best one, but that's not right -- that's not really how quantum computing works.

To learn more about how quantum computing works, I recommend you study Scott Aaronson's book Quantum Computing since Democritus, or his lecture notes on quantum computing.

Don't expect to find a one-sentence summary that is simultaneously enlightening and accurate.  Quantum physics is highly counter-intuitive, so you shouldn't expect your existing intuition to necessarily help you understand how quantum computing works.  Keep in mind that it's a bit unreasonable to expect an explanation in layman terms: quantum physics is tricky stuff, so your intuition from the everyday world doesn't really translate into a useful way of thinking about quantum computing.

You can also look at other questions on this site.  See, e.g., Why and how is a quantum computer faster than a regular computer? and quantum-computing.


$ADD = {x=y+z}$ with $x, y, z$ binary integers, and $x$ is the sum of $y$ and $z$. Pumping lemma to show that $ADD$ is not regular

Your answer has a slight omission: If perchance $y$ is of length $p$ (note: $x$ is permitted to be empty), then choosing $i=0$ leaves one with, not a false equation, but no equation (the string begins with '=').  But of course the conclusion is the same.  You can avoid that nit by choosing $i=2$ (say) instead of $i=0$.

And yes, I think yours is just another correct pick.


It depends on the context. From a computer architecture perspective, you can insert a hazard detection unit that inserts a bubble in the pipeline when it detects this condition. It's shown top/left-ish in this picture from Patterson&Hennessy:

The logic doesn't do anything unexpected, it detects the case that an instruction in the ID wants to read a register that a memory read in the EX stage will write to, the instruction from the ID stage is then killed and PC is "held" so the instruction will re-execute.

From a programmer perspective, suppose there is no hazard detection unit, just insert the NOP yourself.


Hint: If I understand you correctly, you are after
$$ \sum_{B \subseteq A} \sum_{x \in B} x. $$
Try reversing the order of summation:
$$ \sum_{B \subseteq A} \sum_{x \in B} x = \sum_{x \in A} \sum_? x, $$
where $?$ is some condition that you will have to come up with. See if that helps you to find a closed formula for the original double sum.


Towers of Hanoi but with arbitrary initial and final configuration

The most succesful approach to deal with the original version of the Towers of Hanoi is using Pattern Databases (PDBs). The current state of the art is described in "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem"

Pattern Databases are an automated means for deriving admissible heuristics which are necessary in order to find optimal solutions (as your problem requires). In the particular case of the Towers of Hanoi, some discs are preserved while others are just ignored. This results in a smaller state space which can then be fully traversed with a backward breadt-first search algorithm. It is traversed with a breadth-first search to derive optimal lengths in this abstract state and it is traversed from the goal node $t$ (i.e., backwards), to ensure that the optimal lengths computed are relative to the goal. Since the abstract space is smaller, these distances are admissible estimates in the original state space.

This said, I would highly recommend using PDBs again for solving this particular problem since "moving only between towers at distance at most $d$" is trivial since pegs are not abstracted, only the discs.

I do not see, indeed, any reason to change the typical approach just in view of this particular constraint.

Hope this helps,


$T$ is a tree that connects the chosen subset of terminals $U$. Thus $U$ is a subset of $V(T)$, and $V \setminus V(T)$ is a subset of $V \setminus U$ (we're summing $i$ not in $U$).


How to generate a binary string so to minimize weighted bitwise distance?

It is not possible to uniquely determine $i$-th combination because a function $f: \{0,1\}^* \to \mathbb{R}$ assigning distance to a string is not generally injective., that is - there may be multiple strings that correspond to a specific distance $d \in \mathbb{R}$ (which you example actually presents).

Also, it is not possible to know in advance all the possible distances as to determine which strings could be in $i$-th position, without actually calculating all the distances. It would be like knowing the shortest route to some destination by examining just that route.

I would suggest a different approach (but it will not make you happy as I generally think there is no way to achieve this in its fullest without generating all combinations); creating an algorithm that takes as input not $i$, but the distance $d$ and returns strings that are $d$ distance from your base string (note that it is in fact irrelevant).
You can then eliminate from further process the weights that are larger than $d$ (and even ones equal to $d$, with further care).

If you want all strings $d$ distance away and remaining weights vector is not too long, you can generate all subsets (a power set) of weights array and checking which has the sum $d$, but considering your restrictions on the solution - you do not want that because it would generate all the binary strings in the process.
If you need just one string on distance $d$, no matter which, you can implement some backtracking search/sum on the weights array to find a combination that sums to $d$. (You can then store ones you got and repeat this process ignoring ones you found already, if you still want all.)
You can model your problem as finding a path of length $d$ in a fully connected directed graph where you graph has $N$ nodes and the weight of an edge going to node $i$ is $weights[i]$. Then you can maybe use some optimized graph path finding (heuristic) algorithms, but that seems like an overkill.

I am quite sure this problem is in NP.


Why is $L = \{ \langle M \rangle : L(M) = \{ \langle M \rangle \} \}$ not Turing-recognizable?

Given a Turing machine $T$, use the recursion theorem to construct a Turing machine $T'$ that halts if its input $x$ is $\langle T' \rangle$, runs $T$ on $x$ if $x < \langle T' \rangle$, and runs $T$ on $x-1$ if $x > \langle T' \rangle$. If you could recursively enumerate $L$, then you could use this reduction to recursively enumerate all machines that never halt.


Repeating what MCH said, every time you run the algorithm, you use fresh random bits.

As an example, here is a BPP algorithm that computes the number $1$:

Toss a biased coin (heads w.p. 2/3, tails w.p. 1/3). If heads, output 1, else output 0.

The algorithm "succeeds" with probability $2/3$. The amplification procedure amounts to tossing $n$ biased coins, outputting $1$ if the majority of them were heads, and $0$ otherwise. Since we expect roughly $(2/3)n > n/2$ of the coins to be heads, it is very likely that the amplified algorithm is successful (outputs $1$).

In other words, when you run your algorithm $n$ times, each time you run it, you re-toss all the coins. So the amplified algorithm tosses $n$ times as many coins, and the probability is taken over all these coin tosses.


No, it depends on your application. The measures of sortedness are often refered to as measures of disorder, which are functions from $N^{<N}$ to $\mathbb{R}$, where $N^{<N}$ is the collection of all finite sequences of distinct nonnegative integers. The survey by Estivill-Castro and Wood [1] lists and discusses 11 different measures of disorder in the context of adaptive sorting algorithms.

The number of inversions might work for some cases, but is sometimes insufficient. An example given in [1] is the sequence

$$\langle \lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \ldots, n, 1, \ldots, \lfloor n/2 \rfloor \rangle$$

that has a quadratic number of inversions, but only consists of two ascending runs. It is nearly sorted, but this is not captured by inversions.

[1] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


Casting to boolean in integer linear programming

Add the following two constraints:
$$
y \leq 5-x \\
y \geq 1-x/5
$$
If $x = 5$, then these constraints state that $y \leq 0$ and $y \geq 0$, hence $y = 0$. If $x \leq 4$, then $5-x \geq 1$, and so the first constraint doesn't impose any constraint on $y$. On the other hand, $1-x/5 > 0$, forcing $y = 1$; and this assignment satisfies the constraint since $x \geq 0$ implies $1-x/5 \leq 1$.


How to prove that insert complexity in binary search tree is minimum O(log n)?

The minimal height of a BST is always log n, you can easily prove it by induction. Then if you want to insert a new node you need to find the corresponding leaf where to insert it, which takes at least log n operations (comparisons) in the worst case, more if the tree is not balanced (larger height). Hence you obtain an insert cost of O(log n). We always focus on the worst case scenario to compute the O-complexity.


Covering radius of a code in the Hamming space

It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is max(1,1)=1

Overall, the algorithm is the following:

for each possible code x, find the closest element c in C (i.e. the one with minimum distance d(x,c)) and record this distance
find the maximum of all distances recorded at the previous step

I find that it's well visualized with set of spheres covering part of 3D space. You check all points outside of spheres and find one that has the largest distance to its closest sphere.


Product of a Transition System and a Finite Automaton

In Section 4.2.2 of the book "Principles of Model Checking", there is a definition (Definition 4.16; Page 165) of "Product of Transition System and NFA". You are right about the states (i.e., $S \times Q$) of the product but make mistakes about its transition relation. Below I focus on the transition relation.

  Definition 4.16 Product of Transition System $TS = (S, Act, \to, I, AP, L)$ and NFA $\mathcal{A} = (Q, \Sigma, \delta, Q_0, F)$. The transition relation $\to'$ of their product is the smallest relation defined by the rule
  $$\frac{s \to^{\alpha} t \; \land \; q \to^{L(t)} p}{(s,q) \to'^{\alpha} (t,p)}$$

Intuitively, the transition system TS generates atomic propositions and feeds them into the automaton $\mathcal{A}$, driving the automata running. This semantics can be used to verify if the TS satisfies some property expressed by an automaton.

Additionally, the start states of the product is $$I' = \{ (s_0, q) \mid s_0 \in I \land \exists q_0 \in Q_0. q_0 \to^{L(s_0)} q \}.$$ That is, $q_0$ in automaton has moved one step forward, driven by the atomic propositions in $s_0$.

Based on the definition above, I calculate the product as follows (please check it):

For what it concerns the terminal states, please refer to "Remark 4.17" (immediately following the Definition above) in the book.
By the way, the labels for transitions (action denoted by $\alpha$ above) in $TS$ are often ignored (because they are irrelevant).


DFA/NFA/ε-NFA: subsetting each other or different sets?

If I understand your question correctly, you are essentially talking about the syntactic difference between DFAs, NFAs and NFAs with $\epsilon$ transitions.

Well, in a way, every DFA is also an NFA, and every NFA is also an NFA with $\epsilon$ transitions (it just so happens that the former does not use these transitions).
A caveat here is that if you really stick to the standard definitions, then in a DFA the "type" of the transition function returns a state, whereas in an NFA it returns a subset.
This is just a technicality, of course, as you can define a DFA to be an NFA whose transition function only returns singletons.

I would look at things this way:
An $\epsilon$-NFA would be the "standard".
Then, define an NFA to be an $\epsilon$-NFA that does not use the $\epsilon$ transitions.
Finally, define a DFA to be an NFA with a single initial state and a transition function that only returns singletons.

In the comments, you ask about the size of the different models, w.r.t a fixed language. This is an entirely different issue. As it turns out, $\epsilon$ transitions can always be removed, and no new states are introduced in the process, only new transitions.
As for the translation to DFA - this may involve an exponential blowup in the state space.


How do I work out the recurrence relation of the given function?

In the following I won't pay much attention to floors, celings, and "off-by-one" errors since they won't ultimately matter in the analysis of the recurrence relation. However all of the following calculations can be made precise.
If $n = \texttt{high} - \texttt{low}$ then $\texttt{gap} = n/5$ and the algorithm will perform three recursive calls:

The first on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}$ and $\texttt{low}+2\texttt{gap}$.
The second on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}+ \texttt{gap}$ and $\texttt{low}+3\texttt{gap}$.
The third on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{high}- 2 \texttt{gap}$ and $\texttt{high}$.

Also notice that when $n = O(1)$ then the time complexity of the algorithm is constant, and that the time spent in the non-recursive parts of the algorithm is also $O(1)$.
The recurrence relation is then:
$$
T(n) = 3T\left( \frac{2}{5} n \right) + O(1),\\ \quad T(1)=O(1)
$$
which can be solved...

 using the Master theorem to yield $T(n) = O(n^{\log_{5/2} 3}) = O(n^{1.1989\dots})$.


Proving the language $L= \{0^n 1^m \space | \space m \equiv 0 \space mod \space n, \space n \geq 2 \}$ is not regular using the pumping lemma

Here is a nicer proof, (implicitly) using the Myhill-Nerode criterion. Let $p_1,p_2,p_3,\ldots$ be the list of all primes, and consider the words $x_i = 0^{p_i}$, $y_i = 1^{p_i}$. Then $x_i y_i \in L$ while $x_i y_j \notin L$ for $i \neq j$. So given a DFA for $L$, if $\sigma_i$ is the state that the DFA is at after reading $x_i$, we must have $\sigma_i \neq \sigma_j$ for $i \neq j$ (why?), so the DFA must have infinitely many states.


Loopless NFA equivalent in strength to NFA

Make two copies of your original NFA and connect them in an appropriate way.


How to understand the recurrence relation and time-complexity of StoogeSort?

Here are some more hints:

The algorithm partitions the array $A$ into three parts $B,C,D$ such that $|C| \geq |B|,|D|$ and then sorts $BC$ (the array formed by the first two parts), $CD$ (the array formed by the last two parts), and then $BC$ again. Show that for any such partition, the result is sorted. You can use the 0-1 principle.
When $n=4$, the algorithm sorts $a_1,a_2$, then $a_3,a_4$, then $a_1,a_2$. You can easily give an example showing that this doesn't work.
You should be able to solve this yourself.
The recurrence in the preceding bullet involves $m = \lceil \frac{2n}{3} \rceil$. This part asks you to replace $m$ with $\frac{2n}{3}$, and then solve the recurrence using the master theorem.
For a permutation $\pi$, the number of inversions is the number of pairs $i<j$ such that $\pi(j)<\pi(i)$. A permutation can have at most $\binom{n}{2}$ inversions (this is the number of pairs $i < j$). Each swap operation reduces the number of inversions by 1.


The intuition behing the residual graph in the Maximum flow problem is very well presented in this lecture. The explanation goes as follows.

Suppose that we are trying to solve the maximum flow problem for the following network $G$ (where each label $f_e/c_e$ denotes both the flow $f_e$ pushed through an edge $e$ and the capacity $c_e$ of this edge):

One possible greedy approach is the following:

Pick an arbitrary augmenting path $P$ that goes from the source vertex $s$ to the sink vertex $t$ such that $\forall e \: (e \in P \rightarrow  f_e \lt c_e $); that is, all of the edges in $P$ have available capacity.
Push the maximum possible flow $\Delta$ through this path. The value of $\Delta$ is determined by the bottleneck of $P$; that is, the edge with minimum available capacity. Formally, $\Delta=\min_{e \in P} (c_e-f_e)$.
Go to step 1 until no augmenting paths exist.

That is, find a path with available capacity, send flow along that path, and repeat.

In $G$, one possible execution of the above heuristic finds three augmenting paths $P_1$, $P_2$, and $P_3$, in this order. These paths push 2, 2, and 1 units of flow, respectively, for a total flow of 5:

Choosing paths in this order leads to an optimal solution; however, what happens if we select $P_3$ first (i.e., before $P_1$ and $P_2$)?

We get what is called a blocking flow: no more augmenting paths exist. In this case, the total flow is 3, which is not optimal. This issue can be resolved by allowing undo operations (i.e., by allowing flow to be sent in reverse, undoing work of previous iterations): simply push 2 units of flow backwards from vertex $w$ to vertex $v$ like this:

Encoding these allowed undo operations is the main goal of the residual graph.

A residual graph $R$ of a network $G$ has the same set of vertices as $G$ and includes, for each edge $e=(u,v) \in G$:

A forward edge $e'=(u,v)$ with capacity $c_e-f_e$, if $c_e-f_e \gt 0$.
A backward edge $e''=(v,u)$ with capacity $f_e$, if $f_e \gt 0$.

For example, consider the residual graph $R$ that is obtained after the first iteration of the greedy heuristic when the heuristic selects $P_3$ first (that is, when it gets the blocking flow):

Note that the undo operation that pushes 2 units of flow from $w$ to $v$ is encoded as a forward (augmenting) path from $s$ to $t$ in $R$:

In general:

  When an augmenting path $P'$ is selected in the residual graph $R$:

  Every edge in $P'$ that corresponds to a forward edge in $G$ increases the flow by using an edge with available capacity.
  Every edge in $P'$ that corresponds to an edge going backwards in $G$ undoes flow that was pushed in the forward direction in the past.

This is the main idea behind the Ford–Fulkerson method.

The Ford–Fulkerson method proceeds in exactly the same way as the greedy approach described above, but it only stops when there are no more augmenting paths in the residual graph (not in the original network). The method is correct (i.e., it always computes a maximum flow) because the residual graph establishes the following optimality condition:

  Given a network $G$, a flow $f$ is maximum in $G$ if there is no $s-t$ path in the residual graph.


Creating a 2D map of objects given a sparse matrix of pairwise distances

This is known as "graph layout" or "graph drawing" (practical methods) or "graph embedding" (theoretical interest).  The relevant techniques are more closely associated with computational geometry and mathematical optimization, not machine learning.   See this Wikipedia article and Recovering a point embedding from a graph with edges weighted by point distance and Efficient algorithm to fulfil a set of coordinate constraints for an overview of some standard techniques.  Pairwise comparisons with confidence might also have some helpful techniques (it is focused on the 1D case, not the 2D case, but it might be possible to generalize Yuval's answer to the 2D case as well).


How to find the minimal DFA for the language?

Your approach towards estimating the number of states is just fine. however the number of states looks quite intimidating and it may be cumbersome to minimize the DFA later.
 In such cases constructing the automaton through intersection is easier. for example as we know the regular languages are closed under the intersection operation we can devise 3 different automata to accept :
 1. String divisible by 25
 2. String divisible by 4
 3. Strings beginning with 101

And then arrive at the final automaton by taking intersections of the 3 machines.

How this helps?

Many of the states originally present in the different machines gradually become unreachable from the initial state in the final automaton and thus the number of states reduce or the DFA is minimized.


Can file snapshots aid in detecting malware?

This is not likely to be very effective in practice.  Malware might corrupt the file before you were first able to take a snapshot... or, more realistically, it might corrupt the snapshot you have taken, so that the snapshot matches the current version of the file.  It is difficult to defend against that attack.

So, while your idea is not a bad one, it has significant limitations that might render it not terribly useful in practice.

This also assumes that the underlying file is one that should never change.  Of course, in practice, for any given file, there are valid circumstances when the file should be allowed to change.  So this means you'd need some way to recognize valid, legitimate changes to the file.  This starts to get a bit more complex to implement.

You might take a look at Tripwire, which is a system that does something like this -- except it keeps only a cryptographic hash of each monitored file, rather than a full copy of the file.


If you have a solution for all even numbers, it might be sufficient to realize $T(k+1) \ge T(k)$.
But generally this is proved by induction where the even numbers use the odd ones. There, you have two leads :

Take good care of your bounds during your induction
More simple (but with less efficient approximation) : prove it for powers of two with a given constant ; and then use those to prove the general case for another constant


Changing binary counter structure such that increament and decreament methods will work in O(1) amortized

They may by suggesting that you use a binary counter with three digit values, $\{-1,0,1\}$, and budget a fixed additional time whenever you set a digit to $\pm1$.
To increment the counter you start at the least significant trit, and if it's $-1$ you set it to $0$ and stop, if it's $0$ you set it to $1$ and stop, and if it's $1$ you set it to $0$ and loop (using the previously budgeted time). Decrementing is the same with everything negated.


why nominal unification is a first-order unification?

Most experience people have with unification (if any) is usually unification modulo syntactic equality: two terms unify if there is a substitution for unification variables that makes the terms syntactically identical.  However, you can consider other base equivalence relations that are coarser than syntactic equality.  For example, there's associative, commutative equality that let's you unify two bags (aka multisets) of terms, e.g. the term $\{\!\!\{\mathtt{x},\mathtt{y}\}\!\!\} = \{\!\!\{\mathtt{y},\mathtt{x}\}\!\!\}$ where I'm using $\{\!\!\{ \ldots \}\!\!\}$ to represent a bag.  Unification with a base equivalence like this, coarser than syntactic equality, come up, for example, in checking record types.  You can imagine you have a bag of record labels and you want to record types to be the same regardless of how you wrote down the labels.

So, in this context, higher-order unification is unification modulo $\alpha\beta\eta$-equivalence.  The base equivalence is what makes it higher-order-unification, not the terms it operates on. I can apply normal, syntactic, first-order unification to lambda terms too. Unification modulo $\alpha\beta\eta$-equivalence means being able to unify expressions like $E(3) = (3,3)$ via a substitution such as $[E \mapsto \lambda x.(x,x)]$ as these are $\beta$-equivalent. (Following Prolog, I'll use capital letters to indicate unification variables.  Also, note $[E\mapsto\lambda x.(3,3)]$ is another non-equivalent substitution which is why higher-order unification produces extra non-determinism.)  Nominal unification does not unify these terms. $(\lambda x.(x,x))(3)$ is not $\alpha$-equivalent to $(3,3)$.  An application will never be $\alpha$-equivalent to a pair constructor. (However, if the notation was implicitly in curried-style, i.e. $(3,3)$ meant $((,)(3))(3)$, these would syntactically unify.  Generally, though, multi-ary application is never $\alpha$-equivalent to unary application.)

Nominal unification is unification modulo $\alpha$-equivalence.  At a raw syntax level $\lambda x.x$ is syntactically different from $\lambda y.y$ because $x$ is different syntax than $y$.  This is undesirable as we want to treat these terms as completely identical.  We don't want the choice of variable name to matter to, e.g., type checking.  This problem is clearly solvable because we could use deBruijn notation and the only term corresponding to the two above lambda terms would be something like $\lambda\mathbf{1}$.  The power of deBruijn notation is that syntactic equality is $\alpha$-equality.  Nevertheless, it would be nice not to use deBruijn notation.

So one way to implement nominal unification would be to simply convert each term to deBruijn notation and unify.  This would be fine if all we needed to do was answer "yay" or "nay", but we also need to produce a substitution.  If we convert $\lambda x.x$ and $\lambda y.E$ to $\lambda\mathbf{1}$ and $\lambda E$ respectively, then unify them, we get $[E \mapsto \mathbf{1}]$. But obviously $\lambda x.x \neq (\lambda y.E)[E\mapsto x]$.  Basically, we need to keep track of what variable corresponds to $\mathbf{1}$ on each side of the equation.  This gives us two bijections (for any particular unification variable, i.e. locally) that maps variables to deBruijn indices, here $[x \mapsto \mathbf{1}]$ and $[y\mapsto\mathbf{1}]$.  We can compose these bijections to get a bijection (i.e. permutation) between variables on each side.  This leads to $[E \mapsto (x\ y)\bullet x]$, in their notation, which simplifies to $[E\mapsto y]$, the desired substitution.  There are some extra concerns about capturing variables that additionally complicates the picture.

Summarizing, higher-order unification means unification modulo $\alpha\beta\eta$-equivalence.  Nominal unification means unification modulo only $\alpha$-equivalence.  This can be reduced to syntactic unification of deBruijn terms, but if we want to produce substitutions on non-deBruijn terms we need to keep track of some extra information.  Doing a similar reduction for higher-order unification would involve reducing to terms in $\beta\eta$-normal form, which thus requires such normal forms to exist hence the focus on the typed case, and leads to creating terms out of nowhere which themselves require unification.


Task scheduling algorithm that limits concurrency

You (or the algo) probably assigns a constant amount of time slice per process. Since amount is constant, as with number of process increases this effectively hinders concurrency. If this is the case, you need a fair scheduler type algorithm. Check on different algo's on a linux kernel may have.


Is there a method for automatic runtime analysis of algorithms?

No algorithm can decide whether a given algorithm ever halts or not, so in particular no algorithm can tightly analyze the complexity of a given algorithm.


Two-way finite automaton: How does the automaton remember the state

Here is a simpler example, for NFAs.

We will show that if $L_1,L_2$ are regular languages over disjoint alphabets $\Sigma_1,\Sigma_2$, then so is the following language over $\Sigma = \Sigma_1 \cup \Sigma_2$:
$$
L = \{ xyz : x,z \in \Sigma_1^*, y \in \Sigma_2^*, xz \in L_1, y \in L_2 \}.
$$
Here is the idea. Start with DFAs $A_1,A_2$ for $L_1,L_2$. We will construct a DFA for $L$ which acts as follows. It starts by simulating $A_1$. When it encounters a symbol from $\Sigma_2$, it remembers the state that $A_1$ is in, and switches to $A_2$. When it encounters a symbol from $\Sigma_1$, it switches back to $A_1$, assuming that $A_2$ is at an accepting state. It goes to a failure state if it encounters a letter from $\Sigma_2$ again.

Here are the details, showing how we implement remembering the state of $A_1$.

Let $A_1 = \langle Q_1,\Sigma_1,q_{01},\delta_1,F_1 \rangle$ and let $A_2 = \langle Q_2,\Sigma_2,q_{02},\delta_2,F_2 \rangle$. We construct a new DFA $A = \langle Q,\Sigma,q_0,\delta,F \rangle$ as follows:

The set of states is $Q = (Q_1 \times \{1\}) \cup (Q_1 \times Q_2) \cup (Q_1 \times \{2\}) \cup \{q_f\}$. States in the first part will be used to simulate $A_1$ before a symbol from $\Sigma_2$ is ever encountered. States in the second part will be used to simulate $A_2$ while remembering the state of $A_1$. States in the third part will be used to simulate $A_1$ after reading the $y$ part. The final state will handle various modes of failure.
The initial state is $(q_{01},1)$.
The transition function is defined as follows:

If $\sigma \in \Sigma_1$ then $\delta((q,1),\sigma) = (\delta_1(q,\sigma),1)$: we just advance $A_1$.
If $\sigma \in \Sigma_2$ then $\delta((q,1),\sigma) = (q,\delta_2(q_{02},\sigma))$: we remember the state of $A_1$, and advance $A_2$.
If $\sigma \in \Sigma_2$ then $\delta((q_1,q_2),\sigma) = (q_1,\delta_2(q_2,\sigma))$: we advance $A_2$, while keeping the state of $A_1$ intact.
If $\sigma \in \Sigma_1$ and $q_2 \notin F_2$ then $\delta((q_1,q_2),\sigma) = q_f$: the $y$ part is not in $L_2$, so we signal failure.
If $\sigma \in \Sigma_1$ and $q_2 \in F_2$ then $\delta((q_1,q_2),\sigma) = (\delta_1(q_1,\sigma),2)$: we go back to simulating $A_1$.
If $\sigma \in \Sigma_1$ then $\delta((q_1,2),\sigma) = (\delta_1(q_1,\sigma),2)$: we just advance $A_1$.
If $\sigma \in \Sigma_2$ then $\delta((q_1,2),\sigma) = q_f$: the input is malformed, so we signal failure.
For all $\sigma$, $\delta(q_f,\sigma) = q_f$.

The final states are $(F_1 \times \{1\}) \cup (F_1 \times F_2) \cup (F_1 \times \{2\})$. The first part handles the case $y=z=\epsilon$, the second handles the case $y\neq\epsilon$ and $z=\epsilon$, the third handles the case $y,z \neq \epsilon$.

Hopefully this explains how a DFA can commit a piece of information to memory. Since a DFA has only finitely many states, it can only store a constant amount of information.


Comparing dual of a canonical primal program - Directly and by dual of the standard program

Since $Ax\ge b$, you should make $Ax$ smaller to get equality. Slack variables are also non-negative, so the coefficients should be $-1$. It's $[A|-I]$ instead of $[A|I]$.


Computational complexity vs. Chomsky hierarchy

There are four classes of language in the Chomsky hierarchy:

Regular languages — this class is the same as $\mathrm{TIME}(n)$ or $\mathrm{TIME}(o(n\log n))$ (defined using single-tape machines, see Emil's comment), or $\mathrm{SPACE}(0)$ or $\mathrm{SPACE}(o(\log\log n))$ (per Emil's comment).
Context-free languages — this class doesn't have nice closure properties, so instead one usually considers $\mathrm{LOGCFL}$, the class of languages logspace-reducible to context-free languages. It is known that $\mathrm{LOGCFL}$ lies in $\mathrm{AC}^1$ (and so, in particular, in $\mathrm{P}$), and it has nice complete problems detailed in the linked article.
Context-sensitive languages — this class corresponds to $\mathrm{NSPACE}(n)$.
Unrestricted grammars — this class consists of all recursively enumerable languages.

If a language in NP-complete then assuming P$\neq$NP, it is not context-free. However, it could be context-sensitive (clique and SAT both are). Any language in NP is described by some unrestricted grammar.


Diameter-constrained Minimum Spanning Tree Problem

Consider the complete graph $K_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.


Difference between First Order Logic and Predicate Calculus

First-order logic and first-order predicate calculus are the same thing, which is exactly why the terms are used interchangeably. See, for example, Wikipedia:

  First-order logic [...] is also known as first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic.


Shortest subsequence containing all elements

Start by computing the set of all elements in the input sequence. This takes time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ using a hash table.
Suppose there are $m$ such elements $x_1,\ldots,x_m$. Initialize a histogram $H$ of length $m$ with zeroes, and a counter $C$ to $m$. Go over the elements in the sequence from left to right. When processing $a_i$, update $H[a_i] \gets H[a_i] + 1$ (the indexing operation takes time $O(\log n)$ if we are only allowed comparisons, and $O(1)$ using a hash table), decreasing $C$ if $H[a_i]$ were zero. Stop once $C = 0$. If we stopped at $a_j$, then this means that $a_1,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_1$.
Now update $H[a_1] \gets H[a_1] - 1$. If after the update $H[a_i] > 0$, then $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$. Otherwise, continue scanning the sequence, updating $H$ as before, until $H[a_1] > 0$. If we stopped at $a_j$, that $a_2,\ldots,a_j$ is the shortest subsequence containing all elements and starting at $a_2$.
In this way we can find the lengths of all shortest subsequences containing all elements and starting at $a_i$, for each $i$. We output the length of the shortest one. The entire algorithm runs in time $O(n\log n)$ if we are only allowed comparisons, and $O(n)$ otherwise.
In the latter case, $O(n)$ is optimal, as a simple adversary argument shows (whenever the algorithm accesses an element, answer $1$; even after accessing all but one element, the algorithm cannot tell whether the correct answer is $1$ or $2$).
If we are only allowed comparisons, then we can get an $\Omega(n\log n)$ lower bound from Element Distinctness. Suppose that we could solve our problem using $T(n)$ comparisons. Given a sequence $a_1,\ldots,a_n$, consider the sequence $a_1,\ldots,a_n,a_1,\ldots,a_n$. If all elements are distinct, the shortest subsequence containing all elements has length $n$. Otherwise, if $a_i = a_j$ for $i < j$ then the subsequence $a_{i+1},\ldots,a_n,a_1,\ldots,a_{i-1}$ contains all elements and has length $n-1$. This shows that we can solve Element Distinctness in time $T(2n)$. The well-known lower bound $\Omega(n\log n)$ on Element Distinctness implies that $T(2n) = \Omega(n\log n)$, and so our algorithm is optimal. (Formally speaking, we also need to handle odd input lengths. We can do this by adding a fresh element between the two copies of the original sequence.)
Credit for the algorithm: https://www.glassdoor.com/Interview/Find-shortest-substring-in-a-string-that-contains-all-of-a-set-of-characters-QTN_66124.htm


Turing proved that the halting problem is undecidable.

No algorithm that you can come up with will solve the halting problem.


Let's use $+$ to denote the start of a segment and $-$ to denote the end. For each segment, create two pairs, one for each endpoint:

Segment1: (-2, +), (3, -)
Segment2: (1, +), (5, -)
Segment3: (-3, +), (1, -)

Sort the $2N$ pairs by their first coordinate (in case of equality, put + before -). You can do this in time $O(N \log N)$ with any reasonable sorting algorithm, or in time $O(N + K)$ using key-indexed counting. In the example, we get:

(-3, +)
(-2, +)
(1, +)
(1, -)
(3, -)
(5, -)

Now process the endpoints in order. Maintain a count of the number of active segments, which is initially 0. Every time you process a $+$, increase the count by 1. Every time you process a $-$, decrease the count by 1. After processing each endpoint, check if the new count is higher than the largest count so far; if it is, update your solution.

(-3, +) -> count=1, max_count=0, sol=-3
(-2, +) -> count=2, max_count=1, sol=-2
(1, +) -> count=3, max_count=2, sol=1
(1, -) -> count=2, max_count=3, sol=1
(3, -) -> count=1, max_count=3, sol=1
(5, -) -> count=0, max_count=3, sol=1

This second phase of the algorithm takes time proportional $N$. The whole algorithm takes time $O(N \log N)$ with a generic sort, or $O(N + K)$ with key-indexed counting.


What is the fastest way to check if an integer is divisible by another?

Integer division

The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$.  In particular, it is something like $O(n \lg n 2^{\Theta(\lg^* n}))$ (which is a bit faster than $O(n \lg n \lg \lg n)$.  The time complexity of integer division is the same as the time complexity of integer multiplication.  See https://en.wikipedia.org/wiki/Division_algorithm and https://en.wikipedia.org/wiki/Multiplication_algorithm.

Caution: these algorithms are purely theoretical.  The constants hidden by the big-O notation make them impractical for most sizes you'll run into in real life.  But there are plenty of other algorithms that are faster than the naive algorithm and are useful in practice.

No, you can't do it in $O(\lg n)$ time, where $n$ is the number of bits in the input: you obviously can't do it in less than $O(n)$ time, since it takes that much time just to read in the entire input.

Testing divisibility

The problem of testing divisibility could in theory be easier: it asks for just a yes-or-no answer (is $y$ divisible by $x$ or not?) instead of the result of the full division (compute $\lfloor y/x \rfloor$).  Obviously, you can use any algorithm for integer division to test integer divisibility (with the same running time).  I don't know if there is any faster way to test integer divisibility.

A conceptually simple way to test whether $y$ is divisible by $x$ is to check whether $y \bmod x$ is zero or not.  However, I don't know of any way to compute the remainder $y \bmod x$ in linear time (in time linear in the number of bits of the input, i.e., in $O(n)$ time, where $n=\lg(x)+\lg(y)$).  As before, you obviously can't do it in less than $O(n)$ time.

See also https://cstheory.stackexchange.com/q/16788/5038, which basically states the same thing: no faster algorithms are known, but no one has proven lower bounds ruling out the possibility of faster algorithms.


How do you "time" the measure of binary streams?

To most components we can attach an internal clock, that is made sure to "tick" at a rate with intervals bigger than the time needed for the current to pass through the circuit. Then, each "tick" the components look at their input and evaluate the output.
This is what defines "when" and "what" a component sees, which (also) allows it to differentiate even between a single 0 and series of 0's.


See

"Understanding Java Stack Inspection" by D. S. Wallach and E. W. Felten (1998)

From the paper:

... The stack inspection algorithm used in current Java systems
can be thought of as a generalization of the following simple
stack inspection model:

In this model, the only principals are “system” and “untrusted”. Likewise,
the only privilege available is “full.” This model
resembles the stack inspection system used internally in
Netscape Navigator 3.0.

In this model, every stack frame is labeled with a principal
(“system” if the frame is executing code that is part of
the virtual machine or its built-in libraries, and “untrusted”
otherwise), and contains a privilege flag which may be set
by a system class which chooses to “enable its privileges,”
explicitly stating that it wants to do something dangerous.
An untrusted class cannot set its privilege flag. When a
stack frame exits, its privilege flag (if any) automatically
disappears.

All procedures about to perform a dangerous operation
such as accessing the file system or network first apply a
stack inspection algorithm to decide whether access is allowed.
The stack inspection algorithmsearches the frames
on the caller’s stack in sequence, from newest to oldest.
The search terminates, allowing access, upon finding a
stack frame with a privilege flag. The search also terminates,
forbidding access and throwing an exception, upon
finding an untrusted stack frame (which could never have
gotten a privilege flag). ...

and the book "Securing Java" (in particular chapter three also available online)


Do we need to read the input completely in Turing machine?

There is no such requirement. A Turing machine which decides a language can do whatever it wants as long as it always halts; the language it decides is the set of words which it accepts.

There are many languages which don't require reading the entire input:

The empty language.
The complete language.
The language of all words starting with 0.
The language of words of length 2.

Here is a more non-trivial example:

Given a language $L$, define the language
$$ X(L) = \{ 0^\ell 1 w x : |w|=\ell \text{ and } w \in L \}. $$
The language $X(L)$ can be decided by a Turing machine which doesn't always read the entire input. Moreover, generally speaking $L$ and $X(L)$ have roughly the same complexity (though $X(L)$ requires the ability to count).


P reduction between np-complete to np-complete

Hint: What is the definition of "NP-complete"?


Is every file an integer amount of bytes?

Yes, every file has an integer amount of bytes. In fact, most file systems deal with blocks or clusters of bytes. If cluster size is 64KB a file may claim to take up 250KB, but it will actually take 4 clusters or 256KB. This reduces the problem of fragmentaton (now fragments can only get so small, and there can only be so many of them) and the problem of addressing (how big do addresses need to be to access any byte in your 500GB drive? Now the addresses can be shorter by 16 bits).


The universal method to check whether a set of connectives is complete in this sense is Post's classes: there are 5 function classes such that a set of functions is complete iff it isn't a subset of any of these 5. One of the 5 is affine functions, as described in Yuval's answer; the rest are monotone, self-dual, 0-preserving, and 1-preserving functions.

It's pretty easy to show that all 5 classes are closed: any composition of functions from one of them will also belong to the same class. So if your set is a subset of a Post's class, it can't be complete. Showing the other direction is more complicated, but likely you'll learn the proof in the near future.


An argument for error accumulation during complex DFT

Since the fourier coefficients might in general be complex numbers $xi + y$ with $x$ or $y$ or both irrational, a standard finite precision computer of course will not output the exact fourier coefficients. However, if you want to claim that you cannot get a good approximation, you are wrong.

Look at this answer. Markus shows that if you want to compute DFT of a vector of length $n$ up to $b$ bits of precision, then you need floating point numbers with $m$ bits where $m = \log n + \log \log n + b + C$ for $C$ some fixed constant. This is a fairly good bound. Also, there is no reason why the double type of the C language should be any hard limitation if you care about precision: there are libraries for high-precision arithmethic, and it's not even all that hard to code your own procedures to multiply and add floating point numbers of fixed high (higher than that of double) precision. Markus's answer shows that you won't lose much in running time: the running time will be roughly $n \log n (b/\log n)$ (for $b > \log n$) arithmetic operations on standard C types.