| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Wed | Jan 18 | Gary | Lecture 1: Introduction and Strassen's Algorithm | ClassNotes -- Lec 1 Kozen -- Optional Reading: Mathematical Background -- Scribe Notes |
| Fri | Jan 20 | Gary | Lecture 2: Binomial Heaps | ClassNotes -- Lec 8 Kozen -- Scribe Notes |
| Mon | Jan 23 | Gary | Lecture 3: Fibonacci Heap | ClassNotes -- Lec 9 Kozen -- Scribe Notes |
| Wed | Jan 25 | Gary | Lecture 4: BST Introduction and Treaps | ClassNotes -- Lec 13 Kozen -- Scribe Notes |
| Fri | Jan 27 | Gary | Lecture 5: Splay Trees I | ClassNotes -- Sleator's Notes -- Lec 12 Kozen -- Scribe Notes |
| Mon | Jan 30 | Gary | Lecture 6: Splay: Dynamic Optimality Conjecture | ClassNotes -- Sleator's Notes on Static Optimality -- Goemans' Notes -- Scribe Notes |
| Wed | Feb 01 | David | Lecture 7: Dynamic Programming I: Optimal BSTs | ClassNotes -- OldClassNotes -- Lewis Denenberg 6.5 -- [CLRS Chap 15.5] -- Scribe Notes |
| Fri | Feb 03 | David | Lecture 8: Dynamic Programming II: Inference on Graphical Models | ClassNotes -- Mezard and Montanari Chapters 9 and 14 -- Scribe Notes |
| Mon | Feb 06 | David | Lecture 9: Graph Algorithms: Depth-First Search | ClassNotes -- OldClassNotes -- [Readings: Kozen Chaper 4 and CLRS Sections 22.3-22.4] -- Scribe Notes |
| Wed | Feb 08 | David | Lecture 10: Graph Algorithms: Strongly Connected Components | ClassNotes -- OldClassNotes -- Sleator's notes -- [CLRS Section 22.5] -- Scribe Notes |
| Fri | Feb 10 | David | Lecture 11: Probability Review | ClassNotes -- OldClassNotes: Exponential Dist -- Scribe Notes |
| Mon | Feb 13 | Gary | Lecture 12: Low Diameter Decomposition using Exponential Delays | ClassNotes Dasgupta's Notes Scribe Notes |
| Wed | Feb 15 | Gary | Lecture 13: Graph Spanners via Low Diameter Decomposition | ClassNotes Shen Chen Xu's Talk Scribe Notes |
| Fri | Feb 17 | Amir | Lecture 14: Computational Geometry: Introduction and Sweep Line | Lecture Slides OldClassNotes Intro BKOS Sweep Line Scribe Notes |
| Mon | Feb 20 | Gary | Lecture 15: Sorting, Convex Hull, and 2D Random Incremental Convex Hull | ClassNotes Backwards Analysis ClassNotes Convex Hull CH Intro Scribe Notes |
| Wed | Feb 22 | Gary | Lecture 16: Linear Programming: 2D Random Incremental | ClassNotes -- 2D-LP -- Scribe Notes |
| Fri | Feb 24 | Gary | Lecture 17: 2D-Closest Pair using Hashing | ClassNotes -- Har-Peled-Chap-1 -- Scribe Notes |
| Mon | Feb 27 | David | Lecture 18: Max Flow I: Introduction and Ford-Fulkerson | ClassNotes -- OldClassNotes -- [Readings: Kozen Chapter 16] -- Scribe Notes |
| Wed | Mar 01 | David | Lecture 19: Max Flow II: Edmonds-Karp | ClassNotes -- Jeff Erickson's notes on Zwick's example with irrational capacities -- Notes on Edmonds-Karp from CMU 15-451 -- [CLRS 26.2] -- Scribe Notes |
| Fri | Mar 03 | David | Lecture 20: Linear Programming: Introduction | ClassNotes -- Notes from CMU 15-859(E) Lecture 1 (Anupam Gupta) -- OldClassNotes -- [CLRS 29.1-2, 26.3] |
| Mon | Mar 06 | David | Lecture 21: Linear Programming Duality and Max Flow | ClassNotes -- Notes from CMU 15-859(E) Lecture 5 (Anupam Gupta) -- Notes from CMU 15-859(E) Lecture 6 (Anupam Gupta) -- OldClassNotes -- Trevisan Chap 5,6,15 -- Gordon's Notes -- Scribe Notes |
| Wed | Mar 08 | David | Lecture 22: FFT | ClassNotes -- OldClassNotes -- [Readings: Kozen Chapter 35 and CLRS Chapter 30] -- Scribe Notes |
| Fri | Mar 10 | Spring Break - No Class | ||
| Mon | Mar 13 | Spring Break - No Class | ||
| Wed | Mar 15 | Spring Break - No Class | ||
| Fri | Mar 17 | Spring Break - No Class | ||
| Mon | Mar 20 | Midterm review | ||
| Wed | Mar 22 | Midterm - In Class Test | ||
| Fri | Mar 24 | David | Lecture 23: Dimensionality reduction and the Johnson-Lindenstrauss Lemma | ClassNotes -- Anupam Gupta's notes on JL from CMU 15-859E Spring 2015 -- Roman Vershynin's tutorial on random matrix theory with section on subgaussian and subexponential random variables -- Martin Wainwright's book chapter on tail bounds with section on subgaussian and subexponential random variables |
| Mon | Mar 27 | David | Lecture 24: Johnson-Lindenstrauss and compressed sensing | ClassNotes -- Matousek's notes -- Scribe Notes |
| Wed | Mar 29 | Gary | Lecture 25: Resistive Model of a Graph | ClassNotes -- Doyle and Snell -- Bollobas Random Walk Chap IX |
| Fri | Mar 31 | Gary | Lecture 26: Random Walks and Electricity I | ClassNotes -- Lovasz's Survey -- Scribe Notes |
| Mon | Apr 03 | Gary | Lecture 27: Random Walks with Restarts and Spilling Paint | ClassNotes - Spielman's Notes - Berkhin Painting - Andersen and Chung |
| Wed | Apr 05 | Gary | Lecture 28: Midterm Discussion and Little Paint Spilling | ClassNotes |
| Fri | Apr 07 | Gary | Lecture 29: Parallel Algorithms: Parallel models, Work and Time | ClassNotes -- Blelloch Chap 1 |
| Mon | Apr 10 | Gary | Lecture 30: Parallel Algorithms I: Prefix-sum, List-ranking, Parallel Tree Contraction | ClassNotes -- Synthesis of Parallel Algorithms |
| Wed | Apr 12 | Gary | Lecture 31: Parallel Algorithms II: Parallel Tree Contraction, More List-Ranking | ClassNotes-Tree Contraction -- ClassNotes-Opt List Ranking -- Synthesis of Parallel Algorithms |
| Fri | Apr 14 | Gary | Lecture 32: Parallel Algorithms III: Maximal Independent Set | ClassNotes -- [Readings-Out of Date: Kozen Chapters 36 and 37] -- Scribe Notes |
| Mon | Apr 17 | David | Lecture 33: Sparsest Graph Cut I | ClassNotes -- OldClassNotes -- Readings: Trevisan Lecture 4 -- Anupam Gupta's lecture notes from CMU 15-854B Spring 2008 -- Scribe Notes |
| Wed | Apr 19 | David | Lecture 34: Sparsest Graph Cut II | ClassNotes -- OldClassNotes -- Readings: Trevisan Lecture 4 -- Anupam Gupta's lecture notes -- Section 3 of Sanjeev Arora's lecture notes |
| Fri | Apr 21 | Spring Carnival - No Class | ||
| Mon | Apr 24 | David | Lecture 35: Online Algorithms: Paging | ClassNotes -- OldClassNotes -- Sleator's Notes -- CMU 15-451 notes |
| Wed | Apr 26 | David | Lecture 36: NP-Completeness | ClassNotes -- OldClassNotes -- [Readings: Lec 21-25 Kz, Chap 34 CLRS ] -- Scribe Notes |
| Fri | Apr 28 | David | Lecture 37: Proving NP-Completeness via Reductions | ClassNotes -- OldClassNotes -- [Readings: Lec 21-25 Kz, Chap 34 CLRS ] -- Scribe Notes |
| Mon | May 01 | Jason | Lecture 38: Fixed-Parameter Tractibility | ClassNotes -- Readings: Cygan et al. Parameterized Algorithms Sections 3.1, 2.2.1, 5.2, 5.3 and beginning of Chapter 1 -- Scribe Notes |
| Wed | May 03 | David | Lecture 39: Approximation Algorithms | ClassNotes -- OldClassNotes -- KT-11.2 -- [Readings: CLRS Chap 35] -- Avrim Blum's lecture notes on MAX-SAT from 15-859(D) Randomized Algorithms |
| Fri | May 05 | Final review |