Conversations: Jon Bentley

DDJ: Jon, do you have a standard process that guides you when you're designing a new algorithm?

JB: I have long been interested in that question. The primary contribution of my 1976 Ph.D. thesis was a collection of geometric algorithms. Along the way, though, I tried to describe the design process itself. Although I hadn't looked at it for decades before you asked, Section 6.1 on "Principles of algorithm development" seems to have stood the test of time. The principles include generalizing, using high-level and abstract description of algorithms, examining degenerate cases, and employing standard speed-up tricks. Perhaps the most important advice is to read and use Polya's 1945 classic book How To Solve It.

But before you get immersed in the details of designing an algorithm, the most important step is to find out what the real problem is. Column 1 of my book Programming Pearls talks about the importance of speaking to your user to learn exactly what he needs.

DDJ: Algorithm analysis seems different from algorithm design. In what way?

JB: The goal of algorithm design is to develop a good algorithm; the goal of algorithm analysis is to understand how good an algorithm is.

The two activities sometimes proceed hand-in-hand: In classes students typically design an algorithm so that it can be analyzed. In a divide-and-conquer algorithm, for instance, you split the original problem into two equal-sized pieces, solve those recursively, and then marry those subsolutions into a solution to the original problem. A recurrence relation that describes the runtime of the program is straightforward to derive and (usually) to solve.

Sometimes, though, people design algorithms and report that they are fast without analyzing their runtime. What a delightful challenge for an algorithm analyst! I've walked both sides of that street. My most frequently cited paper was for the 1975 ACM Undergraduate Student Paper competition; it introduced multidimensional binary search trees, which Don Knuth called "k-d trees." I described an algorithm for nearest-neighbor searching, but I couldn't even begin to analyze it. Many folks have made great progress on the analysis since then. In 1985, Cathy McGeoch and I published an amortized analysis of the move-to-front sequential search heuristic, which had been around for at least two decades.

DDJ: You and Doug McIlroy once wrote, "The key to performance is elegance, not battalions of special cases." How would you define "elegance" in this context?

JB: I tried to answer that question in detail in Chapter 3 of Beautiful Code, which was published by O'Reilly last year. My chapter starts with a pretty little program, and then methodically transforms it, step-by-step, to be faster and faster and smaller and smaller. My inspiration was a comment I heard about a great programmer decades ago: "He adds function by deleting code." In this case, I was able to add a great deal of function by deleting (eventually) all the code, so I called my chapter "The Most Beautiful Code I Never Wrote." I can't define programming elegance in a few words, but I do know it when I see it, and I tried to give an example in that chapter.

DDJ: Joshua Bloch, a student when you taught at Carnegie Mellon, said when discussing a bug in a binary search program that, "It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code." Thoughts?

JB: You left out an important piece: It was a substantial bug in a program that I had written, and that was published widely over two decades earlier! My first thought therefore was, "Ouch!" Programming is a fun, exciting, challenging task, and Josh taught me an important lesson about why that is so (and I would expect no less of Josh, who is a particularly fun, exciting, and challenging person). His comment is dead on: Programming is subtle, and we must learn from Edsger Dijkstra to be "humble programmers." We have lots of tools to use: Precise specifications, formal methods, and extensive tests among them. One of the best tools is the eyes of really smart friends, and I am fortunate to know Josh Bloch and to have had him take the time to study my code.

DDJ: Is algorithm design central to any of your day-to-day activities now, or are you working on other things?

JB: Once an algorithms guy, always an algorithms guy. I have long enjoyed the interaction of theory and practice. When I taught at Carnegie Mellon, I was an algorithms researcher who consulted to ground my work in real problems. Now, at Avaya Labs Research, I work on the company's problems, but bring to bear a background in algorithms that is useful surprisingly often. Plus, the company appreciates the long-term value of basic research, and encourages us to prepare for the future. Dig deep enough, and you'll find interesting algorithmic problems at the heart of most real systems.