15-850: Advanced Algorithms, Spring 2017

Description

An advanced course on the design and analysis of algorithms, more specialized than the Graduate Algorithms course 15-750.

The current list of topics are:

  1. MSTs. Recap Prim/Kruskal/Boruvka, an $O(m \log^* n)$ time algorithm, a randomized linear-time algorithm, MSTs in directed graphs
  2. Shortest paths. recall Dijkstra/Bellman-Ford/etc, Seidel's algorithm using matrix multiplication, Williams' APSP algorithm from 2014.
  3. Matchings: classical matchings using augmenting paths, matching using matrix inversions (Tutte/Lovasz, Mucha-Sankowski), matchings using random walks.
  4. The Experts algorithm via multiplicative weights, and online gradient descent.
  5. Flows, including via electrical flows.

  6. Linear and Convex Programming
  7. Fixed-parameter tractable algorithms.
  8. High-dimensional geometry: Dimension reduction and singular value decompositions.
  9. Streaming algorithms (a.k.a. algorithms for big data)
  10. Online algorithms
  11. Approximation Algorithms
  12. Submodular Optimization
  13. ...
The goal is to give a glimpse into some ideas/techniques from each area. For topics that were covered in 451/750, the goal is to cover advanced content, and new techniques.

As an example, here are the 2015 and the 2009 versions of the course; the latter has fewer HWs than we'll have, and a greater emphasis on data structures.

Prerequisites:

A good understanding of basic algorithms, e.g., from a previous algorithms course like 15-451 or 15-750. Basic Probability, Algebra, graph theory, combinatorics. Mathematical maturity essential.

Remarks

Grades will be based on 4 or 5 6 problem sets, attendance, and class participation. Some of the homeworks allow collaboration, others must be done individually. Students will be required to write LaTeX notes for 1-2 lectures, and possibly help with grading. One of the HWs will count as a take-home final.

There is no textbook for the course. References and readings from books, research paper and other material will be provided as the course progesses.


Maintained by Anupam Gupta