6.854/18.415J: Advanced Algorithms (Fall 2007)

Lecture:	Monday, Wednesday, and Friday 2:30-4 in 32-144.

Units:	5-0-7 Graduate H-level
Professor:	David Karger	karger at mit edu	Office hours: By appt. in Building 32, Room G592
TA:	Katherine Lai	k_lai at mit edu	Office hours: Mondays, 4:30-6:30pm in lounge next to "Theory Lab" (32G-575), or by appointment
Course assistant:	Be Blackburn	be at theory csail mit edu	Office: Building 32, Room G692

Course announcements

Please register for the course using the following form.
In order to allow completion of a course project at the end of the semester, I hope to use our friday recitation time to present a few actual lectures early in the semester, and cancel lectures in the final weeks.

Course Overview

The need for efficient algorithms arises in nearly every area of computer science. But the type of problem to be solved, the notion of what algorithms are "efficient," and even the model of computation can vary widely from area to area. In this second course in algorithms, we will survey many of the techniques that apply broadly in the design of efficient algorithms, and study their application in a wide range of application domains and computational models. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms; network optimization; parallel algorithms; computational geometry; online algorithms; external memory, cache, and streaming algorithms; and data structures.

The prerequisites for this class are undergraduate courses in algorithms (e.g., 6.046) and discrete mathematics and probability (e.g., 6.042), in addition to mathematical maturity.

The coursework will involve problem sets and a final project that is research-oriented. For more details, see the handout on course information.

Problem Sets

Collaboration on problem sets is strongly encouraged except where explicitly forbidden. However, each person must independently write up his/her own solution, and you must list all collaborators on your problem set. You may not seek out answers from other sources without prior permission. In particular, you may not use bibles or posted solutions to problems from previous years.

Here is the handout on the final project. It is due Wednesday, December 12.

Problem Set	Due Date	Solutions	Graders/Other notes
1	Wed, Sep. 12	1	Nada Amin, Hyun Soo Kim, Anthony Kim, Debmalya Panigrahi
2	Wed, Sep. 19	2	Matt Faulkner, Polychronis Ypodimatopoulos, Issao Fujiwara
3	Wed, Sep. 26	3	Evan Jones, Zuoyu Tao, Yuetian Xu
4	Wed, Oct. 3	4	Yaodong Zhang, Jing Chen, Dahua Lin
5	Wed, Oct. 10	5	Albert Ni, Radu Berinde
6	Wed, Oct. 17	6	Wonsik Kim, Michael Forbes
7	Wed, Oct. 24	7	Thomas Belulovich, Oleg Golberg
8	Wed, Oct. 31	8	Nadia Benbernou, Ankur Moitra
9	Wed, Nov. 7	9	Kuat Yessenov, Zachary Remscrim
10	Wed, Nov. 14	10	Thomas Mildorf, Alvin Cheung
11	Wed, Nov. 21	11	Po-Ru Loh, Greg Price
12			This will be an optional problem set.

Lectures

1.	Wed, Sep. 5:	Course introduction. Fibonacci heaps. MST.(scribe notes, latex source) (raw notes on intro, Fibonacci heaps).
2.	Fri, Sep. 7:	Persistent data structures (notes, sources) (raw notes on persistent data structures).
3.	Mon, Sep. 10:	Splay trees (old scribe notes, old latex sources, raw notes ).
4.	Wed, Sep. 12:	Hashing. (old scribe notes, old latex sources) (raw notes on hashing).
	Fri, Sep. 14:	Rosh Hashana, no class
5.	Mon, Sep. 17:	Perfect Hashing. Dijkstra's Algorithm. Dial's Algorithm. Tries. (Erik's lecture notes)
6.	Wed, Sep. 19:	van Emde Boas queues. (old scribe notes, old latex sources) (raw notes on multi-level buckets, and vEB queues). Network Flows (scribe notes, latex sources, raw notes on flow). (Erik's lecture notes)
7.	Fri, Sep. 21:	Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. (see notes from previous lecture)
	Mon, Sep. 24:	student holiday, no class
8.	Wed, Sep. 26:	Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows (scribe notes, latex sources) and (scribe notes, latex sources).
	Fri, Sep. 28:	Optional Lecture: Link cut trees (raw notes)
9.	Mon, Oct. 1:	Min-Cost Flows. Definitions. Algorithms. feasible prices. complementary slackness. (scribe notes, sources, raw notes on min-cost flow).
10.	Wed, Oct. 3:	Min-Cost Flows: shortest augmenting path; pseudopolynomial solution. (scribe notes, sources).
	Fri, Oct. 5:	Optional lecture: Push Relabel Algorithm
	Mon, Oct. 8:	Columbus day, no class
11.	Wed, Oct. 10:	Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. (scribe notes, sources, raw notes on linear programming).
12.	Fri, Oct. 12:	Linear-Programming: Duality. (scribe notes, sources)
13.	Mon, Oct. 15	Linear-Programming: Complementary slackness. LP algorithms
14.	Wed, Oct. 17	Linear-Programming algorithms: Simplex, Ellipsoid. (old scribe notes with sources) (scribe notes, latex sources)..
15.	Fri, Oct. 19:	Linear-Programming Algorithms: Interior Point. NP-hard problems. Approximation Algorithms. (scribe notes, latex sources).
16.	Mon, Oct. 22:	Relative Approximations. PAS and FPAS. Scheduling.
17.	Wed, Oct. 24	Enumeration. Relaxations. 3/2-approximation for TSP. (notes, sources).
18.	Fri, Oct. 26:	ILP relaxations. Randomized Rounding. (scribe notes, sources)
19.	Mon, Oct. 29:	Fixed-parameter tractability. (scribe notes, sources) Treewidth. (notes, sources)
20.	Wed, Oct. 31:	Online algorithms: ski rental, stock market, load balancing. (notes, sources)
	Fri, Nov. 2:	[Optional]: PTAS for Geometric TSP
21.	Mon, Nov. 5	Online algorithms: paging. (notes, sources)
22.	Wed, Nov. 7	Randomized online algorithms, adversaries. k-server. (notes, sources)
23.	Fri, Nov. 9	Computational geometry: orthogonal range search, sweep algorithms (segment intersections) (notes, sources)
	Mon, Nov. 12	Veteran's day, no class
24.	Wed, Nov. 14	Computational geometry: convex hull (notes, sources)
25.	Fri, Nov. 16	Computational geometry: Voronoi diagrams (notes)
26.	Mon, Nov. 19	External memory algorithms. (raw notes)
27.	Wed, Nov. 21	Cache oblivious algorithms
	Fri, Nov. 23	Thanksgiving vacation; no class
	Mon, Nov. 26	Parallel algorithms: circuits and PRAMs. (raw notes on parallel algorithms)
	Wed, Nov. 28	Online algorithms: k-server on a line. Finance. Yao's minimax principle. (notes, sources)
	Mon, Dec. 3
	Wed, Dec. 5
	Mon, Dec. 10	Tries. Suffix trees (old scribe notes, old latex sources, raw notes).
	Wed, Dec. 12	Last day of classes

References

The Stellar website now includes some of the inaccessible papers.

Wed, Sep. 5

M. Fredman and R. Tarjan, Fibonacci heaps and their uses in improved network optimization algorithms, Journal of the ACM, 34 (1987), 596--615.

Fri, Sep. 7

H. Gabow, Z. Galil, T. Spencer, R. Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Combinatorica 6(2): 109-122 (1986).
D. Karger, P. Klein, R. Tarjan, A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees, J. ACM 42(2): 321-328 (1995).
S. Pettie, V. Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM, vol. 49, no. 1, pp.16-34, 2002.
B. Chazelle, A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity, Journal of the ACM, 47 (2000), 1028-1047.

Mon, Sep. 10

N. Sarnak and RE Tarjan. Planar point location using persistent search trees. Commun. ACM, 29:669--679, 1986.
Sleator, D. D. and Tarjan, R. E. 1985. Self-adjusting binary search trees. J. ACM 32, 3 (Jul. 1985), 652-686.

In the future:

Edward M. McCreight (1976). A Space-Economical Suffix Tree Construction Algorithm. Journal of the ACM 23 (2): 262–272
Robert B. Dial, Algorithm 360: shortest-path forest with topological ordering. Communications of the ACM, Vol. 12, 1969.
P. van Emde Boas, R. Kaas, E. Zijlstra, Design and implementation of an efficient priority queue