Is Karp Reduction identical to Levin Reduction Definition: Karp Reduction
A language $A$ is Karp reducible to a language $B$ if there is a polynomial-time computable function $f:\{0,1\}^*\rightarrow\{0,1\}^*$ such that for every $x$, $x\in A$ if and only if $f(x)\in B$.
Definition: Levin Reduction
A search problem $V_A$ is Levin reducible to a search problem $V_B$ if there is polynomial time function $f$ that Karp reduces $L(V_A)$ to $L(V_B)$ and there are polynomial-time computable functions $g$ and $h$ such that

$\langle x, y \rangle \in V_A \implies \langle f(x), g(x,y) \rangle \in V_B$,

$\langle f(x), z \rangle \in V_B \implies \langle x, h(x,z) \rangle \in V_A$

Are these reductions equivalent?

I think the two definitions are equivalent. For any two $\mathsf{NP}$ languages $A$ and $B$, if $A$ is Karp reducible to $B$, then $A$ is Levin reducible to $B$.
Here is my proof:
Let $x$ and $\overline{x}$ be arbitrary instances of $A$ while $x'$ be that of $B$.
Suppose $V_A$ and $V_B$ are verifiers of $A$ and $B$.
Let $y$ and $\overline{y}$ be arbitrary certificates of $x$ and $\overline{x}$ according to $V_A$.
Let $z$ be that of $x'$ according to $V_B$.
Construct new verifiers $V'_A$ and $V'_B$ with new certificates $y'$ and $z'$:
$V'_A(x,y'):$

$y'=\langle 0,\overline{x},\overline{y}\rangle$: If $f(x)\ne f(\overline{x})$, reject.
Otherwise output $V_A(\overline{x},\overline{y})$.
$y'=\langle 1,z\rangle$: Output $V_B(f(x),z)$.

$V'_B(x',z'):$

$z'=\langle 0,z\rangle$: Output $V_B(x',z)$.

$z'=\langle 1,x,y\rangle$: If $x'\ne f(x)$, reject.
Otherwise output $V_A(x,y)$.

The polynomial-time computable functions $g$ and $h$ are defined as below:
$g(x,y')$

$y'=\langle 0,\overline{x},\overline{y}\rangle$: Output $\langle 1,\overline{x},\overline{y}\rangle$.

$y'=\langle 1,z\rangle$: Output $\langle 0,z\rangle$.

$h(x',z')$

$z'=\langle 0,z\rangle$: Output $\langle 1,z\rangle$.

$z'=\langle 1,x,y\rangle$: Output $\langle 0,x,y\rangle$.

Let $Y_x$ be the set of all certificates of $x$ according to $V_A$ and $Z_{x'}$ be the set of all certificates of $x'$ according to $V_B$.
Then the set of all certificates of $x$ according to $V'_A$ is $0\overline{x}Y_\overline{x}+1Z_{f(x)}$ such that $f(x)=f(\overline{x})$,
and the set of all certificates of $x'$ according to $V'_B$ is $0Z_{x'}+1\overline{x}Y_\overline{x}$ such that $x'=f(\overline{x})$.
(This is derived from the accepting language of $V'_A$ and $V'_B$.)
Now let $x'=f(x)$, the rest part is easy to check.

No. First note that Levin reduction only makes sense with respect to classes which certificate has a meaning, e.g. $\mathsf{NP}$ while Karp reduction is general. The word "certificate" for a problem makes sense only when a verifier is fixed. Levin's reduction assumes that the verifiers are fixed. You cannot change the verifiers. (In the following I assume that certificate verifiers are fixed as required by definition of Levin reduction.)

Second, Levin reduction means that one can find the certificate for one from the certificate for the other. It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general.

If we can reduce instances of a problem $A$ to problem $B$ it doesn't mean we have a way of computing a certificate for one from a certificate for the other.

For this to be true we need the fact that a certificate search problem corresponding to the decision problem is polynomial time reducible to the decision problem. This is true for $\mathsf{NP\text{-}complete}$ problems but not known to be true generally even for $\mathsf{NP}$ problems.


Algorithm for assigning items to one of two sets (2-CNF?) I have a set of items (A, B, C, D, ...) which I want to assign to one of two sets (set1, set2). Trying all possible assignments and selecting my favorite has complexity $O(2^n)$, so I am trying to prune the number of assignments evaluated. I want to do this based on available knowledge that certain pairs MUST be present in the same set.
For instance: given A, B, C, D, and knowing that the following pairs must be together:
A & B, B & C a solution would be set1 = {A,B,C}, set2 = {D}. Knowing that A, B, C must be together drastically reduces the number of assignments which have to be evaluated.
Note that there are pairs of items that may not occur in the same set. These relations however, are less obvious, which is why I restricted myself to finding the pairs listed above.
This already kind of looks like a satisfiability problem, which is good, as 2-CNF can be solved in linear time. In satifiablity, setting the variables to true / false could mean assigning the items to set1 / set2 respectively. However, expressing items must be in the same set looks like this: (A /\ B) V (!A /\ !B), which is 2-DNF.
2-DNF can be converted to 2-CNF in polynomial time, but would it be possbile to translate my problem directly to 2-CNF? This would allow me to keep the linear time complexity.
EDIT:
As explained in the comments, 2-CNF would be satisfied by placing all items in the same set, which would defeat the purpose as this may not result in a "favorite" assignment. A better solution is the answer by @D.W., where for each connected component (which represents a cluster of items that must appear together), we can choose in which set to place it. This reduces the number of assignments that have to be evaluated, and allows us to find our "favorite" assignment.

There's a simpler approach, without using 2CNF.  Instead, build an undirected graph with edges between pairs of items that must be together, then find connected components (e.g., using DFS).  Now you can freely choose, for each component, which set it is associated with, and add all of its elements to that set; the result will be valid regardless of how you make those free choices.


Knapsack dynamic programming complexity issue for $W=1$, is it $O(n)$? The 0-1 knapsack problem is given by

$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P1}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(nW)$.

If I define $p_i=w_i/W$, I get the following knapsack problem:

$$\begin{align}&\text{maximize } \sum_{i=1}^n v_ix_i,\tag{P2}\\&
\text{subject to } \sum_{i=1}^n p_i x_i \leq 1,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

Running the dynamic programming algorithm for this problem would give an optimal solution in $O(n)$. This is not true, isn't it?

The running time is $O(nW)$ if all weights are integers. This is because the dynamic programming table is indexed by possible weights of subsets. If all weights are integers, then since we are only interested in subsets whose sum of weights is at most $W$, there are only $W+1$ weights of subsets that could possibly interest us. This is where the $W$ factor in the running time is coming from.

Dividing all weights by $W$ accomplishes exactly nothing. You haven't changed the problem, so the required time for solving it is remains exactly the same.


What is the case 2 in master theorem? I am confused about the statement of the Master theorem in CLRS book.

Here is the link of the book CLRS.

In page 94, the theorem, in case 2, states that:

If $\displaystyle f(n)=\Theta(n^{\log_ba})$, then $T(n) = \Theta(n^{\log_ba}\lg n)$.

What if $T(n) = T(n/2) + \Theta(\lg n)$? We have $f(n)=\Theta(\lg n)\neq\Theta(1)$.

I found the slides of the CLRS book in MIT website here where the statement of the theorem looks different in case 2 (page 5).

If $\displaystyle f(n)=\Theta(n^{\log_ba}\lg^k n)$, then $T(n) = \Theta(n^{\log_ba}\lg^{k+1} n)$.

What am I missing here?

There are several different versions of the Master Theorem. This situation is common in mathematics: a well-known theorem may have several common versions, for example the Chernoff–Hoeffding bound(s). Perhaps one version is the original, and another is a widely known strengthening; or perhaps one version is the original, and another is the one appearing in textbooks, which is slightly weaker (since the proof of the complete theorem is too long or too difficult). Sometimes an apparently weaker version of the theorem is equivalent to the full theorem with a short proof (for example, Hilbert's Nullstellensatz).

As Raphael mentions in his comment, here you are encountering two common versions of the Master Theorem, one of which is stronger and can handle your case. If you were writing a paper, I would recommend citing a source which states (and preferably proves) the version of the theorem you use.


hamming distance of bloom filters In the introduction of Distance-Sensitive Bloom Filters the authors state:

  The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can be used as a measure of the similarity of the underlying sets.

This statement is followed by a reference to another paper, which could not clarify this statement for me.

Question: What is the precise relation between the hamming distance of two bloom filters and the similarity of the corresponding sets?

Let $S,T$ be two sets of size $n$.  Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x_S$ be the $m$-bit vector corresponding to $S$, and $x_T$ the $m$-bit vector corresponding to $T$.

If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then
the expected value of the Hamming distance between these two bit-vectors is

$$\mathbb{E}[d(x_S,x_T)] \approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

This gives a relation between the similarity of the two sets (in terms of the number of elements they have in common) and the Hamming distance between their Bloom filters.  In particular: the greater their similarity, the smaller the (expected) Hamming distance between their Bloom filters.

Derivation and details

Where did I get this expression for the expected value of the Hamming distance from from?  Well, consider the $i$th bit of $x_S$.  The probability that this is 0 is

$$\Pr[x_S[i]=0] = \left( 1 - {1 \over m} \right)^{kn}.$$

For the corresponding bit of $x_T$, the probability it is 1 is

$$\Pr[x_T[i]=1] = 1 - \left( 1 - {1 \over m} \right)^{kn}.$$

How about the conjunction of these two events, i.e., that $x_S[i]=0$ and $x_T[i]=1$?  We can't just multiply the two probabilities, because the two events aren't independent: the $pn$ elements in $S \cap T$ will certainly hash to the same place.  However, we can take that into account by expressing the probability as

$$\Pr[x_S[i]=0 \land x_T[i]=1] = q_1 \times q_2 \times q_3$$

where $q_1$ is the probability that none of the elements of $S \setminus T$ hash to position $i$ (i.e., $\Pr[x_{S \setminus T}[i]=0]$); $q_2$ is the probability that none of the elements of $S \cap T$ hash to position $i$ (i.e., $\Pr[x_{S \cap T}[i]=0]$); and $q_3$ is the probability that at least one of the elements of $T \setminus S$ hashes to position $i$ (i.e., $\Pr[x_{T \setminus S}[i]=1]$).  Each of these can be computed as

$$\begin{align*}
q_1 &= \left(1 - {1 \over m}\right)^{k \cdot |S \setminus T|} = \left(1 - {1 \over m}\right)^{k(1-p)n}\\
q_2 &= \left(1 - {1 \over m}\right)^{k \cdot |S \cap T|} = \left(1 - {1 \over m}\right)^{kpn}\\
q_3 &= 1 - \left(1 - {1 \over m}\right)^{k \cdot |T \setminus S|} = 1 - \left(1 - {1 \over m}\right)^{k(1-p)n}.
\end{align*}$$

Therefore, multiplying these quantities, we find that

$$\Pr[x_S[i]=0 \land x_T[i]=1] =
\left(1 - {1 \over m}\right)^{kn} \times \left(1 - \left(1 - {1 \over m}\right)^{k(1-p)n} \right).$$

Using the approximation $(1 - 1/m)^t \approx e^{-t/m}$, we see that

$$\Pr[x_S[i]=0 \land x_T[i]=1] \approx
\exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).$$

Now by symmetry,

$$\begin{align*}
\Pr[x_S[i] \ne x_T[i]]
 &= \Pr[x_S[i]=0 \land x_T[i]=1] + \Pr[x_S[i]=1 \land x_T[i]=0]\\
 &\approx 2 \exp\{-kn/m\} \times (1 - \exp\{-k(1-p)n/m\}).
\end{align*}$$

Finally, linearity of expectation tells us that the expected Hamming distance between $x_S$ and $x_T$ is $m$ times the above quantity.


Software metric for data growth I'm writing a paper for some software that uses combinatorics to generate large result sets. I would like to describe that if I put in $n$ elements, I will get in return $2^n$ elements.

Is there a software metric that describes "data growth" for an algorithm or do I simply write "the data grows exponentially"?

btw: The size of the $2^n$ elements varies , so I cannot determine their size (storage)

Apparently, the best you can do is write something on the lines of "the number of result sets is exponential in the number of input input elements". This is better than simply saying "the data grows exponentially" since such growth must happen with respect to some quantity. It also might be a good idea to state the value $2^n$ somewhere (in the more technical sections) so it is clear it is a precise and not an asymptotic estimate.

It is unfortunate you cannot estimate the size of each result set. Are you sure not even very conservative or even empirical estimates are possible? (If that is the case, then consider adding at least one of those.)


Developing invariants for comparing two strings The following algorithm is supposed to compare two strings $S_1$ and $S_2$ ("/\" for empty string):

X = S1
Y = S2

E = true
// (1)
while X != /\ and Y != /\ and E == true
  if head(X) == head(Y)
    X = tail(X)
    Y = tail(Y)
  else
    E = false
// (2)
if !(X == /\ and Y == /\)
  E = false
  // (3) S1 != S2 \land E = false
// (4) S1 = S2 <=> E = true
return E

I want to develop invariants at points (1) and (2).

The invariant at (1) I choose is $$S_1 = S_2 \iff X = Y \land E = true.$$

From it, I can derive an invariant at (2):

$$(S_1 = S_2 \iff X = Y \land E = true) \land \lnot(X \neq \Lambda \land Y \neq \Lambda \land E = true).$$

Then I tried to simplify the formula:

$$(S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda \lor Y = \Lambda \lor E = false)\\
\equiv
\big((S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (Y = \Lambda)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big) \\
\equiv
(S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor
\\ (S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true) \lor
\\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big)\\
\equiv
\big(S_1 = S_2 \iff (X = \Lambda \land Y = \Lambda) \land (E = true)\big) \lor \\ \big((S_1 = S_2 \iff X = Y \land E = true) \land (E = false)\big)$$

My problems are

Is the derivation above correct? If so, how to further simplify this formula? In particular, how to deal with the second disjunction? Is it simply $S_1 \neq S_2 \land E = false$?
How does the invariant at (3) and (4) follow from the one at (2)?
Can we obtain an invariant at (2) in a single conjunct instead of multiple disjuncts?

I would not simplify $(2)$ at all. Just apply the rules for if, =, and command composition. Use weakening (pre- or post- rules) when convenient to do so.

Below, I added an empty else branch for clarity.

// (2): (S1 = S2 <=> X = Y \land E = true)
//            \land \lnot(X != /\ \land Y != /\ \land E = true)
if !(X == /\ and Y == /\)
  // (3a): (2) \land (X != /\ \lor Y != /\)
  // (3b): S1 != S2 \land false = false
  E = false
  // (3): S1 != S2 \land E = false
  // (4): S1 = S2 <=> E = true
else
  // (3c): (2) \land X = /\ \land Y = /\
  // (4): S1 = S2 <=> E = true
// (4): S1 = S2 <=> E = true
return E

Above, we used weakening, so we are left with proving:

$3a\implies 3b$. By contradiction, assume $\lnot 3b:\ S_1=S_2$ and $3a$. Since $S_1=S_2$, then by $2$ (part of $3a$) we have that $X=Y \land E=true$. We also know that at least one of $X,Y$ is not empty from $3a$, hence both are not empty since they are equal. This contradicts the last part of $2$, namely $\lnot(X\neq\Lambda \land Y\neq\Lambda \land E=true)$.
$3 \implies 4$. Two truths are always equivalent.
$3c \implies 4$. Replacing both $X,Y$ in $2$ with $\Lambda$, the first part of property $2$ immediately simplifies into $4$.

The first item can also be proved more formally, but I think you get the idea.

About your attempt: you used the equivalence

$$
\begin{array}{l}
\big((S_1 = S_2 \iff X = Y \land E = true) \land (X = \Lambda)\big)
\\
\equiv (S_1 = S_2 \iff X = \Lambda \land Y = \Lambda \land E = true)
\end{array}
$$

However, this does not hold in general, e.g. for $X={\sf x}, Y={\sf y}, S_1=\Lambda, S_2={\sf h}, E=true$. Or, more in general, when $X$ is non empty, and $S_1\neq S_2$. In such case, the former is false, but the latter is true.


Behavior of iterative application of LZ77 I have been experimenting with LZ77 (naively $O(n^2)$ runtime, infinite window). Applying it to the 7th Fibonacci word $abaababaabaab$ yields the correct LZ factorization:

$\qquad a,b,a,aba,baaba,ab$.

My question is about the behavior of LZ77 if we iterate it. My experiments suggest that reapplication of LZ77 to the input will yield no further patterns that were not found the first time.

By reapplication I mean, where in the first instance we treat the factors of the string as the sequence of unit symbols 'a' and 'b', in the second application the factors are the LZ factors. I was hoping to discover (over larger various texts, like the Complete Sonnets of Shakespeare) increasing gains, and possibly, "multilevel" patterns found by LZ over the sequence of factors of the previous iterate. But none of this occurred. The sequence of factors after the second iteration is exactly the same as the first.

So where is the bug in my thinking? Is there a simple proof of this given the definition of an LZ factor being the longest prefix from the current position occurring in the concatenation of the preceding LZ factors?

Lempel and Ziv proved that under some reasonable assumptions, the limiting rate of their algorithm is equal to the entropy of the text. That means that in the limit, the output should be completely random. Random text cannot be compressed (on average), so you should expect that if you take a long text and apply Lempel-Ziv twice, then the second time wouldn't compress the text at all.


Sum of $\log n$ $n$-bit integers is in $\mathsf{AC^0}$ I am trying to show that the sum of $\log n$ $n$-bit integers can be computed in $\mathsf{AC^0}$. I know that the iterated addition is computable by fan-in $2$ circuits of depth $O(\log n)$, so the sum of $n$ $n$-bit integers is in $\mathsf{NC^1}$. This means that the bound is very tight. I found somes notes here which show that the iterated sum of $n$ $n$-bit integers actually lies in $\mathsf{TC^0}$.

Any help or hint on the subject would be greatly appreciated.

Here is a proof sketch. We use the fact that any function on $O(\log n)$ bits can be computed in depth 2 and polynomial size.

The input is $\log n$ integers of length $n$, which we can think of as an $n\times \log n$ matrix.
Sum the columns of the matrix to get a vector of length $n$ in which each entry has length $\log\log n$. We can also think of this as a staggered sum of $n$ numbers of length $\log \log n$, which is equivalent to the original sum.
Divide the staggering sum into blocks of length $\log n/\log\log n$, by possibly dividing each summand into two parts. Each block contains $\log n/\log\log n$ summands of length $\log\log n$. Sum each block to obtain a result of length at most $2\log\log n \leq \log n/\log\log n$ (for large enough $n$). We can think of this as a new staggering sum.
Repeat the previous construction. Now each block contains two summands, so the result is of length $\log n/\log\log n + 1$.
Again divide into blocks. This time each block contains the sum of a full length ($\log n/\log\log n$) integer $x$ and one extra bit (a least significant bit) $y$. The actual sum also includes an extra carry bit $z$ which depends on the less significant blocks. If we could determine $z$ then we could determine the value of the sum in that block.
It remains to show how to calculate the carry bit coming from the addition of blocks $B_k,\ldots,B_0$ (most significant to least significant). Suppose that in block $B_i$ we are adding $x_i$ to the bit $y_i$. Let $M$ be a block full of 1s. There is carry iff for some $i$, $x_k + y_k = x_{k-1} + y_{k-1} = x_{i+1} + y_{i+1} = M$ and $x_i + y_i = M + 1$.

If you have trouble with the proof sketch (which I haven't described very clearly), try using diagrams. The idea is to start with the initial sum and replace it with progressively simpler but equivalent sums, until the final sum can be computed in one go.


Show that the running time of the build_heap function is $O(n)$ Given the following two functions, prove that the build_heap function, which transforms an array A into a max-heap-sorted array A' runs in $O(n)$.

heapify(A, i):

Input: array A of length n, index i

left = 2i + 1 (left child node)
right = 2i + 2 (right child node)
largest = i if left < n and A[left] > A[i] then
    largest = left
end if
if right < n and A[right] > A[largest] then
    largest = right end
if if largest != i then
    swap(A, i, largest)
    heapify(A, largest)
end if

build_heap(A):

Input: Array of length n

for i = floor((n-1)/2) to 0 do
  heapify(A, i)
end for

  Hint: Assume that A has $2^j-1$, for $j \in \mathbb{N}$, elements. You can also use the fact that $\sum_{k=0}^{\infty}\frac{k}{2^k} = 2$.

I don't really understand why the formula is given in the hint, or rather how to explicitly use it to prove that build_heap(A) runs in $O(n)$.

I would say that the worst case for the heapify function is given when a call of `heapify(A,0) calls itself recursively as much as possible. I think a binary tree with n nodes has depth of $\lceil lg(n) \rceil $, so the maximum number of recursive calls should be $\lceil lg(n) \rceil $.

I'm not sure but my guess is that the formula is trying to tell me that the running time of heapify is $O(1)$? But I don't really see how that's possible. If it were a constant then clearly build_heap(A) would run in $O(n)$, but how can it be constant?

Can someone please help me out?

The main point is to do the analysis exactly without being sloppy. Let me define the depth of a node in this way. Depth of any leaf is 0 and depth of any non-leaf node is maximum depth among its children plus 1. One can note that
depth = $\log n - $ height.

Then for a particular node how much time does heapify take? By definition of depth you can see it is order of depth of the node.

Now the total time for buildheap is $$\sum_{d=0}^{\log n} \text{(number of nodes of depth d)}\cdot O(d).$$

Now my claim is that there are at most $n/2^d$ nodes at depth $d$ (can you see why?). For example number of leaves (depth 0) is at most $n/2^0 = n$.

Then, building time is
$$ \sum_{d = 0}^{\log n}  \frac{n}{2^d} \cdot O(d) = O(n)\cdot\sum_{d = 0}^\infty  \frac{d}{2^d} = O(n) \cdot 2 = O(n). $$


Computing automaton for $L(A) / L(B)$ gives ones for $A,B$ I'm trying to figure out whether infinite language change the answer.

Show that the following language is decidable:
$$L=\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)=L(0^*1^*)$}\}.$$

(I am talking about right division.)
We know how to check whether the language of a DFA is finite, and given two DFAs, we know how to check whether their languages are equal. The algorithms I know to the above problems uses the DFA's, so it is necessary having the DFA's in order to decide those problems.
I'm trying to figure out whether $|L(B)|=\infty$ changes the answer. To the best of my understanding, because $|L(B)|<\infty$, we can explicitly construct a DFA that accepts $L(A)/ L(B)$, whereas if $L (B)=\infty$ all we know is about the existence of $DFA$ that accepts $L(A)/ L(B)$.
However, even if $L(B)$ is an infinite language, since there is a finite number of DFAs, one of which accepts $L(A) / L(B)$, I can certainly know that there is a Turing machine that decides the language $L$.
Right?

This answers a different version of the question, in which the language in question is $L(A) \setminus L(B)$.
Here is an algorithm for deciding $L$:

Use the product construction to construct a DFA $C$ whose language is $L(A) \setminus L(B)$.
Let $D$ be a DFA whose language is $0^*1^*$.
Use the product construction again to construct a DFA $E$ whose language is $L(C) \Delta L(D)$.
Check (using BFS/DFS) whether some final state of $E$ is reachable from its initial state.
Output "yes" if no final state is reachable from the initial state. Otherwise output "no".

As you can see, whether the languages encountered along the way are finite or infinite makes absolutely no difference for this algorithm.


What is the difference between a module in a monolithic kernel and a server in a microkernel? I´m not exactly sure what kind of impact these two things have on kernel design. Are servers more flexible because of running in user space, for instance, and does adding a module require a new build of a kernel?

Basically, a module runs at the same memory space than the kernel and a server runs in a different one.

Although a module can surely be added/removed on-the-fly (linux kernel does that), any misbehavior caused by it may affect the entire system, whether in the micro-kernel architecture, only the server gets compromised.


Efficiently finding the maximum pairwise GCD of a set of natural numbers Consider the following problem:
Let $S = \{ s_1, s_2, ... s_n \} $ be a finite subset of the natural numbers.
Let $G = \{$ $\gcd(s_i, s_j) \mid s_i, s_j \in S,$ $ s_i \neq s_j  \}$ where $\gcd(x,y)$ is the greatest common divisor of $x$ and $y$
Find the maximum element of $G$.
This problem can be solved by taking the greatest common divisor of each pair using Euclid's algorithm and keeping track of the largest one.
Is there a more efficient way of solving this?

Solution 1
Time Complexity: $\mathcal{O}(n\sqrt{\max(s_i)})$
Maintain an array, $\texttt{cnt}$, to store the count of divisors. For each $s_i$, find its divisors and for each $u$ in those divisors, increment $\texttt{cnt}[u]$ by one. The greatest GCD shared by two elements in $S$ will be the greatest $u$ where $\texttt{cnt}[u] > 2$.
For each $s_i$, we only need to check up to $\sqrt{s_i}$ for its divisors, so the complexity is $\mathcal{O}(n\sqrt{\max(s_i)})$.
Solution 2
Time Complexity: $\mathcal{O}(\max(s_i)\log(\max(s_i)))$
Given a value $x$, we can check whether there exists a pair with GCD equal to $x$ by counting all the multiples of $x$ in $S$ and checking whether that count is at least 2.
With that information, loop through all possible values of $x$ and keep the maximum one with at least two multiples in $S$. This works in $\mathcal{O}(\max(s_i)\log(\max(s_i)))$ time since
$$
\sum_{x = 1}^{\max(s_i)} \frac{\max(s_i)}{x} \approx \max(s_i)\log(\max(s_i)).
$$


Programming a genetic algorithm with a non-fixed size I am trying to write a genetic algorithm for a program. Most examples for genetic algorithms use something like this as the input:

aaaaaaaaaa

and mutate/crossover until they get

helloworld

or similar. This requires however that you start with something of length N, but my search space doesn't have a fixed length. How should I alter the mutation/crossover steps to allow for changes in unit size?

There are plenty of possibilities:

Add/remove a symbol at the end with probability $c$.
Add/remove $k$ symbols at the end with probability $c \cdot 2^{-k}$.
For every symbol, remove it with probability $c_1$;
for every gap, insert a symbol with probability $c_2$.
For every symbol $a$, convert it to $a^k$ with probability $c \cdot 2^{-k-1}$.

And so on and so on. Basically, whatever works for you is good. Without any knowledge about the function you are trying to optimise, it is impossible to guess which strategies make more sense than others.


Questions about SIMD instructions What is the trend over time for the size of registers of x86 CPUs? I know that we have today 512-bit registers, but is there a kind of Moore's Law to predict the size of registers in the future?

Thank you very much.

Moore's law is only indirectly involved here.  NVidia's SIMD registers are 1024 bits wide, have been that wide since at least 2006, and haven't grown.  Intel's slowly grew from 64-bit MMX in 1996, to 128-bit SSE in 1999, to 256-bit AVX in 2008, to the 512-bit AVX-512 in 2015.

My prediction is that neither Intel nor NVidia will grow their SIMD registers any wider from here on out.  The cost would be large, and the benefits decrease with each doubling.

The reason the cost would be large for Intel is that Intel has a whole bunch of inter-related design decisions that would need to be revisited.  Intel processors have used a cache-line width of 512 bits since the Pentium-4.  The cache ports to the cpu pipeline are 512-bits wide.  The BTB designs probably assume 64-byte cache lines.  I assume the coherence busses for multi-socket systems are 512-bits wide.  (I'm in the software division, not the hardware division.)  There is probably quite a bit of legacy code that has now been optimized for 512-bit cache lines.  For example: to avoid false-sharing overhead on cache lines, data structures may be aligned on 64-byte boundaries.  Customers would get annoyed if they spent thousands of dollars for a new server only to discover that their legacy code now runs slower.  I would guess that NVidia faces similar constraints.

The benefits decrease with each doubling because of something similar to Amdahl's law.  The benefit of SIMD is supposed to be that you double your ALU bandwidth, while keeping the area (and power) of the rest of your pipeline constant.  Suppose your processor is 16mm2, of which 1mm2 is your 32-bit ALU and register file, and you are getting 1 GFlOPS.  That's 1/16 GFlOPS/mm2.  Move to 64-bit SIMD, and your performance doubles, but so does the size of your ALUs and register file.  So now you are getting (at best) 2 GFloPS/17mm2, which is almost twice as good.  But when you get up to 512-bit SIMD you have 16 GFlOPS/31mm2.  Now doubling to 1024-bit SIMD gets you to 32 GFlOPS/47mm2, which is only 32% better.


Maximum bipartite matching when some nodes must be matched Consider the problem of finding a maximum cardinality bipartite matching under the additional condition that some set $S$ of nodes (all lying on the same side of the bipartition) must be matched.

Can this problem be reduced to (ordinary) bipartite matching? Bipartite matching can be solved in $O(m \sqrt{n})$ by Hopcroft Karp or $O(n^{\omega})$ where $\omega$ is the exponent of matrix multiplication due to a recent result, or $\widetilde{O}(m^{10/7})$ in terms of the number of edges m. Do these running times carry over to this problem? I think Hopcroft-Karp can produce the same running time with some modifications, but am not sure about the others; so I'm wondering if a simple reduction to matching exists -- this would allow one to bypass an analysis of the above papers.

Assume the maximum matching problem is $U-V$ matching, and $S\subset U$.

Find maximum $S-V$ matching. If the result equals $|S|$, then it is a feasible matching in original $U-V$ matching problem. Othewise, no matching meets the requirement.
Using the feasible matching got in previous step as basis, improve it by augmentation, thus computing maximum $U-V$ matching.

Since an augmenting path never turns a matched vertex into unmatched vertex, the maximum matching found by above algorithm meets the requirement.

Using Hopcroft Karp algorithm, the complexity is $O(m\sqrt{n})$.

I don't know if the $O(n^{\omega})$ or $\tilde{O}(m^{10/7})$ algorithm works. But basically any maximum matching algorithm that based on augmentation works. And for those unit capacity network flow algorithms, it also works as long as it accepts an initial feasible flow and arguments along it, taking the lower capacity bound into account. (ie. never augment back through edges $s \to x (x\in S)$)


How many bytes of memory is used just to "acknowledge" that a certain file is a .jpg? I'm rather new to computers and how they work in the microscopic scale, but here's the little bit that I know.

  Computers have lots of transistors in them, both in memory and processor, and each transistor has two states, on and off. They are translated to binary equivalents 0 and 1. All data is stored in computers as combinations of 0s and 1s. Each 0 or a 1 is called a bit, and 8 bits make up a byte. A single byte is too small so units like kilobytes, megabytes, and gigabytes are more common.

I know that .jpg images occupy some memory in the computer, usually in the orders of kilobytes. However, the computer must know that the 0s and 1s that make up the image are for the image, and the computer must acknowledge this. In order to inform the computer that these 0s and 1s are assigned for a .jpg image, there must be a few bytes of data to inform that the rest of the bytes are a part of the image file. How many bytes would just acknowledging the file type take?

Depends on how accurately you want it to be.

If you trust the extension then all you need is the 4 last characters in the file name (32 bits)

If you trust the magic header number then you need to check the file starts with 3 bytes ff d8 ff (24 bits). Though other file types have different sizes of magic number. There is a (non-exhaustive) list of them on wikipedia.

If you want to make sure the file is an actual image then you need to actually decode it. Here the size depends on the file size.


If the language $A$ is decidable and the language $B$ is recognizable, then the language $A \cap B$ is recognizable? I am discussing with a friend the following question:

If the language $A$ is decidable and the language $B$ is recognizable, Then the language $A \cap B$ is recognizable?

I believe it is.
My point is that if the machine that recognizes B never halt in some string, so the bigger machine will never know what to answer.

The image makes my point.

But my friend says that the $A \ cap B$ is a subset of $A$, then it is decidable.

You are correct, without further information we can only say that $A\cap B$ is recognizable.

A simple example would be to let $B$ be any recognizable (but not decidable) language - the Halting Problem for example, if you want to be melodramatic, and let $A = \Sigma^{\ast}$. Then $A \cap B = B$, so clearly can't be decidable.

It is of course possible that the intersection happens to be decidable, (for example if $A \cap B = \emptyset$ is a trivial example), but this may not be true in general.


Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$ Sipser provided the following proof to prove the mapping reduction from $A_{TM}$ to $HALT_{TM}$, it in fact tried to build a mapping function:

My problem is the way this proof works. The function must take $<M,w> \in A_{TM}$ and produce $<M',w'>$  if and only  if $<M',w'>\in HALT_{TM}$ We know by the hypothesis $<M,w>\in A_{TM}$. The machine $M'$ runs $M$ on an input $x$ not the input $w$. Now what if $<M,x>\notin A_{TM}$ and $<M,w>\in A_{TM}$? then $M'$ will output the loop while since $<M,w>\in A_{TM}$ the output must be accept. As a result the output $<M',w>$ which is supposed to be in $HALT_{TM}$ is not truly corresponded to the input. I would be appreciated if you explain about my problem.

Thanks

Your conception of a reduction is incorrect. The reduction takes an instance $\langle M, w \rangle$ of $A_{TM}$ and returns an instance $F(\langle M,w \rangle)$ of $HALT_{TM}$ such that $\langle M,w \rangle \in A_{TM}$ iff $F(\langle M,w \rangle) \in HALT_{TM}$.

Second, $M'$ is a Turing machine that accepts a single input $x$. The pair $\langle M',w \rangle$ belongs to $HALT_{TM}$ if $M'$ halts when running on the input $w$. Hence when analyzing whether $\langle M',w \rangle \in HALT_{TM}$ or not, the relevant value of $x$ is $w$.

Here is another way to think of the proof. Given a Turing machine $M$, we construct another Turing machine $M'$ such that $M$ accepts $w$ iff $M'$ halts on $w$.

When describing $M'$, we use $x$ to denote its input. There is no definite value of $x$ like your post seems to assume — it stands for the input to $M'$. For a similar example, consider the function $f(x) = x^2$. What is the value of $x$? It has no definite value, being just a place holder. If we plug in $w$ for $x$ then we get $f(w) = w^2$.


How to decide if a propositional formula is a well formed? So, I have the following propositional formula:
(((P → Q) ∨ S) ↔ T)
How do I decide if it's well formed?

Perhaps this might help.

Well-formed: $(P \lor Q)$.

Not well-formed: $(P \lor Q$.

More generally, in class you must have been shown a definition of well-formed formulae. Use it.

Well-formed formulae are usually defined inductively. One possible definition is:

For every variable $v$, $v$ is a well-formed formula.
For every well-formed formula $\varphi$, $(\lnot \varphi)$ is well-formed.
For every binary symbol $\circ \in \{ \land, \lor, \rightarrow, \leftrightarrow \}$ and two well-formed formulae $\varphi,\psi$, $(\varphi \circ \psi)$ is well-formed.
"No other formula is well-formed."

The last "axiom" isn't quite formal. What we really mean is that a formula is well-formed only if it can be proved well-formed by using the first three axioms. (This is equivalent to the definition using least fixed points, which you might have seen in class.)

What all this means is that in order to show that a formula is well-formed, all you need to do is derive it from the axioms. Showing that a formula isn't well-formed could be more difficult. Since the set of well-formed formulae is context-free, there is an efficient algorithm which given a formula decides whether it is well-formed.


Grammar for parsing simple mathematical expression mexp ::= (< mexp >) | < mexp >< mathlowop >< mexp > | < mulexp > | < float > | < var >

mulexp ::= < mexp >< mathhighop >< mexp >

mathlowop ::= + | -

mathhighop ::= / | *

That's the BNF I've come up with for parsing simple mathematical expressions where the operands can only be floats or variables. I've looked at a number of resources in books and on the web and for the same type of problem, they usually have a slightly longer, more complex bnf. Is my BNF incorrect in some way? Or is it correct but there is a significant advantage in doing it another way?

Your grammar will generate mathematical expressions, but you haven't captured the notion of operator precedence. For instance, there are two different ways your grammar can generate the expression $a+a*a$, one having the interpretation we'd write as $a+[a*a]$ and the other having $[a+a]*a$. Using the jargon, we'd say your grammar is ambiguous.

A grammar that avoids this problem is

< expression > ::= < term > + < expression > | < term > - < expression > | < term >

< term > ::= < factor > * < term > | < factor > / < term > | < factor >

< factor > ::= (< expression >) | < float > | < var >

See if you can generate $a+a*a$ in two different ways using your grammar and then try the same thing with this grammar. That should give you an idea of what's going on here.


Estimation of the number of solutions by Counting This is a question from a quantum computation textbook.

Consider a classical algorithm for counting the number of solutions to a problem. The algorithm samples uniformly and independently $k$ times from the Search Space of size $N$ for solutions using an Oracle that outputs 1 or 0, and let $X_1,X_2,X_3,...X_k$ be the results of the Oracle calls. So $X_j=1$ if the $jth$ Oracle call found a solution and $X_j=0$ otherwise. This algorithm estimates the number of solutions $S$:

  $$S=N * \sum_{j}\frac{X_j}{k}$$

Assuming the number of solutions is $M$ and this is not known in advance. The Standard Deviation of $S$ is stated and found to be:

  $$\Delta S=\sqrt{\frac{M(N-M)}{k}}$$

The question is:
Prove that to obtain a probability at least $\frac{3}{4}$ of estimating $M$ correctly to within an accuracy $\sqrt{M}$ for all values of $M$, we must have $k=\Omega(N)$.

I know how to get the 2nd equation from the 1st, which is by moving $N$ and $k$ to the left, thus treating $kS/N$ as a Binomial Distribution $B(k,\frac{M}{N})$. Then finding the variance of the Binomial Distribution and some algebraic manipulation will lead to the 2nd equation. I'm clueless in proving of $k=\Omega(N)$. Only thing I tried writing is:

  $$P\Big(\sqrt{\frac{M(N-M)}{k}}\leq \sqrt{M}\Big)\geq \frac{3}{4}$$

Can someone help me with this?

Consider a binomial random variable $X \sim \mathrm{bin}(n,p)$, and let $Y = (X - pn)^2$. A straightforward but long calculation shows that
$$
\frac{\mathbb{E}[Y]^2}{\mathbb{E}[Y^2]} =
\frac{np(1-p)}{p^3 + (1-p)^3 + 3(n-1)p(1-p)} = \frac{1}{3} + o(1).
$$
(This is to be expected, since a binomial random variable has roughly Gaussian distribution, and for Gaussian distributions the ratio is exactly $1/3$.)

Now let $Z = (S - M)^2$. It is still the case that
$$
\frac{\mathbb{E}[Z]^2}{\mathbb{E}[Z^2]} = \frac{1}{3} + o(1),
$$
since $Z$ is just a scalar multiple of $Y$ above, for an appropriate choice of parameters.

In view of applying the Paley–Zygmund inequality, let us estimate
$$
\theta = \frac{M}{\mathbb{E}[Z]} = \frac{M}{M(N-M)/k} = \frac{k}{N-M}.
$$
It follows that
$$
\Pr[|S-M| > \sqrt{M}] = \Pr[Z > M] \geq (1-\theta)^2 \left(\frac{1}{3} + o(1)\right).
$$
If we want the right-hand side to be bounded by some constant (in your case, $1/4$) then we need $\theta$ to be bounded from below by some constant $c$ (in your case, roughly $1-\sqrt{3/4}$). In other words, we need
$$
k = \theta (N-M) = \Omega(N-M).
$$
As long as $M$ is not very close to $N$, this is $\Omega(N)$.

(When $M$ is very close to $N$, less samples are needed. For example, only one sample is needed when $M = N$.)


A way to convert a binary tree into a grid Wondering if there is a way to convert a binary tree into a grid such as this:

                    a
                  /   \
                 b     c
                / \   / \
               d   e f   g

                    or

                 d--b--e
                    |
                    a
                    |
                 f--c--g

                    to

                 d--b--e
                 |  |  |
                 y--a--x
                 |  |  |
                 f--c--g

An arbitrary sized binary tree. I'm not super familiar with binary tree properties so I am not sure if this would even be possible or if edge cases would prevent it from being possible.

A vertex in the grid has $O(d)$ vertices at distance $d$ from it. In contrast, the complete binary tree of height $h$ as $2^h$ vertices at distance $h$ from the root. Therefore there is no isometric embedding of arbitrary binary trees in the grid. Similar considerations show that there is also no embedding of bounded distortion (in which distances increase by at most a constant factor).


Log-Space Reduction $CO-2Col \le_L USTCON$ I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction)

$USTCON$

  The $s-t$ connectivity problem for undirected graphs is
  called $USTCON$.

  [Input]: An undirected graph $G=(V,E)$, $s,t \in V$.

  [Output]: 1 iff $s$ is connected to $t$ in $G$.

$CO-2Col$

  A graph is $2$-colorable if there is a way to color the vertices
  of $G$ with $2$ colors, such that for every edge the two vertices
  on the edge are colored differently. $CO-2Col$ is the following
  problem:

  [Input]: An undirected graph $G$.

  [Output]: 1 iff $G$ is NOT $2$-colorable.

My solution is for an input graph $G$ the reduction outputs $(G',s,t)$ where
 $s$ an arbitrary vertex of $G$, $t$ is one of its neighbours and
$G'=G^2$ namely an edge $(u,v)\in E(G')$,iff there is $w \in V (w \ne u,v)$
such that $(u,w)\in E(G)$ and $(w,v)\in E(G)$.

$G$ is bipartite
iff $G'$ is not connected (and $s$ and $t$ belongs to different
parts).

But this only works when the input graph $G$ is connected.

A counter example: (if we choose s,t to be A,B)

How can I improve my reduction that it will work at the unconnected case? or maybe a new reduction is needed?

Thanks!

Hint: Extend the input graph to a connected graph which is bipartite iff the original graph is bipartite.

If the original graph is not bipartite, then the new graph will a fortiori not be bipartite. The more difficult direction is ensuring that when the original is bipartite, the new edges do not render it non-bipartite. This property is satisfied as long as the edges that you introduce do not close an odd cycle.

Further hint: Take $n$ copies of your original graph (where $n$ is the number of vertices), and add a new vertex $s$. Connect $s$ to the $i$th vertex in the $i$th copy.


Grammar for $\{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$ I'm trying to understand how the construction of simple grammars works.
In my textbook, there's the following example I am supposed to find a grammar for:

Let $L_1= \{a^n b^n c^m d^m \mid n \geq 1, m \geq 0\}$ be a language over the alphabet $\Sigma = \{a,b,c,d\}$. Find a grammar $G = (\Sigma, N, S, P)$ - where $N$ denotes the non-terminals, $S$ the start symbol and $P$ the production rules - such that $L(G) = L_1$, i.e. the grammar $G$ generates the language $L_1$.

These were my first thoughts analyzing the problem:

We need to have the same number of $a$'s and $b$'s
We need to have the same number of $c$'s and $d$'s
There needs to be at least one $a$ and one $b$
Examples of such a string: $aabbcccddd$, $ab$, $aabbcd$

Furthermore, let $\lambda$ be the empty symbol.
The start symbol $S$ should map to something like:
$$ S \rightarrow XY$$
Then
$$X \rightarrow aZb, \; Z \rightarrow X | \lambda$$
$$Y \rightarrow cYd | \lambda$$
Would something like that work? I'm confused because the textbook presented similar grammars and the production rules almost never used the empty symbol ($\lambda$).
Is it possible to construct this grammar without using $\lambda$?

You can always write a grammar without $\lambda$, unless the language itself includes $\lambda$. In that case, you will need the single production $S\to\lambda$ (where $S$ is the start symbol).
There's a simple algorithm for removing $\lambda$ from grammars. First, figure out which non-terminals might produce $\lambda$. (These non-terminals are called "nullable non-terminals".) Then, for each nullable non-terminal and for each production in which it occurs, add a new production which is the same but without the non-terminal. (If the non-terminal appears more than once in the same production, do this for each occurrence of the non-terminal.) Keep doing this until no more additions are possible. Then remove all of the productions with empty right-hand sides, except the empty production for the start symbol (if there is one).
Applying this algorithm to your example, we first find that $Y$ and $Z$ are nullable, while $S$ and $X$ are not. So then we need to add additional productions:

From $X\to a Z b$, add $X\to a b$.
From $Y\to c Y d$, add $Y\to c d$.
From $S\to X Y$, add $S\to X$.

That gives us:
$$S\to X Y, S\to X\\
X\to a Z b,
X\to a b \\
Z\to X,
Z\to \lambda \\
Y\to c Y d,
Y\to c d,
Y\to \lambda
$$
We then delete the two empty productions, leaving:
$$S\to X Y, S\to X\\
X\to a Z b,
X\to a b \\
Z\to X \\
Y\to c Y d,
Y\to c d
$$
At this point, we might note that $Z$ is totally redundant. We can simplify the grammar by just substituting its right-hand side in the only place where it is used:
$$S\to X Y, S\to X\\
X\to a X b,
X\to a b \\
Y\to c Y d,
Y\to c d
$$


How is it possible for a problem to be NP-Complete under polylog-time reductions? I have no source for this, but I've heard people offhandedly mention problems that are NP Complete under polylog reductions (I think SAT was one of them).

This confuses me - it seems to me that this is a violation of the nondetermistic time hierarchy.  If SAT (or whatever) can be solved in $NTIME(n^c)$ for some $c$, and any $NP$-problem can be reduced to SAT in $O(n^k)$ time for some fixed $k$, then it seems that we can solve any $NP$ problem in $O(n^{c+k})$ nondetermistic time -- obviously false.

So, it seems to me that SAT (or whatever) can only be NP-Complete under polytime reductions, and that for any polynomial, we can find a problem whose reduction to SAT takes more than that polynomial amount of time.

What am I missing?

What you probably heard was that many problems are NP-complete under logspace reductions, for example 3SAT. All this means is that (say) the algorithm in Cook's theorem can be carried out in logarithmic space, and that many reductions among problems can be carried out in logarithmic space. Wikipedia contains a relevant discussion of various notions of reducibility and their relation to NP-completeness.


Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct? In my formal language class, we define a language called PAL, which is on a alphabet set $\Sigma = \{0,1\}$. $PAL = \{w \in \{0,1\}^* : w = w^R\}$. We have proved that every string in this language will be pairwise inequivalent, i.e. every string is in its own Myhill-Nerode equivalence class.

However, what if we extend this definition to an alphabet $\Sigma$ that contains more than two characters?  Can I still claim any 2 distinct strings in $\Sigma^*$ are still pairwise inequivalent?

Your proof goes also through with a larger alphabet. Let $x,y\in \Sigma^*$, with $x\neq y$. We use as $z$ the word $10^{|x|+|y|+2}1x^{rev}$. Clearly, $xz$ is a palindrome and therefore the word is in the language. The word $yz$ however is not a palindrome. Note that the middle of $yz$ there has to be a $0$ coming from $z$, hence for being a palindrome the middle of $yz$ has to be centered between the two $1$s of $z$. As a consequence, $yz$ is a palindrome only if $x=y$. Thus $yz$ is not in the language.

For the proof you only need that $|\Sigma|\ge 2$. I would say having more letters makes it even easier, since you have more possibilities to choose the split word $z$.


Is there a typed SKI calculus? Most of us know the correspondence between combinatory logic and lambda calculus. But I've never seen (maybe I haven't looked deep enough) the equivalent of "typed combinators", corresponding to the simply typed lambda calculus. Does such thing exist? Where could one find information about it?

The expressive completeness of the typed combinators compared to the simply typed lambda calculus has been demonstrated. For each untyped combinator, one needs a whole family of typed combinators. For example, one has

$\mathbf{I}_{\alpha\to\alpha}$
$\mathbf{K}_{\alpha\to(\beta\to\alpha)}$
$\mathbf{S}_{\alpha\to(\beta\to\gamma)\to(\alpha\to\beta\to(\alpha\to\gamma))}$

for all combinations of simple types $\alpha,\beta$ and $\gamma$.

Alternatively, just think of the types as type schemes (or polymorphic types) and enter them into Haskell and voila: combinators.


checking time for a circuit of size in polynomial k On the page 1073 of CLRS(Introduction to Algorithms),

Given a circuit C, we might attempt to determine whether it is satisfiable by simply checking all possible assignments to the inputs. Unfortunately, if the circuit has k inputs, then we would have to check up to 2^k possible assignments. When the size of C is polynomial in k, checking each one takes Ω(2^k), which is superpolynomial in the size of the circuit.

Can I ask what is the reason that checking if one truth assignment is a satisfying assignment takes Ω(2^k)?

You've misunderstood.  They are saying that the running time to check all $2^k$ assignments (not the time to check one assignment) is $\Omega(2^k)$.  It's a reasonable misunderstanding, as their wording is unclear, but that's what they mean.


Solving complexity using summation I have the following algorithm:

func()
{
    for(i=1; i<n; i=i*2)
        print("aa");
}

How can I find Big-Oh using summation?

Finding a suitable sum here is a bit awkward since sums in mathematics tend to step up by one, always. So we have to normalize the sequence of values of i

$\qquad i = 1, 2, 4, 8, \dots [i<n]$

to

$\qquad i' = 0,1,2,3, \dots [???]$.

My notation already suggests that it's about finding the right termination predicate.

Roughly speaking, you're looking for the inverse operation to the repeated step function, which by itself is $i \mapsto 2i$.
I'm not sure how to lead you towards an answer unless you know about logarithms. If you do, it should be kind of obvious; roughly:

$\quad i' = 0,1,2,3, \dots [i'<\log_2 n \pm 1]$.

Do some tinkering to find out whether you need to use $\lfloor \log_2 n \rfloor$ or $\lceil \log_2 n \rceil$ as upper bound on $i'$.
Now, the rest is elementary.

Note that you can go about this by normalizing the for loop first:

for(i=1; i<n; i=i*2)
    print(i)

becomes

for(i' = 0; i' < log(2,n) +- 1; i'++)
    print(2^i');

Note that for functional equivalence, I start with $i'=0$ so that $2^{i'} = i$ in each iteration; you can also use $2^{i'-1}$ instead and start with $i'=1$. Try out a few things -- some make the code nicer, others the mathematics afterwards.

Make sure -- by proof and/or testing -- that the normalized loop computes exactly the same thing as the old one, and then it's all standard. You might need a cheat sheet to simplify the sum.


Turing Machine to write number How to construct a single-tape Turing Machine which writes the number 7 in UNARY number system, leaving the tape with a delimiter symbol followed by 7 1s?

So outout would be a tape contains #111111 and blank symbols afterward.

The language you describe is regular (because it's finite), so this can be really straight forward.

You could simple write a 1 and advance to the next state. Create 7 states, one state for each 1.

Consider input\output/direction the syntax for "if input is on the tape write output and move in direction"


When is Huffman code the most unoptimal? By giving an Huffman coding tree and the total frequency of the characters. how can I find the most unoptimal frequencies for each character such that the size of the code will require the most possible of bits?

There are several definitions of "unoptimal".
As vonbrand noted, Huffman coding falls back to binary encoding if all frequencies are equal.
For longest code length, this happens if the frequencies are Fibonacci numbers.
For worst compression rate compared to the entropy, this happens with an alphabet of two symbols where $p_0 = \varepsilon$ and $p_1 = 1-\varepsilon$. The Shannon entropy approaches $0$ bits per symbol as $\varepsilon \rightarrow 0$, but any Huffman code requires $1$ bit per symbol.
For size of the Huffman tree, there is no "worst case", because the size is the same no matter what the frequencies are. For an alphabet of $n$ symbols, the Huffman tree must have $n$ leaves and $n-1$ branches.


Algorithm to solve job assignment problem Can someone suggest an algorithm to solve job assignment problem with condition?

With condition means that some jobs cannot be done by some workers. For example table as shown below:

In this table x - means that it is impossible to do. For example, worker 1 cannot do jobs 1,3 and 5.

I encountered such situation and there may be cases as shown above when usual Hungarian algorithm seems cannot solve such task because there is no way to complete all tasks by distributing one task per worker.

However, my main case it is allowed that one worker wil do several tasks (tasks, which worker can do). Main task is to complete all jobs using existing workers, but it is desirable that, all workers do roughly same number of tasks.

So is there some solution of such problem? May be any algorithms do exist?

Instead of putting x, put some very high cost values in those cells.
Then the Hungarian algorithm avoids selecting those cells automatically (if that's possible).


Set of all rational numbers less than given computable real number is decidable Prove that set of rational numbers less than given computable real
  number is decidable

This problem was in my exam yesterday, but I was not able to solve it. However I still want to give it another try.

Same problem can be stated in this way:
Construct an algorithm, which answers the question: Is our given rational number less or greater than their(fixed) computable number?

Here's my poor try so far.

Since it's analysis related problem, I used the $\epsilon - \delta$ definition of computable number, which is:
$\exists f$ computable function, such that $\forall \epsilon > 0, \epsilon \in \mathbb{Q}, f$ gives us $\delta > 0, \delta \in \mathbb{Q}$ such that$|a - \delta| \leq \epsilon$ holds for given computable number $a$

Let $p \in \mathbb{Q}$ be our input, and let $f$ compute for us 2 rationals $q_1$ and $q_2$. It is well known that $|q_1 - q_2| < 2\epsilon$

Now let's choose $\epsilon = \frac{1}{2^{i}}, i = 0,1,2,...$
For each $i$-th step I compute $f$ twice and get $q_{i_{1}},q_{i_{2}}$. I think that our given rational $p$ should hold some condition with both $q_{i_1},q_{i_2}$ which will help me to finish the algorithm, but I couldn't figure this out. I believe there are finitely many checks for each step which will let me know that for example $p < a$ just like in picture below.

What do you think about this problem? Maybe there's more straightforward way to prove this. Thank you.

I would approach this problem as follows. Let $a$ be the computable real, and $A = \{x\in\mathbb{Q}\ |\ x<a\}$.

If $a \in \mathbb{Q}$, then $A$ is decidable since $x<a$ is a comparison between rationals, which is decidable.

Otherwise, we can assume $a$ is irrational. Our algorithm performs the following.
First, we take the candidate $x\in\mathbb{Q}$ as input.
We then query $f$ (the function which approximates $a$ as requested) repeatedly with $q=2^{-n}$ for every $n>0$.
Eventually, for some $n$ we will obtain one of

$$
f(2^{-n}) + 2^{-n} < x
\qquad \lor\qquad
x < f(2^{-n}) - 2^{-n}
$$
Indeed, this will happen as soon as $2^{-n} < |x-a| / 2$, which is a possibility because we know $x \neq a$.

In the first case, we return $x > a$ ($x \notin A$), in the second we return $x<a$ ($x \in A$).

The correctness comes from
$$
a \leq f(2^{-n}) + 2^{-n}
\qquad \land\qquad
f(2^{-n}) - 2^{-n} \leq a
$$
being true for all $n$.

Note that this solution is not uniform in $a$. That is, we only prove that there is an algorithm for any computable $a$, taking a candidate rational $x$ as input. We do not show that there is a single algorithm that, given both $a$ and $x$ as input is able to decide $<$ (indeed, that would be undecidable).


Modular exponentiation running time I read on Wikipedia that modular exponentiation can be done in polynomial time. I've a few questions regarding it (sorry if they seem a bit easy – I'm not a comp sci student).

Is it poly time only for base 2, i.e in binary or will it remain poly time algorithm even if i run it in decimal system i.e base 10?
If I'm calculating $(a^b) \bmod p$,  where $1<a<11$, $1 < b \leq (p-1)/2$, and we run this modular exponentiation at most $p/2$ times, all this being done in decimal base 10 system, will it still be poly time?
Even if this is poly time, and this is a big IF, can this process actually be completed in reasonable time in terms of the real worldly time?

With regards to (3), there's a fairly simple algorithm to compute large exponents.
exp(a, b) =
  if b is even
     let half = exp(a , b/2)
     return half * half
  else
    return a * exp(a, b-1)

This will be logarithmic in the magnitude of $b$, meaning the number of multiplications is linear in the number of bits used to represent $b$. It's also a very general algorithm: it works for normal exponentiation, matrices, modular arithmetic, etc. The complexity will change depending on the complexity of your multiplication operation.


Naive Bayes where Feature Space is LDA Output I understand that the output for Latent Dirichlet Allocation is a distribution over K topics.

Suppose I have a Dx(K+1) matrix, where rows are documents and columns are the topic distribution + one column for class. For example, each row represents one movie review. The first K columns represent the topic distribution of the document, and the last column is the classification of this document. For example, if K=5, one row may read as:

2 | 0.25 | 0.4 | 0.1 | 0.15 | 0.1 | 1

where moview review 2 had 25% of the text about topic 1 (pleasure), 40% topic 2 (discontent), 10% topic 3 (personal feelings) ... and the classification of this document was to class #1.

How would I go about creating a Naive Bayes Classifier using this data?

Typically, I have used a Gaussian Naive Bayes where the feature space is iid over normally distributed variables, but this assumption I do not believe makes sense for LDA output. Would I need to assume the features are the individual columns distributed in a particular way (say a Dirichlet probability)?

This exercise is more for proof of concept to use Naive Bayes. I want to use, say 60%, of the data to construct a Naive Bayes Classifier and test the accuracy of the remaining 40%. My main concern is to how to define the PDF for the Naive Bayes Classifier.

The topic scores (the numbers in the first $K$ columns) come from a Dirichlet distribution.  The marginals of the Dirichlet distribution are a beta distribution.

Therefore, it would be reasonable to model the distribution on each feature as beta-distributed, not normally-distributed.  With this adjustment, all the math for Naive Bayes goes through.

Let me flesh this out.  Given some data $x=(x_1,\dots,x_k)$, the Naive Bayes classifier computes the likelihood of a class $c$ as

$$L(c) = P(c) \prod_{i=1}^k P(x_i | c).$$

Here $x_i$ is the value in the $i$th column (the estimated probability the document came from topic $i$).  Given the comments above, we will estimate that the conditional distribution $P(x_i | c)$ has a beta distribution with some parameters, i.e., $\text{Beta}(\alpha_i,\beta_i)$.  Thus,

$$P(x_i | c) = {1 \over B(\alpha_i,\beta_i)} x_i^{\alpha_i-1} (1-x_i)^{\beta_i-1}$$

for some parameters $\alpha_i,\beta_i$.

Where do we get the parameters from?  From the training set, as usual.  In other words, we take from the training set just the documents that are classified with class $c=0$, and from those, we fit a beta distribution to the conditional distribution $P(x_i | c=0)$ and find the parameters $\alpha_i,\beta_i$ that make the beta distribution best fit the observed values of $x_i$ (out of the training documents classified as class $c=0$).  We use those as our estimate for $P(x_i | c=0)$.  How do we find $\alpha_i,\beta_i$?  By using standard methods for estimating the parameters of a beta distribution, given a bunch of observations drawn from it.

Then, we do the same for the documents in the training set that are classified as $c=1$, to fit a beta distribution and use that as the distribution for $P(x_i | c=1)$.

Finally, once you have formulas for $P(x_i | c=0)$ and $P(x_i | c=1)$, you plug that into the definition of $L(c)$ above and use that in the Naive Bayes classifier just as normal.


Beginnings of multiptogramming and compilations for it I want to know how the first programs to be able to execute more than one programs within a common time span were like . I went through the history of the topic and
it seemed like Strachey was the first one to work on multi-programming . Hence , i thought of reading his paper "Time sharing in large and fast computers"

Where can I find this paper ?

Is it so that in multi- programming , two addresses are stored in a memory location and the program counter is sequentially switched between the values in the two locations and after the execution of instructions the value in the corresponding register is incremented ? So basically for a language to support multi-programming the keyword or function ,it should use to create concurrent programs or to make two programs run in parallel , should translate to a machine code having conditional jump instructions .

For example , a version of AlGol 60 ,  used "cobegin" and "coend" keywords to mean the parallel execution of two streams of instructions as follow :

Cobegin :

process 1 Begin :..... End

process 2 begin .......End

Coend

So , is it so that cobegin and coend translate to a machine code which stores the addresses of the machine codes obtained from translation of process1 and process 2 to two different registers , and use jump instruction to  sequentially switch between the present values in the registers which are incremented as the programs get executed .

P.S : It would also be  of great help , if someone can point towards a link where the code for the OS used by Burrough's written in ALGOL60 is available provided such a link exists .

The early multiprogramming systems ran two or three programs simultaneously in a single computer. They did so by partitioning the memory amongst

operating system
one user-program
another user-program
...

The user programs shared a single copy of the operating system, which provided input/output and other services through system calls, which switched the processor into a special privileged mode that can access the external hardware. Programs had to be relocatable - able to run wherever in the memory they happened to end up.

Many advances were made in the Ferranti Atlas hardware and operating system:

virtual memory - both mapping and one-level store;
memory-addressed hardware;
three-level processing hierarchy: interrupt, supervisor, and user;
SPOOLing - buffering of slow input/output devices.

Time-sharing - time-division multiplexing of processor and sometimes of computer memory - dragged behind, and proved difficult to make a success of.

Multi-tasking within a single programming model is different and developed almost orthogonally.


Can a subset of indexes of a partial recursive function be recursively enumerable but not recursive? Consider a Gödelian numbering of partial recursive functions. Consider the set of indexes corresponding to some function $\phi$. It may be seen that this set is not recursively enumerable. Does this set contain a recursively enumerable non-recursive subset?

I guess the answer is yes, but please check critically. One can easily construct an infinite recursive set of indices of $\phi$ (adding "comments" to a program). From this infinite recursive set one can pick out a non recursively enumerable subset.


Metrics on which Clock Cycles Per Instruction(CPI) depends In the book - Computer Organization and Design: The Hardware/Software Interface [RISC-V Edition] by Patterson and Hennessy, CPI is defined like this:

The term clock cycles per instruction, which is the average number of clock
cycles each instruction takes to execute, is often abbreviated as CPI. Since different
instructions may take different amounts of time depending on what they do, CPI
is an average of all the instructions executed in the program. CPI provides one
way of comparing two different implementations of the identical instruction set
architecture, since the number of instructions executed for a program will, of
course, be the same.

I am solving question 1.7 from the Exercises section of chapter 1:

1.7 Compilers can have a profound impact on the performance
of an application. Assume that for a program, compiler A results in a dynamic
instruction count of 1.0E9($I_A)$ and has an execution time of 1.1 s($T_A$), while compiler B
results in a dynamic instruction count of 1.2E9($I_B)$ and an execution time of 1.5 s($T_B$).
a. Find the average CPI(both $CPI_A$ and $CPI_B$) for each program given that the processor has a clock cycle
time of 1 ns.
b. Assume the compiled programs run on two different processors. If the execution
times on the two processors are the same, how much faster is the clock of the
processor($P_A$) running compiler A’s code versus the clock of the processor($P_B$) running
compiler B’s code?
c.  A new compiler C is developed that uses only 6.0E8 instructions($I_C$) and has an
average CPI($CPI_C$) of 1.1. What is the speedup of using this new compiler versus using
compiler A or B on the original processor?

Attempted Solution:

a.

Using the formula $T = I * CPI * CC$
where $CC = $ clock cycle time, I calculated part a of the question
$CPI_A = \frac{T_A}{I_A * CC_A} = 1.1$
Similarly, $CPI_B = 1.25$

b.

Given, execution times on two different processors are same
Again using the formula, I calculated
$\frac{T_A}{T_B} = \frac{I_A * CPI_A * CC_A}{I_B * CPI_B * CC_B}$
My task is to find $\frac{CC_A}{CC_B}$, which I am unable to, since I don't know the value of $CPI_A$ and $CPI_B$.

c.

Again, using the formula, I calculated
$\frac{T_A}{T_C} = \frac{I_A * CPI_A * CC_A}{I_C * CPI_C * CC_C}$
My task is to find $\frac{T_A}{T_C}$, which I am unable to, since I don't know the value of $CPI_A$. Here I know that, $CC_A = CC_C$, since the processor remains same.

In part b and part c of the solution, will the value of $CPI$ be same as that calculated in part a. If so, please explain why? What are the metrics on which $CPI$ depends. Does it not change with processor, or execution time, or any other metric?

In part a same processor is assumed, and 2 compilers are used. In part b, 2 processors with different clock frequency is used, since the execution times for both processors are equal but the CPIs and dynamic instruction counts are unequal. The CPI for both processors is the same as the CPI from part a because the same compilers were used and the same compiled program is run.
So the dynamic instruction count and CPI is the same from part a.
$\frac{f_A}{f_B}=\frac{CC_B}{CC_A}=\frac{T_B}{CPI_B*I_B}*\frac{CPI_A*I_A}{T_A}$.
Since $T_A=T_B$,
we get
$\frac{f_A}{f_B}=\frac{CPI_A*I_A}{CPI_B*I_B} = \frac{1.1*1*10^9}{1.25*1.2*10^9} =0.7333 $
or $\frac{f_B}{f_A} = 1.37$
For part c, use CPIs obtained in part a.
Speedup
$\frac{T_A}{T_C}=1.67$
$\frac{T_B}{T_C}=2.27$
CPI depends on the processor's hardware architecture, processor clock frequency, compiler and the number of instructions.


$\mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{P}/\mathrm{poly} \implies \mathrm{strict}$-$\mathrm{SUBEXP} \subset \mathrm{MA}$ Is anyone able to give a concise proof for the implication stated in the title? This is gonna be in stark contrast to this question.

For definition of $\mathrm{strict}$-$\mathrm{SUBEXP}$, see here.

Yes, I can.

First of all, $\mathrm{poly}(\mathrm{subexp}) = \mathrm{subexp}$. So, we can simulate a subexp TM in subexp time. (This is in stark contrast to standard $\mathrm{SUBEXP}$ where we do not have any particular subexp machine)

Using this, we are able to put $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$. The poly space TM would try every possible poly-size circuit and for each circuit make $2^n \times 2^n$ local checking of the tableaux using the current circuit. Note that the subexp TM never touches the $2^n$th cell and would cease to run long before $2^n$ time but that does not affect the poly space bound.

After putting $\mathrm{strict}$-$\mathrm{SUBEXP}$ inside $\mathrm{PSPACE}$, we use the result of interactive proving protocol with the power of the prover at most $\mathrm{P}^\mathrm{L}$ (where $\mathrm{L}$ is the language at hand) to push it down to $\mathrm{MA}$.


Dynamic All Pairs Shortest Paths algorithm I heard about the following problem in a competitive programming camp:

Given an undirected weighted graph $G$ with one vertex initially.

Suppose you are given two types of queries:

Add a new vertex to $G$ with some undirected weighted edges between this vertex and subset of vertices added previously to $G$ in time complexity $O(n^2)$, where negative weights are allowed.
Find the length of the shortest path between two vertices in $O(1)$.

Note: Floyd Warshall's algorithm is $O(n^3)$ for each query of type 1.

I'm looking for (in addition to your answer):

Any useful reference to solve such a problem.
Links for similar problems in online judges (Codeforces, SPOJ .. etc).

You maintain a table $d$ where $d(i,j)$ represents the length of the shortest path from vertex $i$ to vertex $j$, so query 2 can be done in $O(1)$.

For query 1, when a new vertex $u$ is added, for each old vertex $v$, calculate the length of the shortest path from $u$ to $v$ by

$$d(u,v),d(v,u)\leftarrow\min_s(w(u,s)+d(s,v)).$$

where $s$ varies among all neighbors of $u$, and $w(u,s)$ represents the weight of edge $(u,s)$. This process takes $O(n^2)$. Now if there is no negative cycle, for each old vertex $v$, $d(u,v)$ and $d(v,u)$ correctly record the length of the shortest path from $u$ to $v$. It's also not hard to detect if there is a negative cycle.

Then, for any old vertices $s,t$, update $d(s,t)$ to

$$d(s,t)\leftarrow\min\{d(s,t),d(s,u)+d(u,t)\}.$$

This can also be done in $O(n^2)$.

Now after the two steps above, if there is no negative cycle, for each pair of vertices $x,y$, $d(x,y)$ correctly records the length of the shortest path from $x$ to $y$.


Proving Equivalence of 1-dimensional Cellular Automaton and Turing Machines I'm considering an automaton $A$ over a alphabet $\Sigma$, with a set of states $Q$, such that $\Sigma \subset Q$, which includes special "accept" and "blank" states not in $\Sigma$. It also has an infinite list of cells, which begins with the input string, the rest being blank. It has a transition function $\delta: Q \times Q \times Q \to Q$. The automaton computes by updating the value  of the middle cell, $a$, using $\delta(x,a,y)$. The automaton accepts if any cell is in the accept state. From what I understand, this automaton is very similar to a 1-dimensional cellular automaton, with the addition of the accept state.

I'm trying to prove that a language is recognizable by a Turing machine if and only if it can be recognized by the automaton described.

I've been trying to do a proof by construction, but I'm really lost. I did some research on cellular automata, but the material I've been finding is way over my level. I know somehow I'm going to have to construct a TM from CA, and vica versa, but I'm not even sure how to get started. I would really appreciate any help.

Here are some hints. The easy direction is simulating cellular automata with Turing machines. Turing machines can simulate C programs, and you can simulate cellular automata in C. (Replace C with your favorite programming language.)

Given a Turing machine, we want to construct a cellular automaton simulating it. We need to upgrade the alphabet by allowing, besides regular symbols $\sigma$, also symbols $\langle q,\sigma \rangle$ which signify that the head is currently at that point, the state is $q$, and the tape symbol is $\sigma$. The initial tape would contain $\langle q_0,\sigma_0 \rangle$ as the first symbol, where $q_0$ is the initial state and $\sigma_0$ is the first symbol on the input tape of the Turing machine.

It remains to show how to simulate the Turing machine by an appropriate choice of the propagation rules $\delta$. The basic idea is to maintain the invariant that the contents of the cells constitute of the tape of Turing machine, with the exception of the location of the head, which is of the form $\langle q,\sigma \rangle$. I'll let you work out the details.


Virtual Memory and processes In a Operating System, who decides which parts of a program (or task) has to be stored in the virtual memory and which in the RAM ?

The application itself gets to decide what it wants in virtual memory (within some restrictions). By default that will be the code it run and the memory it uses. The application can also request files to be mapped into memory, or that memory gets shared with another application.

Then the kernel will decide which parts of virtual memory are loaded in RAM based on various factors like: how much ram is available; how much is needed by other processes; how recently a region of virtual memory was accessed, ...


Notation for a Kleene fixed point with a starting element Assume a CPO $Q,\leq$ and a Scott-continuous function $f : Q \rightarrow Q$. As it is known, the chain $\bot \leq f(\bot) \leq \ldots \leq f^n(\bot)$ (where $f^n$ denotes the function $n-1$-times composed with itself) leads to a fixed point of $f$.

It is also clear, if $f$ is inflationary, that for any $q \in Q$, the chain $q \leq f(q) \leq \ldots \leq f^m(q)$ leads to a fixed point. (This follows immediately by just considering the subset $\{\,p\,|\, p \in Q \wedge q \leq p\}$, which is also a CPO.)

This second form is often more useful in practice. But how to denote it? While the fixed point of $f$ is easily written $\text{fix} f$, is there a standard convention for the second form? Writing $\text{fix} f(q)$ seems intuitive but is - strictly speaking - wrong, since $f(q)$ is not a function (it might also be confusing in the case of higher-order functions).

edit: Added note, that $f$ must be inflationary.

Suppose $Q$ is a join semilattice.  Define $g:Q \to Q$ by

$$g(x) = f(x) \sqcup q.$$

Then $\text{fix} \; g$ is equal to the least fixpoint of $q,f(q),f^2(q),\dots$.  So, at least for cpo's that form a join semilattice, you can indicate it pretty naturally using existing notation -- there's not a strong need to invent a new notation (though you could of course introduce one if you wanted).

If $Q$ is not a join semilattice, I think you can still define

$$g(x) = \sup \{ f(x), q \}$$

and then do the same thing.  The least fixpoint of $q,f(q),f^2(q),\dots$ will be $\text{fix} \; g$.


Coq --- non-terminating programs People usually say Coq does not allow writing non-terminating functions. I have a question regarding that.

Does Coq allow writing exactly all terminating functions? In other words, what are the completeness and soundness properties of Coq's procedure for checking well-foundness of fixpoint definitions?

Coq cannot always know whether a program will terminate, because that would be a solution to the halting problem.

Coq is able to notice that a certain class of programs will terminate. The main heuristic it uses is that if one of the arguments to the function must get smaller on each recursive call, the program must terminate.

If you have a function that terminates, but Coq cannot tell that it terminates, you can add an extra argument that always get smaller on recursive calls. Doing this amounts to providing a proof that the function terminates.

So basically, Coq accepts any program that the user can prove the termination of.


Given the hash of a collection, H(X), can I build a proof that F(X) == Y, without having X? Given a cryptographic fingerprint of a collection, K == hash(X), an arbitrary function F, and a value Y, is it possible to build a short proof that F(X) == Y that doesn't require having X? I.e., a proof that Y is the result of applying F to some X such that hash(X) == K?

Yes, this is possible.  Use a zero knowledge proof (of knowledge).  If F is computable in polynomial time, then there exists a polynomial-time zero-knowledge proof of the property you want, i.e., given K,Y, the prover can construct a proof that there exists X such that H(X)=K and F(X)=Y.  Amazingly, this proof is "zero-knowledge": it reveals nothing about X (other than the property is true).

If you don't care about the zero knowledge part, you can just use an interactive proof system.

Zero-knowledge proofs can be made non-interactive using standard techniques.

There's tons of work on this in the cryptographic research literature.  I can't explain the ideas in the length of an answer here, so I suggest you spend some quality time studying this material.  However, while the theory is elegant and beautiful, you're probably going to find the generic schemes are not very practical and the performance overhead is significant.  Therefore, if you actually want to do this in practice, you'll want to focus on a specific function F and see whether you can build a custom protocol specialized to that particular function F.


Independence Implies P $\ne$ NP Suppose P vs. NP is independent of ZFC. Then there cannot be an efficient SAT solver, otherwise it would constitute a proof for P = NP. Therefore P $\ne$ NP.

What we see here is that independence implies unequality. So why is independence a big deal? It is just one way to show P $\ne$ NP. See Scott Aaronson's paper Is P Versus NP Formally Independent?.

As Yuval Filmus comments, your argument is flawed: just because a given algorithm is a SAT-solver doesn't mean that we can prove that it is a SAT-solver.

Technically, the same issue applies to the time bound - we can cook up a Turing machine which always runs in polynomial time iff ZFC is consistent - but this is easily avoidable: given a Turing machine $T$ and a polynomial $p$, we can form a machine $T[p]$ which behaves like $T$ except with the time bound $p$ artificially imposed: on input of length $n$, $T[p]$ simulates $T$ for $p(n)$-many steps and diverges if it hasn't halted within that time. We can decide whether a machine $S$ has the form $T[p]$ for some $T, p$, so if $T$ happens to be a SAT solver which operates in polynomial time $p$, then $T[p]$ is a polytime SAT solver which we can prove operates in polynomial time. The culprit is "is a SAT solver," for which there doesn't appear to be a similar trick.

The issue here is logical complexity. "Undecidability implies truth" holds for statements with verifiable counterexamples; these are the $\Pi^0_1$ statements.$^*$ The Goldbach conjecture is a good example: in order to be false, there would need to be a counterexample, and being a counterexample to Goldbach is an easily checkable property since it only relies on "bounded quantifiers." By contrast, the Twin Primes Conjecture is a priori merely $\Pi^0_2$, and so at the moment we don't have any reason to believe that its undecidability from (say) PA would imply its truth.

Even in the $\Pi^0_1$ context, however, undecidability is more than just a method for proving a statement. It establishes that the principle is true "for deep reasons" in some sense. If a statement $P$ about the natural numbers$^{**}$ is true but not PA-provable, this means that the reason $P$ is true is more complicated than just our simple intuitions about induction, since PA already incorporates the full arithmetical induction scheme. Now whether one consider this a worthwhile observation depends on one's particular interests, but it (and even weaker independence phenomena) is certainly noteworthy to me.

$^*$This is in fact an exact characterization, in the following sense. If $S$ is a reasonable theory of arithmetic, and the independence of $P$ from $S$ implies the truth of $P$, then $P$ is equivalent to the statement "$P$ is not provable from $S$" (part of "reasonable" here is soundness). But this latter statement is $\Pi^0_1$. Now this is actually silly - every sentence is either equivalent to $0=0$ if true or $0=1$ if false - but it can be "de-sillified" by phrasing it as: if $T,S$ are reasonable theories and $T$ proves that $S$ is consistent and that if $P$ is $S$-undecidable then $P$ is true, then $T$ proves that $P$ is equivalent to the $\Pi^0_1$ sentence "$P$ is not $S$-disprovable."

$^{**}$Or a statement interpretable as a statement about the natural numbers; e.g. "P=NP" is a statement about Turing machines, but by the usual techniques is "faithfully translateable" into the language of arithmetic.


Help me identify the type of Knapack Problem I am dealing with I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the problem itself.

The Problem

I have a theoretically large model train track with dozens of short identical trains on it. I need to buy some power supplies to power my model trains.

The track is split in to equal length sections. I have a data structure that describes the power consumption for each individual length of track based on the movement of the trains. Each length has a peak power consumption (for example, when a train needs to accelerate), and an RMS power consumption.

I need to hook my track up to the power supplies, but I can only power contiguous lengths of track for each power supply. I can't power track section 1 with power supply A, then skip track section 2 and power track section 3 with the same power supply A. I have to power either track section 1, 2, and 3, or just 1 and 2, or just 1.

There is only one type of power supply that has a peak and RMS power output limit. When looking at a combination of lengths of track, I combine their power profiles to get a new RMS and peak power for the combined section. If one of these values goes over the power supply limit, it will not work. Assume that no individual length of track on its own will violate the RMS/peak limit of a power supply.

You cannot/will not have more than 1 power supply per length of track.

You can have at most 10 lengths of track on one power supply. You cannot have 11+ lengths of track hooked up to one power supply. The cord is not long enough.

The goal is to FIRST minimize the number of power supplies (these things are expensive) I have to purchase and THEN determine the most optimal distribution of power such that no power supply is loaded significantly heavier or lighter than any other.

Another way of looking at it is:

Limits

All knapsacks have the same capacity (10 items max).
All items have the same volume.
All items have different weights (densities).
All items come in a specific order (a circuit) and must be put into a knapsack with only adjacent items.

Goals

Minimize (optimize) the number of knapsacks first.
Distribute the items as equally as possible such that no backpack is lighter or heavier than it should be.

Considerations

I might be asking more than one question here: One about optimization and the other about the knapsack classification.
Is this actually a knapsack problem since the items don't have a value/profit?
Does the adjacent/contiguous limit I put on the problem make it easier or harder to solve?
Should I be considering anything from graph theory because my track is like a bunch of nodes and edges? Or is that an unnecessary complication.

The question still remains: Classify the type of knapsack problem, or at least extract the correct one from the above problem statement.

Please point me in the right direction.

Notes

The weights can be rounded to integers if that helps.

There's no special "name" for this problem that I'm aware of. Don't assume that problem specifications this specific will necessarily have a "name" or "type".

Instead, it's simply one of many problems that can be solved straightforwardly with dynamic programming.  You fill in an array $A[1..n]$, defined as follows: $A[i]$ is the minimum number of power supplies needed to provide power to sections $1,2,3,\dots,i$.  Then there is a simple recurrence for $A[i]$ that allows you to fill in the entire array in $O(n)$ time, namely,

$$A[i] = 1 + \min \{ A[j] : 10-i  \le j < i \text{ and } P(j,i-1)\}$$

where $P(j,i-1)$ is true if a single power supply can power sections $j,j+1,\dots,i-1$ simultaneously.

This allows you to compute the minimal number of power supplies needed.

Then, once you know this number, you can know optimize things to find the most equal distribution of power.  Let $k$ denote the number of power supplies, and $\mu$ denote the average power per supply when using $k$ supplies.  Given a constant threshold $t$, you can determine whether there exists a way to power all sections using $k$ power supplies such that every power supply's power consumption falls in the range $\mu-t \dots \mu+t$, using similar methods.  Now use binary search on $t$ to find the minimal $t$ such that this is possible.  This will give you the solution to your problem.

In general, computer science provides many techniques that can be combined in creative ways to solve problems.  When you have a new problem with multiple specific requirements, you might have to look for how to apply those techniques in a way specific to your particular situation; there's no guarantee that it will fall cleanly into some existing "category" or "type".


Finding a worst case of heap sort I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest.

The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift down) to build the heap.

Input: Input ﬁle contains $n$ ($1 \le n \le 50{,}000$).
Output:  Output the array containing $n$ different integer numbers from $1$ to $n$, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible.

Sample input: 6
Corresponding output: 6 5 3 2 4 1

And the basics outputs:

[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 3, 2, 1]
[6, 5, 3, 4, 1, 2]

Given the worst-case for $n$, we can construct the worst-case for $n+1$ as follows: we do a 'swap cycle' as follows: we take $n+1$, put it in $a[0]$, and we swap $a[0]$ with the maximal element of its children, which is $a[1]$ or $a[2]$, which we again swap with the maximum element of its children and so on, until we leave the $n$-element heap, at which point we put that last element at the $n+1$-th position.

An example: the worst-case for $n=5$ is $[5, 4, 3, 2, 1]$. We swap in 6 which creates the heap $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1]$, after which we end up with 2, which we insert at the end: $[\textbf{6}, \textbf{5}, 3, \textbf{4}, 1, \textbf{2}]$.

The above method works by induction: we start from the worst result for $n-1$ elements and perform a sift-down operation in reverse, maximizing the number of swaps it has to do ($\lfloor\log(n)\rfloor$ swaps). You can't do more swaps than this, so you maximize the number of swaps after the first extract-min operation, after which you are left with exactly the worst-case for $n-1$ elements for the next extract-min operation. This implies that the number of swaps is indeed maximal.

Note that this method gives different results than you have gotten:

[1]
[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 1, 3, 2]
[6, 5, 1, 4, 2, 3]
[7, 6, 1, 5, 2, 4, 3]
[8, 7, 1, 6, 2, 4, 3, 5]
[9, 8, 1, 7, 2, 4, 3, 6, 5]
[10, 9, 1, 8, 2, 4, 3, 7, 5 ,6]

However, both solutions are correct:

[5, 4, 1, 3, 2]
[2, 4, 1, 3| 5]
[4, 2, 1, 3| 5]
[4, 3, 1, 2| 5]
[2, 3, 1| 4, 5]
[3, 2, 1| 4, 5]

[5, 4, 3, 2, 1]
[1, 4, 3, 2| 5]
[4, 1, 3, 2| 5]
[4, 2, 3, 1| 5]
[1, 2, 3| 4, 5]
[3, 2, 1| 4, 5]

[6, 5, 1, 4, 2, 3]
[3, 5, 1, 4, 2| 6]
[5, 3, 1, 4, 2| 6]
[5, 4, 1, 3, 2| 6]
[2, 4, 1, 3| 5, 6]
[4, 2, 1, 3| 5, 6]
[4, 3, 1, 2| 5, 6]
[2, 3, 1| 4, 5, 6]
[3, 2, 1| 4, 5, 6]

[6, 5, 3, 4, 1, 2]
[2, 5, 3, 4, 1| 6]
[5, 2, 3, 4, 1| 6]
[5, 4, 3, 2, 1| 6]
[1, 4, 3, 2| 5, 6]
[4, 1, 3, 2| 5, 6]
[4, 2, 3, 1| 5, 6]
[1, 2, 3| 4, 5, 6]
[3, 2, 1| 4, 5, 6]


How is the formula for calculation in row/column major obtained? In my book, this formula is given for calculation of address of row major order's element $[I,J]$:

Address of $[I,J]$th element in row major order  $= B + W[n(I-L_r)+ [J-L_c]]$

where B denotes base address, W denotes element size in bytes, n is the number of columns; $L_r$ is the first row number, $L_c$ is the first column number.

A similar formula is given for address in column major order.

I would like to know how this formula is obtained.

Row-major order stores the rows of the array one after another in memory. That is, the array

a d g j
b e h k
c f i l

is stored as

a d g j b e h k c f i l

To determine the address of an element in this list, we need to know how many elements come before it. For element $[I,J]$, this is the number of complete rows above row $I$ times the length of a row, which is $(I-L_r)\times n$, plus the number of elements before it in the current row, which is $J-L_c$.

Since the first element is at address $B$ and each element takes $W$ bytes, the addresses of the elements are $B$, $B+W$, $B+2W$, ... and, in general, if there are $k$ elements before you, your address is $B+kW$. For element $[I,J]$, we have calculated that $k=n(I-L_r)+(J-L_c)$.

For column-major, the argument is basically the same. If you understand the above, it should be easy to adapt it.


Registers of Control Unit and Arithmetic Logic Unit For an Instruction fetch cycle we have the flowing registers in a CPU.

Memory Address Register (MAR)
Memory Buffer Register (MBR)
Program Counter (PC)
Instruction Register (IR):
Accumulator Register:
Stack Control Register:
Flag Register:

Out of these I have come to know that PC and IR registers belong to control unit and accumulator belong to ALU but I do not know about rest of the registers. Either they also belong to CU or ALU or they exist separately not as apart of ALU OR CU ?

They are part of the memory interface between the CPU and the memory subsystem.

The MAR (Memory Address Register) is closely associated with the memory address bus, and the MBR (Memory Buffer Register) is closely associated with the memory data bus.

Some CPUs choose to connect their general purpose registers more or less directly to those busses, thus eliminating these specialized registers, but this is not usually the case in accumulator machines that you're describing in your question.

Some CPUs have a secondary ~ALU dedicated to addressing computation (so probably just add and some specific shifts, e.g. by 0, 1, 2, or 4); such a secondary ALU might also work in conjunction with the MAR or in replacement of an MAR.

On some processors, the CU will have to interleave requests for instructions from memory with requests by the program for data from memory. The instruction address (found in the PC) may first go through the MAR during fetch, or the PC value may be sent directly to the address bus during fetch, depending on the CPU design.

If the processor has a separate instruction cache and data cache, then it has two memory subsystem interfaces.  Typically the PC will then serve directly as the MAR for the instruction memory interface rather than creating a second MAR for that.

Note that the MAR, MBR, and the IR are internal registers that are generally not visible to the program or programmer, and so only visible if you're looking inside a particular processor's design.  The same instruction set architecture can be implemented in different ways, and in these alternative implementations, the discussions of the above considerations may vary; this happens in a processor family, like x86.


Algorithm for the complete parenthesization of n factors Is there an algorithm that can list all possible parenthesizations of a given set of commutative factors?

This is related to the Catalan number. It, however, merely determines the number of such occurrences, while keeping a given factor order.

As an example (found at the above link): from "abcd", the algorithm should produce { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))" }.

Another related problem is the optimal matrix multiplication order, where given a number of matrices that ought to be multiplied together, the task is to parenthesize them in an order such as the resulting multiplication operations take the least computational resources. From this, I tried to work out an exhaustive way to list all possibilities, but wasn't able to.

Additionally, if the factors are commutative (thus not matrices in the general case), the number of combinations is larger than the Catalan number. As an example, given the above input, additional elements in the output are expected { "((ab)c)d", "(a(bc))d", "(ab)(cd)", "a((bc)d)", "a(b(cd))", "(ac)(bd)", "d(b(ca))", ... }. In other words, if the factors are commutative, the matrix chain multiplication problem and Catalan number considerations are no longer applicable (at least I can't make a fruitful connection).

So, the question focuses primarily on the algorithm for the general case, i.e. when commutative factors are involved.

As with most things involving trees, it's easiest to analyse recursively.

Given a one-element set $\{a\}$, the only parenthesisation is $(a)$.

Given a larger set $S$, we choose an arbitrary element $x \in S$. Then for each proper subset $T \subset (S \setminus \{x\}) $ we have parenthesisations $(p)(q)$ where $p$ is a parenthesisation of $\{x\} \cup T$ and $q$ is a parenthesisation of the remaining elements. There are a total of $(2|S| - 3)!!$ such.


What is the algo used for Phonetic Search I am new to the field of text mining. Could not figure out what to search on google so am here for the same help.
When we talk of approximate / fuzzy string match. searching for RAT would give RAAT too. i have used utl_match.edit_distance in oracle. searching for BAAT would give BAT. but if i search for RAT. it would return BAT, CAT, etc. How does google bring the phonetically same rhyming / sounding words eg if some one does'nt know spelling of 'Schwaznegger', even then correct data is brought by google. For 'levenshtein distance', cat and bat are pretty close but for google. closest to cat is kat not bat. Please tell me what we call such a search and what algorithms are used for it.
 Thanking you in advance for patience.

Take a look at Soundex, Levenshtein edit distance, and related ideas.


Is induced subgraph isomorphism easy on an infinite subclass? Is there a sequence of undirected graphs $\{C_n\}_{n\in \mathbb N}$, where each $C_n$ has exactly $n$ vertices and the problem

  Given $n$ and a graph $G$, is $C_n$ an induced subgraph of $G$?

is known to be in class $\mathsf{P}$?

This question has been answered on cstheory.

Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W[1]$-hard for every infinite class of graphs.


Best known (state of science) time complexity of an array access problem Consider an Array $A$ with $n$ values and the following operations:

get(i): Returns the value of $A[i]$
insert (x): Insert the element x into the any free place in A (not necessarily in $A[x]$ or the end of the array)
delete (x) delete the element $A[x]$

What is the best known (amortized) time complexity of all operations? Especially the delete-op seems like it needs at least $\Omega(log n)$

See also the papers in this post. However the insert operation is defined slightly different by me, does this have any effect?

Ok so I think you can build a structure that has $O(1)$ (amortized) complexity for all operations, and using $O(n)$ space for $n$ insertions.

The underlying array is a dynamic array (let's call it $T$) : it has amortized O(1) complexity for insertion at the end. In the array, you store tuples of values and booleans : the boolean will be set to false when you delete, true when you insert. You also keep a stack / queue / some dynamic data structure with O(1) push and pop to keep the indexes of empty places in the array that were previously filled (i.e. they are not at the end of the array), let's call it $S$.

get(i) : if the boolean at i is true, return the elemet at position $i$ in $T$ : $O(1)$, otherwise return an error : no element at that position.
Insert(x) : if $S$ is empty, insert the element at the end (setting the associated boolean to 1) : $O(1)$ amortized with dynamic array. If $S$ is not empty : pop a position from $S$ and insert the element at that position : $O(1)$ as well.
Delete(i) : set the boolean at $i$ to false, and add $i$ to $S$. $O(1)$ as well.

The only downside of that method is that the array is never reduced, and therefore has size $O$(number of insertions) and not $O$(number of element).