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; exam dates are not.
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 ✍️.
Videos of all past lectures, with transcriptions, are available on a separate page. New transcribed videos should appear automatically at most a day after each lecture. (Unfortunately, ClassTranscribe is misbehaving; hopefully we'll catch up on transcribed videos soon.) I will also add links on this page to my own screen-capture videos, but that process is manual, so it may take some time.
After spring break, in response to the COVID-19 pandemic, all instruction moved online and all lectures became asynchronous. Lecture videos are uploaded at least a few hours in advance of the corresponding "lecture" time. We still hold course meetings over Zoom at the regular lecture time, for discussion and questions about the course material. For privacy reasons, videos of Zoom sessions (marked 🔒) are restricted to registered students and course staff; log in with your university NetID and password.
Prerequisite material
- already
-
Induction
Solving recurrences
Divide and conquer
Whatever-first search
Depth-first search and topological sorting
Recursion/Dynamic Programming
- Wed Jan 22
- Introduction, administrivia
Recursion and
backtracking
[
video with transcript,
raw video, scribbles]
- Fri Jan 24
-
Dynamic programming: subsequences
[
video with transcript,
raw video, scribbles]
- Wed Jan 29
-
Dynamic programming: subsequences and trees
[
video with transcript, raw video, scribbles]
- Fri Jan 31
-
Dynamic programming: trees and dags
[
video with transcript, raw video, scribbles]
- Mon Feb 1
- Add deadline
- Wed Feb 5
-
Advanced dynamic programming: divide-and-conquer ✍️
[
video with transcript, raw video, scribbles]
- Fri Feb 7
-
Advanced dynamic programming: four Russians, fast longest increasing subsequence, monotonicity
✍️
[
video with transcript, raw video, scribbles]
- Wed Feb 12
-
Advanced dynamic programming: SMAWK, concave minimum weight subsequence
✍️
(sloppy; clarified next Wednesday)
[
video with transcript, raw video, scribbles]
Randomization
- Fri Feb 14
-
Flipping coins, collecting Pokémon, and shuffling cards
✍️
[
video with transcript, raw video, scribbles]
- Wed Feb 19
-
Sorting nuts and bolts
✍️
[
video with transcript, raw video, scribbles]
- Fri Feb 21
-
No lecture; optional review session
[
video with transcript, raw video,
just the problems,
scribbles]
- Tue Feb 25
- Midterm 1, 7pm-9pm
- Wed Feb 26
-
Treaps
✍️
[
video with transcript,
raw video,
scribbles]
- Fri Feb 28
-
Tail inequalities
✍️
[
video with transcript,
raw video,
scribbles]
- Wed Mar 4
-
Hashing: limited randomness, universality, chaining, perfect hashing
✍️
[
video with transcript,
raw video,
scribbles]
- Fri Mar 6
-
Hashing: open addressing, linear/binary probing
✍️
[
video with transcript,
raw video,
scribbles]
- Wed Mar 11
-
String matching: Sliding hash function
✍️
[
video with transcript,
raw video,
scribbles]
- Fri Mar 13
-
String matching: Knuth-Morris-Pratt (dynamic programming)
✍️
[
video with transcript,
raw video,
scribbles]
- Mar 14–22
- ☼ Spring break ☼
Optimization
- Wed Mar 25
-
Flows and cuts, maxflow-mincut theorem, residual graphs and augmenting paths
[videos with transcripts:
1,
2,
3.
4,
5;
raw videos:
1,
2,
3,
4,
5;
scribbles]
- Fri Mar 27
-
Ford-Fulkerson, efficient maxflow algorithms, flow decomposition
[videos with transcripts:
1,
2,
(more soon);
raw videos:
1,
2,
3,
4,
Zoom🔒;
scribbles]
- Wed Apr 1
-
Applications of maximum flows
[videos with transcripts:
1,
2,
3;
raw videos:
1,
2,
3;
scribbles]
- Fri Apr 3
- Midterm 2 review session
[videos with transcripts:
0,
1,
2,
3,
4;
raw videos:
0,
1,
2,
3,
4,
Zoom🔒;
just the problems;
scribbles]
- Mon Apr 6
-
8am: Midterm 2 released
- Wed Apr 8
-
3pm: Midterm 2 due
- Fri Apr 10
-
More applications of maximum flows
[raw videos:
1,
2,
3,
4,
5;
scribbles]
- Wed Apr 15
-
Supplies, demands, and pseudoflows
✍️
[raw videos:
1,
2,
3,
4,
5,
Zoom🔒;
scribbles]
- Fri Apr 17
-
Minimum-cost flows: minimum-cost circulations, cycle canceling, successive shortest paths
[raw videos:
1,
2,
3,
4,
5;
Zoom🔒;
scribbles]
- Wed Apr 22
-
Linear programming: definitions, duality
✍️
[raw videos:
1,
2,
3,
4,
5;
scribbles]
- Fri Apr 24
-
The (primal and dual) simplex algorithm(s)
[raw videos:
1,
2,
3,
4,
5;
scribbles]
Other Cool Stuff
- Wed Apr 29
-
Fast Fourier transforms
✍️
[raw videos:
1,
2,
3,
4;
scribbles]
- Fri May 1
-
Old and new algorithms for cyclic dynamic programming
[raw videos:
1,
2,
3,
4,
5;
scribbles]
- Mon May 4
- 8am: ICES forms released
- Wed May 6
-
Final exam review
[raw videos:
intro,
1,
2,
3,
4,
5;
6;
just the problems,
scribbles]
- Wed May 6
- Drop and CR/NC deadline
- Mon May 11
- 8am: Final exam released
- Tue May 12
- 10pm: Final exam due
- Fri May 15
- 5pm: ICES forms due