Dijkstra's algorithm runtime for dense graphs The runtime for Dijkstra's algorithm implemented with a priority queue on a sparse graph is $O((E+V)\log V)$. For a dense graph such as a complete graph, there can be $V(V-1)/2$ edges.

Since $E \sim V^2$, is the runtime $O((V+V^2)\log V)$?

The runtime of Dijkstra's algorithm (with Fibonacci Heaps) is $O(|E|+|V|\log|V|)$, which is different from what you were posting.

If $|E|\in \Theta(|V|^2)$, that is your graph is very dense, then this gives you runtime of $O(|V|^2+|V|\log|V|)=O(|V|^2)$. A better runtime would be "surprising", since you have to look at every edge at least once.

When using binary heaps, you get a runtime of $O((|E|+|V|)\log|V|)$ which for $|E|\in \Theta(|V|^2)$ gives $O(|V|^2\log |V|)$.

You can also get rid of the log factor in dense graphs, and do it in $O(V^2)$.
See here.

They might give you around $V=5000$ nodes but $O(V^2) = O(2.5 \cdot 10^7)$ edges which will give the leading edge over normal $O(E\log V)$ Dijkstra.


Show that problem is PSPACE-complete - path in directed graph I have a following problem:
Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch circuit on this input and get result $0$.

Problem:
Is there exists path from vertex $k$ to vertex $l$ ?

I can reduce arbitrary problem from $PSPACE$ to above problem. The only thing that I can't do is showing that problem given in exercies belongs to PSPACE.

Tell me please, if my reasoning is correct (it seems to be too simple):
We know that $PSPACE = NPSPACE$. So we can give non-determinitic algorithm. Algorithm can guess sequentially verticles and check (using circuit) if there exists path).
I can say more, let algorithm guess ansewr (0 or 1).

Can you help me ?

Given $k$ and $l$ you can check if there is a path between these nodes using DFS. DFS requires polynomial space and time. So,  that problem is in PSPACE.

Update: I'd be glad to take into account the downvoter's opinion and improve the answer.


What is most efficient for GCD? I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers.
But in practice you can code this algorithm in various ways. (In my case, I decided to use Java, but C/C++ may be another option).

I need to use the most efficient code possible in my program.

In recursive mode, you can write:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

And in iterative mode, it looks like this:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

There is also the Binary algorithm for the GCD, which may be coded simply like this:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}

Your two algorithms are equivalent (at least for positive integers, what happens with negative integers in the imperative version depends on Java's semantics for % which I don't know by heart). In the recursive version, let $a_i$ and $b_i$ be the argument of the $i$th recursive call:
$$\begin{gather*}
  a_{i+1} = b_i \\
  b_{i+1} = a_i \mathbin{\mathrm{mod}} b_i \\
\end{gather*}$$

In the imperative version, let $a'_i$ and $b'_i$ be the values of the variables a and b at the beginning of the $i$th iteration of the loop.
$$\begin{gather*}
  a'_{i+1} = b'_i \\
  b'_{i+1} = a'_i \mathbin{\mathrm{mod}} b'_i \\
\end{gather*}$$

Notice a resemblance? Your imperative version and your recursive version are calculating exactly the same values. Furthermore, they both end at the same time, when $a_i=0$ (resp. $a'_i=0$), so they perform the same number of iterations. So algorithmically speaking, there is no difference between the two. Any difference will be a matter of implementation, highly dependent on the compiler, the hardware it runs on, and quite possibly the operating system and what other programs are running concurrently.

The recursive version makes only tail recursive calls. Most compilers for imperative languages do not optimize these, and so it is likely that the code they generate will waste a little time and memory constructing a stack frame at each iteration. With a compiler that optimizes tail calls (compilers for functional languages almost always do), the generated machine code may well be the same for both (assuming you harmonize those calls to abs).

For small numbers, % is quite an expensive operation, perhaps
the simpler recursive

GCD[a,b] := Which[
   a==b , Return[a],
   b > a, Return[ GCD[a, b-a]],
   a > b, Return[ GCD[b, a-b]]
];

is quicker? (Sorry, Mathematica code and not C++)


Is there a system behind the magic of algorithm analysis? There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis).  Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made.

On the other hand, the answers to another general question explain the larger picture (in particular regarding asymptotic analysis) with some examples, but not how to get your hands dirty.

Is there a structured, general method for analysing the cost of algorithms?  The cost might be the running time (time complexity), or some other measure of cost, such as the number of comparisons executed, the space complexity, or something else.

This is supposed to become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

Translating Code to Mathematics

Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements, memory accesses, cycles some abstract machine needs, and so on.

Example: Comparisons in Bubblesort

Consider this algorithm that sorts a given array A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Let's say we want to perform the usual sorting algorithm analysis, that is count the number of element comparisons (line 5). We note immediately that this quantity does not depend on the content of array A, only on its length $n$. So we can translate the (nested) for-loops quite literally into (nested) sums; the loop variable becomes the summation variable and the range carries over. We get:

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$,

where $1$ is the cost for each execution of line 5 (which we count).

Example: Swaps in Bubblesort

I'll denote by $P_{i,j}$ the subprogram that consists of lines i to j and by $C_{i,j}$ the costs for executing this subprogram (once).

Now let's say we want to count swaps, that is how often $P_{6,8}$ is executed. This is a "basic block", that is a subprogram that is always executed atomically and has some constant cost (here, $1$). Contracting such blocks is one useful simplification that we often apply without thinking or talking about it.

With a similar translation as above we come to the following formula:

$\qquad\displaystyle C_{\text{swaps}}(A) =  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$.

$A^{(i,j)}$ denotes the array's state before the $(i,j)$-th iteration of $P_{5,9}$.

Note that I use $A$ instead of $n$ as parameter; we'll soon see why. I don't add $i$ and $j$ as parameters of $C_{5,9}$ since the costs do not depend on them here (in the uniform cost model, that is); in general, they just might.

Clearly, the costs of $P_{5,9}$ depend on the content of $A$ (the values A[j] and A[j+1], specifically) so we have to account for that. Now we face a challenge: how do we "unwrap" $C_{5,9}$? Well, we can make the dependency on the content of $A$ explicit:

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) +
    \begin{cases}
        1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]}  \\
        0 &, \text{else}
    \end{cases}$.

For any given input array, these costs are well-defined, but we want a more general statement; we need to make stronger assumptions. Let us investigate three typical cases.

The worst case

Just from looking at the sum and noting that $C_{5,9}(A^{(i,j)}) \in \{0,1\}$, we can find a trivial upper bound for cost:

$\qquad\displaystyle C_{\text{swaps}}(A) \leq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1
    = \frac{n(n-1)}{2} = \binom{n}{2}$.

But can this happen, i.e. is there an $A$ for this upper bound is attained? As it turns out, yes: if we input an inversely sorted array of pairwise distinct elements, every iteration must perform a swap¹. Therefore, we have derived the exact worst-case number of swaps of Bubblesort.
The best case

Conversely, there is a trivial lower bound:

$\qquad\displaystyle C_{\text{swaps}}(A) \geq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0
    = 0$.

This can also happen: on an array that is already sorted, Bubblesort does not execute a single swap.
The average case

Worst and best case open quite a gap. But what is the typical number of swaps? In order to answer this question, we need to define what "typical" means. In theory, we have no reason to prefer one input over another and so we usually assume a uniform distribution over all possible inputs, that is every input is equally likely. We restrict ourselves to arrays with pairwise distinct elements and thus assume the random permutation model.

Then, we can rewrite our costs like this²:

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

Now we have to go beyond simple manipulation of sums. By looking at the algorithm, we note that every swap removes exactly one inversion in $A$ (we only ever swap neighbours³). That is, the number of swaps performed on $A$ is exactly the number of inversions $\operatorname{inv}(A)$ of $A$. Thus, we can replace the inner two sums and get

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$.

Lucky for us, the average number of inversions has been determined to be

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

which is our final result. Note that this is exactly half the worst-case cost.

Note that the algorithm was carefully formulated so that "the last" iteration with i = n-1 of the outer loop that never does anything is not executed.
"$\mathbb{E}$" is mathematical notation for "expected value", which here is just the average.
We learn along the way that no algorithm that only swaps neighbouring elements can be asymptotically faster than Bubblesort (even on average) -- the number of inversions is a lower bound for all such algorithms. This applies to e.g. Insertion Sort and Selection Sort.

The General Method

We have seen in the example that we have to translate control structure into mathematics; I will present a typical ensemble of translation rules. We have also seen that the cost of any given subprogram may depend on the current state, that is (roughly) the current values of variables. Since the algorithm (usually) modifies the state, the general method is slightly cumbersome to notate. If you start feeling confused, I suggest you go back to the example or make up your own.

We denote with $\psi$ the current state (imagine it as a set of variable assignments). When we execute a program P starting in state $\psi$, we end up in state $\psi / \mathtt{P}$ (provided P terminates).

Individual statements

Given just a single statement S;, you assign it costs $C_S(\psi)$. This will typically be a constant function.
Expressions

If you have an expression E of the form E1 ∘ E2 (say, an arithmetic expression where ∘ may be addition or multiplication, you add up costs recursively:

$\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$.

Note that

the operation cost $c_{\circ}$ may not be constant but depend on the values of $E_1$ and $E_2$ and
evaluation of expressions may change the state in many languages,

so you may have to be flexible with this rule.
Sequence

Given a program P as sequence of programs Q;R, you add the costs to

$\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$.
Conditionals

Given a program P of the form if A then Q else R end, the costs depend on the state:

$\qquad\displaystyle C_P(\psi) = C_A(\psi) +
    \begin{cases}
        C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\
        C_R(\psi/\mathtt{A}) &, \text{else}
    \end{cases}$

In general, evaluating A may very well change the state, hence the update for the costs of the individual branches.
For-Loops

Given a program P of the form for x = [x1, ..., xk] do Q end, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

where $\psi_i$ is the state before processing Q for value xi, i.e. after the iteration with x being set tox1, ..., xi-1.

Note the extra constants for loop maintenance; the loop variable has to be created ($c_{\text{init_for}}$) and assigned its values ($c_{\text{step_for}}$). This is relevant since

computing the next xi may be costly and
a for-loop with empty body (e.g. after simplifying in a best-case setting with a specific cost) does not have zero cost if it performs iterations.

While-Loops

Given a program P of the form while A do Q end, assign costs

$\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) +
    \begin{cases}
        0 &, \mathtt{A} \text{ evaluates to false under } \psi \\
        C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else}
    \end{cases}$

By inspecting the algorithm, this recurrence can often be represented nicely as a sum similar to the one for for-loops.

Example: Consider this short algorithm:

while x > 0 do    1
  i += 1          2
  x = x/2         3
end               4

By applying the rule, we get

$\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< +
    \begin{cases}
        0 &, x_0 \leq 0 \\
        c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else}
    \end{cases}$

with some constant costs $c_{\dots}$ for the individual statements. We assume implicitly that these do not depend on state (the values of i and x); this may or may not be true in "reality": think of overflows!

Now we have to solve this recurrence for $C_{1,4}$. We note that neither the number of iterations not the cost of the loop body depend on the value of i, so we can drop it. We are left with this recurrence:

$\qquad\displaystyle C_{1,4}(x) =
    \begin{cases}
        c_> &, x \leq 0 \\
        c_> +  c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else}
    \end{cases}$

This solves with elementary means to

$\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> +  c_{+=} + c_/) + c_>$,

reintroducing the full state symbolically; if $\psi = \{ \dots, x := 5, \dots\}$, then $\psi(x) = 5$.
Procedure Calls

Given a program P of the form M(x) for some parameter(s) x where M is a procedure with (named) parameter p, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$.

Note again the extra constant $c_{\text{call}}$ (which might in fact depend on $\psi$!). Procedure calls are expensive due to how they are implemented on real machines, and sometimes even dominate runtime (e.g. evaluating the Fibonacci number recurrence naively).

I gloss over some semantic issues you might have with the state here. You will want to distinguish global state and such local to procedure calls. Let's just assume we pass only global state here and M gets a new local state, initialized by setting the value ofp to x. Furthermore, x may be an expression which we (usually) assume to be evaluated before passing it.

Example: Consider the procedure

fac(n) do
  if ( n <= 1 ) do         1
    return 1               2
  else                     3
    return n * fac(n-1)    4
  end                      5
end

As per the rule(s), we get:

$\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\})
  &= C_{1,5}(\{n := n_0\}) \\
  &= c_{\leq} +
    \begin{cases}
      C_2(\{n := n_0 \}) &, n_0 \leq 1 \\
      C_4(\{n := n_0 \}) &, \text{ else}
    \end{cases} \\
  &= c_{\leq} +
    \begin{cases}
      c_{\text{return}} &, n_0 \leq 1 \\
      c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\})
       &, \text{ else}
    \end{cases}
\end{align*}$

Note that we disregard global state, as fac clearly does not access any. This particular recurrence is easy to solve to

$\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}})
                                        + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

We have covered the language features you will encounter in typical pseudo code. Beware hidden costs when analysing high-level pseudo code; if in doubt, unfold. The notation may seem cumbersome and is certainly a matter of taste; the concepts listed can not be ignored, though. However, with some experience you will be able to see right away which parts of the state are relevant for which cost measure, for instance "problem size" or "number of vertices". The rest can be dropped -- this simplifies things significantly!

If you think now that this is far too complicated, be advised: it is! Deriving exact costs of algorithms in any model that is so close to real machines as to enable runtime predictions (even relative ones) is a tough endeavour. And that's not even considering caching and other nasty effects on real machines.

Therefore, algorithm analysis is often simplified to the point of being mathematically tractable. For instance, if you don't need exact costs, you can over- or underestimate at any point (for upper resp. lower bounds): reduce the set of constants, get rid of conditionals, simplify sums, and so on.

A note on asymptotic cost

What you will usually find in literature and on the webs is the "Big-Oh analysis". The proper term is asymptotic analysis which means that instead of deriving exact costs as we did in the examples, you only give costs up to a constant factor and in the limit (roughly speaking, "for big $n$").

This is (often) fair since abstract statements have some (generally unknown) costs in reality, depending on machine, operating system and other factors, and short runtimes may be dominated by the operating system setting up the process in the first place and whatnot. So you get some perturbation, anyway.

Here is how asymptotic analysis relates to this approach.

Identify dominant operations (that induce costs), that is operations that occur most often (up to constant factors). In the Bubblesort example, one possible choice is the comparison in line 5.

Alternatively, bound all constants for elementary operations by their maximum (from above) resp. their minimum (from below) and perform the usual analysis.
Perform the analysis using execution counts of this operation as cost.
When simplifying, allow estimations. Take care to only allow estimations from above if your goal is an upper bound ($O$) resp. from below if you want lower bounds ($\Omega$).

Make sure you understand the meaning of Landau symbols. Remember that such bounds exist for all three cases; using $O$ does not imply a worst-case analysis.

Further reading

There are many more challenges and tricks in algorithm analysis. Here is some recommended reading.

How to come up with the runtime of algorithms?
How to describe algorithms, prove and analyse them?
Why use comparisons instead of runtime for comparing two algorithms?
How can we assume that basic operations on numbers take constant time?
What constitutes one unit of time in runtime analysis?
Solving or approximating recurrence relations for sequences of numbers
Basics of Amortised Analysis

There are many questions tagged algorithm-analysis around that use techniques similar to this.

Algorithm analysis, like theorem proving, is largely an art (e.g. there are simple programs (like Collatz problem) that we do not know how to analyze).  We can convert an algorithm complexity problem to a mathematical one, as answered comprehensively by Raphael, but then in order to express a bound on the cost of an algorithm in terms of known functions, we're left to:

Use techniques we know from existing analyses, such as finding bounds based on recurrences we understand or sum/integrals we can compute.
Change the algorithm to something that we know how to analyze.
Come up with a completely new approach.


Is computation independent of hardware? We use electronics to build computers and do computation. Is computation independent of the hardware we use? Would it be possible to do whatever a computer does with pen and paper? If computation is not dependent of how we make our computers, then does the same principle which apply to a computer apply to how brain works?
I want to know if computation is an abstract object which then is realized as computers. In other words, if we visit some alien civilization we expect that our mathematicians and physicists understand the alien physics and math. Is it the same as with the notion or concept of computation?
It seems that in order to consider computation first we need consider a realization of a machine or a model. For example according to the first two lines of this question there are Turing machine, circuits and lambda calculation. How do we know that there is not another way of computation? For example, the way the brain works and does computation might not be describable by the computation which we consider in Turing machine.

To put it another way, are there axioms which we build a theory of computation based on them? like the way we build Euclidean geometry.

To answer the title question, yes, computation is independent of hardware. Computation is defined by the transformation of information, not by how it's embedded in the real world. This is easy to see: all the computation models have a mathematical formulation, and you can write mathematics as symbols on paper. In fact, many models of computation, such as the lambda calculus (1936) and Turing machines (1936) were invented before there were general-purpose computing machines (there were numeric calculators and data sorters, but programmable machines didn't exist until the 1940s).

It is possible to model today's computers by mathematical tools. They're just finite-state machines, after all. There are a lot of states, so a complete pen-and-paper representation is not feasible, but if you only model the part that you're interested in, that can be within reach.

As to whether there is only a single notion of computation, we don't know. We think so: that's the Church-Turing thesis. We think so because we've invented a lot of models of computation, and they all turned out to be equivalent. Some of them are easier to work with than others, or more directly applicable to certain problems, or are a closer match for certain computing hardware (e.g. in terms of performance or locality). But they can express the same computations.

Are Turing machines (or any of the equivalent concepts) the last word on the topic? We don't know. We certainly have weaker models of computation, but we think of them as restricted computation. And we have stronger models of computation, but we think of them as “magic“ — we can reason about them, but we have no idea how they could be implemented.

Is the brain a Turing machine? That's a question about the brain, and we don't know. We know that it's at least as powerful as a Turing machine, since it can simulate one. We are very far from being able to accurately simulate a brain with a Turing machine, but we don't know whether that's a matter of scale (a brain has tens of millions of neurons — a PC doesn't have enough memory to even store all the connexions). We do tend to think of brains as being more powerful than computers — when a problem is undecidable (in the Turing computation sense), we offer to solve it by thinking, but that doesn't answer the question. When we solve a problem by thinking, the solution is expressible in Turing machine terms. The problem solving method, however, may or may not be more powerful than Turing machines.

Would aliens have the same notion of computations? We don't know. We think so — mathematics seems universal to us — but that's a question about aliens, and since we don't know anything about aliens except what your imagination tells us, we can't answer it.

in fact,no have the thing to calling the computation.it's just the transformation of energy to some phenomena.but in my opinion,things look like don't depend on the cause or consequence,it's random.Because in the quantum scale,we have no intractable or get out of zeno paradox in the transfer the energy.so they would been in disjointed.so it's no difference if say the event is random,so does computing.


Regular language not accepted by DFA having at most three states Describe a regular language that cannot be accepted by any DFA that has only three states.

I'm not really sure where to start on this and was wondering if someone could give me some tips or advice. I understand that the pumping lemma can be used to prove a language is not regular, but in this case, it should be a regular language. If anyone has any thoughts it would be appreciated.

The pumping lemma can be stated to take into account the number of states in the DFA. Every language $L$ accepted by a DFA with $p$ states satisfies the following pumping lemma:

  Each word $w$ of length at least $p$ can be broken up as $w=xyz$, where $|xy| \leq p$ and $|y| \geq 1$, such that $xy^iz \in L$ for all $i \geq 0$.

You can use this characterization to prove that the language $\{0^p\}$ requires $p+1$ states.

Another method is to use the Myhill--Nerode theorem. Two words $x,y$ are inequivalent (with respect to some language $L$) if for some word $z$, either $xz \in L$ and $yz \notin L$ or the other way around. The Myhill--Nerode theorem states that if there are $p$ pairwise inequivalent words, then every DFA for $L$ has at least $p$ states. For the example $L = \{0^p\}$, you can find $p+1$ pairwise inequivalent words, namely $\epsilon,0,\ldots,0^p$.

another idea, diagonalization! enumerate all 3-or-fewer-state DFAs, take the union of all of them, and then take the complement. this is a DFA by regular language operations closure. this could be constructed via an algorithm, but the question only asks for a description.


Proof that dead code cannot be detected by compilers I'm planning to teach a winter course on a varying number of topics, one of which is going to be compilers. Now, I came across this problem while thinking of assignments to give throughout the quarter, but it has me stumped so I might use it as an example instead.

public class DeadCode {
  public static void main(String[] args) {
     return;
     System.out.println("This line won't print.");
  }
}

In the program above, it's obvious that the print statement will never execute because of the return. Compilers sometimes give warnings or errors about dead code. For example, the above code will not compile in Java. The javac compiler, however, will not detect all instances of dead code in every program. How would I prove that no compiler can do so?

It all comes from undecidability of the halting problem. Suppose we have a "perfect" dead code function, some Turing Machine M, and some input string x, and a procedure that looks something like this:

Run M on input x;
print "Finished running input";

If M runs forever, then we delete the print statement, since we will never reach it. If M doesn't run forever, then we need to keep the print statement. Thus, if we have a dead-code remover, it also lets us solve the Halting Problem, so we know there can be no such dead-code remover.

The way we get around this is by "conservative approximation." So, in my Turing Machine example above, we can assume that running M on x might finish, so we play it safe and don't remove the print statement. In your example, we know that no matter which functions do or don't halt, that there's no way we will reach that print statement.

Usually, this is done by constructing a "control-flow graph". We make simplifying assumptions, such as "the end of a while loop is connected to the beginning and the statement after", even if it runs forever or runs only once and doesn't visit both. Similarly, we assume that an if-statement can reach all of its branches, even if in reality some are never used. These kinds of simplifications allow us to remove "obviously dead code" like the example you give, while remaining decidable.

To clarify a few confusions from the comments:

  Nitpick: for fixed M, this is always decidable. M has to be the input

As Raphael says, in my example, we consider the Turing Machine as an input. The idea is that, if we had a perfect DCE algorithm, we would be able to construct the code snippet I give for any Turing Machine, and having a DCE would solve the halting problem.

  not convinced. return as a blunt statement in a no-branch straight forward execution is not hard to decide. (and my compiler tells me it is capable of figuring this out)

For the issue njzk2 raises: you are absolutely right, in this case you can determine that there is no way a statement after the return can be reached. This is because it's simple enough that we can describe its unreachability using control-flow graph constraints (i.e. there are no outgoing edges out of a return statement). But there is no perfect dead code eliminator, which eliminates all unused code.

  I don't take input-dependent proof for a proof. If there exists such kind of user input that can allow the code to be finite, it's correct for the compiler to assume that following branch is not dead. I can't see what are all these upvotes for, it's both obvious (eg. endless stdin) and wrong.

For TomášZato: it's not really an input dependent proof. Rather, interpret it as a "forall". It works as follows: assume we have a perfect DCE algorithm. If you give me an arbitrary Turing Machine M and input x, I can use my DCE algorithm to determine whether M halts, by constructing the code snippet above and seeing if the print-statement is removed. This technique, of leaving a parameter arbitrary to prove a forall-statement, is common in math and logic.

I don't fully understand TomášZato's point about code being finite. Surely the code is finite, but a perfect DCE algorithm must apply to all code, which is an infinte set. Likewise, while the code-itself is finite, the potential sets of input are infinte, as is the potential running-time of the code.

As for considering the final branch not-dead: it is safe in terms of the "conservative approximation" I talk about, but it's not enough to detect all instances of dead code as the OP asks for.

Consider code like this:

while (true)
  print "Hello"
print "goodbye"

Clearly we can remove print "goodbye" without changing the behavior of the program. Thus, it is dead code. But if there's a different function call instead of (true) in the while condition, then we don't know if we can remove it or not, leading to the undecidability.

Note that I am not coming up with this on my own. It is a well known result in the theory of compilers. It's discussed in The Tiger Book. (You might be able to see where they talk about in in Google books.

I think in a computing course, the notion of dead code is interesting in the context of understanding the difference between compile time and run time!

A compiler can determine when you've got code that can in no compile-time scenario ever be traversed, but it cannot do so for runtime. a simple while-loop with user input for the loop-break test shows that.

If a compiler could actually determine runtime dead code (i.e. discern Turing complete) then there's an argument that the code never needs be run, because the job's already done!

If nothing else, the existence of code that passes compile-time dead code checks illustrates the need for pragmatic bounds-checking on inputs and general coding hygiene (in the real world of real projects.)


What does apostrophe-like symbol in the superscript mean? It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written.

That apostrophe-type symbol in the sequence notation - what is that?

That's a prime.

  In mathematics, statistics, and science, the prime is generally used to generate more variable names for things which are similar, without resorting to subscripts – $x'$ generally means something related to or derived from $x$.

As Mowji already mentioned, it means a one thing is derived from another.

Think of it as what it come from, the prime used in mathematics, for the a kind of function, named derivative of a function, as in: $f(x) = 2 \times x, f'(x)$ = 2 or another example $f(x) = sin(x), f'(x) = cos(x)$.

The keyword to have in mind sawing this sign is, “derivative” and/or “derived”.


Compiler instructions to sync core caches: are they really needed? I have read reviews of this book, and quote the following from one of the reviews (emphasis mine):

  Other than straining your eyes with old-styled C++, you can read such
  misconceptions in the book like "Since Boolean values are generally
  atomic, setting and checking can be done simultaneously without risk
  or requiring a mutex." Which ignores the facts that, the compiler
  doesn't necessarily have to generate instructions to resync the value
  in register with the one in memory. And even if it does, the hardware
  doesn't have to resync the cache lines.

I have also followed all of the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube) and learned about cache coherency protocols.

From what I have learned, modern processors will use the write-invalidate protocol; when one core writes to a block, any other cores that share this same block will learn of the change via an invalidation message sent on the bus so they will have to go and get the new value from memory instead of using their cached copy.

With this in mind, what is the author of this comment talking about?  It seems the coherency protocol is doing everything for me, hence there is no need to use synchronisation?  Are they wrong or am I missing something?

PS Yes I know I mention C++ but I feel this is more hardware related hence me asking it here.

PPS If I've missed something, please post a link to the information before just downvoting; a downvote without explanation is useless.

Update

If a boolean b was being used in two threads, each one on a different core, what would making the variable atomic/using a sync variable do regarding the cache coherency that doesn't happen with a none-atomic var/no use of a sync variable?  (I think this is the problem in my understanding - I am believing that the cache coherency protocol fires off "for free" (is this right?); or do I need to use some special instruction to "start it off" (that is, trigger the sending of the invalidation message on the bus) for want of a better phrase?)

Update 2

Write Invalidate Snooping Coherence - Georgia Tech - HPCA: Part 5 talks about how the caches of different cores operating on the same block are synchronized.

My confusion stems from the fact that the comment I quote seems to state that boolean values are not guaranteed to be synchronized between caches on different cores, and that some sort of atomic operation or synchronization primitive (eg mutex) is needed to do this.  The video I link to however mentions nothing of the sort; it suggests (to me at least) that the caches are updated automatically by virtue of the coherency protocol, not by any special instructions (such as those generated for atomic operations or synchronization primitives) in the code.  This is what I am asking for clarification on.

This is very simple actually, and has nothing to do with hardware whatsoever. If you have a variable

static bool b;

and some code

b = true;
dosomething();
b = false;
dosomethingelse();
b = true;

If the compiler can figure out that dosomething() and dosomethingelse() don't read or write b, then the compiler is not required to generate code for the assignments to b, except the last one.

With the book's subtitle "Write robust, concurrent, and parallel applications" this is quite worrying.

After an extended chat with @Bulat here we can boil this down to the fact that, regarding the cache coherency protocol:

  ...your video says how it CAN be done, and actually done in many systems,
  but not not all

and that generally atomic variables/sync primitives should be used when threading is involved.  With this point in mind, using these must force the coherency protocol in my video to sync the caches.


What does it mean to multiply or divide polynomials? What does it mean to multiply or divide polynomials?

I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical representation/ interpretation.

I have always pondered what did it mean when someone multiplies a line with a curve to get another hyperplane of a bigger dimension.

I know the formulae and properties of polynomial multiplication & division, I am specifically looking for a graphical/algebraic interpretation of it.

I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. I will go off on the assumption that overly abstract "graphical" representations do not count.

Graphical Plots: In abstract algebra, the polynomials that work with the $y$ vs. $x$ type of graphing are in the ring of polynomials over $\mathbb{R}$, otherwise known as $\mathbb{R}[x]$. Evaluating any of these for an $x \in \mathbb{R}$ gives you a continuous function that you can plot. This works for $\mathbb{R}[X]$'s extensions, too ($\mathbb{C}[X]$).

Graphs: Cryptography and coding theory involve a massive number of structures, each of which can be represented as a graph. A notable set of examples are graphs depicting algebras over structures of finite size. Rings of polynomials are not one of them, since they contain, at minimum, a countable number of elements. Some intuition can be gathered from how these graphs change as you vary/limit the degree of your polynomial (more on this later). Though I imagine that this is not the kind of representation that you had hoped.

For other graphical/geometrical/topological aspects of crypto and coding theory, you might want to look into things like vector spaces, sphere packing, and lattices.

Polynomials Over Finite Fields:

Even so, it is important to realize that the inclusion of rings of polynomials in cryptography and coding theory are over finite fields. That is, they usually only consider $\mathbb{F}_q[X]$, which is the finite field with $q$ elements. An easily recognized one would be $\mathbb{F}_2^k = \{0,1\}^k$ (your typical algebra over binary strings).

A slight extension of this idea, rings of multivariate polynomials, are also useful. They are typically represented by $\mathbb{F}[X_1,X_2,...]$ where $\mathbb{F}$ is a field. An algebra of multivariate polynomial over $\mathbb{F}_2$ is equivalent to a boolean algebra. A boolean formula, $\varphi(x_1,x_2,...,x_n)$, would be equivalent to evaluating a degree $n$ multivariate polynomial over $\mathbb{F}_2$. The intuition behind this is to see that $+$ and $\times$ act like XOR and AND logic gates on your binary inputs, $x_1,x_2,...,x_n \in \{0,1\}$.

Beyond drawing something fundamentally equivalent to circuit diagrams, I do not see a fruitful way to represent this graphically. Though, this did not stop these guys from trying (I still think it is the same): http://polybori.sourceforge.net/zdd.html

There are obviously way more concepts from abstract algebra that are involved in these areas (e.g. $\mathbb{Z}_p$, the ring integers mod $p$). Some may even have graphical representations that make the idea more intuitive. Though these fall outside the scope of the question, which is specific to algebras over polynomials.

You should not try to visualize this. Algebraic properties can span to multi dimensions.. try to ask what would an algebraic interpretation of it? Use linear algebra to reason about it.


Convert DFA to Regular Expression In this old exam-task I don't understand all the steps to convert the DFA below to a Regular Expression. The $q_2$ state is eliminated first.
The provided solution to eliminate $q_2$ is:

If we first eliminate $q_2$ we obtain an intermediate automata with $3$ states
$(q_0$,$q_1,q_3)$ such that:

  We go from $q_0$ to $q_1$ with RE $a+ba$
  We go from $q_0$ to $q_3$ with RE $bb$
  We go from $q_1$ to $q_1$ with RE $ba$
  We go from $q_1$ to $q_3$ with RE $a+bb$

I don't understand nr2. $q_3$ can also be reached using RE $aa$. Why is this left out?

:

:

The conversion in each step forms REs that describe

The previous direct edge from one state to another and
the path(s) that use(s) only the removed state as an intermediate state.

In your example, the path for $aa$ goes through $q_1$, which is not removed in this step. Thus it is not added to the RE.

it is not left out , see q3 cn still be reachable using "aa" from intial state q1 , just tk 2nd term from unioned terms and then pick 'a' from (a+ba) , tk (ba)* as NULL String and then take 2nd 'a' from (a+bb) : so by concatenation we got "aa" and we reached final state q3


Can we remove duplicates faster than we can sort? The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers):

  Given a sequence $S_\text{in}$ of $n$ integers, produce a sequence $S_\text{out}$ of elements such that any element in $S_\text{in}$ also appears in $S_\text{out}$, and all elements in $S_\text{out}$ are distinct.

Ignoring some details regarding the elements' size in bits, this can be done by sorting in $O(n \log n)$ time; or by hashing in expected time $O(n)$.

Given that we don't require $S_\text{out}$ to be sorted - is it possible to do better than sorting in the worst case?

Notes:

Some dependence on the output size (let's call it $m$) rather than $n$ is an improvement, but I'm mostly interested in getting closer to linearity in $n$.
The details I've ignored may not be so insignificant.
Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.
We cannot make any assumptions regarding the input distribution.

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (rather than just $x_i - x_j$).

The element distinctness problem asks whether all elements in the input are distinct. This is clearly easier than your problem, since you can just compare the sizes of the input and output arrays. Hence in these computation models, you cannot do asymptotically better than $n\log n$.

If every element of the array ($a$) is in the range of $0$ to $k$, you can have $\theta(n)$ runtime when $k=O(n)$. All you have to do is to maintain an array ($c$) of $k$ elements initialized to $0$ and set $c[a[i]] = 1$ whenever $a[i]$ is encountered to be 0. At the same time you should write the corresponding element ($a[i]$) in an array $b$ only if the $c[a[i]] =0$.


How can I prove that a build max heap's amortized cost is $O(n)$? Suppose a build max-heap operation runs bubble down over a heap. How does its amortized cost equal $O(n)$?

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair.  We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.

Algorithm of Build Heap:

BUILD-HEAP(A)
 heapsize := size(A);
 for i := floor(heapsize/2) down to 1
 do HEAPIFY(A, i);
 end for
END

A quick look over the above algorithm suggests that the running time is O(nlogn), since each call to Heapify costs O(logn) and Build-Heap makes O(n) such calls. This upper bound, though correct, is not asymptotically tight.

As we know that heapify is called for all internal nodes, and heapify takes O(logn) time, but this is not exactly the case. In reality, the O(logn) time is taken by root only, as root is at the height logn, time varies for the internal nodes with different height. For example, for the internal nodes at the second last level, heapify will take O(h) time for all the nodes at that level where h=1, for the internal nodes at the third last level, heapify will take O(h) time for all the nodes at that level where h=2, therefore depending height time to heapify is changing. So considering this, we can derive a tighter upper bound than O(nLogn).

For finding the Time Complexity of building a heap, we must know the number of nodes having height h. For this we use the fact that, A heap of size n has at most ceil( n / 2^(h+1) ) Now to derive the time complexity, we express the total cost of Build-Heap as-

T(n)= ceil( n / 2^(h+1 )) * O(h)
 = n/2 * h / (2^h)
 =O( n * h /( 2^h) )

Step 3 uses the properties of the Big-Oh notation to ignore the ceiling function and the constant 2 ( since 2^(h+1) = 2.(2^h) = O(2^h) ), and the upper limit of the summation can be increased to infinity since we are using Big-Oh notation.
Here we will consider that ‘h’( means the height) tends to infinity for the worst case time complexity.

Now, ∑ h / 2^h = (0 / 2^0) + (1 / 2^1) + (2 / 2^2) + (3 / 2^3) + (4 / 2^4) + ……….

= 0/1 + 1/2 + 2/4 + 3/8 + 4/16 + 5/32 + …………. ------------> eqn 1

Now, if we divide the whole equation from 2 we get,

∑ h / 2.(2^h) = 0 / 2.(2^0) + 1 / 2.(2^1) +2 / 2.(2^2) +3 / 2.(2^3) +4 / 2.(2^4) + …….

= 0/2 + 1/4 + 2/8 + 3/16 + 4/32 + 5/64 + ………….. ------------> eqn 2

Now, subtracting (eqn 1 – eqn 2) —->we get,

∑ h / (2^h) - h /( 2.(2^h)) = 1/2+ 1/4 + 1/16 + 1/32 + ……………. + 1/∞

=> ∑ 1/2(h / 2^h) = 1/2 / (1 – 1/2) (using formula for infinite GP, sum = a / (1-r))

=> ∑ h / 2^h = 2

Therefore, T(n) = O( n * h /( 2^h) ) = O(n * 2) = O(n),

So, time complexity of build-heap is O(n).


Book for algorithms beyond Cormen I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations?

NOTE: I asked this on stackoverflow but wasn't all too happy with the answer.

NOTE: Looking at most of the comments I think ideally I would like to find a book that would cover the material of the the 787 course in this course description.

As others have noted, books about (advanced) algorithms are best selected by topic. A good but heavy-weight general reference with rigorous analysis is probably The Art of Computer Programming by Knuth.

As for analysis techniques, you may be interested in An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, and Algorithmic Combinatorics by Flajolet and Sedgewick for more theory in the same direction.

For approaches on tackling hard problems, see Algorithmics for Hard Problems by Hromkovič.

The computer algorithms are very complex and hard to understand topic, so there is no best book, i.e. just one book which will explain you everything. You need to read couple of them to get hold of this topic.

here are my 2 cents based upon my 10 years of programming and attending numerous interviews:

Algorithm Design Manual  by Steven S. Skiena
Algorithms (http://algs4.cs.princeton.edu/home/) by Sedgwick
Introduction to Algorithms  By Thomas Cormen
Algorithms for Interviews  by Adnan Aziz
Python Algorithms: Mastering Basic Algorithms in the Python Language
Algorithms Unlocked by Thomas Cormen

Reference:

Top 10 Algorithm books Every Programmer Should Read


Human computing power: Can humans decide the halting problem on Turing Machines? We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines or general purpose computers?

Note: Obviously, in the strictest sense, you can always say no, because there are Turing Machines so large they couldn't even be read in the life span of a single human. But this is a nonsensical restriction that doesn't contribute to the actual question. So to make things even, we'd have to assume humans with an arbitrary life span.

So we could ask: Given a Turing Machine T represented in any suitable fashion, an arbitrarily long-lived human H and an arbitrary amount of buffer (i.e. paper + pens), can H decide whether T halts on the empty word?

Corollary: If the answer is yes, wouldn't this also settle if any computer has a chance of passing the turing-test?

It is very hard to define a human mind with a such mathematical rigor as it is possible to define a Turing machine. We still do not have a working model of a mouse brain however we have the hardware capable of simulating it. A mouse has around 4 million neurons in the cerebral cortex. A human being has 80-120 billion neurons (19-23 billion neocortical). Thus, you can imagine how much more research will need to be conducted in order to get a working model of a human mind.

You could argue that we only need to do top-down approach and do not need to understand individual workings of every neuron. In that case you might study some non-monotonic logic, abductive reasoning, decision theory, etc. When the new theories come, more exceptions and paradoxes occur. And it seems we are nowhere close to a working model of a human mind.

After taking propositional and then predicate calculus  I asked my logic professor:
"Is there any logic that can define the whole set of human language?"
He said:
"How would you define the following?
To see a World in a grain of sand
And a Heaven in a wild flower,
Hold Infinity in the palm of your hand
And Eternity in an hour.
If you can do it, you will become famous."

There have been debates that a human mind might be equivalent to a Turing machine. However, a more interesting result would be for a human mind not to be Turing-equivalent, that it would give a rise to a definition of an algorithm that is not possibly computable by a Turing machine. Then the Church's thesis would not hold and there could possibly be a general algorithm that could solve a halting problem.

Until we understand more, you might find some insights in a branch of philosophy. However, no answer to your question is generally accepted.

http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems#Minds_and_machines
http://en.wikipedia.org/wiki/Mechanism_(philosophy)#G.C3.B6delian_arguments

All human thought conflates single problems into personal experience. We might satisfy ourselves that we have adequately solved a problem sufficiently to halt, but we never know for sure in the algorithmic sense a computer would acquire a solution.
Be still and watch your own mind. 99.9% of the messaging going on in our neural circuitry has nothing to do with a logical representation of the world. Instead, we are dealing with "gut" feelings, sensory data and a flood of memories, associations and attitudes which vary constantly.
That's why we have scientific method.


Why is A implies B true if A is false and B is false? It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday language use.

Let's take two examples:

  If today is Monday then tomorrow is Tuesday.

This is true.

But if we say:

  If the sun is green then the grass is green.

This is also considered true. Why? What is the 'logic' in natural English behind this? It blows my mind.

Humans are bad at logic until they have to employ it to figure out human affairs. Think of "if $A$ then $B$" as a kind of promise: "I promise to you that if you do $A$ then I will do $B$". Such a promise says nothing about what I might do if you fail to do $A$. In fact, I might do $B$ anyhow, and that would not make me a liar.

For instance, suppose your mother tells you:

  If you clean up your room I will make pancakes.

And let us say that you did not clean up your room, but when you walked into the kitchen your mom was making pancakes. Ask yourself, whether this makes your mom a liar. It does not! She would be a liar only if you cleaned the room but she refused to make pancakes. There might be other reasons that she decided to make pancakes (perhaps your sister cleaned up her room). Your mom did not tell you "If you do not clean up the room I will not make pancakes," did she?

So, if I say

  "If the sun is green then the grass is green."

that does not make me a liar. The sun is not green (you did not clean up the room), but the grass turned out to be green anyhow (but your mom made pancakes anyhow).

To put your head in the right place for my answer, I want to mention what I like to call the Flying Monkeys Theorem, or what Wikipedia likes to call the Principle of Explosion, which states:

$$
(p\wedge\neg p) \rightarrow q
$$

Or, in English, this says "given a contradiction, monkeys might fly out of my butt (NSFW audio)", or alternately "from falsehood, anything follows". One way to think about this is that if $2+2=4$ and $2+2=5$ then $4=5$, which means that $0=1$, or it could mean that $16=25$, etc., and you can basically generate any equality you want. This is why there are so many tricks that result in $1=0$ or $1=-1$ by abusing a hidden division by zero, because you are not allowed to divide by zero so you can make anything you want true.

Once we're in this realm where we know $p$ is false, we're no longer in reality. We're in some alternate dimension where the Babel Fish is real, black is white and watch out for that Zebra crossing. So given that we're no longer in reality, of course the statement could be true. Specifically, I can use my false thing that I'm assuming to prove anything I want. So of course $F \rightarrow T$ and $F \rightarrow F$ are both true statements.


Efficiently computing the smallest integer with n divisors In order to tackle this problem I first observed that

$$\phi(p_1^{e_1} \space p_2^{e_2} \cdots \space p_k^{e_k}) = (e_1 + 1)(e_2 + 1)\cdots(e_k +1)$$

Where $\phi(m)$ is the number of (not necessarily prime) divisors of $m$. If $m$ is the smallest integer such that $\phi(m) = n$, then

$$\phi(m) = n$$
$$(e_1 + 1)(e_2 + 1)\cdots(e_k +1) = n$$

Now we must choose $e_i$ such that $\prod_{i} p_i^{e_i}$ is minimal. The choices for $p$ are trivial - they are just the primes in ascending order.

However, my first thought for choosing $e_i$ was incorrect. I thought you could simply factor $n$, sort the factors in descending order and subtract 1. Most of the time this works fine, e.g. the smallest integer with $n = 15$ divisors is:

$$15 = 5 \cdot 3$$
$$15 = (4 + 1)(2 + 1)$$
$$m = 2^4 3^2 = 144$$

But this is incorrect for $n = 16$:

$$16 = 2 \cdot 2\cdot 2 \cdot 2$$
$$16 = (1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^1 3^1 5^1 7^1 = 210$$

Whereas the correct answer is:

$$16 = (3 + 1)(1 + 1)(1 + 1)$$
$$m = 2^3 3^1 5^1 = 120$$

So it's clear sometimes we need to merge factors. In this case because $7^1 > 2^2$. But I don't exactly see a clean and direct merging strategy. For example, one might think we must always merge into the $2$ power, but this is not true:

$$1552 = (96 + 1)(1 + 1)(1 + 1)(1 + 1)(1 + 1)$$
$$m = 2^{96} 3^1 5^1 7^1 11^1 > 2^{96} 3^3 5^1 7^1$$

I can't immediately think of an example, but my instinct says that some greedy approaches can fail if they merge the wrong powers first.

Is there a simple optimal strategy for merging these powers to get the correct answer?

Addendum. A greedy algorithm that checks every possible merge and performs the best one on a merge-by-merge basis, fails on $n = 3072$. The series of one-by-one merges is:

$$2^2 3^1 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1 31^1$$

$$2^3 3^2 5^1 7^1 11^1 13^1 17^1 19^1 23^1 29^1$$

$$2^5 3^3 5^1 7^1 11^1 13^1 17^1 19^1 23^1$$

However the optimal solution is:

$$2^7 3^3 5^2 7^1 11^1 13^1 17^1 19^1$$

Here's a solution, based on my comments above.  I make no claims this is optimal.

The idea is to consider $T(n,m)$, which we defines as "the smallest positive integer with exactly $n$ divisors and $m$ distinct prime factors". We make the easy observations:

\begin{align}
T(n, 1) &= 2^{n-1}\\
T(2^m, m) &= p_1p_2\cdots p_m
\end{align}

And we also have the recurrence:

\begin{equation}
T(n,m) = \min_{d|n} [T\left(\frac{n}{d}, m-1\right)\cdot p_m^{d-1}]
\end{equation}

Finally, the quantity you're looking for is
\begin{equation}
\min_{1\le i\le\lceil\log(n)\rceil} T(n, i)
\end{equation}

To that end, here is some Python code, which agrees with all the numbers you gave above.  Note that it works with the logarithms to keep the numbers smaller: so the actual integer you seek is round(2**smallest(n)).

import functools
import itertools
import math

# All primes less than 100.
PRIMES = [
  2, 3, 5, 7, 11,
  13, 17, 19, 23, 29,
  31, 37, 41, 43, 47,
  53, 59, 61, 67, 71,
  73, 79, 83, 89, 97,
]

LOG_PRIMES = [math.log2(p) for p in PRIMES]

def smallest(n):
  max_factors = math.ceil(math.log2(n))
  min_so_far = float('Infinity')
  factors = factorize(n)
  memo = {}
  for i in range(1, max_factors+1):
    t = T(n,i, factors, memo)
    if 0.0 < t < min_so_far:
      min_so_far = t
  return min_so_far

def T(n, m, factors=None, memo=None):
  if memo is None:
    memo = {}
  if n < 2 or m < 1:
    return 0
  elif m == 1:
    # Everything on the smallest prime.
    return (n-1) * LOG_PRIMES[0]
  elif n < 2**m:
    return 0
  elif n == 2**m:
    # Product of first m primes, in log.
    return sum(LOG_PRIMES[:m])
  elif (n,m) in memo:
    return memo[(n,m)]

  if factors is None:
    factors = factorize(n)
  if len(factors) < m:
    return 0

  smallest = float('Infinity')
  for factor_list in powerset(factors):
    divisor = product(factor_list)
    first = T(divisor, m-1, factor_list, memo)
    # No such product.
    if first < 1.0:
      continue
    second = (n/divisor - 1) * LOG_PRIMES[m-1]
    total = first + second
    if total < smallest:
      smallest = total

  memo[(n,m)] = smallest
  return smallest

def product(nums):
  return functools.reduce(lambda x,y: x*y, nums, 1)

def factorize(n):
  prime_factors = []
  for p in PRIMES:
    while n%p == 0:
      n //= p
      prime_factors.append(p)
    if n == 1:
      break
  return prime_factors

def powerset(lst):
  # No empty set.
  return itertools.chain.from_iterable(itertools.combinations(lst, r)
                                       for r in range(1, len(lst)+1))

Possible candidates for "smallest integer with n divisors" are the integers of the form $2^a·3^b·5^c...$ where a ≥ b ≥ c ... and (a+1)(b+1)(c+1)... = n.

So you need to find all ways to express n as the product of integers ≥ 2 in non-ascending order, and calculate and check the corresponding candidates. For example, when n = 16, 16 = 8·2 = 4·4 = 4·2·2 = 2·2·2·2, so possibilities are $2^7·3$, $2^3·3^3$, $2^3·3·5$, $2·3·5·7$, and the smallest is $2^3·3·5 = 120$.

If n is the product of two primes p·q, p ≥ q, the only candidates are $2^{pq-1}$ and $2^{p-1}·3^{q-1}$, and the latter is always smaller.

You can figure out some condition when there could be a factor $2^{ab-1}$ for example, by checking whether $2^{ab-1} > 2^{a-1}·x^{b-1}$ for some prime x that isn't a factor. In the example n = 16, there is a factor $2^3$ because $2^3 < 2·7$.


Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses? I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning about writing GUI programs, and the graphical library (GTK) relies on things like signals and callbacks, which I have not seen modeled by either Turing Machines or the $\lambda$-Calculus; can either the $\lambda$-Calculus or Turing Machines model things like signals, callbacks, sleeping/waiting, or buses? If so, where can I find some good reference material to learn more? If not, why not? and are there any formalisms which are capable of expressing such things?

Yes, there are natural extensions of the $\lambda$-calculus for handling I/O, parallelism, concurrency, exceptions, timeouts, etc. In general such things are viewed as computational effects and there is a rich theory of $\lambda$-calculus for computational effects. This is what Haskell monads are about -- Haskell is $\lambda$-calculus extended with features that you are asking about.

But let me point out that you mix a bunch of features together which are really of two different kinds:

Interaction with external environment: I/O, communication, timeouts, concurrency, etc.
Programming models: callbacks, semaphores, shared memory, parallelism, etc.

A classical Turing machine does not interact with an external environment, but it can be modified to do so. For instance, an oracle is essentially an input stream. The so-called "type 2 machines" are Turing machines with infinite input and output tapes which correspond to an input and an output channel, etc. I am sure someone invented "real-time Turing machines", but I think such endaveours miss the point of mathematical models of computation. A mathematical model is designed specifically to fit well a chosen set of features that we want to model. Turing machines were invented to explain what "possible to compute" means, not "how to compute". If you want to model I/O and such then there are better mathematical models to stick to ($\pi$-calculus was suggested by someone).

The second set of features you asked about is really a bunch of programming methods. As is well known, any Turing complete computational model can be used to simulate any other such model. For instance, a Turing machine can compute things in parallel through a technique known as dovetailing. I would not be surprised if dovetailing was invented several decades before the first parallel operating sytem came into existence. (In fact, it must be the case that dovetailing appreaded already in Turing's original 1936 paper, can someone confirm this?)

Callbacks are well known to functional programers, as these are just functions (but if you spend your life programming operating systems in C you will think they are special), while threads and coroutines are known as continuations. So some concepts that look fancy from one perspective are basic and straightforward from another. Another that comes to mind is the object-oriented idea of an "iterator" which gets vastly generalized in functional programming.

This question mixes two disparate areas of CS and attempts to use analogies that are relevant in one realm in the other realm (or in English vernacular "mixing apples and oranges"). On one end of the spectrum, Turing machines (TM) are an abstraction to understand computation. On the other end of the spectrum are practical "design patterns" and software architecture concepts such as "signals", "callback functions," "GUI" APIs etc.

A TM can implement any programming design pattern hence the term "Turing complete". However, this would require a TM compiler for a high-level language. Apparently almost nobody has written actual high-level language compilers for TMs. The theoretical crowd would regard it as a waste of time and the practical/pragmatic/applied crowd do also. So the theory guarantees it can be done, but not beyond that.

In at least one item you're missing the nearly obvious: in $\lambda$-calculus a lambda function can also function as a "callback".

Buses are more of an EE concept. Signals, sleep, and wait are modelled with threads, processes, or parallelism.


Formulas vs Circuits In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is $1$. Is it true that for a formula, (given that its fan-out is already $1$, by defintion) the fan-in is also constant?

In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).

So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?

No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large.

If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.

Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.

Fan-in in a circuit tree or a formula (i.e. outdegree $= 1$ as you mention) is limited by the number of input variables. A node or a gate cannot connect to more than the input variables. However, note that often in many constructions, the indegree is limited to 2, and gates are combined using the simple rule $a \wedge b \wedge c$ = $(a \wedge b) \wedge c$, and similarly for all typical or associative gates. In other words, "unlimited" indegree is converted to 2-indegree with a small increase in gates.


How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm? I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond to.

reference: https://en.wikipedia.org/?title=Shor%27s_algorithm

This paper by Pavlidis and Gizopoulos walks through one possible construction of the circuit you're looking for and also provides references to other literature on the subject:

"Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm". Archimedes Pavlidis, Dimitris Gizopoulos.  http://arxiv.org/abs/1207.0511

The algorithm uses the functional superposition s of f. A state with 2q qubits (2q=Q, where Q is the same as in the Wikipedia article):

s(xy) = Q-1/2 where y = f(x), else 0

You can see xy as the concatenation of x and y in binary form. x and y run from 0 to Q-1.

Here is how it can be done with q ancillary qubits (3q qubits total):

Start with 3q qubits in the zero state (1,0,0,...). I'll call the first q qubits x, the second q qubits y and the third q qubits z
Apply the Hadamard transform to x
Follow x to y with CNOT. This yields the state s(xyz) = Q-1/2 where x = y and z = 0, else 0
Apply f'(x,y) = (x,f(x) XOR y) to y and z. f' is invertible and has a unitary matrix. This yields the state s(xyz) = Q-1/2 where x = y and z = f(x), else 0
Apply g(x,y) = (x,x XOR y) to x and y. This yields the state s(xyz) = Q-1/2 where y = 0 and z = f(x), else 0
Swap x and y with swap gates. This yields the state s(xyz) = Q-1/2 where x = 0 and z = f(y), else 0. x is in the zero state (1,0,0,...) and can be separated from yz - which forms the functional superposition of f


Which Type of Grammar is this? I am learning Compiler Design. Can somebody explain what type of Grammar this is? The answer given is $LL(1)$ but there exists a left recursion in the grammar so it cannot be $LL(1)$. I derived the parse table it had conflicts. Am I doing some thing wrong or is the answer given wrong?

My texbook defines:

  For LL(1) Grammar if there is left recursion or left factoring then that grammar is not LL(1) grammar if this applies to this grammar then it is not a LL(1) grammar

$E \to E+T \mid E$

$T \to T$#$F \mid F$

$F \to (E) \mid i$

I also have one more question: "Is there a Grammar which can be LL(1) but not LALR(1)"

There is left recursion in the grammar, so it isn't $LL(1)$.

The set of $LL(1)$ grammars is a proper subset of the $LR(1)$ grammars, see for example this summary, which incidentally also shows that $LL(1)$ isn't a subset of $LR(0)$. The first part is is intuitively easy to see, the $LL(k)$ parser has to decide looking only at the $k$ first symbols; the $LR(k)$ has the whole left hand side (and $k$ extra symbols) at its disposal.

If you want to test the grammer is LL(1).

First if you have left recursion it must be solve it .

Then the new output you want to calculate the first and follow to draw the table .

Then check if you don't have multiple entry in the table so this grammer is LL(1) else is not LL(1).
Note in your grammer may be have error in writting it.
plz check it.

E→E+T∣T

T→T#F∣F

F→(E)∣i


Need help understanding how to find big theta of a snippet of code Say I have a snippet of code:

k = 5
i, j = 0

for i -> n
    if i == k
        for j -> k
            /* do something */
        end for
    k = k * 4/3
    end if
    /* do something */
end for

I can tell that the algorithm is worse than n but can't be worse than n^2. In fact it seems like it would be less than n log (n). Though I admit these are just guesses I'm making. Is there any methodology to figuring out what the big theta is for such algorithms?

In order to estimate the running time of the code it is enough to count the number of times the two "do-somethings" are executed. Call them do-something 1 and do-something 2 (in their order of appearance). Do-something 2 is executed about $n$ times. As for do-something 1:

If $n < 5$, no times.
If $5 \leq n < (4/3)5$, $5$ times.
If $(4/3)5 \leq n < (4/3)^25$, $(4/3)5$ times.
Generally, if $(4/3)^k5 \leq n < (4/3)^{k+1}5$, $(4/3)^k5$ times.

Be creative and estimate the number of times that do-something 1 is executed in terms of $n$. Conclude the running time of the code snippet.

it can't be big theta because it has an escape clause, ie if this then don't do this. generally you would look for a loop through n values to be O(n) and two nested loops to be O(n^2), etc.


Clock synchronization in a network with asymmetric delays Assume a computer has a precise clock which is not initialized. That is, the time on the computer's clock is the real time plus some constant offset. The computer has a network connection and we want to use that connection to determine the constant offset $B$.

The simple method is that the computer sends a query to a time server, noting the local time $B + C_1$. The time server receives the query at a time $T$ and sends a reply containing $T$ back to the client, which receives it at a time $B + C_2$. Then $B + C_1 \le T \le B + C_2$, i.e. $T - C_2 \le B \le T - C_1$.

If the network transmission time and the server processing time are symmetric, then $B = T - \dfrac{C_1 + C_2}{2}$. As far as I know, NTP, the time synchronization protocol used in the wild, operates on this assumption.

How can the precision be improved if the delays are not symmetric? Is there a way to measure this asymmetry in a typical Internet infrastructure?

Inability to measure asymmetry

No, you can't measure the asymmetry. Consider these two communication diagrams, the first with a negative clock offset and equal delays and the second with no clock offset and entirely asymmetric delays (but the same round trip time).

The important thing to notice is that, from the perspective of both the PC and the server, the two interactions are exactly identical. They receive messages at the same time. They send messages at the same time.

You can create more cases by 'grabbing' the PC timeline and 'sliding' it, holding the message send/receive points fixed relative to their respective timelines. The asymmetries you cause are exactly negated by the clock offset. In fact, you can even make messages go BACKWARDS IN TIME one way (as long as the round trip time is still the same) and the server/client STILL can't tell!

Therefore it is impossible to measure latency asymmetries. In the worst case, where you have no information other than that one way latencies are positive and sum to the round trip time, the accuracy of clock synchronization is limited to the round trip time.

Can intermediate infrastructure help?

Whether or not the intermediate infrastructure can help will be heavily dependent upon your theoretical model of the situation.

If the asymmetry is constant and the intermediate infrastructure is the routers on the communication path between you and the server, then no. Even if each router synchronized their clock with the adjacent router, the errors would compound in the same way as if you had synchronized with the server via communication across the routers.

In the real world you can rely on delays being somewhat symmetric for architectural reasons, repeated synchronizations to reduce asymmetry due to queuing delays (etc), and multiple communication paths to reduce other sorts of asymmetry.

If you put your model's assumptions somewhere in between (because it's interesting to explore model space, of course) I expect the result should also be somewhere in between.

Here is an idea that sounds absolutely convincing to me and might therefore be absolutely wrong in a dumb way.

Consider the following scenario. We have two nodes $N_1$ and $N_2$ with clocks $C_1$ and $C_2$, respectively. For sake of simplicity, let us assume that the clocks run with the same speed; we denote their difference by $\delta = C_1 - C_2$ which is constant for our purposes. Let us furthermore assume that transmission delays $d_{1 \to 2}$ and $d_{2 \to 1}$ are constant¹.

Have $N_1$ send a message timestamped with $T_1^m$ to $N_2$ and let $T_2^r$ the current time on $C_2$ upon receiving it (do the same for the other direction). In addition, measure round trip time (on either node) $D$ by sending a message back and forth. Now set up this equation system:

$\qquad\begin{align*}
  T_2^r - T_1^m &= d_{1 \to 2} + \delta \\
  T_1^r - T_2^m &= d_{2 \to 1} - \delta \\
  D &= d_{1 \to 2} + d_{2 \to 1}
\end{align*}$

As this system consists of three equations, has three unknowns and we know there is a solution, it can be solved. Of course the nodes have to exchange their measurements so that they can both compute the same value for $\delta$ (if necessary).

1] I think the assumptions are natural and necessary. They can be justified with the hope that the respective quantities do not change too much for the duration of our synchronisation attempt.


Differences and relations between high-performance/throughput computing and parallel computing? I wonder if high-performance computing and parallel computing always mean the same?
If not,

what are the differences and relations between  them?
what are some examples of high-performance computing that are not parallel computing?
what are some examples of parallel computing that are not high-performance computing?

Are high-throughput computing and high-performance computing the same concept?

As noted by @JukkaSuomela, you can do parallel computing on low-end resources such as your laptop and even on your mobile phone (if they are equipped with a multicore processor). However, HPC (High Performance Computing) is, roughly stated, parallel computing on high-end resources, such as small to medium sized clusters (ten to hundreds of nodes) up to supercomputers (thousands of nodes) costing millions of dollars. Therefore, the difference is mainly in the hardware used.

Finally, HTC (High Throughput Computing) refers to executing the maximum number of tasks (or jobs if you prefer) per time unit. A classical example of HTC computation is the so called parameter sweep, in which you must run the same executable, but varying in each execution a set of parameters (thus the sweep spans the whole parameter space).

the field of supercomputing has undergone a significant paradigm shift in the last decade or so such that it used to require highly specialized hardware and designs. a supercomputing company that embodied this approach is Cray supercomputers.

however a new concept/trend has emerged that extremely high performance can be achieved with "off-the-shelf" components such as those used in consumer electronics and heavy internetworking using standard networking components. supercomputer designs have always utilized a large amount of parallelism but this trend has been amplified with the proliferation of the off-the-shelf type approach. also parallelism is much more being supported with sophisticated software architectures such as MPI, MapReduce, etc

so the systems are still highly parallel but the particular means of achieving that parallelism has shifted in the hardware and software. the parallelism is more visible at the application layer and not abstracted away.

also recently power consumption has become much more of an issue and supercomputers are starting to focus on energy-efficient designs and low-energy CPUs such as those used in mobile computing. [1] is a nice ref on key issues in current trends/barriers on high performance computing scalability.

[1] Next-Generation Supercomputers Kogge


Can I use "XORing" in my thesis? I'm currently writing my bachelor thesis and explain some algorithms where the XOR-operation is used.

Can I use "XORing" or "XORed" in my thesis or is this too informal?

For example: "xoring the plaintext with the stream cipher results in the cypher text" and "the plaintext is XORed with the stream cipher..."

Also what would be the correct way to write it? Completly lowercase or with an uppercase XOR?

Hope this is the right community to ask this question.

Some useful guidelines for writing are:

Who is my audience?
Will my audience understand what I am writing?
Will my usage of language be distracting or otherwise take attention away from the message I'm trying to make?

In this case, your audience is probably another computer scientist who has at least some knowledge of your area.  Therefore, yes, I would expect that another computer scientist will understand your meaning if you write "XORing" or "XORed".  Also, it's common enough that I don't think it will be distracting.  Whether it's too information is perhaps a bit subjective, but I don't view it as too informal.

I've seen it both ways: "xoring" and "XORing".  Personally, I find the all-caps jarring, so my eye prefers "xoring", but I think that is a matter of taste.

Note that "ciphertext" is normally spelled that as one word, and with an "i", not a "y".  Right: "ciphertext".  Wrong: "cyphertext", "cypher text", "cipher text".

People will know what you mean, but "XOR" is a noun, and verbing it into the word "XORing" is a little crass.

Usually authors will explain that bits are "combined using the exclusive-OR operation" and then speak of "combining", or something like that.


How can an algorithm have exponential space complexity but polynomial time complexity? For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback problems". It is said that it runs in polynomial time but uses exponential space in a dictionary.

insert F_q into Q and into D;
while Q is not empty do
  remove any set F from Q;
  output F;
  for each uG-successor F′ of F do
    if F′ is not contained in D
      insert F′ into D and Q;
    fi
  od
od

How can this be? Does an exponential number of insert operations to the dictionary not inevitably imply exponential time?

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes:

  Observe that the number of minimal, and even minimum solutions, can be
  exponential in the size of the graph; Fig. 1 gives an example.
  Therefore, the total running time of any enumeration algorithm cannot
  be expected to be polynomial in the size of the graph.

The paper goes onto explain the concept of polynomial delay,

  However, certain enumeration algorithms for other combinatorial
  problems work with polynomial delay, i.e., the algorithm performs at
  most a polynomial number of steps before the first and between
  successive outputs.

What's polynomial isn't the entire runtime of the algorithm, its the time between successive outputs. Since the algorithm can output an exponential number of items, the total run time can quite easily be exponential.

When it comes to memory, the paper states:

  Note that memory requirements are polynomial for graphs with a
  polynomial number of MFVS, but potentially exponential for the general
  case.

Memory goes exponential if we have an exponential number of outputs. But in that case, there is an exponential amount of time passing to fill up that amount of memory as well.

Put another way, memory is exponential because we are measuring memory usage over the entire enumeration process. Time is polynomial because we are only measuring time between two outputs.

Splitting calculations into space and time is one way to describe the behavior of the equation. What this is saying is that the calculations do not need to actually compute over the full size of the data to compute the result. This is maybe reasonable since you only need to locate a single vertex in each cycle.

didn't read the full algorithm but probably it has something to do with

Say you have a clique of size N. That queue could approach N! in size, but you may not actually need to computer over the full N! edges to find the solution


Prove: Every decidable set is Turing reducible to the empty set Question-
Prove:  Every decidable set is Turing reducible to the empty set.

Can anyone help me with this please?

All reductions tutorials I've seen use practical examples of reduction such as sipser's introduction to computation theory:

"A reduction is a way of converting one problem to another problem in such a
way that a solution to the second problem can be used to solve the first problem.
...
For example, suppose that you want to find your way around a new city. You
know that doing so would be easy if you had a map. Thus, you can reduce the
problem of finding your way around the city to the problem of obtaining a map
of the city"

I don't see how to use this kind of information as a general proof, or how the empty set is even usable to solve anything else in a practical example even.

You're trying to prove something, so you need to use something closer to an actual definition of Turing reducibility. The statement you quote from Sipser is an intuition about what reductions do, but it's not precise enough to let you solve problems.

Here's an informal definition of Turing reducibility that lets you start to reason about what it can do.

  A set $A$ is Turing-reducible to a set $B$ if, assuming the existence of a subroutine that determines whether its input is in $B$, we can write a program that determines whether its input is in $A$.

We're considering $B=\emptyset$, so we need to assume the existence of a subroutine that determines whether its input is in $\emptyset$. Well, that's not much to assume. Here's the subroutine:

 return false

OK – we don't need to assume anything: we know this subroutine exists.  So now, we just need to show that every decidable set is Turing reducible to $\emptyset$. That is, we need to show that

  For every decidable set $A$, we can write a program that determines whether its input is in $A$.

So... what's the definition of decidable?

2 languages A and B.
If B is <= t A,
then A is <=t B.
run A on B until {},
if A is {} (empty),
then B is {}.


Fastest algorithm for finding the longest palindrome subsequence First of all we must read a word, and a desired size.
Then we need to find the longest palindrome created by characters in this word used in order.
For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

See Wikipedia's reference

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

Edit

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good:
\begin{align*}
f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad j<k\\
f_{k,k}&=1\\
f_{j,k}&=0,\qquad j>k\\
\end{align*}
where $f_{j,k}$ denotes the length of the longgest palindrome subsequence of $S_{j..k}$, and $[P]$ is Iverson bracket I think it's just like LCS.

I'm probably missing something, because it seems rather trivial to me: Try to pair each character with an equal character. Then put the first character of each pair on the left side, the other character on the right side, and if there are any characters remaining (ie, characters not paired with another one), then pick one of them and put that one in the middle.


How do I find my wife in a supermarket? If two people are lost in a maze, is there an algorithm that they can both use to find each other without having previously agreed what algorithm they will be using?

I think there are some characteristics that this algorithm will have:

Each person must be able to derive it using logic that makes no assumptions about what the other person is deciding, but as each person knows the other is in the same position they may make deductions about what the other must be deciding.
An identical algorithm must be derived by both people as there is total symmetry in their situations (neither has any knowledge about the starting position of the other, and the maze is a fixed size, and fully mapped by both).  Note that the algorithm is not required to be deterministic: it is allowed to be randomized.

This is called rendezvous problem.

As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:

  Two astronauts land on a spherical body that is much larger than the
  detection radius (within which they can see each other). The body does
  not have fixed orientation in space, nor does it have an axis of rotation,
  so that no common notion of position or direction is available to
  the astronauts for coordination. Given unit walking speeds for both astronauts, how should they move about so as to minimize the expected
  meeting time T (before they come within the detection radius)?

In the survey paper above,

  Abstract: Recent results on the problem of mobile agent rendezvous on distributed networks are surveyed with an emphasis on outlining the various approaches taken by researchers in the theoretical computer science community.

It covers both "Asymmetric Rendezvous" (in Section 4) and "Symmetric Rendezvous" (in Section 5).

For symmetric rendezvous, the paper by Alpern shows:

  It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise.

Actually any consistent pre-arranged scheme will do.

For example:

Turn always left
If on a dead-end backtrack to previous turn and turn right
One will have to walk double the (pre-arranged) speed of the other (or in more number-theoretic terms, the speeds of the two agents should be relatively prime, or more generaly be linearly-independent).

Or even simpler

One agent stays in the same place
While the other uses a consistent scheme to explore the maze (e.g using an Ariadne's thread approach).
Eventualy, in finite time, they will meet.

This scheme will guarantee that the people will meet eventualy (but it might take some time)

Why? Because the scheme is consistent for both and does not lead either to a dead-end. So since the maze is finite and is connected, after a finite time they will meet.

If the scheme is not consistent, there is no guarantee they will meet since they can result in closed loops.

If they have the same speed then depending on the architecture of the maze, e.g a cyclic maze, then it is possible they can always be at anti-diametrical points of the maze, hence never meet, even though the scheme is consistent.

It is clear from the above that the scheme needs to be pre-arranged, but any consistent pre-arranged scheme will do.

Else one can rely on probabilistic analysis and infer that with a large probability they will meet, but this probability is not one (i.e under all cases).

One can also consider the converse of the rendezvous problem, the avoidance problem where the objective is for the agents to always avoid each other.

The solution to the avoidance problem is for the agents to reflect each other exactly. Meaning that what one agent does the other should do the reflection of that. Since the avoidance problem also has a solution, it is clear that  strategies for the rendezvous problem that may lead to reflection behaviour of the agents, cannot guarantee solution.

One can say that the strategy for the avoidance problem is parallelization (ie maximum divergent point) whereas the strategy for the rendezvous problem is orthogonality (i.e least convergent point)

The above analysis can be turned into an randomised algorithm which does not assume pre-arranged roles for the agents, like the following:

Each agent throws a coin on which role to choose (e.g either staying in place or exploring the maze)
Then they proceed as described above.

This on average will lead to people eventually meeting, but is not guaranteed under all cases.

If we assume that the agents can leave traces, e.g labels of their (current) direction and speed. Then, the other agent, can use these traces as information to adjust both its own direction and speed (see below).

This kind of problem is an example of global optimisation using only local information. Or, in other words, a way to map global constraints to local constraints. This, more general, problem (which subsumes the rendezvous problem) is tackled in this math.se post (and references therein) "Methods to translate global constraints to local constraints"


Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming? Let me clarify:

Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number of points nearby.

Yet, in programming, given a set of points n, in order to find the closest point to any one, it requires checking every other point, which is ${\cal O}(n)$ time.

I am guessing that the visual sight of a graph is likely the equivalent of some data structure I am incapable of understanding; because with programming, by converting the points to a more structured method such as a quadtree, one can find the closest points to $k$ points in $n$ in $k\cdot\log(n)$ time, or ammortized ${\cal O}(\log n)$ time.

But there is still no known ${\cal O}(1)$ ammortized algorithms (that I can find) for point-finding after data restructuring.

So why does this appear to be possible with mere visual inspection?

Your model of what you do mentally is incorrect. In fact, you operate in two steps:

Eliminate all points that are too far, in $O(1)$ time.
Measure the $m$ points that are about as close, in $\Theta(m)$ time.

If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the target, but you may need to measure the closest contenders.

To illustrate this point, which green dot is closest to the red dot? (Only by a little over 1 pixel, but there is one that's closest.) To make things easier, the dots have even been color-coded by distance.

This picture contains $m=10$ points which are nearly on a circle, and $n \gg 10$ green points in total. Step 1 lets you eliminate all but about $m$ points, but step 2 requires checking each of the $m$ points. There is no a priori bound for $m$.

A physical observation lets you shrink the problem size from the whole set of $n$ points to a restricted candidate set of $m$ points. This step is not a computation step as commonly understood, because it is based on a continuous process. Continuous processes are not subject to the usual intuitions about computational complexity and in particular to asymptotic analysis.

Now, you may ask, why can't a continuous process completely solve the problem? How does it come to these $m$ points, why can't we refine the process to get $m=1$?

The answer is that I cheated a bit: I presented a set of points which is generated to consists of $m$ almost-closest points and $n-m$ points which are further. In general, determining which points lie within a precise boundary requires a precise observation which has to be performed point by point. A coarse process of elimination lets you exclude many obvious non-candidates, but merely deciding which candidates are left requires enumerating them.

You can model this system in a discrete, computational world. Assume that the points are represented in a data structure that sorts them into cells on a grid, i.e. the point $(x,y)$ is stored in a list for the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$. If you're looking for the points that are closest to $(x_0, y_0)$ and the cell that contains this point contains at most one other point, then it is sufficient to check the containing cell and the 8 neighboring cells. The total number of points in these 9 cells is $m$. This model respects some key properties of the human model:

$m$ is potentially unbounded — a degenerate worse case of e.g. points lying almost on a circle is always possible.
The practical efficiency depends on having selected a scale that matches the data (e.g. you'll save nothing if your dots are on a piece of paper and your cells are 1 km wide).

Generally speaking you are solving two different problems and if you compete in the same competition, complexity will be O(1) for both of you. Why? Let's make situation a bit simpler - assume that you have a line with one red point and n green points. Your task is to find green point which is closest to red point. Everything is on the graph. Now what you do and what you program is doing is basically the same - just "walk away"(in both directions) from red point and check whether the pixel you are looking at is white/black(background) or green. Now the complexity is O(1).

What's interesting is that some data presentation methods gives answers to some questions immediately(O(1)). Basic example is extremely simple - just count white pixels on black image(each pixel value is 0 = black or 1 = white). What you need to do is  just add all pixels values - complexity is the same for 1 white pixel and for 1000, but it depends on image size - O(m), m=image.width*image.height. Is it possible to do it faster? Of course, all we need to do is use different method of storing images which is integral image:

Now calculating the result is O(1) (if you have integral image already calculated). Another way is just store all white pixels in array/vector/list/... and just count it size - O(1).