| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Mon | Jan 11 | Gary | Lecture 1: Introduction and Strassen's Algorithm | ClassNotes -- Lec 1 Kozen -- Optional Reading: Mathematical Background |
| Wed | Jan 13 | Gary | Lecture 2: Binomial Heaps | ClassNotes -- Lec 8 Kozen |
| Fri | Jan 15 | Gary | Lecture 3: Fibonacci Heap | ClassNotes -- Lec 9 Kozen |
| Mon | Jan 18 | Martin Luther King Day - No Class | ||
| Wed | Jan 20 | Gary | Lecture 4: BST Introduction and Treaps | ClassNotes -- Lec 13 Kozen |
| Fri | Jan 22 | Graph Isomorphism Day - No Class | ||
| Mon | Jan 25 | Gary | Lecture 5: Splay Trees I | ClassNotes -- Sleator's Notes -- Lec 12 Kozen |
| Wed | Jan 27 | Gary | Lecture 6: Splay Trees II | -- Sleator's Notes on Static Optimality |
| Fri | Jan 29 | Gary | Lecture 7: Dynamic Programming: Optimal BST's | ClassNotes -- Lewis Denenberg 6.5 -- [CLRS Chap 15.5] |
| Mon | Feb 01 | Gary | Lecture 8: Dynamic Programming: Uniquely Decipherable Codes | ClassNotes-UD-Codes -- ClassNotes-Coloring -- Even |
| Wed | Feb 03 | Gary | Lecture 9: Graph Algorithms: Depth-first Search | ClassNotes -- [Readings: Kozen Chaper 4 and CLRS Chapter 22] |
| Fri | Feb 05 | Gary | Lecture 10: Graph Algorithms: Strongly Connected Components | ClassNotes
-- Sleator's notes |
| Mon | Feb 08 | Gary | Lecture 11: Graph Algorithms: Low Diameter Decomposition | ClassNotes
ClassNotes: Exponential Dist |
| Wed | Feb 10 | Gary | Lecture 12: Low Diameter Decomposition using Exponential Delays | ClassNotes
ClassNotes: Exponential Dist Dasgupta's Notes |
| Fri | Feb 12 | Gary | Lecture 13: Graph Spanners via Low Diameter Decomposition | ClassNotes Shen Chen Xu's Talk |
| Mon | Feb 15 | Gary | Lecture 14: Computational Geometry: Introduction and Sweep Line | ClassNotes Intro BKOS Sweep Line |
| Wed | Feb 17 | Gary | Lecture 15: Sorting, Convex Hull, and 2D Random Incremental Convex Hull | ClassNotes Convex Hull ClassNotes Backwards Analysis CH Intro |
| Fri | Feb 19 | Gary | Lecture 16: Linear Programming: 2D Random Incremental | ClassNotes -- 2D-LP |
| Mon | Feb 22 | Gary | Lecture 17: Linear Programming: 2D Random Incremental | ClassNotes -- 2D-LP |
| Wed | Feb 24 | Gary | Lecture 18: 2D-Closest Pair using Hashing | ClassNotes -- Har-Peled-Chap-1 |
| Fri | Feb 26 | Gary | Lecture 19: Linear Programming: Introduction | ClassNotes -- [Readings: CLRS Chaper 29 ] |
| Mon | Feb 29 | Gary | Lecture 20: Max Flow Intro | ClassNotes -- [Readings: Kozen Chaper 16 ] |
| Wed | Mar 02 | Gary | Lecture 21: Max Flow II: Preflow-Push | ClassNotes -- Kleinberg-Tardos 7.4 |
| Fri | Mar 04 | Spring Break - No Class | ||
| Mon | Mar 07 | Spring Break - No Class | ||
| Wed | Mar 09 | Spring Break - No Class | ||
| Fri | Mar 11 | Spring Break - No Class | ||
| Mon | Mar 14 | Gary | Lecture 22: Preflow-Push analysis | ClassNotes |
| Wed | Mar 16 | Gary | Lecture 23: Linear Programming Duality and Max Flow | ClassNotes -- Trevisan Chap 5,6,15 -- Gordon's Notes |
| Fri | Mar 18 | Gary | Lecture 24: FFT | ClassNotes -- [Readings: Kozen Chaper 35 and CLRS Chapter 30] |
| Mon | Mar 21 | Gary | Lecture 25: Simple String Matching Algorithms | ClassNotes -- [Readings: CLRS Chapter 32 ] |
| Wed | Mar 23 | Gary | Lecture 26: FFT and String Matching with Wildcards | ClassNotes -- Handout I -- Handout II -- Handout III |
| Fri | Mar 25 | Midterm review | ||
| Mon | Mar 28 | Midterm - In Class Test | ||
| Wed | Mar 30 | Gary | Lecture 27: Parallel Algorithms: Parallel models, Work and Time | ClassNotes -- Blelloch Chap 1 |
| Fri | Apr 01 | Gary | Lecture 28: Parallel Algorithms I: Prefix-sum, List-ranking, Parallel Tree Contraction | ClassNotes -- Synthesis of Parallel Algorithms |
| Mon | Apr 04 | Gary | Lecture 29: Parallel Algorithms II: More List-Ranking, Parallel Tree Contraction | ClassNotes -- ClassNotes -- Synthesis of Parallel Algorithms |
| Wed | Apr 06 | Gary | Lecture 30: Parallel Algorithms III: Maximal Independent Set | ClassNotes -- [Readings: Kozen Chapters 36 and 37] |
| Fri | Apr 08 | Gary | Lecture 31: Planar Graphs: Separator Theorem | ClassNotes -- [Readings: Kozen Chapters 14 and 15] |
| Mon | Apr 11 | Gary | Lecture 32: Planar Separator and Sparsest Graph Cut | ClassNotes -- Readings: Trevisan Lecture 4 |
| Wed | Apr 13 | Gary | Lecture 33: Sparsest Graph Cut and Generalizations | ClassNotes -- Readings: Trevisan Lecture 4 |
| Fri | Apr 15 | Spring Carnival - No Class | ||
| Mon | Apr 18 | Gary | Lecture 34: Resistive Model of a Graph | ClassNotes -- Doyle and Snell -- Bollobas Random Walks Chap IX |
| Wed | Apr 20 | Gary | Lecture 35: Random Walks and Electricity I | ClassNotes: Class-Notes Random Walks -- ClassNotes: Rayleigh Monotonicity -- Lovasz's Survey -- [Readings: CLRS Chapter 32 ] |
| Fri | Apr 22 | Gary | Lecture 36: Random Walks and Electricity II | ClassNotes: Class-Notes Random Walks -- ClassNotes: Rayleigh Monotonicity -- Lovasz's Survey -- [Readings: CLRS Chapter 32 ] |
| Mon | Apr 25 | Gary | Lecture 37: Online Algorithms: K-Server | ClassNotes -- Sleator's Notes |
| Wed | Apr 27 | Gary | Lecture 38: Approximation Algorithms | ClassNotes -- KT-11.2 -- [Readings: CLRS Chap 35] |
| Fri | Apr 29 | Goran-Laxman-Vijay | Lecture 39: Last Lecture TBA |