Below is the calendar for the class (where italicized descriptions are tentative, and topics with question marks (?) may-or-may-not be covered). This includes the lecture topic, the lecture materials, and the associated suggested reading. The calendar (and links) for the psets are also below.
Each lecture is recorded, and the lecture videos are available at echo360. Access to lecture videos is restricted to students currently enrolled in the class.
# | Date | Day | Topic | Reading | psets |
---|---|---|---|---|---|
1 | 08-27 | T | Logistics, Motivation and Goals (slides, boardwork) | Erickson §1.9 | pset0 (tex, pdf) out |
2 | 08-29 | R | Divide and Conquer | ||
3 | 09-03 | T | Dynamic Programming (slides) | Erickson §3 | pset1 (tex, pdf) out |
09-04 | W | pset0 due | |||
4 | 09-05 | R | Dynamic Programming (slides) | Erickson §3 | |
5 | 09-10 | T | Dynamic Programming (slides) | Erickson §8, §9; KT §6.8-6.10 | pset2 (tex, pdf) out |
09-11 | W | pset1 due | |||
6 | 09-12 | R | Dynamic Programming (slides) | Erickson §D.1, wiki | |
7 | 09-17 | T | Randomized Algorithms (boardwork) | Erickson §Z.1, §Z.2 | pset3 (tex, pdf) out |
09-18 | W | pset2 due | |||
8 | 09-19 | R | Randomized Algorithms (boardwork) | Erickson §Z.4; Har-Peled §10; Harvey §2, §3 | |
9 | 09-24 | T | Randomized Algorithms (boardwork) | Erickson §Z.5; Vadhan §3.5; | |
09-25 | W | pset3 due. pset4 (tex, pdf) out. | |||
10 | 09-26 | R | Randomized Algorithms (slides) | ||
11 | 10-01 | T | Randomized Algorithms (slides) | ||
10-03 | R | Midterm review | pset4 due | ||
10-07 | M | midterm 1: 7-9:30pm | |||
12 | 10-08 | T | Randomized Algorithms (slides) | pset5 (tex, pdf) out | |
13 | 10-10 | R | Flows (boardwork) | Erickson §10.0-10.2,10.5; KT §7.0-7.2 | |
14 | 10-15 | T | Flows (boardwork) | Erickson §10.3-10.4; KT §7.1-7.2 | |
10-16 | W | pset5 due. pset6 (tex, pdf) out. | |||
15 | 10-17 | R | Flows (boardwork) | Erickson §10.6-10.7 | |
10-18 | F | drop date (ugrad) | |||
16 | 10-22 | T | Flows (boardwork) | Erickson §11.3; KT §7.5 | |
10-23 | W | pset6 due. pset7 (tex, pdf) out. | |||
17 | 10-24 | R | Flows (boardwork) | Erickson §10.5, 11.1-11.2,11.6, G.1; KT §7.6,7.12 | |
18 | 10-29 | T | Linear Programming (boardwork) | Erickson §H.1-H.3; Har-Peled §21.5.3 | |
10-30 | W | pset7 due | |||
19 | 10-31 | R | Linear Programming (boardwork) | Erickson §H.4-H.6; Har-Peled §21.5.3 | pset8 (tex, pdf) out |
20 | 11-05 | T | Linear Programming (boardwork) | Chekuri (pdf) | |
11-07 | R | cancelled | pset8 due | ||
11-11 | M | midterm 2: 7-9:30pm | |||
21 | 11-12 | T | Linear Programming | ||
11-13 | W | pset9 (tex, pdf) out | |||
22 | 11-14 | R | NP Completeness (slides) | Erickson §12.1-12.12 | |
11-15 | F | drop date (grad) | |||
23 | 11-19 | T | NP Completeness (slides) | Erickson §12.1-12.12 | |
11-20 | W | pset9 due | |||
24 | 11-21 | R | NP Completeness | Erickson §12.1-12.12 | pset10 (tex, pdf) out |
11-26 | T | fall break | |||
11-28 | R | fall break | |||
25 | 12-03 | T | Approximation Algorithms (slides) | ||
26 | 12-05 | R | Approximation Algorithms (slides) | pset10 due | |
27 | 12-10 | T | Approximation Algorithms | ||
12-18 | W | final: 8-11am |