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

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

Recursion

Tue Aug 23: Introduction, administrivia
Recursion
[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]

Randomization

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: Treaps
[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

Optimization

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