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 ✍️
[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: Sliding hash function
[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, efficient maxflow algorithms, flow decomposition
[scribbles, video]
Tue Oct 25
Applications of maximum flows
[scribbles, video]
Thu Oct 27
No lecture; optional midterm review session
[scribbles, video]
Mon Oct 31
Midterm 2, 7pm-9pm, 141 Loomis (🧑🏻‍🔬🧪🧟🧠🧛🩸🕷🪰🎃🕯👻🍫)
Tue Nov 1
More applications of maximum flows
[scribbles, video]
Thu Nov 3
Supplies, demands, and pseudoflows
[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
TBA
[scribbles, video]
Thu Dec 1
TBA
[scribbles, video]
Tue Dec 6
No lecture; optional final review session
[scribbles, video]
Tue Dec 13
Final exam 7pm–10pm, location TBA