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 ✍️.
Videos with technical problems are marked ⚠️. For most topics, scribbles and videos from Jeff's Fall 2022 offering of the course are available on a separate page.
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
[video]
- Mon Sep 30
- Midterm 1 — 7–9pm, locations TBA
- Tue Oct 1
- Treaps
[scribbles,
video]
- Thu Oct 3
- Tail inequalities
[scribbles,
video ⚠️]
⚠️audio only because of technical problems; but scribbles closely track the lecture
- Tue Oct 8
- Hashing: limited randomness, universality, chaining
[scribbles,
video]
- Thu Oct 10
- Hashing: perfect hashing, open addressing, linear/binary probing
[scribbles ⚠️,
video ⚠️]
⚠️recorded later because I forgot to bring cables to class 🤦
- Tue Oct 15
- Streaming algorithms
[scribbles,
video]
- Thu Oct 17
- Sketching and dimensionality reduction
[scribbles,
video]
- Fri Oct 18
- Undergrad self-service drop deadline
- Tue Oct 22
- Flows and cuts
[scribbles,
video]
- Thu Oct 24
- Flow decompositions and algorithms
[scribbles,
video]
- Tue Oct 29
- Applications of maximum flows
[scribbles,
video ⚠️,
Fall 2022 scribbles,
Fall 2022 video]
⚠️lecture starts roughly 30 minutes into the video
- Thu 🎃ct 31
- Midterm 2 review
[video]
- Mon Nov 4
- Midterm 2 — 7–9pm, locations TBA
- Tue Nov 5
- More applications of maximum flows
[scribbles,
video ⚠️,
Fall 2022 scribbles,
Fall 2022 video]
⚠️no sound because I forgot to turn on the microphone
- Thu Nov 7
- Applications of minimum cuts
[scribbles,
video]
- Tue Nov 12
- Linear programming: definitions, duality
[scribbles,
video,
Sariel's notes]
- Thu Nov 14
- The (primal and dual) simplex algorithm(s)
[scribbles,
video,
Sariel's notes,
YouTube video by TomS]
- Fri Nov 15
- Grad drop deadline
- Tue Nov 19
- NP hardness
and approximation algorithms
[scribbles,
video]
- Thu Nov 21
- More approximation algorithms
[scribbles,
video]
- Nov 24–30
- Inconveniently scheduled week-long break
📺
- Tue Dec 3
-
Fast dynamic programming: Two Indians and four Russians
[scribbles,
video]
- Thu Dec 7
-
Monotone arrays and SMAWK
[scribbles,
video]
- Tue Dec 10
- Final exam review
[scribbles,
video,
complete walthrough scribbles,
complete walthrough video]
- Tue Dec 17
- Final exam —
7–10pm,
151 Loomis