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)