BU CLA CS 530: Analysis of Algorithms

Spring 1999

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).

[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] Fundamentals of Algorithmics,
by G. Brassard and P. Bratley, Prentice Hall, 1996.

A very nice text on algorithms, with emphasis on design techniques. I used it in CS330 in the Spring of 1997, leaving out material that is more appropriate for a 500-level course (a list of errata is available). An earlier edition (1988) was once used 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.

[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: 99.01.06