Lecture:  Monday, Wednesday, and Friday 2:304 in 32144.  
Units:  507 Graduate Hlevel  
Professor:  David Karger  karger at mit edu  Office hours: By appt. in Building 32, Room G592  
TA:  Punyashloka Biswal  punya at mit edu  Office hours: Mondays, 6pm onwards in lounge next to "Theory Lab" (32G575)  
Course assistant:  Be Blackburn  be at theory csail mit edu  Office: Building 32, Room G692  
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 researchoriented. For more details, see the handout on course information.
Here is some information about the final project.
Problem Set 1  Due Wed, Sep. 13  Solutions 
Problem Set 2  Due Wed, Sep. 20  Solutions 
Problem Set 3  Due Wed, Sep. 27  Solutions 
Problem Set 4  Due Wed, Oct. 4  Solutions 
Problem Set 5  Due Fri, Oct. 13 (note unusual day)  Solutions 
Problem Set 6  Due Wed, Oct. 18  Solutions 
Problem Set 7  Due Wed, Oct. 25  Solutions 
Problem Set 8  Due Wed, Nov. 1  Solutions 
Problem Set 9  Due Wed, Nov. 8  Solutions 
Problem Set 10  Due Wed, Nov. 15  
Problem Set 11  Due Wed, Nov. 22 
The dates are fixed! Props to David Glasser for helping me find the correct dates for various things. —TA
1.  Wed, Sep. 6:  Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps).  
2.  Fri, Sep. 8:  MST. Persistent data structures (notes, sources) (raw notes on persistent data structures).  
3.  Mon, Sep. 11:  Splay trees (old scribe notes, old latex sources, raw notes ).  
4.  Wed, Sep. 13:  Splay trees. Suffix trees (old scribe notes, old latex sources, raw notes). Tries.  
5.  Fri, Sep. 15:  Suffix trees. Tries. Dial's Algorithm.  
6.  Mon, Sep. 18:  Dijkstra's Algorithm. Van Emde Boas Queues
(old scribe
notes, old latex
sources) (raw notes on multilevel buckets, and vEB queues). 

7.  Wed, Sep. 20:  Van Emde Boas Queues (cont.). Hashing (old scribe notes, old latex sources) (raw notes on hashing).  
8.  Fri, Sep. 22:  2Level Hashing. Network Flows (scribe notes, latex sources, raw notes on flow).  
9.  Wed, Sep. 27:  Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. (see notes from previous lecture)  
10.  Fri, Sep. 29:  Reductions between Flow Problems.
Bipartite Matching.
Shortest Augmenting Path.
Blocking Flows (scribe notes, latex sources). 

11.  Wed, Oct. 4:  Blocking Flows (scribe notes, latex sources).  
12.  Fri, Oct. 6:  MinCost Flows: feasible prices. (scribe notes, sources, raw notes on mincost flow).  
13.  Wed, Oct. 11:  MinCost Flows: complementary slackness, pseudopolynomial
solution. (scribe notes, sources). 

14.  Fri, Oct. 13:  Linearprogramming: definitions: canonical and standard forms, feasibility and optimization. (scribe notes, sources, raw notes on linear programming).  
15.  Mon, Oct. 16  LinearProgramming: structure of Optima. (scribe notes, sources)  
16.  Wed, Oct. 18  LinearProgramming: weak duality.  
17.  Fri, Oct. 20:  LinearProgramming. Strong Duality. (scribe notes, sources).  
18.  Mon, Oct. 23:  LinearProgramming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (old scribe notes with sources).  
19.  Wed, Oct. 25  LinearProgramming. Algorithms: Interior Point. NPhard problems. (scribe notes, latex sources).  
20.  Fri, Oct. 27:  Approximation Algorithms. (scribe notes, latex sources).  
21.  Mon, Oct. 30:  4/3approximation for TSP. Scheduling. (notes, sources)  
22.  Wed, Nov. 1:  Scheduling. ILP relaxations. (scribe notes, sources)  
Fri, Nov. 3:  [Optional] Euclidean TSP.  
23.  Mon, Nov. 6  Fixedparameter tractability. (scribe notes, sources)  
24.  Wed, Nov. 8  More Fixedparameter tractability. Treewidth. (notes, sources)  
25.  Mon, Nov. 13  Online algorithms: ski rental, load balancing. (notes, sources)  
26.  Wed, Nov. 15  Online algorithms: paging. Randomized online algorithms, adversaries. (notes, sources)  
27.  Fri, Nov. 17  Online algorithms: kserver. Yao's minimax principle. (notes, sources)  
28.  Mon, Nov. 20  Computational geometry: orthogonal range search, sweep algorithms (segment intersections) (notes, sources)  
29.  Wed, Nov. 22  Computational geometry: convex hull (notes, sources)  
30.  Mon, Nov. 27  [Optional] Computational geometry: Voronoi diagrams (notes, sources)  
31.  Wed, Nov. 29  [Optional] Finish computational geometry. External memory algorithms. (raw notes)  
32.  Wed, Dec. 6  [Optional] External memory continued.  
33.  Mon, Dec. 11  [Optional] External memory: cacheoblivious algorithms. Parallel algorithms: circuits and PRAMs. (raw notes on parallel algorithms) 
Lecture 1.  Wed, Sep. 7:  Course introduction. Fibonacci heaps (scribe notes, latex source) (raw notes on intro, Fibonacci heaps). 
Lecture 2.  Fri, Sep. 9:  MST. Persistent data structures (scribe notes, latex sources) (raw notes on persistent data structures). 
Lecture 3.  Mon, Sep. 12:  Splay trees (scribe notes, latex sources). 
Lecture 4.  Wed, Sep. 14:  Splay trees. Suffix trees (scribe notes, latex sources). Tries. 
Lecture 5.  Fri, Sep. 16:  Suffix trees. Tries. Dial's Algorithm. 
Lecture 6.  Wed, Sep. 21: 
Dijkstra's Algorithm. Van Emde Boas Queues (scribe notes, latex sources) (raw notes on multilevel buckets, and vEB queues). 
Lecture 7.  Fri, Sep. 23:  Van Emde Boas Queues (cont.). Hashing (scribe notes, latex sources) (raw notes on hashing). 
Lecture 8.  Mon, Sep. 26:  2Level Hashing. Network Flows (scribe notes, latex sources). 
Lecture 9.  Wed, Sep. 28:  Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling. 
Lecture 10.  Fri, Sep. 30:  Reductions between Flow Problems. Bipartite Matching. Shortest Augmenting Path. Blocking Flows (scribe notes, latex sources). 
Lecture 11.  Mon, Oct. 3:  Blocking Flows (scribe notes, latex sources). 
Recitation 1.  Wed, Oct. 5:  Dynamic Trees. PushRelabel MaxFlow Algorithm. 
Lecture 12.  Fri, Oct. 7:  MinCost Flows (scribe notes, latex sources). 
Lecture 13.  Wed, Oct. 12:  MinCost Flows. Linear Programming. (scribe notes, latex sources). 
Lecture 14.  Fri, Oct. 14:  LinearProgramming. Structure of Optima. Weak Duality. (latex sources). 
Lecture 15.  Mon, Oct. 17:  LinearProgramming. Strong Duality. (latex sources). 
Recitation 2.  Wed, Oct. 19:  Simplex 
Lecture 16.  Fri, Oct. 21:  LinearProgramming. Complementary Slackness. Algorithms: Simplex, Ellipsoid. (latex sources). 
Lecture 17.  Mon, Oct. 24:  LinearProgramming. Algorithms: Interior Point. NPhard problems. (latex sources). 
Lecture 18.  Fri, Oct. 28:  Approximation Algorithms. (latex sources). 
Lecture 19.  Mon, Oct. 31:  4/3approximation for TSP. (latex sources). 
Lecture 20.  Wed, Nov. 2:  Relaxations. Directed TSP. (latex sources). 
Lecture 21.  Fri, Nov. 4:  Randomized rounding, Chernoff Bound, Fixed parameter tractability, Kernelization (latex sources). 
Lecture 22.  Wed Nov. 09:  Online algorithms (ski rental, load balancing, paging) (latex sources). 
Lecture 23.  Mon Nov. 14:  Randomized online algorithms (adversaries, Fiat's marking algorithm, potential functions, Yao's minimax principle) (latex sources). 
Lecture 24.  Wed Nov. 16:  kserver problem, doublecoverage algorithm, Computational geometry intro (orthogonal range search) (latex sources). 
Lecture 25.  Fri Nov. 18:  Sweep algorithms (convex hull, segment intersection, Voronoi diagrams) (latex sources). 
Lecture 26.  Mon Nov. 21: 
Sweep algorithms (Voronoi diagrams). Randomized Incremental Constructions. Backwards Analysis. Linear Programming in Fixed Dimension. 
Lecture 27.  Mon Nov. 28: 
(Optional material)
External memory algorithms. 
Lecture 28.  Wed Nov. 30: 
(Optional material)
Cache oblivious algorithms: matrix multiplication, linked lists, median. 
Lecture 29.  Fri Dec. 2: 
(Optional material)
Cache oblivious algorithms: Search. Streaming Model. 
Scribing: Here is the LaTeX style file for scribing, and an example use of it.