6.854/18.415J: Advanced Algorithms (Fall 2009)

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:	Aleksandar Zlateski	zlateski at mit edu	Office hours: Mondays, 4:30-6:30pm in lounge next to "Theory Lab" (32G-575), or by appointment
TA:	Bernhard Haeupler	haeupler at mit edu	Office hours: Mondays, 5:30-7:30pm in lounge next to "Theory Lab" (32G-575)
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 (HTML).

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.

Problem Set	Due Date	Solutions	Graders
1	Wed, Sep. 16	1	TBA
2	Wed, Sep. 30	2	TBA
3	Wed, Oct. 7	3	TBA
4	Wed, Oct. 14	4	TBA
5	Wed, Oct. 21	5	TBA
6	Wed, Oct. 21	6	TBA
7	Wed, Oct. 28	7	TBA
8	Fri, Nov. 6	8	TBA
9	Fri, Nov. 13	9	TBA
10	Wed, Nov. 18	10	TBA
11	Wed, Nov. 24		TBA

Lectures

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

Tentative Schedule

25.		Parallel algorithms: circuits and PRAMs. (raw notes on parallel algorithms)
26.		Online algorithms: k-server on a line. Finance. Yao's minimax principle. (notes, sources)
		Tries. Suffix trees (old scribe notes, old latex sources, raw notes).
	Wed, Dec. 16	Last day of classes

References

The Stellar website now includes some of the inaccessible papers.

Wed, Sep. 9

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. 11

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. 14

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.