Fall 2003

**You can drop the final off in my office (5153 Upson). You can leave it
under my door, if I am not here.**

FAQ for the final:

- The final above has an improved text for the hint for problem 3. The suggestion is to have each edge of the outer cycle in exactly one node of the decomposition tree.
- Problem 1c is a special case of Problem 1a. Each process is needs two SPECIFIC resources, e.g., a specific room, like HO 305, and a specific equipment.

Office Hours During the Final week

- Monday: 11-12 Tom Wexler Upson 4106
- Tuesdays 3-4 Chaitanya Swamy 5136 Upson
- Wednesday 1:30-2:30 Eva Tardos 5153 Upson
- Thursday 2-3 Tom Wexler Upson 4106
- Friday 10:30-11:30 Eva Tardos 5153 Upson

- 5153 Upson
- 255-0984
- eva at cs.cornell.edu
- Regular Office Hours: Wednesdays 1:30-2:20 and Fridays 10:30-11:30

- 5136 Upson 4106 Upson
- 255-0226 255-8758
- swamy at cs.cornell.edu wexler at cs.cornell.edu
- Regular Office Hours Tuesdays 3-4 Regular Office Hours Thursdays 2-3

Time: MWF 2:30-3:20 pm.

Place: 306 Hollister Hall

Handouts and Announcements

- Approximate syllabus
- Old announcements
- The first problem set was due Monday, September 15th. Click here if you prefer to have it in pdf format.
- The solutions for the first problem set in ps or pdf formats.
- The second problem set is due Monday, September 29th. Click here if you prefer to have it in pdf format.
- The solutions for the second problem set in ps or pdf formats.
- The third problem set was due Friday, October 10th.
- The solutions for the third problem set in ps or pdf formats.
- The take-home midterm was due Wednesday, October 22nd. Click here if you prefer to have it in pdf format. The midterm is individual work. Office hours will be changed for this week. See above for the midterm office hours.
- Solutions for midterm with grader's comments for all questions included (and is pdf format).
- The fourth problem set was due Friday November 7th. Click here if you prefer to have it in pdf format.
- The solutions for the fourth problem set in ps or pdf formats.
- The fifth problem set was due Friday November 21st. Click here if you prefer to have it in pdf format.
- The solutions for the fifth problem set in ps or pdf formats.
- The sixth problem set was due Friday December 5th. Click here if you prefer to have it in
pdf format.
- Problem 3 is asking if the randomized algorithm is a c-approximation for some constant c. For the purposes of this problem, a randomized algorithm is a c-approximation, if its expected cost is at most c time the optimal cost.

- The solutions for the sixth problem set in ps or pdf formats.

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.

The course will follow the same basic outline, with a similar set of topics as CS482. However, the actual overlap with 482 will be rather minimal, as all topics will be covered at a more advanced level.

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.

We will use two books throughout the course. The main textbook will be

- a draft of a book by Jon Kleinberg and Eva Tardos, available in the campus store as "CS682 Course Packet". This semester's version is somewhat improved from last spring, with a few extra sections. For those who already own a copy of an earlier version of this book (from CS482) we will provide handouts for the few sections new to this semester.

In the first few weeks we will follow the book:

- D. Kozen. The Design and Analysis of Algorithms. Springer, 1992.

Some other useful books are

- T. Cormen, C. Leiserson, R. Rivest, C. Stein. 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.