15-750: Algorithms in the Real World, Spring 2022
- Lecturers: Anupam
Gupta
(anupamg@cs), Rashmi
Vinayak (rvinayak@cs).
- TAs: Justin Whitehouse (jwhiteho@andrew), Francisco Maturana (fmaturan@cs), Yuanhao Wei (yuanhao1@cs).
- Office hours:Please refer to the class calendar below.
- Piazza: Please use private messages on Piazza instead of
emailing the course staff, that way the messages will not get lost.
- Location: Margaret Morrison A14, Tue/Thu 10:10-11:30.
- Piazza: http://piazza.com/cmu/spring2022/15750/home
- Gradescope: https://www.gradescope.com/
Course Details and Policies
Homeworks
- Homework 1 (due Thursday, Feb 3) [updated Jan 26 with a small fix in Exercise 3], solutions (CMU only)
- Homework 2 (due Thursday, Feb 17), exercises, solutions (CMU only)
- Homework 3 (due Tuesday, Mar 15), solutions (CMU only), Programming problem solution (CMU only).
- Midterm solutions (CMU only)
- Homework 4 (due Thursday, Mar 31), solutions (CMU only)
- Homework 5 (due Thursday, Apr 14), solutions (CMU only)
- Homework 6 (due Sunday, May 1), solutions (CMU only)
Lectures
- Lecture 1 (Jan 18). 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 (Jan 20). Minimum Spanning Trees and Amortized
Analysis
(notes, older
handwritten
notes, PPT slides for proof, board)
- Notes on Kruskal's MST algorithm.
- 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 (optional) the tree-based one we did not get to.
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 (Jan 25). Hashing 1 (board).
- Lecture 4 (Jan 27). Hashing 2 (board).
- Notes on hashing (same as above notes on hashing).
- Detailed description of the proof sketch (on Cuckoo hashing) covered in this lecture can be found here.
- Lecture 5 (Feb 1). Amortization. Shortest Paths (Dijkstra). (amortization
notes, handwritten
notes, some slides
animating Dijkstra)
- Lecture 6 (Feb 3). Dynamic Programming.
- Lecture
notes (and a recitation worksheet)
from the 15-451 course, discussing several problems, via memoization and table-filling.
- Notes for small-space
implementations for DP.
- Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).
- Lecture 7 (Feb 8). Hashing 3: Algorithms for Streaming Data (board).
- Lecture 8 (Feb 10). Hashing 4: Load balancing (board).
- Lecture 9 (Feb 15). Dimension Reduction 1: Preserving Pairwise Distances (JL Transform) (board).
- Lecture 10 (Feb 17). Dimension Reduction 2: Principal Component Analysis and Singular Values (board).
- Lecture 11 (Feb 22). Algorithms for Coding 1 (Slides).
- You might find the scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course useful (although there are some differences in topics covered): Scrie notes 1, Scribe notes 2.
- (Optional) Chapter 1 from David MacKay's book.
- Lecture 12 (Feb 24). Algorithms for Coding 2 (Slides).
- You might find the scribe notes from 15-853 ("Algorithms in the real world") Fall 2019 course useful (although there are some differences in topics covered): Scrie notes 2, Scribe notes 3.
- Lecture 13 (Mar 3). Algorithms for Coding 3 (Slides).
- Lecture
notes on basic concepts on polynomials and Reed-Solomon codes from Spring 2019 15-451/651.
- Lecture 14 (Mar 15). Optimization I: Flows and
Matchings. (preliminary notes, handwritten
notes I
and II)
- Lecture 15 (Mar 17). Optimization II: Linear
Programming (introduction, applications).
- Lecture 16 (Mar 22). Optimization III: Linear
Programming (duality, algorithms).
- Lecture 17 (Mar 24). NP Hardness and Limits of Efficient
Algorithms. (draft
notes, older
handwritten notes)
- Lecture 18 (Mar 29). Combating Intractability via Approximations
(notes)
- Lecture 19 (Mar 31). Online Decision Making I: Online
Algorithms and Competitive Analysis
(online
algos notes from 15-451)
- Lecture 20 (Apr 5). Online Decision Making II: The Experts Problem and the Multiplicative Weights Framework (handwritten notes)
- Lecture 21 (Apr 12). Compression 1 (Slides).
- Lecture 22 (Apr 14). Compression 2 (Slides).
- Guy Blelloch's notes on compression. Chapters 4, 6 and 7 are relevant to the lecture material.
- Lecture 23 (Apr 19). Online Decision III and Optimization IV:
The Gradient Descent Framework (handwritten notes)
- Lecture 24 (Apr 21). Graphs via Matrices: Spectral Graph Theory
(handwritten
notes from S20)
- Lecture 25 (Apr 26). Laplacian Recap, Cheeger's
Inequality, and Random Walks
(handwritten notes on random
walks from S20)
- We will only test you on the Cheeger and
connectivity part, not on the random walks part. See
previous lecture's notes.
- 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 26 (Apr 28). Course Review.
Recitations
- Recitation 1 (Feb 18): Finite fields (Slides).
Maintained by Anupam Gupta and Rashmi Vinayak