15-750: Algorithms in the Real World, Fall 2025
- Lecturer: Jason Li (jmli@cs).
- TA: Meredith Pan (shiqip@andrew).
- Office hours: Meredith Thursdays 4-5pm, Gates 5th floor commons (subject to change); Jason Tuesdays 2-3pm, Gates 5011
- Contacting us: Please use private messages on Piazza instead of emailing the course staff; this helps messages to not get lost.
- Lecture location: Wean 5415, Tue/Thu 11:00-12:20.
- Piazza: Link
- Gradescope: entry code 42EVZR
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.
Homeworks
Lectures
- Lecture 1 (Aug 26). Introduction, Triangle Counting, Strassen's Algorithm (notes)
- Lecture 2 (Aug 28). Minimum Spanning Trees and Amortized Analysis (notes)
- Lecture 3 (Sept 2). The analysis of Union-Find (notes)
- Lecture 4 (Sept 4). Shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall (notes)
- Lecture 5 (Sept 9). Dynamic Programming (notes)
- Notes Sections 4.1, 4.2, 4.5, 4.6
were covered in lecture.
-
451 notes on DP Sections 2 and 3 were covered in lecture.
- Kleinberg-Tardos has many fun examples of solving problems using DP (see the slides1, slides2 by Kevin Wayne).
- Lecture 5 (Sept 11). Hashing 1: Hashing with SUHA, analysis of collisions (notes)
- Lecture 6 (Sept 16). Hashing 2: Two-level hashing, hash function constructions, Load balancing - 1 (notes)
Lecture 7 (Sept 18). Hashing 3: Load balancing - 2 (notes)
- Notes on load-balancing.
- (Additional reading) Some detailed examples/exercises on Chernoff bounds (which includes topics discussed in this lecture).
Lecture 8 (Sept 23). Data Streaming. Frequency Estimator. (notes from 15-850), we covered up to page 4
Lecture 9 (Sept 25). Dimensionality Reduction: Preserving pairwise distances (JL Transform) (notes from 15-850)
Lecture 10 (Sept 30). Trie and Suffix Tree (Meredith's notes)
Lecture 11 (Oct 2). Construction of Suffix Arrays (Meredith's notes)
Lecture 12 (Oct 7). Principal Component Analysis (PCA) (notes)
Midterm Exam (Oct 9).
Lecture 13 (Oct 21). Optimization I: Flows and Matchings (notes)
Resources will be added for each lecture.