book cover

Algorithm Design Techniques
(A Sketch of Column 8 of Programming Pearls)

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.

The Rest of the Column


8.1 The Problem and a Simple Algorithm
8.2 Two Quadratic Algorithms
8.3 A Divide-and-Conquer Algorithm
8.4 A Scanning Algorithm
8.5 What Does It Matter?
8.6 Principles
8.7 Problems
8.8 Further Reading

The teaching material contains overhead transparencies based on this column; the slides are available in both Postscript and Acrobat.

The code for Column 8 contains a program for testing and timing all the algorithms.

Copyright © 1999 Lucent Technologies. All rights reserved. Wed 6 Oct 1999