Lecture Schedule
Future lecture topics are subject to change. Over time we will add links to relevant textbook chapters / lecture notes; links to future lecture notes, videos, and other resources are placeholders. Exam dates are fixed. 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.
Semester progress:
[Jump to current week]
- already
-
Induction
Solving recurrences
Divide and conquer
Whatever-first search
Depth-first search and topological sorting
- Tue Aug 27
- Introduction, administrivia;
recursion
[slides,
scribbles,
video]
- Thu Aug 29
- Fast Fourier transforms
[scribbles,
video,
YouTube (Reducible)]
- Mon Sep 2
- Labor Day
- Tue Sep 3
-
Convolutions;
backtracking
[scribbles,
video,
YouTube (3Blue1Brown)]
- Thu Sep 5
-
Dynamic programming
[scribbles,
video]
- Mon Sep 9
- Add deadline
- Tue Sep 10
- Tree-shaped dynamic programming
[scribbles,
video]
- Thu Sep 12
- Dynamic programming in trees
and dags
[scribbles,
video]
- Tue Sep 17
- Basic discrete probability
[scribbles,
video*]
*(audio only because of technical problems, scribbles closely track the lecture)
- Thu Sep 19
- Testing Identities and More probability
[scribbles,
video]
- Tue Sep 24
- Sorting nuts and bolts
[scribbles,
video]
- Thu Sep 26
- Midterm 1 review
- Mon Sep 30
- Midterm 1 — 7–9pm, locations TBA
- Tue Oct 1
- Treaps
[scribbles,
video]
- Thu Oct 3
- Tail inequalities
[scribbles,
video]
- Tue Oct 8
- Hashing: limited randomness, universality, chaining, perfect hashing
- Thu Oct 10
- Hashing: open addressing, linear/binary probing
- Tue Oct 15
- Sketching/streaming
- Thu Oct 17
- Dimensionality reduction
- Fri Oct 18
- Undergrad self-service drop deadline
- Tue Oct 22
- Flows and cuts
- Thu Oct 24
- Flow decompositions and algorithms
- Tue Oct 29
- Applications of maximum flows
- Thu 🎃ct 31
- Midterm 2 review
- Mon Nov 4
- Midterm 2 — 7–9pm, locations TBA
- Tue Nov 5
- More applications of maximum flows
🇺🇸 Election day 🇺🇸
- Thu Nov 7
- Applications of minimum cuts
- Tue Nov 12
- Linear programming: definitions, duality
- Thu Nov 14
- The (primal and dual) simplex algorithm(s)
- Fri Nov 15
- Grad drop deadline
- Tue Nov 19
- Approximation algorithms
- Thu Nov 21
- More approximation algorithms
- Nov 24–30
- Inconveniently scheduled week-long break 📺
- Tue Dec 3
- Cool
beans
- Thu Dec 7
- More
cool
beans
- Tue Dec 10
- Final exam review
- Tue Dec 17
- Final exam —
7–10pm,
locations TBA