book cover

Why A Second Edition of
Programming Pearls?

In a draft Preface for the second edition, I explained why (and how) I undertook writing this version. The reviewers were unanimous about that Preface: a subtle reviewer said that it was ``more effusive'' than the rest of the book, while a more forthright reviewer said only, ``so little space, so many cliches''. They were right; it is gone from the book, replaced by a straightforward description of the changes. But most of the draft preface now lives on in this tiny corner of the web, complete with effusive cliches.

A long time ago, in a Preface far, far away ...

________________________________

I started writing this second edition as a duty, admittedly a labor of love, but still recalling full well the tribulations of producing a book. It was indeed all that, but more. It became a joy. It became a visit to old friends, seeing that while a few had fallen with time, most had grown into a proud maturity. And, oh, the delight of the next generation! The new sections and the new problems have the strong family resemblance, but they have the vitality of youth, and a freshness of their own.

But I'm getting ahead of myself; let me return to the beginning. I wrote my first program in high school, in 1969. The first magazine I saw about computing was Communications of the ACM. In 1983, I started to write a CACM column called ``Programming Pearls''. It was about about programs whose origins lie beyond solid engineering, in the realm of insight and creativity. A few years later, I collected the most fundamental columns into the first edition of this book.

It is hard for any programming book to survive the tremendous changes in our field, and I watched other books I had written enjoy their years in the sun and then go gently into that good night. This book was different: the examples were showing their age, but the principles seemed to stand the test of time. What to do?

I hemmed and hawed, consistently finding reasons not to undertake the hard work. Things finally came together in early 1999: I came across reviews with words like ``classic but dated'', respected colleagues asked about updating the book, and I had a chunk of free time in my work schedule. It was time to revisit the salt mines.

Following my preferred style of software development, I decided to prototype a single column. I chose Column 8 on algorithm design techniques. The techniques were still relevant, but the implementations were painfully outdated (the run times were reported for the ancient VAX-11/750, and the code was not fit for public consumption). I had great fun recoding the algorithms in a modern style, complete with scaffolding for testing and timing. The tests reported a bug; were my old experiments flawed? No, but Problem 8.7 now describes an interesting aspect of floating-point computation. One tune-up I tried reduced the time of Algorithm 4 by 40 percent, but increased the time of Algorithm 3 by a factor of 100. Fascinating problems started trickling in at a steady rate.

My first real shock came when I prepared a table of the run times of four algorithms. The times were almost unchanged across fifteen years:
ALGORITHM1234
First edition3.4n313n2 46n log2 n33n
Second edition1.3n310n2 47n log2 n48n
I was astonished that the coefficients were so close. The only difference is that the top row reports the run time in microseconds, while the bottom row reports the time in nanoseconds! For these functions, my 400MHz Pentium II is almost exactly one thousand times faster than the venerable VAX. The more things change....

I next dug into Column 2. In 1983, I was able to find all anagrams in a dictionary of 72,000 words in half an hour. Now, a dictionary of 230,000 words was processed in 18 seconds. Problem 2.4 had revealed fascinating paging behavior on the old VAX, and now led to the remarkable graph of Pentium II caching performance in Solution 2.4.

I tried a few more columns, and each one led to surprises. The ancient program in Column 1 for sorting 27,000 political districts in a kilobyte turned into a modern program for sorting ten million toll-free telephone numbers in a megabyte. The old story in Section 3.5 about a new-fangled (for 1983) tool called a database turned into a little essay about hypertext, spreadsheets, databases, and other tools now familiar to high-school students. A section from old Column 4 on implementing binary search grew into a fun program and then into the new Column 5. I was hooked. I called Peter Gordon, my editor at Addison Wesley Longman, and enthusiastically committed to write this second edition.

Copyright © 1999 Lucent Technologies. All rights reserved. Sat 31 July 1999