| Day | Date | Instr | Topics Covered | Notes and Readings | HWs/Quizzes |
|---|---|---|---|---|---|
| Tue | Aug 27 | Gary | Lecture 1: Course Intro | ClassNotes-pdf -note -- LectureNotes |
|
| Thu | Aug 29 | Danny | Lecture 2: Dynamic Programming I | LectureNotes | |
| Fri | Aug 30 | Recitation 1 - Recurrences and DP | Recitation 1 Solutions Recurrences |
HW1 Out HW1 Solutions |
|
| Tue | Sep 03 | Danny | Lecture 3: Dynamic Programming II | LectureNotes | |
| Thu | Sep 05 | Gary | Lecture 4: Max Flow I (Forground-Background Problem) | ClassNotes-pdf -note -- LectureNotes |
Quiz 1 |
| Fri | Sep 06 | Recitation 2 - DP + Flow | Recitation 2 Solutions |
||
| Tue | Sep 10 | Danny | Lecture 5: Amortized Analysis | LectureNotes | |
| Thu | Sep 12 | Danny | Lecture 6: Splay Trees | LectureNotes | Quiz 2 HW1 Due HW2 Out HW2 Solutions |
| Fri | Sep 13 | Recitation 3 - Practice with Potentials | Recitation 3 Solutions |
||
| Tue | Sep 17 | Gary | Lecture 7: DFS and Biconnected Components | ClassNotes-pdf -note -- LectureNotes |
|
| Thu | Sep 19 | Gary | Lecture 8: DFS and Strongly Connected Components | [Classnotes]
pdf
-note -- Sleator's notes -- [CLRS Section 22.5] -- Old Scribe Notes |
Quiz 3 |
| Fri | Sep 20 | Recitation 4 - DFS and Strong Components | Recitation 4 Solutions |
||
| Tue | Sep 24 | Gary | Lecture 9: Probablity 101 and the Exponential Dist., Spanners I | [Classnotes]
pdf
-note -- LectureNotes |
HW3 Out HW3 solution |
| Thu | Sep 26 | Gary | Lecture 10: Low Diameter Decomposition via Exp. Dist., Spanners II | [Classnotes]
pdf
-note -- LectureNotes -- Shen Chen's Talk |
Quiz 4 |
| Fri | Sep 27 | Recitation 5 - Exceptionally Exponential | Recitation 5 Solutions |
||
| Tue | Oct 01 | Gary | Lecture 11: Graph Spanners via Low Diameter Decomposition III | [Classnotes]
pdf
-note -- LectureNotes -- Shen Chen's Talk |
|
| Thu | Oct 03 | Danny | Lecture 12: Max Flow II (more advanced algs, i.e. Dinic's) | LectureNotes | Quiz 5 HW3 Due Prac. Exam 1 PE1 soln |
| Fri | Oct 04 | Recitation 6 - Spanners and more max flow | Recitation 6 Solutions |
||
| Tue | Oct 08 | Midterm Exam 1 (HW4 Out) | |||
| Thu | Oct 10 | Danny | Lecture 13: Hashing 1 (Universal and perfect) | LectureNotes | Midterm1 Soln HW4 Out HW4 Soln Quiz 6 |
| Fri | Oct 11 | Recitation 7 - Hashing/LasVegas/MonteCarlo | Recitation 7 Solutions |
||
| Tue | Oct 15 | Danny | Lecture 14: Hashing 2 (primes and fingerprinting) | LectureNotes | |
| Thu | Oct 17 | Gary | Lecture 15: Computational Geometry I (Introduction and Segment Intersection using Sweep Line) | [Classnotes]
pdf
-note -- LectureNotes -- LastYearNotes |
Quiz 7 |
| Fri | Oct 18 | Recitation 8 - NO RECITATION on Fingerprinting | Recitation 8 Solutions |
||
| Tue | Oct 22 | 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 |
|
| Thu | Oct 24 | Gary | Lecture 17: Computational Geometry III (Sorting, Convex Hull, and 2D Random Incremental Convex Hull) | [Classnotes:]
pdf
-note -- LectureNotes |
Quiz 8 HW4 Due HW5 Out HW5 Soln |
| Fri | Oct 25 | Community Day - No Class | |||
| Tue | Oct 29 | Danny | Lecture 18: Computational Geometry IV (closest pair) | LectureNotes | |
| Thu | Oct 31 | Gary | Lecture 19: Linear Programming I | [Classnotes:]
pdf
-note |
|
| Fri | Nov 01 | Recitation 9 - LP: Initial Bounding Box | Recitation 9 | ||
| Tue | Nov 05 | Gary | Lecture 20: Linear Programming II (Duality) | [Classnotes:]
pdf
-note |
HW5 Due |
| Thu | Nov 07 | Midterm Exam 2 (HW6 Out) | |||
| Fri | Nov 08 | Recitation 10 - Modelling problems using LP | Recitation 10 Solutions |
Quiz 9 HW6 Out HW6 Soln |
|
| Tue | Nov 12 | Danny | Lecture 21: Game Theory, Zero-Sum Games | LectureNotes Duality in Games |
|
| Thu | Nov 14 | Gary | Lecture 22: FFT | [Classnotes:]
pdf
-note --LectureNotes |
Quiz 10 |
| Fri | Nov 15 | Recitation 11 - Games, LP, and FFT Examples | Recitation 11 Solutions |
||
| Tue | Nov 19 | Danny | Lecture 23: Competitive Algorithms | LectureNotes | |
| Thu | Nov 21 | Danny | Lecture 24: Suffix Trees and Suffix Arrays | LectureNotes | HW6 Due HW7 Out HW7 Soln Quiz 11 |
| Fri | Nov 22 | Recitation 12 - Competitive Algs and Suffix Tree Applications | Recitation 12 Solutions |
||
| Tue | Nov 26 | Danny | Lecture 25: Computing the Suffix Array and LCP Array | LectureNotes | |
| Thu | Nov 28 | Thanksgiving Holiday - No Class | |||
| Fri | Nov 29 | Thanksgiving Holiday - No Class | |||
| Tue | Dec 03 | Gary | Lecture 26: Parallel Algorithms I: Intro Prescan | [Classnotes:]
pdf
-note |
|
| Thu | Dec 05 | Gary | Lecture 27: Parallel Algorithms II: MIS | [Classnotes:]
pdf
-note --LectureNotes |
Quiz 12 |
| Fri | Dec 06 | Recitation 13 - Suffix Arrays and LCP Arrays | Recitation 13 Solutions |
HW7 Due | |
| Sun | Dec 15 | FINAL -- 8:30-11:30am GHC 4401 |