The Design and Analysis of Algorithms
Computer Science 681
Fall 2000
- 4126 Upson
- 255-0984
- eva@cs.cornell.edu
- Office Hours:
M and W after class,
-
Monday, 1:30-2:10
-
or by appointment.
Graded final, graded last problems sets, and final
grades are now available.
TA: Chaitanya Swamy
- 4157 Upson
- 255-1164
- swamy@cs.cornell.edu
- Office Hours: Tuesday 3 - 4 pm,
-
or by appointment.
Time: MWF 2:30-3:20 pm.
Place: HO 306
Topics covered so far
Notes on most topics available at request.
- greedy algorithm for the k-center problem
- min-cost spanning tree algorithms (Kruskal, Prim and Boruvka's algorithms)
- matroids, their dual and greedy algorithms
- min-cost arborescences
- shortest path with negative cycles, application to circuit retiming
- maximum flows and min cuts,
- applications of min-cut to project selection,
baseball elimination,
- Goldberg's preflow/push algorithm and excess scaling
- maximum and minimum cost matchings in bipartite graphs
- Randomization in algorithms
- Karger's min-cut algorithm
- linearity of expectation: the coupon collector problem
- Chernoff bounds
- balls and bins,
- power of two choices for balls and bins.
- Finding (almost) disjoint paths via linear programming and randomized
rounding
- Derandomization via conditional expectations
- Lov�sz Local Lemma
- Reductions from SAT to Independent set, 3 coloring, 3 dimensional matching
- The complexity classes P, NP, and co-NP. examples of what is in NP, and
co-NP including prime testing and factoring. Np-completeness, and
Cook-Levin's theorem that SAT is NP-complete.
- More NP-complete problems, and approximation algorithms:
- Knapsack and subset sum (approximation via dynamic programming);
- vertex cover (via linear programming and primal dual algorithm
- k-center and in-appoximability
- Facility location (via local search)
- Solving NP-complete problems (such as max weight independent set) on
trees, and graphs with finite tree width.
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; and fundamental techniques from
combinatorial optimization.
We will be looking at algorithms as they appear in a variety of settings;
some of these may include communication networks, on-line algorithm, computational geometry,
computational biology, 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 an undergraduate algorithms
course, such as CS 482 will
be assumed at various times.
In particular: elementary data structures and elementary algorithms, such as basic sorting and searching,
basic graph terminology, and basic graph algorithms, such as graph search, asymptotic order of growth notation,
and basic recurrence relations for analyzing algorithms. 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.
Homework
Homework will be assigned every 1-2 weeks; it
should be handed in in lecture, at the end of class,
on the day it is due.
Late homeworks will not receive credit.
(If a genuine emergency situation prevents you from handing
in an assignment on time, come talk to me and we can work
something out.)
You are expected to support the answers to the
homework with proofs.
Much of the homework will consist of questions asking
you to design algorithms for various problems.
A complete answer consists of a clear description of an algorithm
(an English description is fine), followed by an analysis
of its running time and a proof that it works correctly;
you do not need to implement the algorithm.
You should try to make your algorithms as efficient as possible.
You may discuss the homework problems
with other members of the class,
but you must write up the assignment separately
and list the names of the people with whom you discussed the assignment.
Exams
There will be a take-home midterm in the middle of the semester,
and a take-home final at the end of the semester.
Unlike the homework assignments, these must be done
completely on your own.
Grading
The homework will count for 50% of the grade,
the mid-term for 20%, and the final for 30%.
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.