The Design and Analysis of Algorithms
Computer Science 681
Fall 1997
4132 Upson.
- 255-1179.
- Office Hours: Monday and Wednesday 1 - 2 pm.
Overview
CS 681 is an introductory graduate-level course on algorithms.
Although we will be covering a number of current research topics in
the design and analysis of algorithms, the primary focus will be on
principles in algorithm design that are conceptually clean and
broadly applicable. Our goal is to make the course both accessible
and useful for graduate students in any area that makes use of
algorithms.
Some of the broad areas we will be considering are: basic graph
algorithms and data structures from a current perspective; the use
of randomization; intractable problems and the design of
approximation algorithms; fundamental techniques from combinatorial
optimization; and on-line algorithms. We will be looking at
algorithms as they appear in a variety of settings; some of these
may include computational geometry, computational biology,
cryptography, communication networks, and the design of
error-correcting codes.
Pre-requisites
There is no specific course pre-requisite, though knowledge of some
material at the level of CS 410 will be assumed at various times.
In particular: elementary data structures, basic sorting and
searching, basic graph terminology, asymptotic order of growth
notation, and basic recurrence relations for analyzing algorithms.
These are nicely summarized near the beginnings of books such as
Cormen-Leiserson-Rivest and Aho-Hopcroft-Ullman (see below). It
will also be helpful to have seen basic definitions of probability
(e.g. random variables and their expectations), as well as some
very basic linear algebra.
Books
The textbook is
- D. Kozen. The Design and Analysis of Algorithms. Springer,
1992.
Some other useful books are
- T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms.
McGraw-Hill, 1990.
- A. Aho, J. Hopcroft, J. Ullman. The Design and Analysis of
Computer Algorithms. Addison-Wesley, 1974.
- M. Garey and D. Johnson. Computers and Intractability: A Guide
to the Theory of NP-Completeness. W.H. Freeman, 1979.
- R. Tarjan. Data Structures and Network Algorithms. SIAM
Regional Conference Series in Applied Mathematics 44, 1983.
- R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge
University Press, 1995.
- S. Even. Graph Algorithms. Computer Science Press, 1979.
- C. Papadimitriou, K. Steiglitz. Combinatorial Optimization --
Algorithms and Complexity. Prentice-Hall, 1982.