BU CLA CS 530: Analysis of Algorithms

Fall 2017

A Short Bibliography

Books on algorithms come in different flavors. Some emphasize design aspects, some emphasize analysis aspects, and some try to mix the two. From a different perspective, some books organize the material by design and/or analysis methods, others organize it by application areas. In any case, no single book can do justice to all aspects of this area of computer science: The design and analysis of algorithms has simply mushroomed over the last 30 years, remains a thriving area of research, and has not yet completely stabilized into a unified core of basic topics (as, for example, Calculus, or Linear Algebra, or Introductory First-Order Logic).

[L] The Design and Analysis of Algorithms,
by Anany Levitin, 2012.
[KT] Algorithm Design,
by Kleinberg and Tardos, 2005.

Recently used as the main CS 330 textbook.

[PV] Algorithms,
by Papadimitriou and Vazirani, 2006.
[A] The Design and Analysis of Parallel Algorithms,
by S.G. Akl, Prentice Hall, 1989.

[AHU] The Design and Analysis of Computer Algorithms,
by A.V. Aho, J.E. Hopcroft, and J.D. Ullman, Addison-Wesley, 1974.

Standard graduate text on the subject for many years. I was taught from it. The style is dense in many places, and not as easy to read as some of the more recent books, even at the same level.

[BB] Algorithmics,
by G. Brassard and P. Bratley, Prentice Hall, 1988.

A very nice text on algorithms, with emphasis on design techniques. Used previously at BU as the required book in CS530, instead of [CLR].

[GJ] Computers and Intractability,
by M.R. Garey and D.S. Johnson, W.H. Freema, 1979.

Standard reference on NP-completeness. Pleasant to read.

[K] The Art of Computer Programming, Vols 1, 2, 3,
by D. Knuth, Addison Wesley, 1973.

Three classic references. The material is a bit dated. Be warned that the style is dense, solutions for many of the exercises are no more than hints, and an assembly-level pseudocode does not make the algorithms any easier to understand.

[MR] Randomized Algorithms,
by R. Motwani and P. Raghavan, Cambridge Univ Press, 1995.

A very attractive, very well written, text on randomized algorithms. It contains extensive and useful historical notes on the topics it covers.

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

A very readable text on approximations algorithms for core combinatorial problems. A good choice of topics, written concisely and somewhat densely, but worth reading.

[PS] Combinatorial Optimization: Algorithms and Complexity,
by C. Papadimitriou and K. Steiglitz, Prentice Hall, 1982.

A thorough and well written text on combinatorial algorithms.

Assaf Kfoury
Created: 96.02.11
Modified: Most recently in 2014 and 2015 and 2017 by Steve Homer