Textbooks: There are dozens of textbooks in print and well over
a hundred out of print, most of which have something unique that
can enhance your understanding of algorithms. So the list below
is only a tiny sample and these are not necessarily the texts
you will find most helpful.
First, some good background texts.
-
A. Levitin.
The Design and Analysis of Algorithms. Addison-Wesley, 2003.
An introductory text with excellent organization and a friendly
approach. This is an undergraduate text, not suitable for our course, but one
of the best choices for the required background material.
-
M. Weiss.
Data Structures and Algorithms in (Java)/(C++). Addison-Wesley, 2007.
The latest editions of a textbook first published in 1992; solid
undergraduate material, obviously very well tested presentation, another good
choice for the required background material.
-
G.J.I. Rawlins. Compared to What? An Introduction to the Analysis of Algorithms. Computer Science Press, 1992.
Note that the title does not include "design", only "analysis": the
emphasis is indeed on analysis, but for all that this is also a regular
undergraduate text on algorithms. Very popular with sophomores and juniors,
this is a great choice if you are having trouble with the math behind
algorithmic analysis.
Now some texts that cover some, much, or most of the material in our course.
-
T.H. Cormen, C.E. Leiserson, R. Rivest, and C. Stein,
Algorithms (2nd ed.), MIT Press, 2001. Widely available.
A hulking monster of a book (1200pp!), divided into 7 parts (plus an
appendix), this has become the standard algorithms text, perhaps more because
of its size (everyone can find something in here) than for any other reason.
Parts II, III, and IV, as well as much of Parts V and VI, are good reviews of
the background expected from the undergraduate Algorithms course. Parts I and
chapter 17 in Part IV give an overview of algorithm analysis techniques. Part
VII (Selected Topics) covers the type of material that is the focus of this
course.
-
S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani,
Algorithms,
McGrawHill, 2006.
This is a slim volume (about 1/4 of the Cormen et al.) and includes
quantum algorithms, but its coverage of algorithms is of necessity rather
limited -- for instance, it has nothing about computational geometry.
Its level is also somewhat below that of our course. For all that, it
is a very handy reference and one of the most readable ones around.
(Note: the authors maintain online the
penultimate
draft of the text, available at no charge.)
-
J. Kleinberg and E. Tardos,
Algorithm Design,
Addison-Wesley, 2005.
This may be my current favorite text, because of its broad coverage,
but also because it discusses exact, randomized, approximate, and heuristic
algorithms, as well as complexity. The level is somewhat uneven, with
some very elementary topics in the first few chapters and a very thorough
treatment of network flow, but this is simply a reflection of the authors'
main areas of research.
In addition, you can find more detailed coverage by area (computational
geometry, computational biology, numerical computing, randomized algorithms,
proof systems, etc.) in a large variety of specialized textbooks, some of
which are listed below.
-
M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars,
Computational Geometry:
Algorithms and Applications (3rd ed.), Springer Verlag, 2008.
This is the best text in computational geometry by orders of magnitude and
perhaps the best algorithms text ever written -- excellent organization,
consistent level, superb exposition, abundant illustrations, and even good
exercises. Suitable to anyone who has taken an introductory course in
algorithms -- no background in computational geometry is required.
-
K. Mulmuley,
Computational Geometry: An Introduction through Randomized Algorithms.
Prentice Hall, 1993.
Not so introductory, but something of a tour de force, as
almost every major algorithm in computational geometry is tackled
from a randomized perspective, often leading to surprising insights.
Perhaps even better for learning randomized algorithms than for learning
algorithms in computational geometry. Out of print, but fac-simile editions
are available.
-
D. Gusfield,
Algorithms on Strings, Trees, and Sequences. Cambridge U. Press, 1997.
A very thorough coverage of all basic (and not so basic) methods
for sequence analysis and tree inference. Highly recommended.
-
J. Setubal and J. Meidanis,
Introduction to Computational Molecular Biology. PWS Publ., 1997.
Slim volume, very nicely organized, excellent
presentation (aimed at computer scientists in 1st graduate year), but
starting to get dated.
-
R. Motwani and P. Raghavan,
Randomized Algorithms. Cambridge U. Press, 1995
Another classic text, with an excellent introduction to the
mathematical material and short chapters on uses of randomization in
a variety of areas. The first and still the best text in the area.
-
M. Mitzenmacher and E. Upfal,
Probability and Computing. Cambridge U. Press, 2005.
10 years later than the above and so considerably more up to date,
but more theoretical and more concerned with general techniques, such
as Markov chains, than with specific algorithms.
-
V. Vazirani,
Approximation Algorithms. Springer Verlag, 2001.
Starts in a very problem-oriented manner, tackling a dozen classic
problems (set cover, knapsack, TSP, etc.) in the first 90 pages, then turns
towards methodological ideas, with LP-based approximations, randomized
rounding, derandomization, low-dimensional embeddings, LP relaxations, etc.
Includes a chapter on semidefinite programming and one on the hardness of
approximation. Somewhat dense in parts, but quite thorough.
-
D.S. Hochbaum, ed.,
Approximation Algorithms for NP-Hard Problems. PWS Publishing, 1996.
An edited volume, with chapters written by leading researchers.
Incomplete coverage and very uneven treatment across chapters, yet all of
them are very well done and very useful, from an incredibly detailed
coverage of bin-packing by Coffman, Garey, and Johnson (chap. 2) to a general
overview by Hochbaum herself (chap. 9), along with perhaps the most readable
treatment I have seen of the PCP theorem and its consequences for the hardness
of approximation, by the master himself, S. Arora (with C. Lund).
An excellent reference, but not written as a textbook.
Finally, there are advanced texts that deal only with the mathematics
needed to analyze algorithms that present particularly challenging running
times. You will normally not need any of these, but those of you who
like mathematics should find them interesting.
-
R.L. Graham, D.E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1994.
The advanced version of a typical discrete mathematics textbook,
with the thoroughness of two of the all-time greats of Math and CS and
with pithy marginal comments by generations of students at Stanford.
Lots of algorithmic analysis techniques.
-
R. Sedgewick and Ph. Flajolet. An Introduction to the Analysis of Algorithms. Addison-Wesley, 1996.
"Introduction" is something of a misnomer here; there is introductory
material, but the text moves on to rather hard recurrences and other
analysis techniques.
-
P.W. Purdom, Jr., and C.A. Brown. The Analysis of Algorithms. Holt, Rinehart, and Winston, 1985.
Everything you ever wanted to know about recurrence relations and how to solve them.
-
D.H. Greene and D.E. Knuth. Mathematics for the Analysis of Algorithms. Birkauser, 2008 (3rd ed. reprint)
The ultimate. Using complex-plane contour integration (poles and zeroes,
remember those?) for solving discrete recurrences? You got it!