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 4-5pm (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
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)
Maintained by Anupam Gupta