O'Reilly logo

Programming Pearls, Second Edition by Jon Bentley

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Column 8: Algorithm Design Techniques

Column 2 describes the everyday effect of algorithm design on programmers: algorithmic insights can make a program simpler. In this column we’ll see a less frequent but more dramatic contribution of the field: sophisticated algorithms sometimes give extreme performance improvements.

This column studies four different algorithms for one small problem, with an emphasis on the techniques used to design them. Some of the algorithms are a little complicated, but with justification. While the first program we’ll study takes fifteen days to solve a problem of size 100,000, the final program solves the same problem in five milliseconds.

8.1 The Problem and a Simple Algorithm

The problem arose in one-dimensional ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required