| Day | Date | Instr | Topics Covered | Notes and Readings | HWs/Quizzes |
|---|---|---|---|---|---|
| Tue | Sep 01 | Gary | Lecture 1: Course Intro and Strassen | ClassNotes-pdf -note -- LectureNotes -Recording |
|
| Thu | Sep 03 | Klaus | Lecture 2: Dynamic Programming I | -- slides -- LectureNotes -Recording |
|
| Fri | Sep 04 | Recitation 1 - Recurrences and DP | Recitation 1 Solutions Recurrences Recording |
HW1 Out HW1 Solutions |
|
| Tue | Sep 08 | Klaus | Lecture 3: Dynamic Programming II | -- slides LectureNotes -Recording |
|
| Thu | Sep 10 | Gary | Lecture 4: Max Flow I (Forground-Background Problem) | ClassNotes-pdf -note -- LectureNotes -Recording |
Quiz 1 |
| Fri | Sep 11 | Recitation 2 - DP + Flow | Recitation 2 Solutions Recording |
||
| Tue | Sep 15 | Klaus | Lecture 5: Amortized Analysis | -- slides LectureNotes -Recording |
Prog 1 Out Prog 1 Solutions |
| Thu | Sep 17 | Klaus | Lecture 6: Splay Trees | -- slides LectureNotes -Recording |
Quiz 2 HW1 Due |
| Fri | Sep 18 | Recitation 3 - Practice with Potentials | Recitation 3 Solutions Recording |
||
| Tue | Sep 22 | Klaus | Lecture 7: DFS and Biconnected Components | -- slides ClassNotes-pdf -note -- LectureNotes -Recording |
HW2 Out HW2 Solutions |
| Thu | Sep 24 | Klaus | Lecture 8: DFS and Strongly Connected Components | -- slides pdf -note -- Sleator's notes -- CLRS Section 22.5] -- [Recording -- Old Scribe Notes |
Quiz 3 |
| Fri | Sep 25 | Recitation 4 - DFS and Strong Components | Recitation 4 Solutions Recording |
||
| Tue | Sep 29 | Gary | Lecture 9: Probablity 101 and the Exponential Dist., Spanners I | [Classnotes]
pdf
-note -- LectureNotes -- Recording |
Prog 2 Out |
| Thu | Oct 01 | Gary | Lecture 10: Low Diameter Decomposition via Exp. Dist., Spanners II | [Classnotes]
pdf
-note -- LectureNotes -- Shen Chen's Talk -- Recording |
Quiz 4 |
| Fri | Oct 02 | Recitation 5 - Exceptionally Exponential | Recitation 5 Solutions Recording |
HW2 Due |
|
| Tue | Oct 06 | Gary | Lecture 11: Graph Spanners via Low Diameter Decomposition III | [Classnotes]
pdf
-note -- LectureNotes -- Shen Chen's Talk -- Recording |
HW3 Out HW3 Solutions |
| Thu | Oct 08 | Midterm Exam 1 | |||
| Fri | Oct 09 | Recitation 6 - Low Diameter Decomposition | Recitation 6 Solutions Recordings -(part 1) (part 2) |
||
| Tue | Oct 13 | Gary | Lecture 12: Max Flow II (more advanced algs, i.e. Dinic's) | [Classnotes]
pdf
-note
-- LectureNotes -- Recording Quiz 5 Prac. Exam 1 PE1 soln |
|
| Thu | Oct 15 | Klaus | Lecture 13: Hashing 1 (Universal and perfect) | --slides LectureNotes -- Recording |
Midterm1 Soln Quiz 6 |
| Fri | Oct 16 | Recitation 7 - Hashing and More Max Flow | Recitation 7 Solutions Recording |
||
| Tue | Oct 20 | Klaus | Lecture 14: Hashing 2 (primes and fingerprinting) | --slides LectureNotes -- Recording |
HW3 Due HW4 Out HW4 Solutions |
| Thu | Oct 22 | Gary | Lecture 15: Computational Geometry I (Introduction and Segment Intersection using Sweep Line) | [Classnotes]
pdf
-note -- LectureNotes -- LastYearNotes -- Recording |
Quiz 7 |
| Fri | Oct 23 | Recitation 8 - Fingerprinting and Sweepline | Recitation 8 Solutions Recording |
||
| Tue | Oct 27 | Gary | Lecture 16: Computational Geometry II (2D LP: Backward Analysis and 2D Random Incremental) | [Classnotes: Backwards Analysis]
pdf
-note [Classnotes: 2D-LP] pdf -note -- LectureNotes -- Recording |
Prog 3 Out |
| Thu | Oct 29 | Gary | Lecture 17: Computational Geometry III (Sorting, Convex Hull, and 2D Random Incremental Convex Hull) | [Classnotes:]
pdf
-note -- LectureNotes -- Recording |
Quiz 8 |
| Fri | Oct 30 | Recitation 9 - LP: Initial Bounding Box | Recitation 9 Solutions Recording |
||
| Tue | Nov 03 | Gary | Lecture 18: Computational Geometry IV (closest pair) | [Classnotes:]
pdf
-note LectureNotes -Recording |
Quiz 8 HW4 Due Nov 1-2 HW5 Out HW5 Solutions |
| Thu | Nov 05 | Klaus | Lecture 19: Linear Programming I | -- slides --Recording |
|
| Fri | Nov 06 | Recitation 10 - Computational Geometry | Recitation 10 Solutions Recordings -(rectangles) (polygon) |
||
| Tue | Nov 10 | Klaus | Lecture 20: Linear Programming II (Duality) | [Classnotes:]
-- slides pdf -note --Recording |
|
| Thu | Nov 12 | Klaus | Lecture 21: Game Theory, Zero-Sum Games | -- slides LectureNotes Duality in Games --Recording |
|
| Fri | Nov 13 | Recitation 11 - Game Theory and more LP | Recitation 11 Solutions Recording |
||
| Tue | Nov 17 | Gary | Lecture 22: FFT | [Classnotes:]
pdf
-note --LectureNotes --Recording |
Quiz 10 |
| Thu | Nov 19 | Klaus | Lecture 23: Suffix Trees and Suffix Automata | -- slides LectureNotes --Recording |
HW5 Due HW6 Out Quiz 11 |
| Fri | Nov 20 | Recitation 12 - FFT and Suffix Trees | Recitation 12 Solutions Recording |
||
| Tue | Nov 24 | Klaus | Lecture 24: Suffix Array and LCP Array | -- slides LectureNotes --Recording |
Prog 6 Out |
| Thu | Nov 26 | Thanksgiving Holiday - No Class | |||
| Fri | Nov 27 | Thanksgiving Holiday - No Class | |||
| Tue | Dec 01 | Klaus | Lecture 25: Competitive Algorithms | -- slides LectureNotes --Recording |
HW6 Due HW7 Out HW7 Solutions |
| Thu | Dec 03 | Gary | Lecture 26: The Resistive View of a Graph | [Classnotes:]
pdf
-note LectureNotes --Recording |
|
| Fri | Dec 04 | Recitation 13 - Competitive Algs and Suffix Tree Applications | Recitation 13 Solutions |
||
| Tue | Dec 08 | Gary | Lecture 27: Random Walks in a Graph | [Classnotes:]
pdf
-note LectureNotes --Recording |
|
| Thu | Dec 10 | Gary | Lecture 28: Random Walks with Restarts and Spilling Paint | [Classnotes:]
pdf
-note - Spielman's Notes - Berkhin Painting - Andersen and Chung --Recording |
|
| Fri | Dec 11 | Recitation 14 - Random Walks on a Graph | Quiz 10 HW7 Due Dec 10-11 |