15-750 Graduate Algorithms (Spring 2011)
Prof. Manuel Blum

---

Books

• 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