Programming Pearls, 2nd Edition

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 ...