The best way to become convinced that careful algorithm design can have a significant impact on performance is to look at case studies. By carefully studying other people's experiences, we learn how they might apply to our work.
Jon Bentley's Programming Pearls columns are probably the most interesting collection of algorithmic ``war stories'' currently available. Originally published in the Communications of the ACM, they have been collected in two books [Ben86, Ben90]. Fredrick Brooks's The Mythical Man Month [Bro74] is another wonderful collection of war stories, focused more on software engineering than algorithm design, but they remain a source of considerable wisdom. Every programmer should read all three of these books, for pleasure as well as insight.
Scattered throughout this text are several of our own war stories, presenting our successful (and occasionally unsuccessful) algorithm design efforts on real applications. We hope that the reader will be able to internalize these experiences so that they will serve as models for their own attacks on problems.
Every one of the war stories is true. Of course, the stories improve somewhat in the retelling, and the dialogue has been punched up to make it more interesting to read. However, I have tried to honestly trace the process of going from a raw problem to a solution, so you can watch how the process unfolded.
The Oxford English Dictionary defines an algorist as ``one skillful in reckonings or figuring.'' In these stories, I have tried to capture some of the attitude, or mindset, of the algorist in action as they attack a problem.
The various war stories usually involve at least one and often several problems from the problem catalog in Part II. The appropriate section of the catalog is referenced wherever it occurs. This emphasizes the benefits of modeling your application in terms of standard algorithm problems. By using the catalog, you will be able to pull out what is known about any problem whenever it is needed.