Design and Analysis of Algorithms: Course Notes

Author : Samir Khuller, Dept. of Computer Science, University of Maryland
Publication Date : August 2003

Excerpts from the Notes:

This is a compilation of lecture notes, used by the author to teach CMSC 651: Design and Analysis of Algorithms at Dept. of Computer Science, University of Maryland. This course has been taught several times and each time the coverage of the topics differs slightly.

The notes will cover many different topics. Readers will start out by studying various combinatorial algorithms together with techniques for analyzing their performance. Readers will also study linear programming and understand the role that it plays in the design of combinatorial algorithms. Finally readers will go on to the study of NP-completeness and NP-hard problems, along with polynomial time approximation algorithms for these hard problems.

The material for the first few weeks was taken primarily from the textbook on Algorithms by Cormen, Leiserson and Rivest. In addition, the author have used material from several other books such as the Combinatorial Optimization book by Papadimitriou and Steiglitz, as well as the Network Flow book by Ahuja, Magnanti and Orlin and the edited book on Approximation Algorithms by Hochbaum. A few papers were also covered, containing some very important and useful techniques that should be in the toolbox of every algorithms researcher.

View / Download Design and Analysis of Algorithms: Course Notes