How to find an arrangement of a sequence that has the lowest cost Given is a set of $n$ items: $x_1, x_2\ldots, x_n$. Additionally, we have a non-symmetrical evaluation function $f(x_i, x_j)$ that gives a cost value of two items. Note that $f(x_i, x_j)\neq f(x_j, x_i)$.

We want to find a list $y$ containing all items from $x$ exactly once such that the total cost of $y$, given by $F(y) = \sum_{i=1}^{n-1} f(x_i,x_{i+1})$, is minimal.

How can we do this?

Unfortunately, this problem is NP-hard, which can be seen by transforming it into a question on graphs.

To see this, construct the graph $G=(V,E)$ with $V=\{x_1,x_2,\ldots,x_n\}$, $(v,w)\in E$ for all $v,w\in V$ and a cost function $c:E\rightarrow \mathbb{R}$ given by $c((x_i,x_j)) : =f(x_i,x_j)$. Observe that any path visiting all vertices in $V$ exactly once corresponds uniquely to an arrangement of the original set.

To show NP-hardness, we must first formulate a decision problem corresponding to the optimization problem. One such formulation is:

  Given set $X$ of $n$ items and function $f:X\times X\rightarrow \mathbb{R}$ and an integer $T$, does there exist an arrangement such that the total cost of the arrangement is at most $T$?

By our discussion above, this problem is equivalent to

  Given the full graph $G=(V,E)$ (i.e. $E=V\times V$) of $n$ vertices and cost function $c:E\rightarrow \mathbb{R}$ and an integer $T$, does there exist an Hamiltonian path such that the total cost of the edges of this path is at most $T$?

This problem is very similar to the traveling salesman problem (TSP), but isn't quite the same, as that problem requires a Hamiltonian cycle instead of a path.

However, as @j_random_hacker mentioned, this problem is in fact equivalent to the TSP problem on a different graph, namely $G'=(V',E')$ with $V' = V\cup \{z\}$, $E'=V'\times V'$ and $c'$ such that $c'(x,y)=c(x,y)$ for all $x,y\in V$ and $c(z,x)=c(x,z)=0$ for all $x\in V'$.

Therefore, the arrangement problem is indeed equivalent to TSP, which is NP-hard.

Although NP-hardness means that there are no efficient algorithms to find an exact solution, there are still heuristics that can find decent solution in reasonable time. There are many such approaches for the TSP problem.

The fact that we know that $f$ is 'fully' non-symmetric doesn't really help, it has the same use as knowing there is no guarantee for symmetry here, which only means some approaches won't work.


If I have a large random array of 0s and 1s that I want to sort what kind of an algorithm and data structures should I consider? What are the types of things that need to be considered if I need to sort a large random array of 0s and 1s?

You can assume large array is in the order of million or billions.

I understand there are tons of sorting algorithms out there (quick, merge, radix,.etc.) and there are so many different data structures out there (trees, skip lists, linked lists, etc.)

If somebody asks me to sort this large array, do I simply jump to Quick Sort and say that's the best solution? If not, what am I supposed to be thinking about?

I'm not even sure if I know the right answer to this question, but I would really appreciate it if somebody in the community can give some advise.

Thanks.

Use counting sort: run through the array once and count the number of 0's. Then run through the array once more and write in it the counted number of 0's, followed by 1's. In any case, this is a purely academic exercise because nobody would ever need to do such a thing in real life.


Probability of k-connectedness for a random graph with given degree sequence For a degree sequence $(d_1,\ldots, d_n)$ with $\min d_i \geq k$ pick a graph with that degree sequence uniformly at random. What's the probability that the graph is k-connected?

I know that for Erdos-Renyi graphs the k-connectivity threshold coincides with with the appearance of degree k vertices, but that doesn't say much about the probability when we only know that the minimum degree is $k$.

This question is related to this question. I'd like to estimate how many graphs you need to sample before picking a biconnected graph.

The answer probably mildly depends on how wild the $d_i$ are. A random $k$-regular graph is $k$-connected whp for $3 \leq k \leq n-4$ according to slides by Wormald (page 12), so I would expect that if, say, $k \leq d_i \leq \ell$ for constants $k,\ell$ (or even $\ell$ growing mildly with $n$) then the graph is still $k$-connected whp. The proof shouldn't be difficult (for constant $\ell$) using the configuration model.

A 1-regular graph is never connected (for $n > 2$), and a random 2-regular graph is, if I remember correctly, disconnected whp. If you only have a few degree 2 vertices then perhaps the graph is 2-connected whp – that would be my guess.


Solving two party problem There are two parties A and B going on.
Some people are going to party A, some are going to party B.
We are given instructions of the form

different 1 3,  meaning that person 1 and person 3 are attending different parties
same      3 4,
different 4 5,

and then given a command tell 1 4 we have to answer if they are attending the same party or a different.
Like from above we can conclude that 1 and 4 must be attending different party as 1 and 3 are attending different and 3 and 4 attend the same.

My thoughts :  Make a hash table for A and B
given x and y determine which one belongs to which hashtable
if any not present put it in the appropriate hashtable.
Not sure if this is an efficient algorithm for this.
I was wondering if we could build a graph from the given info and then we
can answer any amount of questions like that.

It will be difficult with your idea as you don't initially know which table to put a person in.  For example will different 1 2 and different 3 4 have two solutions, namely $A = \{1, 3\}$ and $B = \{2, 4\}$, and also $A = \{1, 4\}$ and $B = \{2, 3\}$ (and symmetrically).  When you get the information that different 2 3, you have now lost some crucial information that you need.
The answer is graphs.
A graph is bipartite if and only if it is two-colorable (if and only if it has no odd cycles).
You are creating a bipartite graph such that when there is an edge between two people then they attend different parties.
When the graph is connected, it is easy to say whether two people are in the same party or not: Given $u$ and $v$, if the shortest path from $u$ to $v$ has an even number of edges, they are in the same party, if it has an odd number of edges, they are in different parties.
The command different u v simply adds the edge between $u$ and $v$.
However, the command same u v is slightly worse since you need to record the fact that they don't have an edge.
I would do the following.

If $u$ or $v$ have neighbors, add edges from $u$ to $N(v)$ and/or $v$ to $N(u)$.  One is enough, but you can also make it complete.  This is a space/time tradeoff.
If neither $u$ nor $v$ have neighbors, construct an artifical vertex $x_{uv}$ and connect both $v$ and $u$ to $x_{uv}$.  If $u$ or $v$ later get a different command, say different v w, you can remove $x_{uv}$, or identify $x_{uv}$ and $w$ (merge the vertices and their neighborhoods).

Complexity:

different a b → $O(1)$.  Add edge in constant time.  Check if $a$ or $b$ has an $x$-neighbor takes $O(1)$ time, delete that vertex takes time $O(1)$.  Add at most two edges after $x$ deleted.
same a b → $O(1)$.  Check existence of neighborhood, if so, add two edges in constant time.  Otherwise, create $x$ vertex and add two edges in constant time.
tell a b → $O(n + m) = O(m)$ with a single BFS search.  When you get the path $P$ you can add edge from $P_i$ to $P_{i+2}$ for all $i$; that could lower the future searching time.


Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular? Question is as follows: Given regular languages $L$, $M$. Is $K=\{uw | u,w \in \Sigma^*,(\exists v \in M) uvw \in L\}$ necessarily regular?

Thank you for any input.

The most direct method to solve the problem is to show to build, starting with finite state automata $A_L$ and $A_M$ for the regular languages $L,M$, a new automaton for the new language $K$ which is constructed from $L$ and $M$.

For this you need an idea, a formal construction, and (if you are not convinced) a proof the construction is correct.

The idea can be as follows. If the automaton $A_L$ follows a path on a word, one should be able to decompose this in the form $uvw$ in such a way that the subword $v$ can be accepted by $A_M$. The middle part $v$ should be made invisible in the new automaton for $K$. This idea can be made formal using concepts from finite automata like $\varepsilon$-instructions and direct product construction.

If you have knowledge of other closure properties then the one from this exercise can be deduced. Closure properties you then need are intersection, morphism and inverse morphism.

Enjoy.


Grammar ambiguous or not? So I've been struggling for the past hour with $G=(\{S\},\{a,b\},P,S)$ with productions $S\to aaSb | abSbS | \varepsilon$. I need to prove whether this grammar is ambiguous or not. Thus far I think it is ambiguous, possibly cuz of abSbS, but not sure (mainly since I have no idea how to prove it's not) . Can anyone help? I tried several words to no avail.

Here is an outline of a parsing procedure. To prove that the grammar is unambiguous, you have to show that it works (parses the string), and furthermore that the parsing tree it produces is the unique one generating the string. If this question came up in the context of a course on compilers, then you should have learned the necessary tools.

The parser is a DPDA. The stack starts initialized with S, and then works according to the following rules, reading the input from left to right.

If the top-of-stack is S:

If the string starts aa, replace S with AS (S on top).
If the string starts ab, replace S with BS.
If the string starts and ends a, reject.
If the string ends, accept.
If the string starts b, delete S and process b again.

If the top-of-stack is A:

If the string starts b, delete A.
Otherwise, reject.

If the top-of-stack is B:

If the string starts b, replace B with S.
Otherwise, reject.

(Unless explicitly stated, the automaton consumes the characters it reads from the string.)
At the end of parsing, the automaton rejects unless the stack is empty.

I'll let you figure out how to construct the actual parse tree. You'll also have to figure out how to prove that this parsing tree is the unique one (if it is indeed the case).


Can one quickly update CRC codes based on small change and previous CRC code? I asked this on StackOverflow, but, alas, no answers.

I'd like to use CRC or similar codes to check whether certain very large objects are likely to be identical. The trouble is, small parts of these objects are sometimes modified, and it would be very inefficient to re-compute CRC code from the entire object. Think of multiple large images, pre-signed with CRC, and of a software the changes single pixels of some of those images and updating those images' CRCs.

Is it possible to re-compute CRC based on: previous CRC value, location of the changed byte, old value of that byte, and the new value of that byte?

If not, what signature scheme would allow that?

Yes, this is possible.  The new CRC value can be computed very efficiently.

To see how, you need to know some math and about how CRCs can be viewed as polynomials.  The CRC checksum of the bit-string $c_0,\dots,c_n$ can be viewed as the value of $c(x) \bmod p(x)$, where $p(x)$ is the CRC polynomial and $c(x) = c_n x^n + \dots + c_0$ and all arithmetic is done modulo 2.  Let $r(x)$ denote the checksum, i.e., $c(x) \bmod p(x)$.  Now if you change the $i$th bit $c_i$ to $c'_i$, then the new checksum will be given by $c'(x) \pmod p(x)$ where we define the polynomial $c'(x) = c(x) - c_i x^i + c'_i x^i$.  The checksum will be $c'(x) \bmod p(x)$, which has the form

$$c'(x) \equiv c(x) - c_i x^i + c'_i x^i \equiv r(x) + (c'_i-c_i) x^i \pmod{p(x)}$$

Since we already know $r(x)$ (it's the checksum of the original file), all we need is to compute the value of $(c'_i-c_i) x^i \bmod p(x)$.  Naively, you might think this takes $O(i)$ time -- potentially slow.  But in fact this can be done very efficiently using fast modular exponentiation, so we compute $x^i \pmod p(x)$, then multiply by $c'_i-c_i$, and we get $(c'_i-c_i) x^i \bmod p(x)$.  Then we add that to the original checksum $r(x)$.  (All arithmetic is done modulo 2, so here "addition" really means xor.)  That gives us the new checksum for the modified file.

If the modification changes multiple bits, there is a natural extension of the move to show how to compute the updated checksum as well.


Worst case analysis of $100n + 5$ for different $n$ For the function $f(n) = 100n + 5$, what is the asymptotic complexity of $f(n)$ in terms of Big O notation. I guess it is $O(n)$, but how can I prove it ?

Big-$O$ is the set of functions
$$O(f)=\{g\colon \exists C>0, \exists N \in \mathbb{N}, \forall n > N, g(n) \leqslant Cf(n)  \}$$
So we can write $100n+5 \leqslant  105\cdot n$, taking $C=105, N=1$, and we obtain
$$100n+5 \in O(n)$$


Expressing conditional in linear program I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are:

if B > 0
         A = 1
else
         A = 0

How to express this as a linear program? I have figured out one condition using the big-M method:

$MA \gt B$

which means that if $B>0$, then $A$ must be 1 to satisfy this constraint. However if $B=0$, then $A$ can be either 1 or 0, and I need another constraint. How to enforce $A$ to be 0 when $B=0$?

If you know the maximum value of $B$ then you can easily express all comparisons as described here: https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/

In your case you need the following:

$0 \le -B + MA \le M-1$

assuming that $M$ is big enough.


Halting problem with extra input Can there be a function HALT(f, y) so that:

There are some x such that f(x) halts iff there are some y such that HALT(f, y) return true;
There are some x such that f(x) doesn't halt iff there are some y such that HALT(f, y) return false;
HALT always halt and return a boolean

? It makes lots of old conflict don't work. E.g. If f(x) loops forever when HALT(f, x) is true, HALT may return true for half of x.

I assume you mean "Turing machine" by "function", otherwise it is meaningless to say a function halts on some input.

Suppose $\mathrm{HALT}$ exists, then we construct a Turing machine $H$ as follows:

On input $\langle M, w\rangle$ where $M$ is an (encoding of) Turing machine:

Construct a Turing machine $N_{\langle M, w\rangle}$ with input $x$ as follows: run $M$ on $x$ and return what $M$ returns.
Run $\mathrm{HALT}$ on $\langle N_{\langle M, w\rangle}, 0\rangle$ and return what $\mathrm{HALT}$ returns.

Note the result of running $N_{\langle M, w\rangle}$ has nothing to do with its input $x$. If $M$ halts on $w$, $N_{\langle M, w\rangle}$ halts on all inputs, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns true. otherwise $N_{\langle M, w\rangle}$ halts on no input, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns false.

Now we can see $M$ halts on $w$ if and only if $H$ accepts $\langle M, w\rangle$. Since $H$ always halts, $H$ is a decider for the normal halting problem, a contradiction!

So $\mathrm{HALT}$ does not exist.


Can the common algorithm to convert to Chomsky Normal Form result in “useless” productions? I have an example below which seems to lead to a “useless” production.
This is the original grammar:
\begin{align*}
    S&\longrightarrow aX\,|\,Yb\\
    X&\longrightarrow S\,|\,\varepsilon\\
    Y&\longrightarrow bY\,|\,b
\end{align*}
Here is the conversion to CNF:
Step 1: Make sure the start symbol does not occur on the RHS.
\begin{align*}
    S'\!\!\!&\longrightarrow S\\
    S&\longrightarrow aX\,|\,Yb\\
    X&\longrightarrow S\,|\,\varepsilon\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 2: Remove rules that lead to $ \varepsilon $.
\begin{align*}
    S'\!\!\!&\longrightarrow S\\
    S&\longrightarrow a\,|\,aX\,|\,Yb\\
    X&\longrightarrow S\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 3: Remove all unit productions.
\begin{align*}
    S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\
    S&\longrightarrow a\,|\,aX\,|\,Yb\\
    X&\longrightarrow a\,|\,aX\,|\,Yb\\
    Y&\longrightarrow bY\,|\,b
  \end{align*}
Step 4: Remove remaining productions which do not conform to CNF.
\begin{align*}
    S'\!\!\!&\longrightarrow a\,|\,AX\,|\,YB\\
    S&\longrightarrow a\,|\,AX\,|\,YB\\
    X&\longrightarrow a\,|\,AX\,|\,YB\\
    Y&\longrightarrow BY\,|\,b\\
    A&\longrightarrow a\\
    B&\longrightarrow b\\
  \end{align*}
It seems that following the algorithm has led to a useless production. The second production will never be invoked from the starting symbol.
Is the production really useless and is it right to remove it from the Chomsky Normal Form grammar?

Given a $CFG \ G$, before converting in $CNF$ you need to clean the grammar, that means (order is important):

  1) eliminate $\epsilon$-productions

  2) eliminate unit productions

  3) eliminate variables that do not derive terminal strings

  4) eliminate unreachable variables from the starting symbol

After this you make substitutions/split rules in order to obtain a CNF grammar.

According to these rules, after your step 3 I would eliminate non generating variables (all the variables can reach a terminal string) and unreachable variables (You cannot reach $S'$ from $S$), to end up with the following productions:

\begin{align*}
  S'\!\!\!&\longrightarrow a\,|\,aX\,|\,Yb\\
    \ X&\longrightarrow a\,|\,aX\,|\,Yb\\
 Y&\longrightarrow bY\,|\,b
  \end{align*}

I don't know which procedure you are following (it may vary according to textbooks/instructors), but if you don't apply steps $3$ and $4$ then yes, you could end up with useless symbols in your grammar in CNF.


How does one generate a list of size N of all possibilities using a dictionary of size D? Say that we have a list of size $N$ to fill with elements of a dictionary of size $D$. So we would have in total $D^N$ elements/possibilities.

It makes sense to me how to write an algorithm for this when the number of possible slots to fill $N$ is fixed. For example if $N = 2$:

A %array of size (D x D x D) = D^3
for i1=1:3
    for i2=1:3
        for i3=1:3
            A[i1,i2,i3] = (i1,i2,i3)

however, I was having some issue generalize such algorithm because it wasn't clear to me how to extend this chain of for loops for general N. Someone have an idea how to do this?

I think the recursive solution is:

V %dictionary of size D
N %number of slots
def combos(n)
    if n==1:
        return V
    answers = []
    for combo in combos(n-1):
        for word in V:
                answers.append(combo+word)
    return answers

The answer is elementary: recursion!

The underlying observation is that if you can create lists of size $N-1$, you can easily create lists of size $N$ by just appending any one of the $D$ values to every $N-1$ long list.

In pseudo code:

def all_possibilities(n, D) {
  if ( n == 0 ) {
    return [[]]
  }
  else {
    smaller = all_possibilities(n-1,D)
    return smaller.map { l =>
        D.map {
          d => l ++ [d]
        }
      }.flatten
  }
}

You can prove this correct by induction over $N$.


SAT formula and satisfying assignment yield another different satisfying assignment Given P=!NP

Is there a polynomial time TM such that for an input of formula and a satisfying assignment will yield a different satisfying assignmentif such exist?

Your problem is NP-complete. Let's call it NextSAT$(F,\tau)$: accept iff $\tau$ is a satisfying assignment of $F$ and there exists a satisfying assignment of $F$ different from $\tau$.

NextSAT is clearly in NP. We now show that SAT $\leq$ NextSAT.

Let $F$ be a CNF on variables $X = \{x_1,\ldots,x_n\}$. If $F$ is the empty CNF, it is obviously satisfiable and we can thus pick any satisfiable instance of NextSAT for the reduction.

Assume now that $F$ has at least one clause. Choose $\tau : X \rightarrow \{0,1\}$ that does not satisfy $F$. It is easy to find by simply choosing a clause of $F$ and negating all its literals. Let $$G = F \lor (\bigwedge_{i \leq n} \ell_i) = \bigwedge_{C \in F} \bigwedge_{i \leq n} C \lor \ell_i$$ where $\ell_i = x_i$ if $\tau(x_i) = 1$ and $\ell_i = \neg x_i$ otherwise. We see that $G$ can be written as a CNF of size polynomial in the size of $F$.

Now, clearly, the satisfying assignments of $G$ is the disjoint union of the satisfying assignments of $F$ and $\tau$ since $\tau$ is the only satisfying assignment of $\bigwedge_{i\leq n} \ell_i$ and does not satisfy $F$. Thus, $F$ is satisfiable if and only if there exists a satisfying assignment of $G$ different from $\tau$. That is, if and only if NextSAT$(G,\tau)$ returns $1$.


Can a vectorized computation always be parallelized? If the question appears vague, I'll gladly clarify. It's not tied to a programing language. If there is a language dependency in the answer, one can place it in the context of Python, R, VB, Mathematica, Matlab, or seek clarification.

Are there situations when a vectorized (aka element-wise application of a function or array programming (AP)) computation cannot be parallelized?

When coding, I frequently replace loops with a vectorized computation, if possible. At times, it's an interesting exercise or (arguably) makes the code more readable. Other times, in hopes of parallelizing it in the future, if need be.

Is there a constraint that would prevent me from parallelizing a vectorized code.

Vectorization example
Note that even seemingly tight loop can be vectorized. For example, cumulative sum of vector elements (1, 2, 3) can be transformed to a matrix form ((1,1,1),(0,2,2),(0,0,3)) and then vectorization is done as column sums producing the desired (1,3,6) cumulative sum. However, vectorization of fibonacci sequence is unlikely(?).

Many thanks for your explanations and references.

If there are dependencies between loop iterations, then the loop cannot be parallelized.  Depending upon the precise definition of "vectorized" you have in mind, your definition might imply that there are no dependencies -- or it might not.

Some examples:

foreach i in S:
    B[i] = f(A[i])

is parallelizable if f is a pure function and A,B don't alias (have no overlap).  (But it is in general not parallelizable if f writes to global state or performs any kind of I/O.)  More generally

foreach i in S:
    B[i] = f(i, x, y, ..)

is parallelizable if f is pure and does not access B (for reading or writing) and none of the arguments alias B.  However,

foreach i in S:
    B[i] = B[A[i]]

is not parallelizable, as there are dependencies between loop iterations.  (At least, it is not trivially parallelizable, if A is not known at compile time.)

I've written using foreach syntax but you can translate each example to map or apply and the same comments apply.


Undecidable unary languages (also known as Tally languages) An exercise that was in a past session is the following:

  Prove that there exists an undecidable subset of $\{1\}^*$

This exercise looks very strange to me, because I think that all subsets are decidable.

Is there a topic that I should read to find a possible answer?

Note that $\{1\}^*$ is isomorphic to $\Bbb N$. There are uncountably many subsets of both $\{1\}^*$ and $\Bbb N$.

Perhaps you are confused with the fact that there are only countably many finite subsets of $\{1\}^*$ (and $\Bbb N$).


Updating the distances matrix after single edge was decreased I was reading this question on how to update the distances matrix D of a graph after one edge was decreased, and I don't understand why it works:

The answer suggests that if the an edge (a,b) was modified - then all you have to do is iterate through every edge of the graph, and calculate: D[u][a] + w(a,b) + D[b][v].

My problem is: how do you know that D[u][a] is correct ?

I've drawn this example:

Now D[u][a] = 100
but, when the edge from a to b decreases:

Now D[u][a] should to be changed to 71 but it's not. and when I will calculate D[u][v] I would use a false D[u][a].

What am I missing here ? is the algorithm presented in the answer linked not correct ? or am I ?

Let me start with the setup, for the simpler case of a directed graph. We are given a weighted directed graph $G$ (with non-negative weights), and for every two vertices $s,t$, the distance $\delta(s,t)$ of a shortest directed path from $s$ to $t$. We modify $G$ to a new graph $G'$ by reducing the weight of an edge $(a,b)$, from $w(a,b)$ to $w'(a,b)$. The claim is that
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t)). $$
(In fact, the claim we want to prove is a bit stronger, since presumably we will be updating the metric sequentially rather than in parallel, but let's leave that for the future.)

In order to prove this formula, we consider two cases.

Case 1. Suppose first that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which doesn't go through the edge $(a,b)$. I claim that $p'$ is also a shortest path from $s$ to $t$ in $G$, and so $\delta'(s,t) = \delta(s,t)$. If not, let $p$ be a shorter path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) < w_G(p') = w_{G'}(p')$, contradicting the definition of $p'$.

It remains to show that $\delta(s,t) \leq \delta(s,a) + w'(a,b) + \delta(b,t)$. Suppose not, and take shortest paths $p_{sa}$ from $s$ to $a$ and $p_{bt}$ from $b$ to $t$, both in $G$. Let $p$ be the (not necessarily simple) path $p_{sa};(a,b);p_{bt}$, so that $w_{G'}(p) = \delta(s,a) + w'(a,b) + \delta(b,t)$. Since $w_{G'}(p) < \delta(s,t) = w_{G'}(p')$, this implies that $p'$ is not a shortest path in $G'$, contradicting its definition.

Case 2. Suppose next that there exists a shortest path $p'$ from $s$ to $t$ in $G'$ which goes through the edge $(a,b)$, say $p' = p'_{sa};(a,b);p'_{bt}$. Since $p'$ is a shortest path and all weights are non-negative, we can assume without loss of generality that $p'$ is simple, and so $p'_{sa},p'_{bt}$ don't go through $(a,b)$.

We claim that $p'_{sa}$ is a shortest path from $s$ to $a$ in $G$, and so has length $\delta(s,a)$. If not, let $p_{sa}$ be a shorter path from $s$ to $a$ in $G$. Without loss of generality, $p_{sa}$ doesn't go through $(a,b)$, since if it did, we would have $p_{sa} = q;(a,b);r$, and could replace $p_{sa}$ with $q$. Since $p_{sa}$ doesn't go through $(a,b)$, it has the same weight in $G$ and in $G'$, and so if we replace $p'_{sa}$ with $p_{sa}$, we would shorten $p'$ in $G'$, contradicting its definition. Similarly, $p'_{bt}$ is a shortest path from $b$ to $t$ in $G$, and so has length $\delta(b,t)$. We conclude that $\delta'(s,t) = \delta(s,a) + w'(a,b) + \delta(b,t)$.

It remains to show that $\delta(s,a) + w'(a,b) + \delta(b,t) \leq \delta(s,t)$. If not, let $p$ be a shortest path from $s$ to $t$ in $G$. Then $w_{G'}(p) \leq w_G(p) = \delta(s,t) < w_{G'}(p')$, contradicting the fact that $p'$ is a shortest path in $G'$.

In the undirected case, we are lowering the weights of two edges, and so the correct formula is
$$ \delta'(s,t) = \min(\delta(s,t), \delta(s,a) + w'(a,b) + \delta(b,t), \delta(s,b) + w'(b,a) + \delta(a,t). $$
(Note $w'(b,a) = w'(a,b)$.)


Partial recursive function and Turing machine The wikipedia article about primitive recursion states that

  An equivalent definition states that a partial recursive function is one that can be computed by a Turing machine.

My question is how one can write down formally this definition?

You first define what a partial recursive function is, and then what a Turing machine is.  Then you show that for every set (problem), there is a Turing machine computing it if and only if it is definable by a partial recursive function.

What you actually would do is to simulate a Turing machine by a partial recursive function and vice versa.  Right to left is simple, left to right takes some work.  You must define an encoding of the machine states (use of e.g. powers of prime numbers), the transition function, a configuration of a machine (i.e., what is currently on the tape, where is the head, and in which state is the machine) etc.


Solution for a combinatorial minimization problem Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality $p \le {a \choose b}$. Is there a closed form solution (can be approximate as well/doesn't have to be exact) for that combinatorial optimization problem?

G. Bach noticed that the best choice for $b$ is $\lfloor a/2 \rfloor$, and furthermore this choice gives the maximal binomial coefficient. The easiest way to see this is to consider the ratio of two adjacent binomial coefficients:
$$ \frac{\binom{a}{b}}{\binom{a}{b+1}} = \frac{b+1}{a-b}.$$
Therefore $\binom{a}{b} \leq \binom{a}{b+1}$ iff $b+1 \leq a-b$ iff $2b+1 \leq a$, and we get the desired result.

The binomial theorem states that
$$ \sum_{b=0}^a \binom{a}{b} = 2^a, $$
hence
$$ \frac{2^a}{a+1} \leq \binom{a}{\lfloor a/2 \rfloor} \leq 2^a. $$
(The correct order of magnitude, $\Theta(2^a/\sqrt{a})$, can be found using Stirling's approximation.) Therefore the optimal $a$ satisfies the following inequalities:
$$ \frac{2^{a-1}}{a} < p \leq 2^a. $$
Therefore $a \geq \log_2 p$. On the other hand, when $p \geq 4$, $a \geq 2$, and so $a - \log_2 a \geq a/2$ (since $a-\log_2 a$ is monotone and $2 - \log_2 2 = 2/2$). Therefore for $p \geq 4$,
$$ 2p\log_2 (2p) > 2\frac{2^{a-1}}{a} (a - \log_2 a) > 2^{a-1}.$$
We conclude that
$$ \log_2 p \leq a < \log_2 p + 1 + \log_2 \log_2 (2p). $$
Therefore the binary search that G. Bach mentions takes only $O(\log\log\log p)$ steps.

If all we want is an asymptotic expression, then since $\binom{a}{\lfloor a/2 \rfloor} = \Theta(2^a/\sqrt{a})$, approximately we have $2^a/\sqrt{a} = Cp$, and so $a = \log_2 p + \Theta(\log_2\log_2 p)$. More terms can be obtained by taking more terms in Stirling's approximation. For example, we can find a constant $A$ such that $a = \log_2 p + A\log_2\log_2 p + o(\log_2\log_2 p)$.


Intuition for Church-Turing thesis for Turing machines I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis -- that any physically computable algorithm can be executed with mu-recursion -- holds for mu-recursion. It reflects exactly the type of algorithms that I can carry out with my own brain.
I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm -- i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?

Imagine you are performing a computation by hand with a pencil and a stack of paper. [1] There is a limit on how many pieces of information you can keep in working memory at a time (sometimes claimed to be seven plus or minus two). So when you can't keep everything in your head, you write some of it down on a sheet of paper. And when you fill up a sheet, you put it in a pile for later reference and pull out another sheet. But there is a limit on how many sheets of paper you can look at at a time, too; you will have to flip between sheets as you work.
Turing machines are an abstraction of this idea of local computation. A Turing machine can write down as much auxiliary information as it wants, but it can only look at a finite amount of it at a time. A Turing machine head is like your brain's working memory—it can only store so much stuff before it has to write it down somewhere to avoid forgetting it.
The Church-Turing thesis says that any physically realizable computation does not require any "essentially nonlocal" operations. That is, any physically realizable computation can be broken down into a series of steps, each of which operates on $O(1)$ bits of information; there is no primitive operation that requires, say $O(n)$ arguments and cannot be reduced to operations with fewer arguments. [2] Or: anything you can compute in the real world can be computed given an unlimited stack of pencils and paper.

[1] Recall that the word "computer" in Turing's time referred to a human profession!
[2] A primitive operation that accepts an unbounded number of arguments is exactly what the oracle in an oracle Turing machine provides—hence why oracle machines can be more powerful than Turing machines.


performance between the data structures I have developed two existing data structures and I want to see their performances over a certain algorithm. In this case I use Dijkstra's algorithm with binary and Fibonacci heaps. Just to ask, if I have 100 to 1000 number of vertices in the tested sparse digraphs, how many times should I execute my program for a single n vertices? How do I know that the empirical differences in performance that I've obtained between data structures are not due to chance?

You can use the program ministat to get statistical information about runtime differences. This blog post gives an example for the usage.

But in general, comparing runtimes is difficult and very machine dependent. Ideally you would find another performance measure that doesn't change so much between processors.

You should also take care that your input instances are well chosen. Random instances might behave very differently from real-world cases, but the latter are typically hard to come by. You should try modelling "interesting" properties of real-world instances and generating instances that also have those properties. You can also try to look very hard at the data structures and try to generate instances that trigger worst-case behaviour, but that is typically also very hard.


Hoare Calculus Incorrect Assignment Axiom I'm currently preparing for an exam and recently came across the following exercise and would like to know whether my solution would be correct.

Exercise:
Prove that the following axiom is not correct in the Hoare Calculus:

{true} u:= t {u=t}

My Proof via Reductio ad absurdum:

Assumption:

Axiom is valid Hoare Calculus Axiom and therefore agrees with the other Axioms.

Proof:

Consider the Hoare Triple: {t = u+1} u:=t {u = t}

This triple is obviously invalid because it does not agree with the Assignment Axiom of the Hoare Calculus.

However, given our Assumption, we can derive it as a valid triple:

(t= u+1) => (true) (Weaken Precondition)

{true} u:=t {u=t} (Axiom of the Assumption)

=> {t = u+1} u:=t {u=t} <- contradiction! => Assumption was false, Axiom is not correct.

q.e.d

Your solution is incorrect because you did not reach a contradiction. You claim that you reached a contradiction with the Assignment axiom. For this to be true, you must produce the negation of an instance of the axiom.

The axiom of assignment states that
$$\{P[e/x]\} \; x \mathbin{:=} e \; \{ P \}$$
In your example we would have $u$ instead of $x$, $t$ instead of $e$, and $P$ would be the statement $u = t$, which gives us the following instance of the axiom
$$\{ t = t \} \; u \mathbin{:=} t \; \{ u = t \}$$
You seem to think this is in contradiction with
$$\{ t = u + 1\} \; u \mathbin{:=} t \; \{ u = t \}$$
but that is a logical error. In fact, the axiom of assignment implies your statement:

$\{ t = t \}\; u \mathbin{:=} t \; \{ u = t \}$ (instance of the axiom of assignment, as above)
$\{ t = u + 1 \}\; u \mathbin{:=} t \; \{ u = t \}$ (weakening of the precondition because $t = u + 1 \Rightarrow t = t$.)

Hint: to solve the exercise, consider the possibility that the expression $t$ contains $u$.


Reversible Merge of Integer Hash Values Context:

I am working with a tree-like data structure. I would like every node in the tree to have an integer hash value that is the result of combining the integer hash values for the node's children. Additionally, I'd like to be able to replace one of the node's children in constant time (i.e., not doing a full recombination of hash values) as the branching factor for the tree could be quite large.

Question:

I am looking for a set of functions ($combine$, $separate$) that operate on fixed width integers and have the following properties.

Let $X$ be some set of integers with fixed width $b$.

(1) $combine(X)$ outputs an integer with width $b$

(2) $combine(X)$ operates in $O(|X|)$ time complexity

(3) $$combine\Bigl(\left\{t, separate\bigl(combine(X), x\bigr)\right\}\Bigr) = combine\Bigl(\bigl(X \setminus \{x\}\bigr) \cup \{t\}\Bigr)$$
where $x \in X$ and $t$ is some integer of width $b$.

(4) $separate(X, x)$ operates in $O(1)$ time complexity

(5) The outputs of $combine$ are going to be used as hash values so an algorithm with a "good" distribution of output values to avoid collisions is ideal. That said, I'd define good as anything better than trivial addition and subtraction (see below).

Initial thoughts:

A trivial implementation would have $combine$ and $separate$ be addition and subtraction (with some modulo logic); however, this obviously won't have a good distribution for tightly bunched input values.

A simple approach is to use the sum of hashes, e.g.,

$$\begin{align*}
\text{combine}(X) &= \sum_{x \in X} H(x)\\
\text{separate}(y,x) &= s - H(x)
\end{align*}$$

where $H(\cdot)$ is some good hash function.  To make the result suitable as a hash, I recommend that you hash the output of combine one more time before using it as a hash value.

More generally, you can use any commutative hash function.  See, e.g., https://crypto.stackexchange.com/q/6497/351 and https://crypto.stackexchange.com/q/11420/351 and https://crypto.stackexchange.com/q/54544/351 and Which fingerprinting/hashing algorithms support compounding?.

Another approach is to use a Merkle hash tree.  Store the list of children in a Merkle hash tree, one mini Merkle hash tree per node of your tree (i.e., a binary tree whose leaves are the children of the node, and where each internal node is augmented with the hash of the values in its two children, and the value in the root of hte Merkle tree is the hash of that node of your tree).  This allows $O(\lg n)$ updates rather than $O(1)$ updates, but that might be good enough.


Proving L = {$ { a^{2^n} \ | \ n \ge 0 } $} is not regular by use of Pumping Lemma I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

We have the language L = {$ { a^{2^n} \ | \ n \ge 0 } $} and we need to prove that it is not regular by use of the pumping lemma.

(i.e. L is words whose length is a power of 2: a, aa, aaaa, aaaaaaaa etc.)

I appreciate the concept of the proof so here we go:

Assuming regularity of L and using the Pumping Lemma, we have $ {a^{2^p}} = {xyz}$ where:

a) ${|y| > 0}$

b) ${|xy| \le p}$

c) $xy^iz \in L \ \forall \ i \ge 0$

(also $ |xyz|\ = 2^p \ge p$)

(notice both x and z can be empty)

I choose $ i = 2$ to get $xy^2z$ so (since $y>0$) $|xy^2z| > 2^p$

I understand that the next step is trying to prove  that $|xy^2z| < 2^{p+1}$ so that the final result is $2^p < |xy^2z| < 2^{p+1}$ and so $xy^2z$ cannot be an element of L.

However if $|y| = p$ and so $|x| = 0,\  |z| = 0$ then this is not possible as taking $y^2$ is just doubling the length of the word which makes another word that fits the language.

Am I missing something important? I have found proofs on multiple web pages (see below) that just seem to assume y cannot be of length p but as far as I can see this isn't the case.

http://cs.geneseo.edu/~baldwin/csci342/fall2012/0928pump.html
http://www.cse.buffalo.edu/courses/cse396/content/hwSol-5.pdf

Thanks very much in advance and please let me know if there is anything I should clarify.

Take a larger $i$. The concept is that gaps between $|2^n|$ get bigger than $|y|$.


Unable to understand a definition of an instruction in a compiler schedule Recently I've accepted a job offer to work on compiler design. To be properly prepared I've decided to review the material. The book that is being used for that is Cooper and Torczon's Engineering a Compiler. That's the one we used in a class. On page 645 there is a definition of a schedule, but I can't figure out what it means

Here is the definition:

  Given a dependence graph $D$ for a code fragment, a schedule $S$ maps each node $n\in N$ to a nonnegative integer that denotes the cycle in which it should be issued, assuming that the first operation issues in cycle 1. This provides a clear and concise definition of an instruction, namely, the $i^{th}$ instruction is the set of operations $\{n \space | \space S(n) = i\}$

I can't understand what this is saying. Can someone phrase this in a simpler way?

I lent my copy of Cooper and Torczon to someone and never got it back, so I can't look up the context.  (It's a good book in general (which is why I didn't get it back)).

The definition of instruction here is unusual.  It corresponds more closely to what you might expect in a Very Long Instruction Word (VLIW) computer or in horizontal microcode.

In a VLIW machine, each instruction is made up of a small fixed number of independent operations.  A typical example would be something like: at most one branch instruction, at most two memory operations, and at most two arithmetic operations.  So you'd expect each instruction to be made up of five operations (some of which might be "no-ops").  So there are going to be two constraints here, and the definition of instruction given by Cooper and Torczon has not yet taken into account those constraints.  (I suspect that they will start discussing the constraints in the pages just after page 645).

To be more specific: a VLIW instruction is a set of operations that can be executed simultaneously/concurrently.  The operations must be (1) independent of each other and (2) the hardware must have sufficient function units to execute all the operations in the set simultaneously.

Cooper and Torczon are probably about to introduce some list scheduling heuristics.  In list scheduling you assign a non-negative integer to each operation such that (1) the dependence dag $D$ is "satisfied" (for all directed edges $x \rightarrow y$, $S(x) \lt S(y)$).  And (2) the set of operations scheduled on each cycle is feasible given the available hardware.  For example, in a greedy list scheduling heuristic you would traverse the dependence DAG in some topological order placing each instruction at the earliest cycle which satisfies both conditions.


Theory of multi-label classification Multi-label classification is a machine-learning problem where each sample can have zero or more labels from a closed set of possible labels. This task has applications in several fields. For example, in dialog systems, each sentence that the human says may have several intents, and the classifier should detect all of them. For example, the sentence "I want a cake and a drink" contains the two intents "WANTCAKE" and "WANTDRINK".

Theoretically, I expect a classifier to classify multi-label samples, even if the training data contained only single-label samples. For example, consider the following training set (where each word is considered a feature):

"I want a cake" -> WANTCAKE
"I want a drink" -> WANTDRINK
"I want a solution" -> WANTSOLUTION

I would expect a classifier to realize, that the words "I want a" are not relevant for classification, and the words cake/drink/solution are indicative of the classes WANTCAKE/WANTDRINK/WANTSOLUTION respectively, and classify the sentence "I want a cake and a drink" correctly as {WANTCAKE,WANTDRINK}.

This seems trivial to humans. Therefore. I was very surprised to find out, that many state-of-the-art multi-label classifiers fail miserably on this simple task!

For example, consider a multi-label classifier in the "Binary Relevance" method. In this method, there is a single binary classifier for each label. For example, there is a binary classifier for the "WANTCAKE" label, trained with I want a cake" as a positive sample, and the other two sentences as negative samples. When this classifier sees the sentence "I want a cake and a drink and a solution", it sees a single feature "cake" that is a positive signal of WANTCAKE, and two features, "drink" and "solution", that are negative signals of WANTCAKE, because they appeared in the training set with sentences that did not have the WANTCAKE label. Therefore, this classifier returns 'negative'. The same happens for the other two binary classifiers, and thus the multi-label classifier returns an empty set!

I also tried other approaches to multi-label classification, such as RF-PCT (Random Forest Prediction Clustering Trees), with a slightly larger example (7 labels instead of 3) and got similar results.

I sent this problem to machine learning experts, and they told me that I need more training data. They said that a classifier cannot tag multi-label instances, if the training data contains only single-label instances. In practice, they are right - adding more training data usually improves the accuracy of the classifier.

But I am still bothered with the theoretical issue - how can it be, that there is no state-of-the-art classifier that can solve this trivial, 3-instance problem?

I am looking for a classifier that provably solves such problems. I.e., a classifier for which there is a proof, that if it is given correct single-label samples, it can correctly solve multi-label cases.

Is there such a classifier?

You subsequently clarified that you are looking for a way to do multi-label classification in general, and the example in the question about wanting a cake was just an example.

OK, here is one standard way to do multi-label classification.  For each candidate label, you build a boolean classifier that outputs true or false: true means that the label applies, false means it doesn't.

In your example, you'd have three classifiers: a "cake classifier" that outputs true if the sentence should be labelled "wants-cake" and false otherwise; a "drink classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise; and a "solution classifier" that outputs true if the sentence should be labelled "wants-drink" and false otherwise.  You now train each one separately.  Given a sentence, you run all three classifiers on it and use that to select which labels should or should not be associated to the sentence.  For instance, if the "cake classifier" outputs true, the "drink classifier outputs false, and the "solution classifier" outputs true, then you label the sentence as "wants-cake + wants-solution".

This allows you to use any boolean classifier as your underlying building block.  For instance, you can use SVMs, decision trees, random forests, and many other schemes.


In fast multiplier circuits, what is the difference between a Counter and a Compressor? When working on fast parallel multiplier circuit designs, like Wallace tree multipliers or Dada tree multipliers I found many papers and books refer to different components used in the tree to reduce the partial products called things like (4:2) compressor, or (7,3) counter or (7:3) compressor.
My question is :

  "What is the difference between a (7:3) compressor and a (7,3) counter?"

  What makes us to call it a compressor rather than a counter? is there any rule?

In multiplier design an (n,k) counter takes an n bit input and produces a k bit output which is the binary representation of the number of input bits that are 1s.  That is: it counts the number of input bits set to 1.

A (3,2) counter is just a full adder.

A (7,3) counter is a circuit with 7 input bits and 3 output bits.  The 3 output bits tell you (in binary) how many of the input bits are set to 1.

In an (n, k) counter it must be the case that $k = \lceil \log_2 (n+1) \rceil$.

A (n:k) compressor is any circuit that takes in n equal weight input bits (plus, possibly, some carry in bits) and outputs a k bit count, plus some additional carry-out bits.  The number of carry-in bits usually equals the number of carry-out bits, but you have to figure out the number by looking at the context.  (Hopefully there's a picture or a detailed description in the paper or book you are reading.)

So a (7,3) counter is also a (7:3) compressor.  But a (7:3) compressor could also mean something else, like something that takes in 7 input bits, plus a carry-in and outputs 3 output bits, plus a carry-out.

The most commonly used compressor is the (4:2) compressor.  This takes in 5 inputs, and output 3 outputs.  The reason it is not just a (5,3) counter is because the output is not a binary number in the range $[0, 5]$.  Rather the output is a 2-bit value in the range $[0,3]$ plus an additional carry-out.  So there are several ways of representing some of the outputs.  For example "2" can be represented as "0+carry-out" or as "2+no-carry-out".


Best way to fusion two list of clusters Imagine the following sets :

A = Set( sortedSet(1,2,3), sortedSet(4,8))
B = Set( sortedSet(3,4), sortedSet(5,6,7) )

Where each inner list represent a cluster composed by indexed dots (1,2,3...).

I want to gather cluster sharing the dots sharing the same index into one to get :

Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )

My first attempt was to merge two Sets

Set( sortedSet(1,2,3) ), sortedSet(3,4), sortedSet(4,8), sortedSet(5,6,7) )

and then merge each subset with subset of the same set where they share a common element. And repeat this process $k$ times with the result set until it doesn't change.

0 : Set( sortedSet(1,2,3,4), sortedSet(3,4,8), sortedSet(5,6,7) )
1 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
2 : Set( sortedSet(1,2,3,4,8), sortedSet(5,6,7) )
1 = 2 then Stop

Unfortunately i think this method is upperbounded in a bit less than $O(k.n^2)$ where n is the total number of elements in every subsets.

My second attempt was to get links which connected subsets of A and B.
Add to each A's subsets every sub sets of B which are connected to them from the link A -> B to get A'. Then use link B -> A to gathered A' subsets to get A''. Finally i apply my first attempt on A'' to get A''' and add it the lonely clusters in A and B.

So my final result is A''' + A_lonely + B_lonely

I use optimization that i know like using SortedSet and exist method (rather than go through each subset to know if they share a common element).

The second method works way faster (5min VS 45min) for a precise test.
But i know that i can still encounter the same issue due to the step A'' -> A''' which remains quadratic.

Any optimizations i could use or proper solution is welcome !

You could create an undirected graph which nodes are the clusters from A and B, two clusters being connected if they have a common dot. This graph can be built in time $O(n)$ where $n$ is the number of dots. Then the problem is to find the connected components of this graph. It is a standard problem that has a solution in linear time in terms of the number of edges and vertices of the graph. The clusters from each connected components are then fusioned to create the resulting clusters.


What do complexity classes look like, if we use Turing reductions? For reasoning about things like NP-completeness, we typically use many-one reductions (i.e., Karp reductions).  This leads to pictures like this:

(under standard conjectures).  I'm sure we're all familiar with this sort of thing.

What picture do we get, if we work with Turing reductions (i.e., Cook reductions)?  How does the picture change?

In particular, what are the most important complexity classes, and how do they relate?  I am guessing that $P^{NP}$ plays the role that used to be taken up by $NP$ and $coNP$ (because $P^{NP}$ is closed under Turing reductions in the same way that $NP$ is closed under Karp reductions); is that about right?

So should the picture look like $P \subset P^{NP} \subset PH \subset PSPACE$ now, i.e., something like the following?

Is there some new sequence that plays a role that corresponds to the polynomial hierarchy?  Is there a natural sequence of complexity classes $C_0=P$, $C_1=P^{NP}$, $C_2=?$, ..., such that each complexity class is closed under Turing reductions?  What is the "limit" of this sequence: is it $PH$?  Is it expected that each class in the sequence is different from the previous one?    (By "expected", I mean under plausible conjectures, similar to the sense in which it is expected that $P \ne NP$.)

Related: Many-one reductions vs. Turing reductions to define NPC.  That article explains that the reason we work with Karp reductions is that it gives us a finer-grained, richer, more precise hierarchy.  Essentially, I am wondering what the hierarchy would look like if we worked with Turing reductions: what the coarser, less rich, less precise hierarchy would look like.

You can use $\mathsf{P}^{\Sigma^\mathsf{P}_i}$.
Some authors denote them by $\square^\mathsf{P}_i$
(similar to $\Delta^\mathsf{P}_i$ and
$\nabla^\mathsf{P}_i$ notations).
It's essentially the Turing closure of the polynomial hierarchy.
We have
$$\mathsf{P}^{\Sigma^\mathsf{P}_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}_i}=
\Sigma^\mathsf{P}_{i+1}\subseteq
\mathsf{P}^{\Sigma^\mathsf{P}_{i+1}}$$
Therefore
$\mathsf{P^{PH}} =
\sum_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}_i} =
\sum_{i\geq 0}\Sigma^\mathsf{P}_{i} =
\mathsf{PH}$.

If the polynomial hierarchy does not collapse all inclusions are strict.


Why has research on genetic algorithms slowed? While discussing some intro level topics today, including the use of genetic algorithms; I was told that research has really slowed in this field. The reason given was that most people are focusing on machine learning and data mining.
Update: Is this accurate? And if so, what advantages does ML/DM have when compared with GA?

Well, machine learning in the sense of statistical pattern recognition and data mining are definitely hotter areas, but I wouldn't say research in evolutionary algorithms has particularly slowed. The two areas aren't generally applied to the same types of problems. It's not immediately clear how a data driven approach helps you, for instance, figure out how to best schedule worker shifts or route packages more efficiently.

Evolutionary methods are most often used on hard optimization problems rather than pattern recognition. The most direct competitors are operations research approaches, basically mathematical programming, and other forms of heuristic search like tabu search, simulated annealing, and dozens of other algorithms collectively known as "metaheuristics". There are two very large annual conferences on evolutionary computation (GECCO and CEC), a slew of smaller conferences like PPSN, EMO, FOGA, and Evostar, and at least two major high-quality journals (IEEE Transactions on Evolutionary Computation and the MIT Press journal Evolution Computation) as well as a number of smaller ones that include EC part of their broader focus.

All that said, there are several advantages the field more generally thought of as "machine learning" has in any comparison of "hotness". One, it tends to be on much firmer theoretical ground, which the mathematicians always like. Two, we're in something of a golden age for data, and lots of the cutting edge machine learning methods really only start to shine when given tons of data and tons of compute power, and in both respects, the time is in a sense "right".


Did 'Eugene Goostman' really pass the Turing test? It is being said that 'Eugene Goostman', a computer programme developed to simulate a 13-year-old boy, managed to convince 33 per cent of the judges that it was human, and thus passed the Turing Test.

The computer programme, aka a chatbot, was pretending to be a 13-year-old Ukranian boy for whom English was a second language – something very different indeed.

For me, Eugene sounds exactly like a mediocre chatbot should: repetitive, nonsensical, and littered with non-sequiturs. I don't know how it convinced the judges (which seem unprofessional).

Many people have criticized Eugene like Prof Stevan Harnad who said "It's nonsense" and "We have not passed the Turing test. We are not even close."

Opinions differ, but I would really like to know if it officially passed the test?

It is also being said that:

  Two one-time-only prizes that have never been
  awarded. 25K is offered for the first chatterbot that judges
  cannot distinguish from a real human and which can convince judges
  that the human is the computer program. $100,000 is the reward for the
  first chatterbot that judges cannot distinguish from a real human in a
  Turing test that includes deciphering and understanding text, visual,
  and auditory input. Once this is achieved, the annual competition will
  end.

Does it mean Eugene won $25,000?

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences.  The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that sense, it passed the test.

Since there is no "official Turing test", it might be more appropriate to say that Eugene Goostman passed a Turing test or even passed a Turing-style test.  It's unlikely that the media would pick up on such subtleties, especially given Turing's fame and the idea of "the Turing test" in the public conscience.


Regular language using pumping lemma a^2n b^(2n+1) is a regular language.
I am not able to decompose it in xyz so that I can pump any power of y as per pumping lemma. Please help me out.

You probably misunderstood the question. For starters, the pumping lemma can't be used to prove that a language is regular, it can only be used to prove that a language isn't regular. The Wikipedia page for the pumping lemma gives a counterexample.

Secondly, as already pointed out by @DavidRicherby, this particular language is not regular, and as it turns out, you can use the Pumping Lemma to prove this statement.

Roughly speaking, the proof goes as follows:

Assume for the sake of contradiction that the language is regular, and thus, the Pumping Lemma holds. The "y" can take one of three forms:

y contains all "a"s
y contains all "b"s
y is of the form $a^ib^j$ for some $i,j > 0$.

Now, can you see how to derive the contradiction?


Meaning of Epilogue in Computing Wordsense.eu defines epilogue as a part of an algorithm that prepares for return.

I’d like to know more & haven’t been able to successfully search for info. Could anyone point me to a source / share their knowledge?

It depends on context, languages, operating systems
In many languages, Prologues and Epilogues are the parts automatically added by compilers at the beginning and end of each function, for example adjusting stack pointers or copying parameters.


Is this possible to solve 3SAT in O(n^24) time and O(1) space? Assume that n is the number variables of the given 3CNF formula (n≥3) and all clauses in the given 3CNF formula are different.

That means that for each clause, each literal can be either positive or negative and be one of the n variables, so the number of options for each literal is 2n, but each clause has exactly 3 literals, so the maximum number of different clauses is 2n•2n•2n = (2n)3 = 8n3 = O(n3).

I have read here that 3CNF formula must have at least 8 different clauses in the form:

(x ∨ y ∨ z) ∧ (x ∨ y ∨ ¬z) ∧ (x ∨ ¬y ∨ z) ∧ (x ∨ ¬y ∨ ¬z) ∧ (¬x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z) ∧ (¬x ∨ ¬y ∨ z) ∧ (¬x ∨ ¬y ∨ ¬z)

to be unsatisfiable.

If this small 3CNF formula is included or subset of a larger 3CNF formula, then the larger 3CNF formula is unsatisfiable for sure, because of that subset.

So the algorithm needs to search for this subset and if the algorithm found it then the algorithm returns "given formula is unsatisfiable" as output.

And this suppose to be correct for sure.

But what happens if the algorithm doesn't find such subset?

Does this necessarily means that the given 3CNF formula is not unsatisfiable, i.e. satisfiable?

Because that the subset has exactly 8 clauses, the algorithm needs to iterate through all the different subsets of 8 clauses in the given 3CNF formula.

If the given 3CNF formula has m clauses, then there should be θ(m8) different subsets of 8 clauses, but if all clauses are different, then m=O(n3), thus O((n3)8) = O(n3•8) = O(n24)

So the running time of the algorithm to iterate through all these subsets and to find the unsatisfiable subset, if exists, takes θ(n24) time.

To do this, the algorithm needs 8 inner for loops, where each for loop is inside the other, with 8 iterative variables.

Because that the algorithm doesn't allocate any memory during the run time, the space complexity of this algorithm suppose to be θ(1).

Let me know if I was wrong and on what, i.e. if I am wrong then why?

Why I was wrong?

Please explain.

I want to learn from mistakes.

I think that

it's too good to be true

and

if it's too good to be true, something's wrong.

You are correct in your assumption that your algorithm correctly identifies some unsatisfiable instances, but for the general case it does not work.

For instance, you can always rewrite a clause $\{A, B, C\}$ to the equisatisfiable clause set $\{A, X, Y\}, \{\neg X, A, B\}, \{\neg Y, B, C\}$. To see this, observe that you can always recover the original clause through resolution. If applied to say, the first clause in the above example, this will already break your algorithm.

Maybe someone with more knowledge on SAT can give some more insightful information.


What is the complexity class of finding vertex cover number of a simple graph? Suppose we have a simple graph $G$. We know that finding the minimum vertex covering set for $G$ is in the NP-hard class. But, what about the complexity class of finding the size of the set, i.e., the vertex cover number denoted by $\tau(G)$. Is there any previous result about this research question?

It is actually finding the number that is NP-complete.  The (decision) problem is formally stated as follows:
Vertex cover.  Given a graph $G = (V, E)$ and an integer $k$, does there exist a set of at most $k$ vertices $C \subseteq V$ such that every edge has at least one endpoint in $C$?
As you can see, this is precisely your $\tau(G)$.
The other problem is often called the optimization problem, and is defined as following:
Vertex cover optimization.  Given a graph $G = (V, E)$, find a set $C \subseteq V$ of minimum size such that every edge has at least one endpoint in $C$.

The two problems are quite easy to jump between, at least if you are given polynomial time.  If you have an algorithm for the optimization problem, I'm sure you have already found out how to answer the decision version.
But given an algorithm for the decision version it is quite easy to create an optimization algorithm.  You can try to work it out yourself, but a hint is to see what happens with $\tau(G)$ if you remove a vertex from the graph.


Proof that CFL aren't closed under intersection using synchronous parallel (N)PDA composition It is well known that the class of CFLs is not closed under intersection as follows e.g. from the following example:
$$L_1 \cap L_2 = \left\{ a^mb^mc^n \mid m,n \ge 1 \right\} \cap \left\{ a^mb^nc^n \mid m,n \ge 1 \right\} = \left\{ a^ib^ic^i \mid i \ge 1 \right\} \not \in \mathcal{L_2},$$
where $L_1,L_2 \in \mathcal{L2}$.

I was wondering if this could be proven using the synchronous parallel composition of two (non-deterministic) PDAs, or rather what is wrong with the following construction which seemingly comes to the opposite conclusion:

  Let $PDA_1, PDA_2, PDA_{1,2}$ be, WOLOG, (non-deterministic) PDAs accepting by final state and with total transition functions:
  $$ PDA_1 = \Big(Q_1, \Sigma_1, \Gamma_1, \delta_1, q^0_1, \gamma^0_1, F_1 \Big) \\
PDA_2 = \Big(Q_2, \Sigma_2, \Gamma_2, \delta_2, q^0_2, \gamma^0_2, F_2 \Big) \\
PDA_{1,2} = \Big(Q_1 \times Q_2 \cup \big(q_{\emptyset}, q_{\emptyset}\big), \Sigma_1 \cup \Sigma_2, \Gamma_1 \times \Gamma_2, \delta_{1,2}, \big(q^0_1, q^0_2 \big), \big(\gamma^0_1, \gamma^0_2 \big), F_1 \times F_2 \Big)$$
  where $q_{\emptyset} \not\in Q_1 \cup Q_2$ and $\delta_{1,2}$ is defined as follows:
  $$ \delta_{1,2} \Big(\big(q_1, q_2 \big), a, \big(\gamma_1, \gamma_2 \big) \Big) = \begin{cases}
    \Big(\big(q'_1, q'_2 \big), \big(\gamma'_1, \gamma'_2 \big) \Big) & \big(q'_1, \gamma'_1 \big) \in \delta_1 \big(q_1, a, \gamma_1 \big) \land \\ & \big(q'_2, \gamma'_2 \big) \in \delta_2 \big(q_2, a, \gamma_2 \big) \\
& \text{(if such transitions are defined)} \\
    \Big(\big(q_{\emptyset}, q_{\emptyset} \big), \big(\gamma_1, \gamma_2 \big)\Big) & \text{otherwise} \\
\end{cases} $$

Surely $PDA_{1,2}$ accepts only words from the intersection of languages $L(PDA_1)$ and $L(PDA_2)$. Why doesn't it accept all of them?

This doesn't work, because the stacks of the two PDAs aren't synchronized.  You can get to a state where $\text{PDA}_1$ pushes a symbol but $\text{PDA}_2$ pops a symbol.  What is $\text{PDA}_{1,2}$ supposed to do at that point?  It's screwed.

The product construction would work if there was a guarantee that the length of the stack of $\text{PDA}_1$ was always the same as the length of the stack of $\text{PDA}_2$ -- but as explained, this is not guaranteed.

Another way to put it: Your definition of $\delta_{1,2}$ does not make any sense.  The output is supposed to be an element of $Q \times \Gamma^*$, where here $\Gamma = \Gamma_1 \times \Gamma_2$.  However, a pair like $(\lambda'_1,\lambda'_2)$ is not an element of $(\Gamma_1 \times \Gamma_2)^*$.  If the length of $\lambda'_1$ was the same as the length of $\lambda'_2$, you could interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$: it is the string whose $i$th symbol is $(\lambda'_1[i],\lambda'_2[i])$.  Unfortunately, when the length of $\lambda'_1$ is different from the length of $\lambda'_2$, there's no way to interpret $(\lambda'_1,\lambda'_2)$ as an element of $(\Gamma_1 \times \Gamma_2)^*$.  Consequently, your definition of $\delta_{1,2}$ is not well-formed: it does not have the proper type signature.

As you quite accurately summarize the situation:  One stack can grow ad infinitum while the other not and in order to access the previous element from the shorter stack, the PDA would need to indestructibly go through the potentially infinitely long stack. This could be fixed if we had an automaton with two separate stacks; however, such an automaton would be computationally equivalent to a Turing machine and thus is more powerful than a PDA (which only has one stack).


Event-based architecture (in the context of Distributed Systems) Our course lecture slides divide architectures of distributed systems into:

object based architectures (e.g. typical distributed web application)
resource-centered architectures (e.g. torrents and magnet links)
event-based architectures (e.g. ???)

I do not understand the explanation on the slides and they don't provide any examples. A google search will not return any results for event-based architecture in the context of distributed systems, only in other contexts where the meaning is different. Can someone explain what are "event-based architectures" with a simple example like "torrents" are for resource-centered architectures?

A simple example of an event based architecture (in daily life) would be a postman sorting letters based on address. The “event” here is the arrival of new letters to sort.

If no letters arrive, the sorter will be idle, waiting for the letters to arrive. On the other hand if too many letters arrive at the same time, the sorter will stack those letters on his/her table and sort them based on their own speed.

The key takeaway here is the fact that the arrival of letters and sorting them is decoupled. The only bottleneck here is the size of the table on which the sorter can stack letters. The requirement is that all the letters should have an address.

The multiple producers of these letters (humans) can keep sending letters and be guaranteed the deliver of the letter (albeit not instantaneously). The consumers (sorter(s)) subscribe to the stream of letters and can sort/process them at their own speed.

This is impotant in distributed systems to do time intensive jobs that take a long time but don’t require instant results.

This allows your application to scale and be responsive independently of the time taken by these intensive jobs to complete.

A good example would be uploading video to youtube. You upload the video to youtube and youtube tells you that it will notify you when the video processing is complete.

In this scenario, your user facing application:
1) Accepts the uploaded video
2) Stores it in a location
3) Produces an event for consumers with details of video location

The consumer (a different server) would be listening for these events and do the video processing. After processing is complete, it would send a notification to the user.

Note: I don’t work with google. This is just an example of how I think it might work at a very basic level.


Mutli-Path Collision Avoidance I need an algorithm which can do the following:

  Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{R}^2$ for the particles to take so they won't collide.

The list of points for a particle specifies the order in which the particle must visit those points.  All particles start moving at the same time.  The time elapsed for a particle to travel from any prescribed point to the next is constant for every particle regardless of distance.  I'd like to find a continuous trajectory for each particle, so they won't collide (the circles won't overlap).  Ideally, I would like to find the solution which minimizes total path length under the constraint that there are no collisions.

Assume that the distance between the n'th prescribed point of different particles are at least the particle's diameter apart so that there are no unfixable collisions.

My best solution is just making splines for every path, and keeping a record of all the collisions.  I have been reading papers about potentially adding more prescribed points to bend the paths, and 'elastic bands', but I'm not sure exactly how to do it.

Let me first discuss some possible solutions for the case of $n$ particles and 2 points per particle, then extend it to an arbitrary number of points.

Suppose we're given $n$ particles and 2 points per particle.    Assume we're also given an additional constraint: the initial direction of each particle is also specified.  For each particle, it's easy enough to draw a path from the starting point to the ending point.  Now consider the collection of those paths, and find all collisions.  If we don't have any limit on the velocities or accelerations of each particle, it should be straightforward to pick a particle, choose the speed at which it traverses its path (if a constant speed causes collisions, slow down until you reach the collision point, then speed up afterwards, and adjust until there are no more collisions), and repeat, one particle at a time.

Let's suppose you have an algorithm you're happy with, for $m=2$ points per particle.  Then you can use that to solve the problem for $n$ particles and $m$ points per particle, for any $m \ge 2$: you simply solve it for each pair of adjacent time steps (i.e., the $i$th and $i+1$th points), then combine those solutions.

Probably this could be improved, by finding a better way to handle the $m=2$ case.  For instance, if there is an algorithm for laying out a graph as a planar graph, given pre-specified locations for all vertices, that might help find better solutions.  However, maybe this illustrates one approach that can find at least a possible solution, even if it's not optimal.


CFG-Infinite recursion As you see, the string production process never ends.
Can someone explain me if  this language is  regular or not  ?
$ S \to Α Β S $
$ A \to S  $
$ B \to a B b $

The language is regular:
$$ L = \{\}$$
It doesn't contain any word not even the empty word $\varepsilon$.
The automaton recognizing it has only one state; a reject state.
Or if you are using DFA the automaton just wouldn't have an accept state.
Notice that the language is regular but that the grammar is written in a form that's usually used for context free grammars, but the language produced by it is still regular.


Rice–Shapiro theorem example Rice-Shapiro theorem is:

  Let $Γ$ be a set of computable functions such that the set $R_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

If $Γ$ is singleton set, for example $Γ = \lbrace ϕ_{10}\rbrace$ then $R_Γ = \lbrace 10 \rbrace$ and is recursively enumerable, but $Γ$ does not satisfy:

$f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

Where I have made a mistake?

The flaw is that $R_\Gamma$ includes not just the natural number $10$, but any natural number which gives rise to the same partial recursive function. It will be infinite, and not recursively enumerable.

In general, for any partial recursive function $f$ you can think of, there will be many Godel numbers which describe it. In other words, many partial recursive function descriptions result in the same actual function. If you are more familiar with Turing machines, there will always be many different Turing machines which compute the same abstract function or language.

In summary: $\Gamma$ is any set of functions. However, $R_\Gamma$ is the set of natural numbers which encode that function. In your case, for $\Gamma = \{\phi_{10}\}$, $R_\Gamma$ is the set of natural numbers which encode the same function as $10$, and this set is not recursively enumerable.


Why are computable numbers (in Turing's sense) enumerable? Why are computable numbers (in Turing's sense) enumerable?
It must be very obvious, but I'm currently just not seeing it.

I'm assuming that your definition of a computable number is this: there is a Turing machine that on input $n$, halts with the $n$th bit of the number.

Suppose there were a recursive enumeration of Turing machines that produce computable numbers. You can use diagonalization to come up with a new computable number which isn't part of this recursive enumeration.

It is tempting to enumerate computable numbers by enumerating Turing machines, but not every Turing machine corresponds to a computable number, and in general deciding whether a Turing machine halts for all inputs (let alone output either 0 or 1) is not computable. It is, however, possible to enumerate all efficient computable numbers, say ones whose running time is polynomial, by using clocked Turing machines.


How does in-order traversal in Binary search tree works (recursion) I visit some question but their implementations are slightly different and my doubt is not like theirs. I have this code in Javascript.

The code is typical BST implementation with methods to support in-order traversal. The code that is the most relavant for this question is the the inOrderTraverse and inOrderTraverseNode. I cannot understand how this code work.

function BinarySearchTree() {

    var Node = function (key) {
        this.key = key;
        this.left = null;
        this.right = null;
    };

    var root = null;

    this.inOrderTraverse = function (callback) {

         inOrderTraverseNode(root, callback);
    }

    this.insert = function (key) {

        var newNode = new Node(key);

        if (root === null) {
            root = newNode;
        }
        else {
            insertNode(root, newNode);
        }

    }

    var insertNode = function (node, newNode) {

        if (newNode.key < node.key) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }

    };

    var inOrderTraverseNode = function (node, callback) {

        if (node !== null) {
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }
}

The code that will use the BinarySearchTree "class".

function printNode(value) {
    document.writeln(value);
}

var tree = new BinarySearchTree();

tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);

tree.inOrderTraverse(printNode);

This will generate a BST like this:

taken from the book Learning Javascript Data Structure and Algorithms by Loiane Grone

I will explain how I think the in-order functionality works.

    var inOrderTraverseNode = function (node, callback) {

    if (node !== null) {     //checks if the node is null, 11 is not null so it continues
        inOrderTraverseNode(node.left, callback);     //keep executing this code until it finds a node with left null
        callback(node.key);      //3, the node with left null is printed
        inOrderTraverseNode(node.right, callback);     // checks if the 3 node has a right node, it doesn't have, so the execution finishes
    }

}

11 the root node is passed to the inOrderTraverseNode, it checks to see if the left is a null, if it is not it continues passing the left node until the left node is null. When a left null node is found Then it prints the value, callback(node.key) will execute as callback(3), so the 3 will be the first item printed on the screen. The execution then continues to inOrderTraverseNode(node.right, callback), 3 don't have a right child so execution will go on and that's that.

in my mind the output would be 3 only.

How do the in-order traversal get from 3 to the 5?

Consider indorder as a command in military. Let the binary tree be the hierarchy among the soldiers.

The general shouts "inorder!" and that means, when a subordinate receives the order, he tells it to his "left" subordinates. If he has no subordinates on the left side, then he yells out his name, and only then he commands his right subordinate to execute the order.

  Inorder! command means "tell your first subordinate, do it yourself, and then tell your right subordinate. Afther you are
  finished, report to your superior."

The general is the root of the binary tree.
He shouts out "inorder!"

That means his left subordinate gets the order, and shouts out "inorder!" himself. This process goes on until the order reaches to a soldier who has no left subordinate. Then, he yells out his name and gives the order to his right subordinate.

After all his right subordinates are done, he reports back to his immediate superior. The superior, like him, yells out his name and gives the order to his right subordinate.

When all the left side is done, the general (root of the binary tree) yells out his name and gives the order to his right side.

Now, consider this tree
(taken from https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/):

The general is 1. He shouts "inorder!"

2 recieves the order, and he shouts "inorder!"

4 receives the order. He has no left child, and thus shouts his name: 4

He has also no right child, and thus reports to 2.

Left side of 2 is done, and this 2 shouts his name: 2, and then gives the order to the right side.

This process goes on, until the root is notified a second time.


Shuffling a list while keeping order relative to related elements I'm looking to shuffle a list of the elements $a_1,\dots, a_6, \dots, e_1, \dots, e_6$

while keeping two rules:

if I loop though the list and filter out a specific letter or number it should be in order:

$a_1, a_2, a_3 \dots$ or $a_1, b_1, c_1 \dots$

How can I shuffle the list keeping these rules? I'm using python, so if there's a library that'd be great. Otherwise, just a generic way I could tackle this problem.

Here's an example of a shuffle that would fit the criteria:

$a_1, b_1, a_2, b_2, c_1, a_3, d_1, c_2, d_2, e_1, a_4, b_3,$ $c_3, d_3, b_4, d_4, c_4, a_5, e_2, d_5, e_3, c_5, a_6, b_5, e_4, a_7, $ $b_6, c_6, b_7, d_6, e_5, e_6, c_7, d_7, e_7$

Your problem can be phrased as generating a random linear extension of a partial order. The partial order in your phrase is generated by your constraints. There is a classical algorithm of Matthews described in his paper Generating a random linear extension of a partial order. This might even be implemented in some library.

Your particular case is generating a random lattice word of certain content (for the reduction, delete all letters or all numbers). This is a concept occurring in representation theory of the symmetric groups, generalizing the classical ballot sequences. If you're lucky you might find an algorithm for generating a random lattice word (in Mupad, for example, somebody implemented an algorithm for generating all lattice words).


What is Pointer Jumping ? Studying parallel algorithms for CLRS, old edition Chapter 30.  Can some one explain with a simple example what is pointer jumping and how exactly it works ?

I really can't explain it better than Wikipedia does:

Suppose you want to traverse a tree. You can traverse it in a serial manner by walking the tree (either recursively or otherwise), or you can traverse it parallel by starting at $N$ leaf nodes and following the shortest path to the root.

In the serial case your running time will be $O(n\log(n))$.
$n$ is because you need to visit all $n$ nodes and $\log(n)$ because of extra time spend going up and down the tree because you can only reach sibling nodes via their parent.

In the parallel case your best running time will be $O(\log(n))$ or more accurate $O(\frac{n}{m}\log(n))$ where $m$ is the number of threads used.
You do this by assigning a leaf node to a thread and finding the shortest path to the root.
If you have more leaf nodes than threads you'll assign more than one leaf node to a thread.

Because the height of a tree is $\log(n)$ the running time per thread is obviously $O(\log(n))$.
This is not as efficient as can be, because the closer you get to the root the more nodes will get visited more than once.
You can solve this issue by having the first thread to arrive at a parent to leave a breadcrumb after which subsequent threads drop out.
If you elect to let duplicate threads drop out of the traverse, you also solve the problem of thread synchronization issues when altering data in the tree.


Sum number of times statement is executed in triple nested loop I have this code fragment:

for( i=0; i<n; i++ )
    for( j=0; j<i; j++ )
        for( k=0; k<j; k++ )
            S;

I need to find the number of times that S is executed in that code block. I plugged it into Wolfram Alpha but I am not sure if that is the right answer.

I want to be able to do the math in order to figure the answer out so can someone point me in the right direction?

The Wolfram Alpha answer isn't quite correct - you're off by one in each sum - the loop will iterate over $\{1,...,n-1\}$, not $\{1,...,n\}$, though other than that your reasoning is sound. What you should be asking W/A for is:

$$
\sum^{n-1}_{i=0}\sum^{i-1}_{j=0}\sum^{j-1}_{k=0} 1
$$

If you break the sums down bit by bit it gets a little easier to swallow, just start at the innermost sum and work outwards. It's probably fairly obvious that $\sum^{j-1}_{k=0}1 = j$, which breaks the triple-sum down into $\sum^{n-1}_{i=0}\sum^{i-1}_{j=0}j$.

We have that $\sum^{i-1}_{j=0}j = \frac{1}{2}(i^2-i)$, so what was a double sum is now the difference of two sums, $\frac{1}{2}(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i)$.

The second term has already been worked out, and we have that $\sum^{n-1}_{i=0}i^2 = \frac{n(n-1)(2n-1)}{6}$. From there, you should be able to work out your answer;

\begin{align*}
\frac{1}{2}\left(\sum^{n-1}_{i=0}i^2 - \sum^{n-1}_{i=0}i\right)
&= \frac{1}{2}\left(\frac{n(n-1)(2n-1)}{6} - \frac{3n(n-1)}{6} \right)\\
&= \frac{1}{2}\left((2n-1)\frac{n(n-1)}{6} - 3\frac{n(n-1)}{6} \right)\\
&= \frac{n(n-1)(2n-4)}{12}\\
&= \frac{n(n-1)(n-2)}{6}
\end{align*}

The results about the sum of the first $n-1$ numbers and the sum of the first $n-1$ square numbers are fairly standard ones - if you want some proofs of them then this page gives some nice arguments, though note that their sums end at $n$ and not $n-1$.


Matching algorithm, match pairs: what would be the right way to do it? How would you solve the following problem...
Theres a table filled with data like this:

Data1: 50 51 48 55 50
Data2: 51 49 52 50 51
Data3: 49 53 50 51 48
Data4: 48 50 52 51 53
Data5: 47 50 51 54 49
Data6: 50 48 50 49 52
Data7: 51 50 51 49 51
Data8: 48 51 49 50 50
...

The goal is to create pairs from the table, based on similarity of the rows.

As i learned from the comments, it is matching, thx :)

A difference bigger than 3 is not allowed.

When values are close to each other, they should be paired, for example

Data2: 51 49 52 50 51
Data7: 51 50 51 49 51

have very close values and should be a paired/grouped. So if this is our first pair, what is the next one?
And how to handle outliers (in the columns)? For example

Data1: 50 51 48 55 50

has in the fourth column the value 55. With the criteria no bigger difference than 3, the only possible companion is Data5:

Data5: 47 50 51 54 49
Data1: 50 51 48 55 50

But in cloumn 1 and 3 the delta is 3, so in the mean maybe it isnt such a good choice.

Outlier who couldnt be assigned because of the too big deviation, will not be considered.
The algorithm has not to be efficient.

Maybe you can see that it is just not clear for me, how to check the data  against each other. To match the best fitting rows together.

So to answer the question about the use: each datarow is one measured device. You need two devices for the signal reproduction. For the best reproduction result you need maximum coherence between those two. So perfect would be an ideal match. So the goal is to find the best matching devices in the table.

This isn't sorting: it's matching. The vertices of your graph are the data rows and there's an edge between two vertices if the two rows are compatible for pairing (e.g., have no difference bigger than 3, or whatever criterion you want to use).  You're looking for a maximum matching, i.e., a biggest-possible pairing between compatible rows.

It's unclear in your question but you might instead want to define a weighted graph where the weight of an edge is the amount of compatibility (e.g., rows that are very close have a high weight, rows that aren't so close have a low weight, rows that are incompatible have no edge, as before) and compute a maximum-weight matching.


Changing binary counter structure such that increament and decreament methods will work in O(1) amortized Just trying to solve the second part of a question with two parts.
First part was to prove that you can't add decrement method to a standart binary counter without hurting the amortized complexity and change it to be more than O(1).
This part i have done with no problems.
Solution in a nutshell - after some method you are going to be in a dead end when you have a number like this: 100...0 so when you decrease by 1 you will get 0111...1 and then when you will increase by 1 you will get again 100...0 and those decreasment and increament are cost n and you will do them m times so its not O(1) amortized.
The second part, is to tell how you can change the structure such that it will support decreament and increase methods and the amortized complexity will stay O(1).
I never saw something like this and it really confusing me what they want me to do.
Their solution is that anytime you want to change 0 to 1 you change it to minus 1.
Problem is, i can't understand what they meant, i mean, on which stracture you are inserting this change and how does it improved the complexity (if you change to -1 you stil going to the same dead end).

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


Relations of some exponential functions -- which is correct? Consider the following functions

$f(n) = 3n^{(n^{1/2})}  $
$g(n) = 2^{(n^{1/2}) \log n }$  // here base of $\log n$ is 2
$h(n) = n !$

Which of the following is true?

$ h (n)$ is $O (f (n) )  $
$h (n)$ is $O (g (n)) $
$g (n)$ is not $O (f (n) )  $
$ f(n)$ is $O(g (n))$

I tried this way :

To check which function is large :

$3n^{(n^{1/2})}$ = taking log

$n^{1/2} \log 3n $

$g(n) = 2^{(n^{1/2}) \log n }$

by taking log :

$((n^{1/2})\log n )\log 2$ => $0.3 (n^{1/2})\log n  $

$h(n) = n !$ => $n^n  $

by taking log :

$n \log n $

So now comparing all these 3 functions I got following equality :

$f(n) < g(n) < h(n)  $
So answer should be (4) but actually answer is (1).
Could anyone explain me where I am wrong ?

(1) is not the correct answer.  Perhaps there is an error in the book, or an error in what you entered.  As you correctly concluded, $f(n) = 3 e^{n^{1/2} \log n}$ and $h(n) \approx e^{n \log n}$ (by Stirling's approximation), so it is not true that $h(n) = O(f(n))$.

I can't tell whether you've drawn the correct conclusions about the pairwise relationships between these three functions.  You wrote that $f(n) < g(n) < h(n)$, but this is not correct.  For instance, $f(1) = 3$, $g(1) = 3$, $h(1) = 1$.  Those inequalities don't hold for all $n$ -- but if we care about big-O notation, then that's not the right question anyway, since big-O notation relates to the asymptotic behavior of these functions (as $n\to \infty$).

The right question is whether $f(n) = O(g(n))$, whether $g(n) = O(f(n))$ (be careful here!  better double-check your work on this one another time), and so on.

See also Sorting functions by asymptotic growth and How does one know which notation of time complexity analysis to use?.  They should answer your remaining questions.


Empirical evidence for the Church-Turing thesis in other disciplines I am aware of the fact that, since the concept of "effectively calculable function" is not rigorous or formally definable, the Church-Turing thesis may not be proven by symbolic or formal reasoning alone.

My impression, though, is that under the domain of physics, philosophy, cognitive science or other disciplines, we may find empirical evidence that gives us a strong reason for accepting it, for instance in the field of numerical cognition. Even if those disciplines are not directly related to computer science, the importance of this thesis in CS make this, in my opinion, an important issue to consider for us; that's why I'm asking this question here. (If you feel like there are better SE suited for this questions, let me know please.)

So, what is the current state of the research for evidence to support the Church-Turing thesis? Are there any recent developments?

A good answer would also provide a list of all the major efforts to this day to empirically validate or refute the CT-Thesis, and the main problems posed by this issue. Investigations on the notion of "effectively calculable" in cognitive science, or what does it mean to "compute" in physics are also welcome.

Proof is an inherently mathematical concept. "Effectively calculable function" has no definition in mathematics and you can't prove something that doesn't have a definition.


Can a DFA have two symbols on one arrow? I know that a DFA has to have exactly one transition for each symbol in the alphabet, but is it allowed to have two symbols on the same arrow? If, for example, I have a DFA with states $q_0$ and $q_1$, can I have one arrow from $q_0$ to $q_1$ with both $a$ and $b$?

This may be a stupid question, but I need to be completely sure that this is allowed (I believe it is).

The transition graph (as a drawing) is merely a representation of an Automaton, which is a well-defined model.

Formally, an DFA is a tuple $(Q,\Sigma,\delta,q_0,F)$, where the "type" of the transition function is $\delta:Q\times \Sigma\to Q$.

Thus, if you have $\delta(q_0,a)=\delta(q_0,b)=q_1$, that's fine.
In the graphic representation, you will either have two arrows from $q_0$ to $q_1$, labeled $a$ and $b$, or you can just put both letters on the same arrow, it's not a formal thing anyway.


What advantages does Block Programming Environment have over High Level Programming Language What advantages do block programming environments like App Inventor have over high level programming languages like Python or Java?

Developing complex software is completely different from writing small programs.

Complex individual systems are usually elements of complex ecosystems of software and hardware platforms, interfaces, languages, and even extra-computational factors. In creating those kinds of systems the choice of languages that use visual metaphors would probably be detrimental, not beneficial, and that is why professional software developers are happy that the languages they use are "spartan".

On the other hand, if your intention is to reduce the learning curve for begginers that are not going to be professional developers of any kind, then you can begin to talk about the benefits of those "soft" languages.


Check whether loop invariants are correct? I'm trying to prove some code is correct, using Hoare logic.  How do I check whether my loop invariants are correct?

I'm asked to prove (using Hoare Logic) that the following program is valid:

x=1;
i=N;
while (i!=0){
    i--;
    x*=A;
}

with the pre-condition that N>=0 and post-condition that x=A^N.

This is my attempt:

{ N>=0 }
x=1;
i=N;
{i >= 0}
while (i!=0){
    {i>=0}
    {x = product(i in (0:N-i); A)}    (loop invariant)
    i--;
    x*=A;
}
{x = A^N}

The curly brackets represent invariants that are supposed to hold at that point in the code.  The 2 loop invariants seem to hold for every instance of the loop.

Is my attempt correct?  Are my loop invariants sufficient? Do I have too many?

I know that {i>=0} is given by the definition of the loop. Should I remove that loop invariant then, since it is the case by default?

EDIT: My new attempt

{N>=0}
x=1;
{x = A^(N-N)=A^0=1}
i=N;
{x = A^(N-i)}
while (i!=0){
    {i>=0}
    i--;
    {x = product(i in (0:N-i-1);A)}
    x*=A;
    {x = product(i in (0:N-i);A)}
}
{x=A^N}

Rather than telling you whether your specific invariants are correct, let me teach you the procedure for how you can check whether your invariants are correct on your own.

Basically, you break it down by looking at each chunk of code separately.  For each chunk of code, you look at the invariant before it and after it and see whether they're consistent with that chunk of code.  If this check passes for all of the chunks, you're done: you're entitled to conclude that your program is "correct".  The beauty of this is that this helps you break down the task into small manageable pieces.  You never have to think about the entire program as a whole -- you only look at one chunk, in isolation, at any given time.

The way you verify a chunk of code depends on what kind of statement it contains.  There are only a few cases you need to worry about:

Straight-line code. Suppose you have a statement with no branching, e.g.,

{P}
stuff;
{Q}

What you need to do is check that if P is true before the statement, then after executing the statement, Q will surely be true.  In other words, if all we know about the state of the program is that P is true, and then we execute stuff, then afterwards it is guaranteed that Q will be true.

Notice that you check this by looking only at P, Q, and stuff: you shouldn't need look at any code in the rest of the program.  If you find yourself trying to think about what the rest of the program is doing or ways you might be able to reach this chunk of code, you're doing something wrong, and probably you need to strengthen P (add some additional clauses that record more information about what states of the program are possible at that point).
Loops.  Suppose you have a while-loop, e.g.,

{P}
while (e) {
    {Q}
    stuff
    {R}
}
{S}

Then you need to check four things.  First, you need to check that the path that skips the loop entirely is valid, i.e., check that P && !e implies S.  Second, you need to check that, on the first iteration of the loop, the loop invariant will hold: i.e., check that P && e implies Q.  Third, you need to check that on any iteration of the loop, the following is valid:

{Q}
stuff
{R}

Fourth, you need to check that R && e implies Q.  Fifth, you need to check that on the last iteration, S is enforced, i.e., that R && !e implies S.  If all of these checks pass, then your invariants for the while-loop are OK.

Here's a different way to think about it that might feel more intuitive.  You can try to find an invariant T that lets you annotate the loop with

{T}
while (e) {
    {T && e}
    stuff
    {T}
}
{T && !e}

All you need to check is that the following code block is valid:

{T && e}
stuff
{T}

If that code block is valid, then the entire while-loop construct is acceptable.
Conditional statements. If statements can be handled similarly, but are a bit easier than while-loops.  For instance, if you have

{P}
if (e) {
    {Q}
    stuff
    {R}
}
{S}

then you need to check both the false-path and the true-path through the conditional.  To check the false-path, check that P && !e implies S.  To check the true-path, check that P && e implies Q, that R implies S, and that the following is valid:

{Q}
stuff
{R}

In this way, you should be able to check all of your invariants step-by-step.  The only two things you need to know how to do are: (1) check whether one logical formula implies another, and (2) verify invariants for straight-line code.  Everything else reduces to those operations.

With practice, you'll find that this becomes pretty mechanical.  And with practice, you'll find that many of these invariants can be omitted (if it's straightforward for a reader to re-derive them), but when you start out, it's best to be verbose and include them all, without trying to omit stuff.