15-750: Graduate Algorithms, Spring 2020
- Lecturer: Anupam
Gupta, GHC 7203.
- TAs: Andrii Riazanov (ariazano@andrew), Paul Gölz (pgoelz@andrew),
and Roie Levin (roiel@andrew).
- Office hours: Anupam: Tuesday 4-5pm (GHC 7203), Andrii: Wednesday 5-6pm (GHC 9009), Paul:
Monday 3:30-4:30pm (GHC 6211), Roie: Wednesday 2-3pm (GHC 9219).
- Location: NSH 1305, TR
10:30-11:50am.
- Piazza: http://piazza.com/cmu/spring2020/15750/
- Gradescope: https://www.gradescope.com/
(use your andrew ID to login please, and code 9RD3ZD if needed)
Course Details and Policies
Homeworks
- Homework 0 (due Monday, Jan 20), solutions (CMU only)
- Homework 1 (due Thursday, Feb 6), solutions (CMU only)
- Homework 2 (due Thursday, Feb 20), solutions (CMU only)
- Homework 3 (due Sunday, Mar 15, end of spring break), solutions (CMU only)
- Homework 4 (due Thursday, Apr 2) solutions (CMU only)
- Homework 5 (due Saturday, Apr 18) solutions (CMU only)
- Homework 6 (due Saturday, May 2)
- Two practice midterms
The Midterm will be in Rashid (GHC 4401), 6-9pm on Thursday Feb 27th.
Lectures
- Lecture 1 (Jan 14). Introduction + Strassen's Algorithm (my
handwritten notes)
- Handout
on big-O and recurrences from 15-451/651.
- Chapter 1
from Kozen (WebISO access only).
- Optional:
Strassen's paper,
some intuition for his formulas
(1,2,3), CACM
article
on low-communication MatMult (and video)
- Lecture 2 (Jan 16). Minimum Spanning Trees and Amortized Analysis (my
handwritten notes)
- Scans of chapters on Kruskal and MSTs (coming soon).
- Notes on the two union-find data structures, we only
covered the first one.
- Optional:
Wayne's slides
on the tree-based data
structures, and a proof that any (reasonable) union-find data
structure takes inverse Ackermann-time.
- Lecture 3 (Jan 21). Shortest Paths: Binary and Binomial Heaps (my
handwritten notes, (yet un)annotated slides)
- Lecture 4 (Jan 23). Randomized Data Structures: Binary Search
Trees and Treaps (tree-heaps)
(my
handwritten notes)
- Lecture 5 (Jan 28). Dynamic Programming
- Lecture
notes (and a recitation worksheet)
from the 15-451 course, discussing several problems, via memoization and table-filling.
- Some notes for the Talk Scheduling (aka Max-Weight
Interval Packing) problem.
- Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).
- Lecture 6 (Jan 30). Hashing for Fun and Profit: Universal
Hashing and Perfect (Two-Level) Hashing
(Notes (updated Feb 4))
- Optional: A tutorial by Mikkel Thorup on basic hashing schemes (from this hashing summer school).
- Optional: A blog post on choosing good hash functions in practice.
- Lecture 7 (Feb 4). Hashing II: Streaming Computation for Big Data
(Notes (updated Feb 4))
- Lecture 8 (Feb 6). Hashing III: Load Balancing and Power of Two Choices
(notes (updated Feb 6))
- Lecture 9 (Feb 11). Hashing IV: Locality Sensitive Hashing and
Near-Neighbor Search (handwritten notes (updated Feb 11))
- Lecture 10 (Feb 13). Dimension Reduction I: Preserving
Distances/Inner
Products. (handwritten
notes, older
more technical notes)
- Lecture 11 (Feb 18). Dimension Reduction II: JL recap, Compressive Sensing and the Single-Pixel Camera. (handwritten
notes)
- Lecture 12 (Feb 20). Dimension Reduction III: Principal
Component Analysis and Singular Values. (handwritten
notes)
- Lecture 13 (Feb 25). Dimension Reduction IV: PCA/SVD (contd.). (same handwritten notes as for lecture 12)
- Lecture 14 (Feb 27). Midterm Exam (no class, exam at 6pm, Rashid)
- Lecture 15 (Mar 3). Optimization I: Flows and Matchings. (handwritten notes)
- Lecture 16 (Mar 5). Optimization II: Max-Flow Min-Cut. (handwritten notes)
- Notes
on modeling (weighted) caching using min-cost flow
- Notes
and worksheet
for Max-Flows from our 15-451 course.
- Week of March 9: Spring Break!!
- Lecture 17 (Mar 19). Optimization III: Linear Programming, Introduction and Examples. (handwritten notes)
- Lecture 18 (Mar 24). Optimization IV: Linear Programming,
Geometry and Simplex. (handwritten notes,
board, updated simplex animation ppt, pdf)
- Lecture 19 (Mar 26). Optimization V: Linear Programming
Duality, finishing Simplex, discussing Interior Point. (handwritten notes, board, updated simplex animation ppt, pdf)
- Notes on duality from our 15-451 class, with a couple exercises, and a short "proof" of strong duality.
- Matousek/Gaertner.
Chapters: Simplex, Duality. (The beginnings of both chapters may be useful.)
- The main classes of algorithms used in commercial solvers
for LPs
are: Simplex
and Interior
Point. Other interesting classes are: Ellipsoid and
Multiplicative Weights.
- Lecture 20 (Mar 31). NP Hardness and Limits of Efficient Algorithms. (handwritten notes, board)
- Lecture 21 (Apr 2). Combating Intractability (new handwritten notes, notes on new material, board)
- Lecture 22 (Apr 7). Approximations (finish) and Making
Decisions Online (begin)
(handwritten
online algos notes, online
algos notes from 15-451, board)
- Lecture 23 (Apr 9). Making
Decisions Online (finish)
(handwritten
online algos notes, online
algos notes from 15-451, board)
- Lecture 24 (Apr 14). Online Decision Making III: The Experts Problem and the Multiplicative Weights Framework (handwritten notes, some slides, board)
- Lecture 25 (Apr 16). Online Decision Making IV and Optimization VI: Regularization Strikes Again! (handwritten notes, board)
- Lecture 26 (Apr 21). Optimization VII: Gradient Descent (handwritten notes, board)
- Lecture 27 (Apr 23). Graphs via Matrices: Spectral Graph Theory (handwritten notes, board)
- Lecture 28 (Apr 28). Random Walks, Sampling and Monte Carlo Methods (handwritten notes, board)
- Avrim Blum's notes on random walks and the connection to electrical networks.
- The book chapter by Jon Kleinberg and David Easley on random walks and Pagerank.
- The delightful little Doyle and Snell book on random walks and electrical networks.
- Lecture 29 (Apr 30). Final Exam (no class, details of exam to come soon)
Maintained by Anupam Gupta