The Algorithm Design Manual Second Edition

1.5

About the War Stories

The best way to learn how careful algorithm design can have a huge impact on per-

formance is to look at real-world case studies. By carefully studying other people’s

experiences, we learn how they might apply to our work.

Scattered throughout this text are several of my own algorithmic war stories,

presenting our successful (and occasionally unsuccessful) algorithm design efforts

on real applications. I hope that you will be able to internalize these experiences

so that they will serve as models for your own attacks on problems.

---

1 . 6

W A R S T O R Y : P S Y C H I C M O D E L I N G

23

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 them 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 this 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 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. I reference the appropriate section of the

catalog when such a problem 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 given problem whenever it is

needed.