CMU Algorithms in the Real World, Fall 2025 (original) (raw)

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

• Homework 1 (due Friday, Sep 12)
• Homework 2 (due Friday, Sep 26)
• Homework 3 (due Friday, Nov 7)
• Homework 4 (due Friday, Nov 21)
• Homework 5 (due Friday, Dec 5)

Lectures

• Lecture 1 (Aug 26). Introduction, Triangle Counting, Strassen's Algorithm (notes)
  * Chapter 1 of Anupam's notes
  * Some resources from previous iterations of the course: older handwritten notes
  * 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 (Aug 28). Minimum Spanning Trees and Amortized Analysis (notes)
  * Chapter 2 of Anupam's notes (MST), (older handwritten notes)
  * Chapter 3 of Anupam's notes (amortized analysis)
  * Optional: Basic animations of Kruskal/Prim's algorithms

• Lecture 3 (Sept 2). The analysis of Union-Find (notes)
  * Log* analysis of Union-Find (451, Spr 19)
  * Chapter 3 of Anupam's notes(amortized analysis)
  * 451 (Fall 23) Lecture on Union-Find (log log n bound using a potential function)

• Lecture 4 (Sept 4). Shortest paths: Dijkstra, Bellman-Ford, Floyd-Warshall (notes)
  * older handwritten notes, some slides animating Dijkstra
  * Lecture notes from 15-451 on shortest-path algorithms.
  * Optional: Kevin Wayne's original slides onbinary and binomial heaps and Fibonacci heaps.

• 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)
  * Chapter 5 of Anupam's notes (which includes topics discussed in this lecture).

• Lecture 6 (Sept 16). Hashing 2: Two-level hashing, hash function constructions, Load balancing - 1 (notes)
  * Chapter 5 of Anupam's notes (which includes topics discussed in this lecture).
  * Notes on load-balancing (which includes topics discussed in this lecture).

• 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
  * Chapter 5 of Anupam's notes (which includes notes on Bloom Filters).
  * Chapter 7 of Anupam's notes (which includes topics discussed on streaming).

• Lecture 9 (Sept 25). Dimensionality Reduction: Preserving pairwise distances (JL Transform) (notes from 15-850)
  * SciKit's random projection implementation.
  * Lecture notes on JL Transform from a previous year.
  * (Optional) Proofs of Johnson-Lindenstrauss: Indyk/Motwani, Dasgupta/Gupta, Achlioptas.
  * (Optional) Fast JL transforms: Ailon-Chazelle,Ailon-Liberty.

• Lecture 10 (Sept 30). Trie and Suffix Tree (Meredith's notes)
  * 451 notes on suffix trees (see sections 1 and 2)

• Lecture 11 (Oct 2). Construction of Suffix Arrays (Meredith's notes)
  * The O(n log n) surrogate algorithm (451 notes)
  * The O(n) Skew Algorithm.
  * The O(n) Skew Algorithm, original paper.

• Lecture 12 (Oct 7). Singular Value Decomposition (SVD) (notes) * Lecture notes on SVD from a CMU course. * Chapter 11 (and slides) from the Mining Massive Datasets book by Leskovec, Rajaraman, and Ullman. * (Optional) Chapter 3 from the Blum-Hopcroft-Kannan book.

• Midterm Exam (Oct 9).

• Lecture 13 (Oct 21). Optimization I: Flows and Matchings (notes)
  * Notes from 15-451
  * Part of the flow chapter from the Kleinberg-Tardos book.
  * Animations of some basic max-flow algorithms (Ford-Fulkerson, Edmonds-Karp, Dinics)

• Lecture 14 (Oct 23). Optimization II: Min Cost Flows (notes)
  * Notes from 15-451

• Lecture 15 (Oct 28). Optimization III: Linear Programs (notes)
  * Anupam's notes on Linear Programming
  * Carl Kingsford's Simplex Slides
  * Notes about LPs from our 15-451 course.
  * Understanding and Using Linear Programming by Matousek/Gaertner is excellent (free from CMU). Chapters:Introduction,Examples,LP Basics.
  * An online LP solver: it's useful to play with, especially if you haven't seen LPs before.
  * More serious solvers: CVXOPT and PuLP: Solving linear/convex optimization problems in Python. Free LP solver from COIN-OR. Commercial ones from Gurobi and CPlex.

• Lecture 16 (Oct 30). Decision Making Under Uncertainty 1: Prediction with Experts (notes from 15-850), we covered up to the top of page 4
  * Prediction from experts and the multiplicative weights algorithm from 15-451
  * Notes on Multiplicative weights algorithm from 15-859

• Lecture 17 (Nov 6). Applications of Multiplicative Weights: Solving LPs and Zero-Sum Games (notes from 15-850 (1)) from page 4 to middle of page 5, (notes from 15-850 (2)) until middle of page 2
  * Prediction from experts and the multiplicative weights algorithm from 15-451
  * Notes on Multiplicative weights algorithm from 15-859

• Lecture 18 (Nov 11). Applications of Multiplicative Weights: Zero-Sum Games (finish) (notes from 15-850)
  * Prediction from experts and the multiplicative weights algorithm from 15-451
  * Notes on Multiplicative weights algorithm from 15-859

• Lecture 18 (Nov 13). Convex minimization and Gradient Descent (notes from 15-850)
  * Notes from 15-451. We will cover sections 1, 2, 3, and 5.
  * Online Convex Programming and Generalized Infinitesimal Gradient Ascent by M. Zinkevich

• Lecture 19 (Nov 18). Compression 1: Entropy, Prefix Codes, Huffman Codes (notes)
  * Guy Blelloch's notes on compression. Chapters 1 to 3 are relevant to the lecture material.
  * (Optional) Claude Shannon's 1948 paper.

• Lecture 20 (Nov 20). Compression 2: Arithmetic Coding, Burrows-Wheeler Transform (notes) (slides)
  * Guy Blelloch's notes on compression. Chapters 3.3, 4, and 6 are relevant to the lecture material.

• Lecture 21 (Nov 25). Compression 3: Burrows-Wheeler Transform, Lossy Compression (Notes in slides format)
  * Guy Blelloch's notes on compression. Chapters 4 and 6 are relevant to the lecture material.

• Lecture 22 (Dec 2). Polynomials in Algorithms 1: k-wise Independence, Reed-Solomon Codes (notes)
  * Notes from 15-451.

• Lecture 23 (Dec 5). Polynomials in Algorithms 2: Graph Matching, Schwartz-Zippel Lemma (notes from 15-850)
  * Notes from 15-451.

Resources will be added for each lecture.