CS 473: Lecture Schedule

The schedule below lists the topic of each lecture, with links to relevant lecture notes or book chapters, lecture videos, and lecture scribbles. All future lecture topics are subject to change; links to future lecture scribbles and videos are placeholders.

Please let me know if you find any of the bugs I've cleverly hidden in the book and notes. Most of these bugs are just typos, but undoubtedly a few are actually quite serious. Notes that have been recently revised (however lightly) are marked ✍️.

Lecture videos are available on a separate page. New videos should be available at most a day after each lecture.

Prerequisite material

Solving recurrences
Divide and conquer
Whatever-first search
Depth-first search and topological sorting


Tue Aug 23
Introduction, administrivia
[scribbles, video]
Thu Aug 25
Fast Fourier transforms ✍️
[ 🔥3Blue1Brown🔥 , scribbles, video]
Tue Aug 30
Backtracking and dynamic programming: subsequences
[scribbles, video]
Thu Sep 1
Tree-shaped dynamic programming
[scribbles, video]
Fri Sep 2
Add deadline
Mon Sep 5
Labor Day — university holiday
Tue Sep 6
Dynamic programming in trees and dags
[scribbles, video]
Thu Sep 8
Advanced dynamic programming: divide-and-conquer
[scribbles, video]
Tue Sep 13
Advanced dynamic programming: monotonicity, SMAWK
[scribbles, video]


Thu Sep 15
Flipping coins, collecting Pokémon, and shuffling cards
[scribbles, video]
Tue Sep 20
Sorting nuts and bolts ✍️
[scribbles, video]
Thu Sep 22
No lecture; optional midterm review session
[just the problems, scribbles, video]
Mon Sep 26
Midterm 1, 7pm-9pm, 141 Loomis
Tue Sep 27
[scribbles, video]
Thu Sep 29
Tail inequalities (and review of midterm problem 3)
[scribbles, video]
Tue Oct 4
Hashing: limited randomness, universality, chaining, perfect hashing
[scribbles, video]
Thu Oct 6
Hashing: open addressing, linear/binary probing
[scribbles, video]
Tue Oct 11
String matching: Rolling hashes ✍️
[scribbles, video]
Thu Oct 13
String matching: Knuth-Morris-Pratt (dynamic programming) ✍️
[scribbles, video]
Fri Oct 14
Undergraduate drop deadline


Tue Oct 18
Flows and cuts, maxflow-mincut theorem, residual graphs and augmenting paths
[scribbles, video]
Thu Oct 20
Ford-Fulkerson, flow decomposition, efficient maxflow algorithms
[scribbles, video]
Tue Oct 25
Applications of maximum flows
[scribbles, video]
Thu Oct 27
No lecture; optional midterm review session
[just the questions, scribbles, video]
Mon Oct 31
Midterm 2, 7pm-9pm, 141 Loomis (🧑🏻‍🔬🧪🧟🧠🧛🩸🕷🪰🎃🕯👻🍫)
Tue Nov 1
More applications of maximum flows
[scribbles, video]
Thu Nov 3
Applications of minimum cuts; supplies and demands
[scribbles, video]
Tue Nov 8
Election day — university holiday
Thu Nov 10
Minimum-cost flows: minimum-cost circulations, cycle canceling, successive shortest paths
[scribbles, video]
Tue Nov 15
Linear programming: definitions, duality
[scribbles, video]
Fri Nov 11
Graduate drop deadline
Thu Nov 17
The (primal and dual) simplex algorithm(s)
[scribbles, video]
Nov 19–27
Thanksgiving break 🍂🏈🦃🥦🍠🍷🥧🥃🛌💤

Other Cool Stuff

Tue Nov 29
Online algorithms: Lost cows and meteor coffee
[scribbles, video]
Thu Dec 1
Splay trees and the dynamic optimality conjecture
[scribbles, video]
Tue Dec 6
No lecture; optional final review session
[just the problems, scribbles, video]
Tue Dec 13
Final exam 7pm–10pm, 2079 Natural History