## 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:

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

- Linear and Convex Programming
- Using convex optimization to solve combinatorial
problems
- Solving convex optimization problems via gradient descent, ellipsoid,
interior-point methods

- Fixed-parameter tractable algorithms.
- High-dimensional geometry: Dimension reduction and singular value
decompositions.
- Streaming algorithms (a.k.a. algorithms for big data)
- Online algorithms
- Approximation Algorithms
- Submodular Optimization
- ...

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*