Fall 2002

- 4126 Upson
- 255-0984
- eva@cs.cornell.edu
- Office Hours: M and W after class, or Thursday 11-12
- or by appointment.

- 5136 Upson
- 255-0226
- swamy@cs.cornell.edu
- Regular Office Hours: 11-12 on Tuesdays. He also also happy to answer email, and set up special appointments.

Office hours for the week of the final:

Monday 1-2: Eva

Tuesday 11-12: Swamy

Wednesday 10:30-11:30 Eva

Thursday 11-12 Swamy and 3-4 Eva

Friday 10-11 Eva

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

Place: Upson 111

- The take-home final is due Friday December 13th 4pm. The final requires individual work.
- Clarification for Problem 3: To be polynomial, it should be polynomial in the number of jobs, number of machines, and the log of the max time T. For this problem, polynomial in n and m is also possible (where dependence on T is just that you need to write such numbers down). Solutions that are polynomial in n, m and T (that is only pseudo-polynomial) will be worth very high partial credit.
- Clarification for Problem 4: May assume edge-costs are nonnegative, and the maximum degree of the tree is bounded.
- Clarification for Problem 5: For those of you
who want to solve this problem without using the e
^{x}~1+x approximation, you need to avoid having to estimate 1+x, as the bound of e^{x}<1+2x, I suggested on the test is not strong enough. - Clarification for Problem 1c: The resources in each type are still different: a process can request a SPECIFIC room and a SPECIFIC piece of equipment.
- More clarification for Problem 4: A cut is a partition of the nodes into two sides A and B. The two sides do not have to be connected.

- Problem set 6 was due on Friday December 6th. Here are the solutions.
- Problem set 5 was due on Friday November 22nd. Here are the solutions.
- Problem set 4 was due on Friday November 8th. Here are the solutions.
- Here are the solutions for the midterm with some comments.
- Here are some practice questions that may help you prepare for the midterms.
- Problem set 3 (due Oct 18th). Here are the solutions.
- Problem set 2 (due Oct 4th). Here are the solutions.
- Problem set 1 (due Sept 20th). Here are the solutions.

Click here for old announcements.

Handouts from the upcoming Algorithms book by Kleinberg and Tardos can be picked up from Esha Mollette in 4119 Upson. Here is a list of the handouts we had.

- The CS 482 book is now available in the campus store under the name of "CS681 course packet"
- Min-Cost Arborescences
- Preflow-Push Maximum Flow Algorithm
- Project Selection Problem
- Minimum Cost Perfect Matchings
- RNA Secondary Structure: Dynamic Programming Over Intervals
- Dynamic Programming and the Shortest Path Problem
- Tree Decompositions
- The Boykov, Veksler, and Zabih paper using graphs cuts for stereo matching.
- Karger, Klein, and Tarjan MST Paper
- Approximate syllabus

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.

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.

The textbook is

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

Some other useful books are

- a draft of a book by Jon Kleinberg and Eva Tardos, which we developed while teaching the last few years of CS 482. Available in the campus store after September 16th.
- 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.