15-750: Algorithms in the Real World, Fall 2023
- Lecturer: Rashmi
Vinayak (rvinayak@cs).
- TAs: Yash Savani (ysavani@cs), Billy Yan (yunzhouy@andrew).
- Office hours: Yash Savani (Wed 4:30-5:30pm) Billy Yan (Mon 2:30 - 3:30pm) (Any changes will be updated in the calendar below).
- Contacting us: Please use private messages on Piazza instead of emailing the course staff; this helps messages to not get lost.
- Lecture location: GHC 4303, Tue/Thu 11:00-12:20.
- Piazza: https://piazza.com/cmu/fall2023/15750/home
- Gradescope: https://www.gradescope.com/
Course Details and Policies
- Please read the course policies
carefully!!!
- Links
to resources to help brush up on your background.
- The course page will develop more as we proceed through the lectures.
Lectures
- Lecture 1 (Aug 29). Introduction, Triangle Counting, Strassen's Algorithm
- Lecture 2 (Aug 31). Minimum Spanning Trees (notes, older
handwritten notes)
- 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.
- Basic animations of Kruskal/Prim's algorithms
- Lecture 3 (Sept 5). Amortization + Shortest Paths with Dijkstra
- Lecture 4 (Sept 7). 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 implementation of LCS.
- Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).
- For the initial part of the lecture which covered Heaps: Animation of a
(max) heap based priority queue data structure.
- Lecture 5 (Sept 12). Hashing 1: Hashing with SUHA, analysis of collisions, two-level hashing
- Lecture 6 (Sept 14). Hashing 2: cuckoo hashing, relaxing SUHA, hash function constructions
- Notes on hashing (which includes topics discussed in this lecture).
- A detailed discussion on the proof sketch of Cuckoo hashing covered in the lecture can be found here.
- Lecture 7 (Sept 19). Hashing 3: Load balancing (balls and bins)
- Lecture 8 (Sept 21). Two Choices, Bloom filters, Data Streaming Model 1
- Notes on hashing (which includes Power-of-Two-Choices and Bloom filters).
- Notes on streaming.
- Lecture 9 (Sept 26). Data Streaming Model 2, Locality Sensitive Hashing and Near-Neighbor Search
- Lecture 10 (Sept 28). Dimensionality Reduction: Preserving pairwise distances (JL Transform)
- Lecture 11 (Oct 3). Principal Component Analysis (PCA)
- Lecture 12 (Oct 5). Principal Component Analysis (PCA) - 2, SVD
- Lecture 13 (Oct 10). Midterm review
- Lecture 14 (Oct 12). Midterm exam day
- Lecture 15 (Oct 24). Compression 1 (Slides)
- Lecture 16 (Oct 26). Compression 2 (Slides)
- Guy Blelloch's notes on compression. Chapters 3, 4, and 6 are relevant to the lecture material.
- Lecture 17 (Oct 31). Lossy Compression and Algorithms for Channel Coding (Slides)
- You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scrie notes 1
- (Optional) Chapter 1 from David MacKay's book.
- Lecture 18 (Nov 2). Algorithms for Channel Coding: basic concepts, number theory (Slides)
- You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scrie notes 2
- (Optional) Chapter 1 from David MacKay's book.
- Lecture 19 (Nov 9). Algorithms for Channel Coding: Algebraic codes (Notes in the form of slides)
- You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scribe notes 3.
- Lecture 20 (Nov 14). Algorithms for Channel Coding: Graph-based codes (Notes in the form of slides)
- You might find the scribe notes from Fall 2019 15-853 course that I had taught useful (although there are some differences in topics covered): Scribe notes 4 and Scribe notes 5.
- Lecture 21 (Nov 16). Optimization I: Flows and
Matchings
- Lecture 22 (Nov 21). Optimization II: Linear Programs
- Lecture 23 (Nov 28). Optimization III: Convex minimization and Gradient Descent
- Notes from our 15-451 (The coverage in this notes is different from what we saw in the lecture. But the contents are mostly relevant.).
- Lecture 24 (Nov 30). Optimization IV: Decision making under uncertainty: Prediction with experts and Online algorithms
- Lecture 25 (Dec 5). Guest lecture by Prof. Nina Balcan on Machine Learning for Algorithm Design
- Lecture 26 (Dec 7). Course review.