Upson 111A.
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.