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 associated suggested reading, lecture recordings, and occasionally a .pdf file of the lecture slides. The psets and pset-schedule are also below.
| # | Date | Topic | Reading | psets | Video | ||
|---|---|---|---|---|---|---|---|
| 1 | 08-26 | W | Logistics, Motivation and Goals | Erickson §1.9 | .mp4 | ||
| 08-27 | R | pset0.tex/.pdf out. | |||||
| 2 | 08-28 | F | Divide and Conquer | .mp4 | |||
| 3 | 09-02 | W | Dynamic Programming (Sequences) | Erickson §3 | .mp4 .pdf | ||
| 09-03 | R | pset0 due (solutions). pset1.tex/.pdf out. |
|||||
| 4 | 09-04 | F | Dynamic Programming (Trees) | Erickson §3 | .mp4 .pdf | ||
| 5 | 09-09 | W | Dynamic Programming (Shortest Paths) | Erickson §8, §9; KT §6.8-6.10 | .mp4 .pdf | ||
| 09-10 | R | pset1 due (solutions). pset2.tex/.pdf out. |
|||||
| 6 | 09-11 | F | Dynamic Programming (Space saving) | Erickson §D.1, wikipedia on LIS | .mp4 .pdf | ||
| 7 | 09-16 | W | Randomized Algorithms | Erickson DC §1 | .mp4 | ||
| 09-17 | R | pset2 due (solutions). pset3.tex/.pdf out. |
|||||
| 8 | 09-18 | F | Randomized Algorithms | Erickson DC §4; Har-Peled §10; Harvey §2, §3 | .mp4 | ||
| 9 | 09-23 | W | Randomized Algorithms (Hashing) | Erickson §Z.5; Vadhan §3.5; | .mp4, .pdf | ||
| 09-24 | R | pset3 due (solutions). pset4.tex/.pdf out. |
|||||
| 10 | 09-25 | F | Randomized Algorithms (Fingerprinting) | .mp4, .pdf | |||
| 11 | 09-30 | W | Randomized Algorithms (Freivalds etc) | .mp4, .pdf | |||
| 10-01 | R | pset4 due (solutions). | |||||
| 10-02 | F | No video | |||||
| 12 | 10-07 | W | Network Flow (Introduction) | Erickson §10.0-10.2,10.5; KT §7.0-7.2 | |||
| 10-08 | R | exam1: 6:30-9:30pm (solutions) | |||||
| 13 | 10-09 | F | Network Flow (Algorithms) | Erickson §10.3-10.4; KT §7.1-7.2 | pset5 .tex/.pdf out | ||
| 14 | 10-14 | W | Network Flow (Algorithms) | Erickson §10.6-10.7 | |||
| 15 | 10-16 | F | Network Flow (Applications) | Erickson §11.3; KT §7.5 | pset6 .tex/.pdf out | ||
| 16 | 10-21 | W | Network Flow (Applications) | Erickson §10.5, 11.1-11.2,11.6, G.1; KT §7.6,7.12 | |||
| 10-22 | R | pset5 due (solutions). | |||||
| 17 | 10-23 | F | Linear Programming (Intro) | Erickson §H.1-H.3; Har-Peled §21.5.3 | |||
| 18 | 10-28 | W | Linear Programming (Simplex) | Erickson §H.4-H.6; Har-Peled §21.5.3 | |||
| pset7 .tex/.pdf out | |||||||
| 10-29 | R | pset6 due (solutions). | |||||
| 19 | 10-30 | F | Linear Programming (Duality) | Erickson §H.4-H.6; Chekuri (pdf) | |||
| 20 | 11-04 | W | Reductions | ||||
| R | pset7 due (solutions) pset8.tex/.pdf out. |
||||||
| 11-06 | F | NP Completeness | Erickson §12.1-12.12 | ||||
| 21 | 11-11 | W | NP Completeness | Erickson §12.1-12.12 | |||
| R |
|
||||||
| 22 | 11-13 | F | |||||
| 11-15 | S | exam2 review session: 7.00-8.30pm | |||||
| 11-16 | M | exam2: 6:30-9:30pm (solutions) | |||||
| 23 | 11-18 | W | pset9 .tex/.pdf out | ||||
| 24 | 11-20 | F | Heuristics and Approx Algrotihms | Erickson notes | |||
| 11-25 | W | break | |||||
| 11-27 | F | break | |||||
| 25 | 12-02 | W | Approximation Algrotihms |
|
|||
| 12-03 | R | pset9 due (solutions) | |||||
| 26 | 12-04 | F | Approximation Algrotihms |
|
|||
| 27 | 12-09 | W | Optional, not for submission Fall 2019: pset10 (solutions) Fall 2019: pset11 Fall 2016: hw10 Fall 2016: hw11 |
||||
| 12-?? | final |