6.854/18.415 Advanced Algorithms
Spring 2016
The design and analysis of algorithms is one of the central pillars of computer science. This course is designed to be a capstone course in algorithms, and will expose students to some of the most powerful and modern modes of algorithmic thinking ---- as well as how to apply them. We will cover a wide variety of topics including hashing, dimension reduction, max flow, linear programming, semidefinite programming, approximation algorithms, multiplicative weights, gradient descent and compressed sensing, and bring students up to the level where they can read and understand research papers.
Announcement: The course is now over, enjoy summer break!
Announcement: Youtube playlist with the videos so far (more to be uploaded soon), courtesy of Andrew Xia!
Announcement: We have set up a Piazza site for the course that you can sign up for here
Course Information
- Instructor: Ankur Moitra
- Lectures: Monday and Wednesday 1:00-2:30, 2-190
- Recitations: Friday 1:00-2:30 (but will be used only as needed)
- Prerequisites: A course in algorithms (6.046/18.410 or equivalent), probability (6.041 or 18.600) and discrete math (6.042 or 18.200). You will need to have done very well in these courses to keep up with the pace.
- TAs: Michael B. Cohen (micohen [at] mit [dot] edu), Christopher Musco, Ali Vakilian
- Office Hours:
Monday 3-5pm, Ali Vakilian (32-G614)
Tuesday 3-5pm, Michael Cohen (32-G585C)
Wednesday 3-5pm, Christopher Musco (32-G578)
Friday 10-11am, Ankur Moitra (2-472)
- Assessment: Students will be expected to solve weekly problem sets (55%), scribe a lecture and help grade a problem set (10%), and complete a final project (30%). The remainder (5%) will be based on participation.
Here is a link to the course information sheet
Homeworks
Scribing and Grading
Here is a link to the signup sheet for scribing. You can find the scribe template here. The grading sign up sheet is available here
Course Outline
Here is a tentative outline for the course. We will add links to further resources that you might find helpful as we go along.
(1) universal hashing, consistent hashing, load balancing, power of two choices
- Course notes on universal hashing and perfect hashing from UW, Princeton and MIT
- Survey paper on power of two choices (see Section 2.1), and course notes on load balancing
- Original paper on consistent hashing and random trees
(2) count-min sketch, dimension reduction, locality sensitive hashing
(3) max flow, minimum cost flow, multi-commodity flow
(4) linear programming, duality theory, ellipsoid method, approximation algorithms
(5) gradient descent, interior point methods, multiplicative weights, boosting
(6) semidefinite programming, hyperplane rounding, Grothendieck inequality, Lovasz theta function
(7) planted clique, eigenvalues of random matrices, compressed sensing, smoothed analysis
Instructor Notes
- Lecture 2: Load Balancing and Power of Two Choices [pdf]
- Lecture 3: Consistent Hashing and Random Trees [pdf]
- Lecture 4: Distinct Elements and Heavy Hitters [pdf]
- Lecture 5: Johnson Lindenstrauss Lemma and Extensions [pdf]
- Lecture 6: Nearest Neighbor Search and LSH [pdf]
- Lecture 7: Flow Decomposition and Augmenting Paths [pdf]
- Lecture 8: Capacity Scaling and Min Cost Matching [pdf]
- Lecture 9: Min Cost Flow and Goldberg-Tarjan [pdf]
- Lecture 10: Introduction to Linear Programming [pdf]
- Lecture 11: Strong Duality, Zero Sum Games and Complementary Slackness [pdf]
- Lecture 12: From Separation to Optimization and Back [pdf]
- Lecture 13: Submodular Functions and the Lovasz Extension [pdf]
- Lecture 14: Rounding Linear Programming Relaxations [pdf], courtesy of Chris Musco and Ali Vakilian
- Lecture 15: Gradient Descent and its Applications [pdf]
- Lecture 16: Interior Point Methods [pdf]
- Lecture 17: Multiplicative Weights and Zero Sum Games [pdf]
- Lecture 18: Applications of MWU: Adaboost and Max Flow [pdf]
- Lecture 19: MAXCUT and Semidefinite Programming [pdf]
- Lecture 20: Grothendieck's Inequality and the Lovasz Theta Function [pdf]
- Lecture 21: Planted Clique and Random Matrix Theory [pdf]
- Lecture 22: Compressed Sensing [pdf]
- Lecture 23: Smoothed Analysis and Knapsack [pdf]
Scribe Notes
- Lecture 1: Universal Hashing and Perfect Hashing [pdf]
- Lecture 2: Load Balancing and Power of Two Choices [pdf]
- Lecture 3: Consistent Hashing and Random Trees [pdf]
- Lecture 4: Distinct Elements and Heavy Hitters [pdf]
- Lecture 5: Johnson Lindenstrauss Lemma and Extensions [pdf]
- Lecture 6: Nearest Neighbor Search and LSH [pdf]
- Lecture 7: Flow Decomposition and Augmenting Paths [pdf]
- Lecture 8: Capacity Scaling and Min Cost Matching [pdf]
- Lecture 9: Min Cost Flow and Goldberg-Tarjan [pdf]
- Lecture 10: Introduction to Linear Programming [pdf]
- Lecture 11: Strong Duality, Zero Sum Games and Complementary Slackness [pdf]
- Lecture 12: From Separation to Optimization and Back [pdf]
- Lecture 13: Submodular Functions and the Lovasz Extension [pdf]
- Lecture 14: Rounding Linear Programming Relaxations [pdf]
- Lecture 15: Gradient Descent and its Applications [pdf]
- Lecture 16: Interior Point Methods [pdf]
- Lecture 17: Multiplicative Weights and Zero Sum Games [pdf]
- Lecture 18: Applications of MWU: Adaboost and Max Flow [pdf]
- Lecture 19: MAXCUT and Semidefinite Programming [pdf]
- Lecture 20: Grothendieck's Inequality and the Lovasz Theta Function [pdf]
- Lecture 21: Planted Clique and Random Matrix Theory [pdf]
- Lecture 22: Compressed Sensing [pdf]
- Lecture 23: Smoothed Analysis and Knapsack [pdf]
- Lecture 24: Oblivious Subspace Emebeddings [pdf]
Links
Here are links to other, similar courses: