| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Mon | Jan 13 | Victor | Lecture 1: Introduction, Master Theorem | Slides - Lecture notes supplement |
| Tue | Jan 14 | Recitation 1 - Big-Oh and recurrences. | Recitation notes | |
| Wed | Jan 15 | Victor | Lecture 2: Strassen | Slides - Homework 1 out |
| Fri | Jan 17 | Victor | Lecture 3: FFT | Slides |
| Mon | Jan 20 | Martin Luther King Day - No Class | ||
| Tue | Jan 21 | Recitation 2 - FFT | Recitation notes | |
| Wed | Jan 22 | Victor | Lecture 4: FFT II | Slides - Homework 2 out |
| Fri | Jan 24 | Victor | Lecture 5: Dynamic Programming: I | Slides |
| Mon | Jan 27 | Victor | Lecture 6: Dynamic programming II | Slides |
| Tue | Jan 28 | Recitation 3 - DP | Recitation notes | |
| Wed | Jan 29 | Gary | Lecture 7: Treaps and QuickSort | ClassNotes
- Kozen Chap 13
Homework 3 out |
| Fri | Jan 31 | Gary | Lecture 8: Treaps-Continued + Amortized Analysis Intro | ClassNotes - CLRS Chap 17 |
| Mon | Feb 03 | Gary | Lecture 9: Splay Trees and Amortized Analysis | ClassNotes - Sleator's notes |
| Tue | Feb 04 | Recitation 4 - Treaps, Binomial Heaps, and Amortized Analysis | Recitation notes | |
| Wed | Feb 05 | Gary | Lecture 10: Splay Trees | |
| Fri | Feb 07 | Victor | Lecture 11: Graphs I | Slides - LectureNotes - Homework 4 out |
| Mon | Feb 10 | Victor | Lecture 12: Graphs II | Slides - LectureNotes - Sleator's notes |
| Tue | Feb 11 | Recitation 5 - Access Lemma and Static Optimality of Splay Trees | ||
| Wed | Feb 12 | Victor | Lecture 13: Graphs III | Slides - LectureNotes |
| Fri | Feb 14 | Victor | Lecture 14: Graphs IV | Slides - LectureNotes - Kleinberg-Tardos |
| Mon | Feb 17 | Gary | Lecture 15: Sorting Lower Bounds, Backwards Analysis | ClassNotes-Sorting - ClassNotes-CompGeo |
| Tue | Feb 18 | Recitation 6 - Midterm Review | Recitation notes | |
| Wed | Feb 19 | Gary | Lecture 16: Computational Geometry I: Line Segment Intersection |
ClassNotes -- BKOS Chap 2.1 |
| Fri | Feb 21 | Gary | Lecture 17: Computational Geometry II: 2D-Linear Programming |
ClassNotes -- BKOS Chap 4.3-4.5 - Homework 5 out |
| Mon | Feb 24 | Gary | Lecture 18: Computational Geometry III: LP-Boundedness -- Convex-hull | ClassNotes -- LectureNotes |
| Tue | Feb 25 | Recitation 7 - Minimum Enclosing Disc | Recitation notes | |
| Wed | Feb 26 | Gary | Lecture 19: Computational Geometry IV: Convex-hull Random Incremental | ClassNotes -- LectureNotes |
| Fri | Feb 28 | Gary | Lecture 20: Computational Geometry V: Closest Pair Using Hashing | ClassNotes -- Har-Peled-Chap1 Homework 6 out |
| Mon | Mar 03 | Victor | Lecture 21: Maximum Flow I | A. Blum's notes |
| Tue | Mar 04 | Recitation 8 - Max-Flow and Application of Hashing | Recitation notes | |
| Wed | Mar 05 | Victor | Lecture 22: Maximum Flow II | A. Blum's notes |
| Fri | Mar 07 | Mid Semester Break - No Class | ||
| Mon | Mar 10 | Spring Break - No Class | ||
| Tue | Mar 11 | Spring Break - No Class | ||
| Wed | Mar 12 | Spring Break - No Class | ||
| Fri | Mar 14 | Spring Break - No Class | ||
| Mon | Mar 17 | Victor | Lecture 23: Maximum Flow III | |
| Tue | Mar 18 | Recitation 9 - Applications of Max-Flow and Min-Cut | Recitation notes | |
| Wed | Mar 19 | Victor | Lecture 24: Minimum Cost Maximum Flow | Sleator's notes |
| Fri | Mar 21 | Gary | Lecture 25: Linear Programming Introduction | ClassNotes -- Readings: CLRS Chapter 29 -- A Blum's notes -- Homework 7 out |
| Mon | Mar 24 | Gary | Lecture 26: Linear Programming Examples | Readings: CLRS Chapter 29 -- A Blum's notes |
| Tue | Mar 25 | Recitation 10 - Linear Programming Duality | Recitation notes | |
| Wed | Mar 26 | Gary | Lecture 27: Linear Programming Duality | ClassNotes -- Trevisan Chap 5,6,15 -- Gordon's Notes |
| Fri | Mar 28 | Gary | Lecture 28: Parallel Algorithms I: Intro | ClassNotes -- Homework 8 out |
| Mon | Mar 31 | Gary | Lecture 29: Parallel Algorithms II: Prescan and List Ranking | ClassNotes -- Blelloch Prefix Sum |
| Tue | Apr 01 | Recitation 11 - Parallel Tree Contraction | Notes by Tangwongsan | |
| Wed | Apr 02 | Gary | Lecture 30: Parallel Algorithms III: More List Ranking | ClassNotes -- Reid-Miller Chap 2 |
| Fri | Apr 04 | Gary | Lecture 31: Parallel Algorithms IV: Maximal Independent Set | ClassNotes -- Julian Shun's Notes |
| Mon | Apr 07 | Victor | Lecture 32: NP-Completeness I | LectureNotes |
| Tue | Apr 08 | Recitation 12 - Reductions | ||
| Wed | Apr 09 | Victor | Lecture 33: NP-Completeness II | LectureNotes |
| Fri | Apr 11 | Spring Carnival - No Class | ||
| Mon | Apr 14 | Gary | Lecture 34: Online Algorithms and Competitive Analysis | ClassNotes -- LectureNotes Adamchik -- LectureNotes Sleator |
| Tue | Apr 15 | Recitation 13 - More reductions | Jeff Erickson's notes | |
| Wed | Apr 16 | Gary | Lecture 35: Randomized Online Algorithms | ClassNotes -- LectureNotes Sleator |
| Fri | Apr 18 | Gary | Lecture 36: Randomized Online Algorithms: Continued | ClassNotes -- LectureNotes Sleator |
| Mon | Apr 21 | Victor | Lecture 37: Aproximation Algorithms - I | lecture notes |
| Tue | Apr 22 | Recitation 14 - Parallel MIS and LP-relaxation of Vertex/Set Cover | Kleinberg & Tardos 11.4 and 11.6 | |
| Wed | Apr 23 | Victor | Lecture 38: Aproximation Algorithms - II | lecture notes |
| Fri | Apr 25 | Victor | Lecture 39: String Matching - I | lecture notes |
| Mon | Apr 28 | Victor | Lecture 40: String Matching - II | lecture notes |
| Tue | Apr 29 | Recitation 15 - KMP Revisited | Jeff Erickson's notes | |
| Wed | Apr 30 | Victor | Lecture 41: Tries and Suffix Trees | lecture notes |
| Fri | May 02 | Gary | Lecture 42: TBA Last Class |