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
Gates and Papadimitrou 1979,
Chitturi et al 2009
(best current bounds for pancake sorting)]
- Fri Sep 4
- Add deadline
- Mon Sep 7
- Labor Day
- Tue Sep 8
- Recursive algorithms: binary search, find local maximum
[scribbles,
video]
- Thu Sep 10
- Divide and conquer: median of two sorted arrays, mergesort, quicksort
[scribbles,
video,
Goldstine and von Neumann 1947 (see §11.4).
Hoare 1961]
-
Tue Sep 15
- More divide and conquer: quickselect, Karatsuba multiplication
[scribbles,
video]
- Thu Sep 17
- Backtracking
[scribbles,
video]
- Tue Sep 22
- Dynamic programming
[scribbles,
video]
- Thu Sep 24
- Dynamic programming too
[scribbles,
video]
- Tue Sep 29
- Dynamic programming also
[scribbles,
video]
- Thu Oct 1
- Midterm 1 review
[scribbles,
video]
- Mon Oct 5
- [tentatively rescheduled from September 28]
Midterm 1 — 7–9pm, location TBA
- Tue Oct 6
- Graph structure and representation
[scribbles,
video]
- Thu Oct 8
- Graph traversal / reachability
[scribbles>,
video]
- Tue Oct 13
- Directed graphs: topological sort, strong components
[scribbles,
video]
- Thu Oct 15
- Shortest paths
[scribbles,
video]
- Tue Oct 20
- Graph modeling and reductions
[scribbles,
video]
- Thu Oct 22
- Local search
[scribbles,
video]
- Tue Oct 27
- More local search
[scribbles,
video]
- Thu Oct 29
- Midterm 2 review
[scribbles,
video]
- Mon Nov 2
- Midterm 2 — 7–9pm, location TBA
- Tue Nov 3
- Introduction to flows and matchings
[scribbles,
video]
- Thu Nov 5
- Flow/cut/matching algorithms
[scribbles,
video]
- Tue Nov 10
- Applications of flows and matchings
[scribbles,
video]
- Thu Nov 12
- More applications of flows and matchings
[scribbles,
video]
- Fri Nov 15
- Grad drop deadline
- Tue Nov 17
- Linear programming
[scribbles,
video]
- Thu Nov 19
- Optimization
[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