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. Notes that have been recently written or revised (however lightly) are marked ✍️.
Lecture videos are available on MediaSpace. New videos should be available at most a day after each lecture.
Semester progress:
[Jump to current week]
- Tue Aug 25
- Introduction and administrivia
[scribbles,
video]
[Strömberg Lei Wu 2026,
Yong Nacenty Este 2026]
- Thu Aug 27
- Review of fundamental data types and linear data structures
[scribbles,
video]
- Tue Sep 1
- Review of tree data structures. Introduction to iterative algorithms and loop invariants
[scribbles,
video]
- Thu Sep 3
-
Iterative algorithms and loop invariants:
pancake sorting,
Dutch national flag
[scribbles,
video]
[Dijkstra 1976,
Gates Papadimitrou 1979,
Chitturi et al 2009,
Algomazing 2026]
- Fri Sep 4
- Add deadline
- Mon Sep 7
- Labor Day
- Tue Sep 8
- Recursive algorithms: binary search, find local maximum
[scribbles,
video]
[
Losaka-Jātaka (Jātakatthavaṇṇanā 41, c.200 BCE),
Lehmer 1960]
- Thu Sep 10
- Divide and conquer: median of two sorted arrays, mergesort, quicksort
[scribbles,
video]
[Shamos 1976,
Goldstine and von Neumann 1947 (see §11.4).
Hoare 1961]
- Tue Sep 15
- More divide and conquer: quickselect, Karatsuba multiplication
[scribbles,
video]
[Blum et al 1973,
Karatsuba 1995,
Purplemind on selection and
multiplication]
- Thu Sep 17
- Backtracking
[scribbles,
video]
[Gauss to Schumacher 1850,
scriptio continua,
Cicero Pro Murena 25]
- Tue Sep 22
- Dynamic programming
[scribbles,
video]
[Singh 1985]
- Thu Sep 24
- Dynamic programming too
[scribbles,
video]
[Fredman 1975]
- Tue Sep 29
- Dynamic programming also
[scribbles,
video]
[Wagner Fischer 1974,
Glibert Moore 1959,
Knuth 1971,
Garsia Wachs 1977]
- Thu Oct 1
- Midterm 1 review
[scribbles,
video,
complete solutions]
- Mon Oct 5
- Midterm 1 — 7–9pm, 3124 Siebel
[questions, solutions]
- Tue Oct 6
- No lecture
- Thu Oct 8
- Graph traversal / reachability
[scribbles,
video]
- Tue Oct 13
- Directed graphs: topological sort, strong components
[scribbles,
video]
- Thu Oct 15
- BFS and Shortest paths
[scribbles,
video]
- Tue Oct 20
- Shortest Paths with Negative Lengths
[scribbles,
video]
- Thu Oct 22
- More Shortest Paths
[scribbles,
video]
- Sun Oct 25
- Graph Modeling and DP
[slides,
notes]
- Tue Oct 27
- Introduction to Network Flow
[scribbles,
video]
- Thu Oct 29
- Algorithms for Flow/Cuts
[scribbles,
video]
- Tue Nov 3
- Applications of Flows for Disjoint Paths and Matchings
[scribbles,
video]
- Thu Nov 5
- Midterm 2 Review
[scribbles,
video]
- Mon Nov 9
- Midterm 2 — 7–9pm, location TBA
- Tue Nov 10
- More Applications of Flows/Cuts
[scribbles,
video]
- Thu Nov 12
- Introduction to Linear Programming
[scribbles,
video]
- Fri Nov 15
- Drop deadline
- Tue Nov 17
- Linear Programming Duality, Applications
[scribbles,
video]
- Thu Nov 19
- Continuous and Discrete Optimization, Convexity, Gradient Descent
[scribbles,
video]
- Nov 22–28
- Inconveniently scheduled week-long break
📺
- Tue Dec 1
-
Cool stuff
[scribbles,
video]
- Thu Dec 3
-
More cool stuff
[scribbles,
video]
- Tue Dec 8
- Final exam review
[scribbles,
video]
- Tue Dec 15
- Final exam —
7–10pm,
location TBA