The Design and Analysis of Algorithms

Computer Science 681
Fall 1997



kleinber@cs.cornell.edu

5134 Upson.
255-3600.
Office Hours: Monday and Wednesday after class, and by appointment.


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

Some other useful books are