15-750: Graduate Algorithms, Spring 2021
- Lecturers: Anupam
Gupta
(anupamg@cs), Rashmi
Vinayak (rvinayak@cs).
- TAs: Michael Rudow (mrudow@cs), Sandeep Pallerla (spallerl@cs).
- Office hours: Please refer to the class calendar below.
- Staff Email List: 15750-spring21-instructors at lists dot andrew dit cmu dah edu (Please use this email list for contacting the instructors instead of individual email addresses.)
- Location: Online (zoom), Tue/Thu 10:40-noon. (Link to be
shared on piazza.)
- Piazza: http://piazza.com/cmu/spring2021/15750/home
- Gradescope: https://www.gradescope.com/
Course Details and Policies
Homeworks
- Homework 0 (due Monday, Feb
8), solutions (CMU only)
- Homework 1 (due Thursday, Feb 25), solutions (CMU only)
- Homework 2 (due Thursday, March 11), solutions (CMU only)
- Homework 3 (due Thursday, Apr 1), solutions (CMU only)
- Homework 4 (due Sunday, Apr 18), solutions (CMU only)
- Homework 5 (due Thursday, May 6), solutions (CMU only)
Lectures
- Lecture 1 (Feb 2). Introduction + Strassen's Algorithm
(notes, older
handwritten
notes, board, intro
slides)
- 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 (Feb 4). Minimum Spanning Trees and Amortized
Analysis (handwritten
notes, board, slides)
- Scan of section on Kruskal and MSTs from Kleinberg/Tardos
(WebISO access only).
- Notes on the union-find data structures, both the list-based one we did in lecture, and the tree-based one we described but did not prove.
I find this proof more accessible than Kozen's proof, try it and see what you think.
- Basic animations of Kruskal/Prim's algorithms
- Optional:
Wayne's slides
on the tree-based data
structures, and a proof that any (reasonable) union-find data
structure takes inverse Ackermann-time.
- Optional: Kozen's
chapters 2, 3
on MST and a generalization called Matroids, and the chapter on Union-find.
- Lecture 3 (Feb 9). Amortization (contd.) Shortest Paths and
Heaps. (amortization
notes, handwritten
notes, board, slides
for dijkstra, heaps)
- Lecture 4 (Feb 11). Dynamic Programming. (board)
- 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 5 (Feb 16). Hashing 1. (board, notes in the form of slides with some handwritten content)
- Lecture 6 (Feb 18). Hashing 2. (board, notes in the form of slides with some handwritten content)
- Lecture
notes on hashing from last year's 15-750 (same as the one linked above).
- Lecture 7 (Feb 25). Hashing 3: k-wise Independence, Cuckoo
Hashing, Bloom Filters. (board, notes in the form of slides with some handwritten content)
- Lecture
notes on hashing from last year's 15-750 (same as the one linked above).
- Lecture 8 (Mar 2). Hashing 4: Bloom Filters, Load Balancing,
Chernoff Bounds. (board, notes in the form of slides with some handwritten content)
- Lecture 9 (Mar 4). Hashing 5: Two Choices, the Data Streaming Model. (board, notes in the form of slides with some handwritten content)
- Lecture 10 (Mar 9). Hashing 6: Locality Sensitive Hashing and
Near-Neighbor Search (notes, board)
- Lecture 11 (Mar 11). Optimization I: Flows and
Matchings. (preliminary notes, handwritten
notes I
and II, board)
- Lecture 12 (Mar 18). Optimization II: Flows (finish), Linear
Programming (introduction). (handwritten notes, board)
- Lecture 13 (Mar 23). Optimization III: Linear
Programming (applications). (handwritten notes, board)
- Lecture 14 (Mar 25). LP wrapup. NP Hardness and Limits of Efficient Algorithms. (handwritten notes, board)
- Lecture 15 (Mar 30). Combating Intractability (notes, board)
- Lecture 16 (Apr 1). Online Decision Making I: Online
Algorithms and Competitive Analysis
(online
algos notes from 15-451, board)
- Lecture 17 (Apr 6). Online Decision Making II: The Experts Problem and the Multiplicative Weights Framework (handwritten notes, some slides, board)
- Lecture 18 (Apr 8). Online Decision III and Optimization IV:
The Gradient Descent Framework (handwritten notes)
- Lecture 19 (Apr 13). Dimension Reduction 1: Preserving Pairwise Distances (JL Transform) (board, notes in the form of slides with some handwritten content)
- Lecture 20 (Apr 20). Dimension Reduction 2: JL continued, Principal Component Analysis and Singular Values (board, notes in the form of slides with some handwritten content)
- Lecture 21 (Apr 22). Dimension Reduction 3: PCA & SVD continued; Algorithms for Coding 1 (board, notes in the form of slides with some handwritten content)
- (Same as above lecture) Chapter
11
(and slides)
from the MMDS book about PCA, SVD, etc, and Chapter 3
from the Blum-Hopcroft-Kannan book.
- Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course.
- Lecture 22 (Apr 27). Algorithms for Coding 2 (Slides, board (used intermittently throughout the lecture))
- Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course.
- Lecture 23 (Apr 29). Algorithms for Coding 3 (Slides, board (used intermittently throughout the lecture))
- Scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course (only some parts are relevant to what we covered in the lecture).
- Lecture
notes on basic concepts on polynomials and Reed-Solomon codes from Spring 2019 15-451/651.
- Lecture 24 (May 4). Compression (Slides, board (used intermittently throughout the lecture))
- Guy Blelloch's notes on compression. Chapters 1, 2 and 3 are relevant to what was covered in the lecture.
- (Optional) Shannon's 1948 paper.
- Lecture 25 (May 6). Compression 2 and Course Review (Slides on Compression 2 and the review of the Hashing module)
Maintained by Anupam Gupta and Rashmi Vinayak.