How to tell algorithms apart

Edgar Daylight was trained both as a computer scientist and as a historian. He writes a historical blog themed for his near-namesake Edsger Dijkstra, titled, “Dijkstra’s Rallying Cry for Generalization.” He is a co-author with Don Knuth of the 2014 book: Algorithmic Barriers Failing: P=NP?, which consists of a series of interviews of Knuth, extending their first book in 2013.

The book is essentially a conversation between Knuth and Daylight that ranges over Knuth’s many contributions and his many insights.

One of the most revealing discussions, in my opinion, is Knuth’s discussion of his view of asymptotic analysis. Let’s turn and look at that next.

Asymptotic Analysis

We all know what asymptotic analysis is: Given an algorithm, determine how many operations the algorithm uses in worst case. For example, the naïve matrix product of square ${n}$ by ${n}$ matrices runs in time ${O(n^{3})}$. Knuth dislikes the use of ${O}$ notation, which he thinks is used often to hide important information.

For example, the correct the count of operations for matrix product is actually

$\displaystyle \frac{1}{3} n^{3} + O(n^{2}).$

In general Knuth suggests that we determine, if possible, the number of operations as

$\displaystyle f(n) + O(g(n)),$

where ${f(n)}$ and ${g(n)}$ are both explicit functions and ${g}$ is lower-order. The idea is that not only does this indicate more precisely that the number of operations is ${\Theta(f(n))}$, not just ${O(f(n))}$, but also is forces us to give the exact constant hiding under the ${\Theta}$. If the constant is only approached as ${n}$ increases, perhaps the difference can be hidden inside the lower-order ${g(n)}$ term.

An example from the book (page 29) is a discussion of Tony Hoare’s quicksort algorithm. Its running time is ${O(n\log n)}$, on average. This allows one, as Knuth says, to throw all the details away, including the exact machine model. He goes on to say that he prefers to know:

${\dots}$ that quicksort makes ${2n\ln n - \frac{8}{3}n + O(\log n)}$ comparisons, on average, and ${\frac{1}{3}n \ln n - \frac{4}{9}n + O(\log n)}$ exchanges, and ${\frac{2}{3}n + O(1)}$ stack adjustments, when sorting random numbers.

The Novelty Game

Theorists create algorithms as one of their favorite activities. A classic way to get a paper accepted into a top conference is to say: In this paper we improve the running time of the best known algorithm for X from order ${n^{3}\log n}$ to ${O(n^{3})}$ by applying methods Y.

But is the algorithm of this paper really new? One possibility is that the analysis of the previous paper was too coarse and the algorithms are actually the same. Or at least equivalent. The above information is logically insufficient to rule out this possibility.

Asymptotic analysis à-la Knuth comes to the rescue. Suppose that we proved that the older algorithm X ran in time

$\displaystyle \frac{1}{4}n^{3}\log n + O(n).$

Then we would be able to conclude—without any doubt—that the new algorithm was indeed new. Knuth points this out in the interviews, and adds a comment about practice. Of course losing the logarithmic factor may not yield a better running time in practice, if the hidden constant in ${O(n^{3})}$ is huge. But whatever the constant is, the new algorithm must be new. It must contain some new idea.

This is quite a nice use of analysis of algorithms in my opinion. Knowing that an algorithm contains, for certain, some new idea, may lead to further insights. It may eventually even lead to an algorithm that is better both in theory and in practice.

Open Problems

Daylight’s book is a delight—a pun? As always Knuth has lots to say, and lots of interesting insights. The one caveat about the book is the subtitle: “P=NP?” I wish Knuth had added more comments about this great problem. He does comment on the early history of the problem: for example, explaining how Dick Karp came down to Stanford to talk about his brilliant new paper, and other comments have been preserved in a “Twenty Questions” session from last May. Knuth also reminds us in the book that as reported in the January 1973 issue of SIGACT News, Manny Blum gave odds of 100:1 in a bet with Mike Paterson that P and NP are not equal.

[fixed picture glitch at top]

And perhaps even find your hidden prime factors

Neil L. is a Leprechaun. He has visited me every St. Patrick’s Day since I began the blog in 2009. In fact he visited me every St. Patrick’s Day before then, but I never talked about him. Sometimes he comes after midnight the night before, or falls asleep on my sofa waiting for me to rise. But this time there was no sign of him as I came back from a long day of teaching and meetings and went out again for errands.

Today Ken and I wish you all a Happy St. Patrick’s Day, and I am glad to report that Neil did find me.

It’s 3/14/15, do you know how much your Π costs?

Larry Shaw apparently created the concept of Pi Day in 1988. He was then a physicist who worked at the San Francisco Exploratorium. He and his colleagues initially celebrated by marching around in circles, and then eating pies—that is fruit pies. As Homer Simpson would say: hmm.

Today Ken and I want to add to some of the fun of Pi Day, and come back to a different Pi that has occupied us.

Can we remove simple errors from math proofs?

 simple-talk interview source

Stephen Johnson is one of the world’s top programmers. Top programmers are inherently lazy: they prefer to build tools rather than write code. This led Steve to create some of great software tools that made UNIX so powerful, especially in the “early days.” These included the parser generator named Yacc for “Yet Another Compiler Compiler.”

The Minimum Circuit Size Problem goes front and center

Eric Allender, Bireswar Das, Cody Murray, and Ryan Williams have proved new results about problems in the range between ${\mathsf{P}}$ and ${\mathsf{NP}}$-complete. According to the wide majority view of complexity the range is vast, but it is populated by scant few natural computational problems. Only Factoring, Discrete Logarithm, Graph Isomorphism (GI), and the Minimum Circuit Size Problem (MCSP) regularly get prominent mention. There are related problems like group isomorphism and others in subjects such as lattice-based cryptosystems. We covered many of them some years back.

Today we are delighted to report recent progress on these problems.

How ∅ versus {ε} can be a life-and-death difference

 Cropped from source

Jeff Skiles was the co-pilot on US Airways Flight 1549 from New York’s LaGuardia Airport headed for Charlotte on January 15, 2009. The Airbus A320 lost power in both engines after striking birds at altitude about 850 meters and famously ditched in the Hudson River with no loss of life. As Skiles’s website relates, he had manual charge of the takeoff but upon his losing his instrument panel when the engines failed,

“Captain Chesley Sullenberger took over flying the plane and tipped the nose down to retain airspeed.”

Skiles helped contact nearby airports for emergency landing permission but within 60 seconds Sullenberger and he determined that the Hudson was the only option. His front page does not say he did anything else.

Today we tell some stories about the technical content of forms of emptiness.