Lecture: |
Monday and Wednesday 2:30-4:00PM in
4-370
(schedule change)
| |

Instructor: |
Michel Goemans
goemans@math.mit.edu
| office: 2-351 (x3-2688) |

TA: |
Mohammad Mahdian
mahdian@math.mit.edu
| office: 2-331 (x3-5029), office hours: Tu 10-11AM and F 2-3PM |

Jan Vondrak vondrak@math.mit.edu
| office: 2-094 (x2-1199), office hours: Th 11AM-12PM and Th 4-5PM | |

This is a graduate course on the design and analysis of algorithms, covering several advanced topics not studied in typical introductory courses on algorithms. Prerequisites include "Introduction to algorithms" (at the level of 18.410J/6.046J), linear algebra (at the level of 18.06 or 18.700), and mathematical maturity (since we'll be doing a lot of correctness proofs). The course is especially designed for doctoral students interested in theoretical computer science.

We will now meet from 2:30 to 4:00 (instead of 3:30 to 5:00) still in room 4-370.

Check back often for updates. (Additions will be marked for 1 week or until the due date.)

- 12/17/01: PS6 solutions.
- 12/17/01: Scribe notes for the lecture on 12/03/01 (lecture 21).
- 12/17/01: Scribe notes for the lecture on 11/28/01 (lecture 20).
- 12/17/01: Scribe notes for the lecture on 11/26/01 (lecture 19).
- 12/11/01: PS5 solutions.
- 12/11/01: PS4 solutions.
- 12/4/01: Scribe notes for the lecture on 11/21/01 (lecture 18).
- 11/30/01: Scribe notes for the lecture on 11/19/01 (lecture 17).
- 11/21/01: Scribe notes for the lecture on 11/07/01 (lecture 16).
- 11/21/01: Scribe notes for the lecture on 11/05/01 (lecture 15).
- 11/11/01: Scribe notes for the lecture on 10/31/01 (lecture 14).
- 11/11/01: Scribe notes for the lecture on 10/29/01 (lecture 13).
- 11/6/01: Scribe notes for the lecture on 10/24/01 (lecture 12).
- 11/6/01: Solutions for PS3
- 10/31/01: Scribe notes for the lecture on 10/22/01 (lecture 11).
- 10/29/01: Scribe notes for the lecture on 10/17/01 (lecture 10).
- 10/29/01: Scribe notes for the lecture on 10/15/01 (lecture 9).
- 10/29/01: Scribe notes for the lecture on 10/10/01 (lecture 8).
- 10/24/01: Splay tree animations. Another one. Yes another one .
- 10/15/01: Scribe notes for the lecture on 10/3/01 (lecture 7).
- 10/15/01: PS3 handed out in class on 10/22/01.
- 10/15/01: Solutions for PS2.
- 10/10/01: Scribe notes for the lecture on 10/1/01 (lecture 6).
- 10/3/01: How to start the interior-point algorithm seen in lecture.
- 10/3/01: PS2 handed out in class on 10/1/01.
- 10/2/01: Solutions for PS1
- 10/1/01: Scribe notes for the lecture on 9/26/01 (lecture 5).
- 10/2/01: Scribe notes for the lecture on 9/24/01 (lecture 4).
- 9/26/01: Scribe notes for the lecture on 9/19/01 (lecture 3).
- 9/20/01: Scribe notes for the lecture on 9/10/01 (lecture 2).
- 9/17/01: PS1 handed out in class on 9/10/01.
- 9/10/01: Information on scribing.
- 9/10/01: Input file preamble.tex for scribing.
- 9/5/01: Course information handout.

- 12/3/01: PS6 is out and due in lecture on 12/12/01.
- 11/30/01: PS5 is out and due in lecture on 12/5/01.
- 10/29/01: PS4 is now available and due in lecture on 11/07/01.
- 10/15/01: PS3 was handed out and due in lecture on 10/22/01.
- 10/1/01: PS2 was handed out in lecture on 10/1/01 and is due on 10/10/2001.
- PS1 was handed out in lecture on 9/10/2001 and due on 9/19/2001 in lecture. The due date is extended to 9/24/01 and late problem sets will be accepted until Monday 10/1/01.

Here is a preliminary and non-exhaustive list of topics we will be or might be covering. This is subject to change at any time, partly based on the audience.

- Linear Programming.
- geometry, Farkas' lemma, strong duality
- complexity
- interior-point algorithms
- ellipsoid algorithm and optimization vs. separation
- extension to conic programming

- Network Flows.
- maximum flows, min-cost flows
- cycle cancelling algorithms
- strongly polynomial-time analysis
- minimum cuts without flows

- Approximation Algorithms.
- limits to approximability
- basic techniques and vertex cover
- primal-dual technique
- semidefinite programming
- multicommodity cut via embedding metric spaces
- approximation scheme for Euclidean TSP

- Planarity Testing of Graphs.
- Number-Theoretic Algorithms.
- primality testing
- Diophantine approximations
- basis reduction for lattices

- Data Structures.
- van Emde Boas queues
- splay trees
- dynamic trees

There will be biweekly problem sets and students will also be expected to take turns to scribe lecture notes. It is thanks to the scribes that we can have a good set of lecture notes with many details. More on scribing is available in the course information handout to be distributed in the first lecture.

Lecture notes from several years ago when I last taught advanced algorithms are available. However, there will be new topics not covered before and even the results that were covered before will sometimes be covered differently. Still, this will be a good starting point. Notes are available on

- linear programming,
- network flows, a simple mincut algorithm,
- approximation algorithms, Euclidean TSP approximation scheme, and
- lattices.

- Linear Programming.
- Schrijver, A., Theory of Linear and Integer Programming, Wiley (Chichester, 1986).
- For the ellipsoid, 3 references are (the latter 2 contain a few
mistakes):
- Groetschel, Lovasz and Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988. Chapter 3. [The standard reference on the ellipsoid. The most complete and precise description.]
- Chvatal. Linear Programming. Freeman and co, 1983. Appendix. [An easy to read description without all the details.]
- Korte and Vygen. Combinatorial Optimization. Springer-Verlag, 2000. Chapter 4. [A detailed description.]

- For interior-point algorithms, a good reference is: C. Roos, T. Terlaky, J.-Ph. Vial. Theory and Algorithms for Linear Optimization. An interior Point Approach. Wiley, 1997.

- Network Flows.
- Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

- Data structures.
- For both splay trees and dynamic trees: Sleator and Tarjan. Self-adjusting binary search trees Journal of the ACM, vol 32, 652--686 (1985).

- Approximation Algorithms.
- Vijay Vazirani. Approximation Algorithms. Springer-Verlag, 2001.
- D.Hochbaum, editor. Approximation Algorithms for NP-hard Problems. PWS Publishing Company, 1997.
- Sanjeev Arora's Euclidean TSP paper.

- Number-Theoretic Algorithms.
- L. Lov'asz, An Algorithmic Theory of Numbers, Graphs, and Convexity. CBMS Regional Conference Series in Applied Mathematics (SIAM, 1986).
- E. Bach, J. Shallit, Algorithmic Number Theory, Vol. I, MIT Press, Cambridge, MA, 1996.