18.415J/6.854J Advanced Algorithms (Fall 2001)

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.

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

General Info.

Class list.

9/18/01: If you want to be added or removed from the class list, send e-mail to mahdian@math.mit.edu

Handouts and links.

Problem sets.

Course outline.

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.


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.

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


There is no textbook required for the course. Lecture notes and scribe notes will be available and whenever appropriate a paper or survey paper will be either distributed, or available from the course homepage, or a reference indicated in the scribe notes. Reference textbooks for each topic are (more to be added):