Book List

Official:
Dexter C. Kozen. The Design and Analysis of Algorithms, Springer-Verlag, 1992.
A timeless and terrific text. Hard important algorithms well presented and clearly analyzed. Worth careful study.

Optional:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms , 3rd Edition, MIT Press, 2009.
An excellent albeit weighty undergraduate text.

N. Alon and J. Spencer. The Probabilistic Method. Wiley Interscience, New York, 1992.
This is an amazing text. It introduces you to the Probabilistic Method again and again and again… mixing hard problems with easy problems.

Sarah Baase and Allen van Gelder. Computer Algorithms, Introduction to Design and Analysis Addison-Wesley, 2000

Jon Bentley. Programming Pearls, Addison-Wesley, Inc., 2000.
Jon Bentley writes beautifully and with great insight.

Avrim Blum. On-line notes for CS451. Lots of good stuff here, done carefully and correctly.

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co. New York, NY, 1990.
A beautifully clear exposition of NP-completeness. Most of the open problems in the back have been solved by now. Still open, however, are Graph Isomorphism, Integer Factorization and 3-processor scheduling.

Michael Kearns and Umesh Vazirani. An Introduction to Computational Learning Theory, MIT Press, 1994.

Jon Kleinberg and Éva Tardos. Algorithm Design, Addison-Wesley, 2005.

U. Manber. Introduction to Algorithms: A Creative Approach Addison-Wesley, 1990.
I especially like the problems at the end of chapter 1. They give a good sense of what sort of problems you’ll learn to solve.

Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms, Cambridge University Press, 1995.

Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani. Algorithmic Game Theory , Cambridge University Press, Cambridge, 2007. Non-printable version on the web

Robert Endre Tarjan. Data Structures and Network Algorithms (CBMS-NSF Regional Conference Series in Applied Mathematics), Society for Industrial and Applied Mathematrics, Philadelphia, PA, 1983.
Bob Tarjan is the world’s grand master of algorithms.

Vijay Vazirani. Approximation Algorithms, Springer-Verlag, Berlin, 2001.

Peter Winkler. Mathematical Puzzles: A Connoisseur’s Collection, A K Peters, Wellesley, MA, 2004.
Wonderful puzzles for the undergraduate, the graduate, and beyond. Solutions to many, but please… try doing each problem before looking at its solution. Many open problems in the last chapter. Of course, open problems don’t have solutions, but they come with information about their origin and what’s currently known. I expect many of these open problems *will* get solved in the next couple decades. Why not by you?

John H. Reid (editor) Synthesis of Parallel Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, 1993.
A good reference book for parallel algorithms, written by multiple authors

Joseph JaJa Introduction to Parallel Algorithms, Addison-Wesley Profssional, 1992.
A book on PRAM algorithms

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s