6.854/18.415J: Advanced Algorithms (Fall 2011)

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

Units:	5-0-7 Graduate H-level
Professor:	David Karger	karger at mit edu	Office hours: By appt. in Building 32, Room G592
TA:	Travis Hance	tjhance at mit.edu	Office hours: not any more in this semester
	Morteza Zadimoghaddam	morteza at mit.edu	Office hours: not any more in this semester
	Zeyuan Allen Zhu	zeyuan at mit.edu	Office hours: not any more in this semester
			Please come back frequently to check the office hour updates.
Course assistant:	Marcia Davidson	marcia@csail.mit.edu	Office: Building 32, Room 32-G764 and 32-G434

Course announcements

Final project submission rules:
- In-class peer review of drafts on Friday Dec 9, 230-4pm. Students are required to come to class on this day.
  - Please bring at least 4 printed copies of your reasonably well-written draft for another group of students to review.
- Final version on last "class" day, Wednesday Dec 14, 4pm.
A draft description of the course project is available.
We deduct an additive 20% for homework handed in before Friday class, and 50% for homework handed in before Monday class. No points are given once the Monday class begins.
Late solutions are only allowed to be submitted via emails from now on. Please send your (possibly-scanned) solution for each problem to the corresponding grader directly, but not the course staff.
- Emails for all students in 6.854 can be found via a secret file that Zeyuan has sent twice to the class.
- Students who submit late solutions as late as Monday 2:30pm might not receive graded solutions with feedbacks since the graders have already turned in the solutions, but the scores will be recorded.
Please send your questions to to removed@csail.mit.edu.
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

Homework is due at the beginning of class. We'll have boxes or piles for dropping them off at the back of the room. Those boxes will be collected a few minutes in, and homework arriving after will be considered late.
We deduct 20% for homework handed in before Friday class, and 50% for homework handed in before Monday class. No points are given once the Monday class begins.
Write each problem on a separate sheet of paper.
Collaboration is strongly encouraged except where explicitly forbidden. However, each person must independently write up his/her own solution, and you must list all collaborators for each problem 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.
Each student is required to grade (at least but hopefully) one problem in the semester. We will have a TA-supervised grading session each week. This session is used to make sure that the graders fully understand the solution, while they can grade the problems at home after this session.

Problem Set	Due Date	Solutions	Grading Supervisor	Graders
PS 1	Wed, Sep. 14	SOL 1	Zeyuan+Travis	Victor+Angela(P1), Claudio+Christos(P2), Henry+Luis (P3), Cosmin+Liz(P5)
PS 2	Fri, Sep. 23	SOL 2	Zeyuan	Lekha K (P1), Keshav Puranmalka + Jing Jian (P2), Cynthia Sung + Leilani Battle (P3), Tom Lieber (P4), Usman Masood (P5)
PS 3	Wed, Sep. 28	SOL 3	Zeyuan	Yanping Chen + Haitao Mao (P1), Ludwig Schmidt + Sepideh Mahabadi (P2), Tahin Syed + Tina S Hsu (P3), Mohammad Bavarian (P4), Brian T Basham (P5)
PS 4	Wed, Oct. 5	SOL 4	Morteza	Adam Bouland + Katie Everett (P1), Abhishek Sarkar (P2), Jason Boggess (P3), Justin Holmgren (P4), Manasi Vartak (P5)
PS 5	Wed, Oct. 12	SOL 5	Morteza	Salman Ahmad (P1), Adrian Vladu (P2), Hao-Yu Wu + Boon Teik Ooi (P3), Matthew Ryan Coudron (P4), Madars Virza (P5)
PS 6	Wed, Oct. 19	SOL 6	Morteza	Pavel Panchekha (P1), Deniz Yorukoglu (P2), Phil Root (P3), Tristan Josef Naumann (P4), Chun-Kai Wang (P5), Edouard Desire Godfrey (P6)
PS 7	Wed, Oct. 26	SOL 7	Morteza	Jian Huang (P1), Jiuchen Shi (P2), Leslie C Dewan (P3), Jonathan T Schneider (P4), Drew E Wolpert (P5)
PS 8	Wed, Nov. 2	SOL 8	Zeyuan	Benjamin Yang (P1), Ioana Ivan (P2), David Benjamin (P3), Aaron Sidford (P4), Eric Shyu (aggregator)
PS 9	Wed, Nov. 9	SOL 9	Morteza	Tatsu Hashimoto + Fredrik Kjolstad (P1), Jin Hao Wan + Chiu Wai Wong (P2), Timothy Chu + Sanja Popovic (P3), Sam Fingeret + Yotam Aron (P4), Anand Oza + Kendell Clement (P5)
PS 10	Wed, Nov. 16	SOL 10	Morteza	Qinxuan Pan (P1), Vlad Firoiu (P2), Will Hasenplaugh (P3), Donglai Wei (P4), Cesar Cuenca (P5)
PS 11	Wed, Nov. 23	SOL 11	Morteza	Benjamin Holmes (P1), Rafael Oliveira (P2), Fulton Wang (P3), Andrei Frimu (P4), Ruben Perez (P5)

Enter hours here
Check if you have submitted your hours yet

Lectures

Be aware that the scribe notes are all very old, and do not necessarily affect all actual details that happened in this year's class. Please use the raw notes as the most authentic references. Please report to us if you see an invalid link.

#	Date	Topic	Raw Notes	Scribe Notes
1.	Wed, Sep. 7:	Course introduction. Fibonacci heaps. MST.	nb nb	nb
2.	Fri, Sep. 9:	Persistent data structures.	nb	nb
3.	Mon, Sep. 12:	Splay trees.	nb	nb
4.	Wed, Sep. 14:	Dial's Algorithm. Tries. Multi-level buckets. Van Emde Boas queues.	nb	nb (vEB)
5.	Fri, Sep. 16:	Hashing. Universal Hashing. Perfect Hashing.	nb	nb
6.	Mon, Sep. 19:	Network Flows. Augmenting Paths. Maximum Augmenting Path.	nb(maxflow)	nb
	Wed, Sep. 21:	No class
7.	Fri, Sep. 23:	Network Flows: Scaling. Shortest Augmenting Path. Blocking Flows.	See above.	nb
8.	Mon, Sep. 26:	Network Flows: More Blocking Flows. Definitions for Min-Cost Flows.	nb(mincostflow)	nb(blocking) nb(mincost)
9.	Wed, Sep. 28:	Min-Cost Flows. Definitions. Algorithms. feasible prices. complementary slackness. Min-Cost Flows: shortest augmenting path; pseudopolynomial solution.	See above.	nb
OPT	Fri, Sep. 30:	Optional lecture: push-relabel algorithms (Morteza)
10.	Mon, Oct. 3:	Linear-programming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima.	nb	nb
11.	Wed, Oct. 5:	Linear-Programming: Duality Theory.		Duality Slackness
12.	Fri, Oct. 7:	Linear-Programing: Duality Applications.		See above
	Mon, Oct. 10:	Columbus day, no class
13.	Wed, Oct. 12:	Linear Programming Algorithms: Simplex and Ellipsoid
OPT	Fri, Oct. 14:	Optional lecture: link-cut trees (Zeyuan)	nb
14.	Mon, Oct. 17	Linear-Programming Algorithms: Interior Point. NP-hard problems. Approximation Algorithms.	nb	nb
15.	Wed, Oct. 19	Relative Approximations. PAS and FPAS. Scheduling.
OPT	Fri, Oct. 21:	Optional lecture: Interior Point Method (Zeyuan)	nb
	Mon, Oct. 24:	No class
16.	Wed, Oct. 26:	Fixed-parameter tractability. (Erik Demaine)	nb	nb
17.	Fri, Oct. 28:	SAT is FPT for tree width. Relaxations. 3/2-approximation for TSP.	nb	nb
18.	Mon, Oct. 31:	ILP relaxations. Randomized Rounding.		nb
19.	Wed, Nov. 2:	Online Algorithms: ski rental, load balancing	nb	nb
20.	Fri, Nov. 4:	Online algorithms: linked lists, paging.		nb
21.	Mon, Nov. 7	Randomized online algorithms, adversaries. k-server. (notes, sources)
22.	Wed, Nov. 9	Computational geometry: orthogonal range search	nb
	Fri, Nov. 11	No class: Veteran's day	nb	nb
23.	Mon, Nov. 13	Computational geometry: convex hull, sweep line, Voronoi diagrams (Fortune's algorithm animation)	See above	nb(Sweep) nb(Voronoi)
24.	Wed, Nov. 15	External memory algorithms.	nb	nb
25.	Fri, Nov. 17	Cache oblivious algorithms.
26.	Mon, Nov. 20	Parallel algorithms (last day of class)	nb

Other Material

XX.		Optional Lecture: Link cut trees (raw notes)
XX.		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).

References

Wed, Sep. 7

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

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

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

Wed, Sep. 14

Boris V. Cherkassky, Andrew V. Goldberg and Craig Silverstein. Buckets, heaps, lists, and monotone priority queues. SODA 1997.
Van Emde Boas. Design and Implementation of an efficient priority queue. Math Syst. Th. 10 (1977)