15-750: Algorithms in the Real World, Spring 2023
- Lecturer: Ryan O'Donnell (odonnell@cs).
- TAs: Liyao Fu (liyaof@andrew), Emre Yolcu (eyolcu@cs), Billy Yan (yunzhouy@andrew).
- Office hours:
- Mon. 3pm--4pm, with Billy, on Zoom.
- Tue. 2:30--3:30, with Ryan, in Gates 7213.
- Wed. 6pm--7pm, with Liyao, on Zoom.
- Fri. 1pm--2pm, with Emre, on Zoom.
- Contacting us: Please use private messages on Piazza instead of emailing the course staff; this helps messages to not get lost.
- Location: Margaret Morrison A14, Tue/Thu 11:00-12:20.
- Piazza: http://piazza.com/cmu/spring2023/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.
Homeworks
Lectures
- Lecture 1 (Jan 17). Introduction + Strassen's Algorithm
(notes, older
handwritten notes).
- Lecture 2 (Jan 19). 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 (Jan 24). Amortization + Shortest Paths with Dijkstra (amortization
notes, handwritten
notes, some slides
animating Dijkstra)
- Lecture 4 (Jan 26). Dynamic Programming. (My handwritten notes)
- 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).
- Lecture 5 (Jan 31). Hashing 1, with SUHA. (My handwritten notes)
- Lecture 6 (Feb 2). Hashing 2: Max load, power of 2 choices, Bloom filters. (My handwritten notes)
- Lecture 7 (Feb 7). Hashing 3: Universal hashing. (My handwritten notes)
- Lecture 8 (Feb 9). Hashing 4: Implementing universal hashing, and perfect hashing. (My handwritten notes)
- Lecture 9 (Feb 14). Dimensionality Reduction with the JL Lemma (My handwritten notes)
- Lecture 10 (Feb 16). Symmetric matrices: finding eigenvalues and eigenvectors (My handwritten notes)
- Lecture 11 (Feb 21). Principal Component Analysis (PCA) (My handwritten notes)
- Lecture 12 (Feb 23). Max-st-Flow and Min-st-Cut (My handwritten notes)
- Lecture 13 (Mar 14). Optimization: From Max-Flow to LP (My handwritten notes)
- Lecture 14 (Mar 16). How to solve Linear Programs (My handwritten notes)
- Lecture 15 (Mar 21). Solving LPs with a separation oracle: Directed MST (My handwritten notes)
- Lecture 16 (Mar 23). Rounding ILPs to LPs.
- Lecture 17 (Mar 28). Online algorithms and decision making, Part 1 (My handwritten notes)
- Lecture 18 (Mar 30). Online algorithms and decision making, Part 2 (My handwritten notes)
- Lecture 19 (Apr 4). Online learning and prediction, Part 1 (My handwritten notes)
- Lecture 20 (Apr 6). Online learning and prediction, Part 2 (My handwritten notes)
- Lecture 21 (Apr 11). Solving zero-sum games via online learning (My handwritten notes)
- Lecture 22 (Apr 18). Random walks on graphs I: Markov Chains (My handwritten notes)
- First of three lectures in a sequence about spectral graph theory. Sorry the audio on this is low, but it gets higher.
- Lecture 23 (Apr 20). Random walks on graphs II: Undirected graphs (My handwritten notes)
- Lecture 24 (Apr 25). Spectral graph theory I (My handwritten notes)
- Lecture 25 (Apr 27). Spectral graph theory II (My handwritten notes)
Maintained by Ryan O'Donnell, based on course pages by Anupam Gupta and Rashmi Vinayak