Lecturer: Anupam Gupta, GHC 7203.
TAs: Jason Li, Goran Zuzic
Office hours: Anupam: Tue 4-5 p.m. in GHC 7203, Jason: Thu 10–11 a.m. in GHC 7607, Goran: Wed 5–6 p.m. in GHC 7515

Location: GHC 4211, MWF 1:30-2:50 (note: 3 days a week)
Blog: https://cmualgos.github.io/
Piazza: here
Gradescope: Use course code 92K6XG to enroll.

Announcements

• All announcements will be on Piazza, please make sure you're signed up there!

Description

An intensive graduate course on the design and analysis of algorithms, picking up from where 15-451 stopped. It will be more specialized and in-depth than the Graduate Algorithms course 15-750. We will cover advanced algorithmic ideas (some classical, some very recent), and the theory behind it (theorems, proofs). For topics that were covered in 451/750, the goal is to cover advanced content and new techniques.

Syllabus

The current list of potential topics are:
1. MSTs. Recap Prim/Kruskal/Boruvka, an $$O(m \log^\star 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' subcubic APSP algorithm for general graphs.
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, online gradient descent.
5. Flows: max-flows via electrical flows, Sherman's near-linear time max-flow.
6. Linear and Convex Programming
• Solving convex optimization problems via gradient descent, ellipsoid, interior-point methods
• Using convex optimization to solve combinatorial problems (maybe)
7. High-dimensional geometry: Dimension reduction and singular value decompositions.
8. Fixed-parameter tractable algorithms.
9. Streaming algorithms (a.k.a. algorithms for big data)
10. Online algorithms
11. Approximation Algorithms
13. Submodular Optimization
Here are the Spr 17 and Spr 15 versions of this course. The topics this year will be similar (though not identical). I will take a poll in mid-Oct about topics to cover in the last 4-5 lectures.

Effort and Criteria for Evaluation:

We have 3 lectures a week for the first ~10 weeks of the semester. Attendance is required. You will scribe 1-2 lectures in Latex: either you will polish/augment old lecture notes, or will write new notes. We have ~7 HWs (including HW0), half solved with collaboration, others solved individually. Your grade will depend on these HWs, scribe notes, class participation, and attendance.

Textbook:

There is no textbook for the course. Most of our material is not in textbooks (yet), so we will rely on papers, monographs, and lecture notes.

Prerequisites:

You should know material in standard UG courses in algorithms, probability, and linear algebra very well. Above all, mathematical maturity/curiosity and problem-solving skills are a must. That way you can make up for gaps in your knowledge yourself. It is natural to not know everything, or for you to get rusty on concepts, but you should learn how to learn. This may seem vague, so here are concrete things.

• You should know material from an undergraduate Algorithms course, say until Lecture 16 (P/NP) from our Spring 2018 version of 15-451. You should definitely know DP, flows, basics of linear programming, duality, etc. If not, please pick these up from the 451 lecture notes/textbooks/Wikipedia/Khan Academy.
• Same for undergraduate probability and linear algebra courses. E.g., for LinAlg, see whether you can solve the first homework from Steve Vavasis' Optimization course at Waterloo. For probability (and randomized algorithms), I will give some problems in HW0.
• HW0 will make an attempt to test this preparedness, and to give you and us feedback. Students late in submitting HW0 will risk being dropped from the course (we are over-subscribed, and have a wait-list), sorry! So talk to us in Lecture #1 if you have a good reason for being late.

FAQs:

• Q: Will you give the real-world context for the algorithms you cover?
This class will focus on the theoretical side, so we will not have much time to motivate the choice of topics or give much real-world context (of which there is plenty). If you are looking for the latter, you should consider taking 15-853: Algos in the Real World.

• Q: I am on the wait-list: will I get in?
We hope everyone who wants to take the class will get in. (Usually some students are "shopping around" in the first couple weeks, and things settle down after that.) Just come to the lectures, and we will try to get clear the wait-lists soon. OTOH, if you are on the wait-list because you have too many credits, or are enrolled for a course with a conflicting time-slot, you should fix those issues yourself.

• Q: I am struggling with the homework: what should I do?
A little struggle in doing the homework is expected (and healthy), since these are not trivial problems, you're probably learning something new. However, if you are struggling a fair bit, or if the struggle is unpleasant for you, come talk to us. You may consider taking 15-451 (UG Algos) or 15-750 (Graduate Algos) instead of this course.