[plt-scheme] Great books on algorithms?

From: Shriram Krishnamurthi (sk at cs.brown.edu)
Date: Tue Oct 30 20:56:58 EDT 2007

Warning: I haven't taken algorithms courses since the mid-90s.  There
may be new gems out there.  Also I haven't read these books in depth
since then, so I may be slightly mis-remembering some purported facts.


Art of Computer Programming is not appropriate for people with a
general interest in algorithms.  The program notation is awful, and
the mathematics is quite heavy.  They are useful as reference books
for particular questions (on which the volumes are likely to be
compendious), but not for general study.


The modern-day standard is the book by Cormen, Lieserson, Rivest,
Stein.  It has been field-tested extensively, it is pretty readable,
it's sufficiently detailed for an undergraduate course, and it covers
a broad variety of material (and constantly gets broader).  It's like
the IBM of algorithms texts: nobody will be fired for choosing it.


I have four lesser-known favorites.

Two that are very area-specific:

- Data Structures and Network Algorithms, by Robert E. Tarjan

The master holding forth on a topic dear to him (and the topic on
which he had the greatest influence).

- Graph Algorithms, Shimon Even

This is now somewhat dated, but the content is essential knowledge for
a practicing computer scientist, and there are some nuggets in here.

Two general-purpose but idiosyncractic books:

- Introduction to Algorithms, Udi Manber

An underrated classic.  Sadly the code is all in Pascal, which is a
terribly verbose notation for expressing elegant ideas, and is
presented in brutal detail.  But Manber really shows the *design* of
algorithms (something virtually nobody else ever discusses) using
induction/recursion as his driving force.  Unlike most other books he
actually shows bad attempts and the mistakes they lead to.  He uses
strenthening-of-hypotheses as his traditional way of fixing these
mistakes.  A real gem.

- The Design and Analysis of Algorithms, Dexter Kozen

To read this book is to watch a great master at work.  A transcript of
Kozen's graduate course, he simply takes 30-40 great and good
algorithms and covers them, one lecture at a time.  There's no attempt
to make a coherent textbook out of this, so this is not appropriate
for the rank beginner.  But to someone who has the basics, it's
difficult to imagine a more masterful survey.


I've read all four books: the first for my breadth-exam in grad
school, the other three as course texts.  The first book has a bit of
a by-committee feel, though the result is (fortunately) closer to a
horse than a camel.  These last three books make me happy, the last
two fill me with joy, and the last one makes my heart sing.


Posted on the users mailing list.