18.415J/6.854J Advanced Algorithms (Fall 2001)
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.)
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.
- 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.
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.
- 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
Requirements.
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
Textbook.
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):
- 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.
- 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.