| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Wed | Jan 17 | Gary | Lecture 1: Introduction and Strassen's Algorithm | [ClassNotes]
pdf
-note -- Lec 1 Kozen -- Optional Reading: Mathematical Background -- Scribe Notes |
| Fri | Jan 19 | Gary | Lecture 2: Binomial Heaps | [ClassNotes]
pdf
-note -- Lec 8 Kozen -- Scribe Notes |
| Mon | Jan 22 | Gary | Lecture 3: Fibonacci Heap | [ClassNotes]
pdf
-note -- Lec 9 Kozen -- Scribe Notes |
| Wed | Jan 24 | Gary | Lecture 4: BST Introduction and Treaps | [ClassNotes]
pdf
-note -- Lec 13 Kozen -- Scribe Notes |
| Fri | Jan 26 | Gary | Lecture 5: Splay Trees I | [ClassNotes]
pdf
-note -- Sleator's Notes -- Lec 12 Kozen -- Scribe Notes |
| Mon | Jan 29 | Gary | Lecture 6: Splay: Dynamic Optimality Conjecture | [ClassNotes]
pdf
-note -- Sleator's Notes on Static Optimality -- Goemans' Notes -- Scribe Notes |
| Wed | Jan 31 | Gary | Lecture 7: Dynamic Programming I: Optimal BSTs | [ClassNotes]
pdf
-note -- Lewis Denenberg 6.5 -- [CLRS Chap 15.5] -- Scribe Notes |
| Fri | Feb 02 | Gary | Lecture 8: Dynamic Programming II: Inference on Graphical Models | [ClassNotes]
pdf
-note ClassNotes-s17 -- Mezard and Montanari Chapters 9 and 14 -- Scribe Notes |
| Mon | Feb 05 | Gary | Lecture 9: Graph Algorithms: Depth-First Search | [ClassNotes]
pdf
-note -- [Readings: Kozen Chaper 4 and CLRS Sections 22.3-22.4] -- Scribe Notes |
| Wed | Feb 07 | Gary | Lecture 10: Graph Algorithms: Strongly Connected Components | [ClassNotes]
pdf
-note -- Sleator's notes -- [CLRS Section 22.5] -- Scribe Notes |
| Fri | Feb 09 | Gary | Lecture 11: Probability Review | [ClassNotes]
pdf
-note -- Scribe Notes |
| Mon | Feb 12 | Gary | Lecture 12: Low Diameter Decomposition using Exponential Delays | [ClassNotes]
pdf
-note Dasgupta's Notes Scribe Notes |
| Wed | Feb 14 | Gary | Lecture 13: Graph Spanners via Low Diameter Decomposition | [ClassNotes]
pdf
-note Shen Chen Xu's Talk Scribe Notes |
| Fri | Feb 16 | Gary | Lecture 14: Computational Geometry: Introduction and Backward Analysis | [ClassNotes]
pdf
-note [ClassNotes-BackwardAnalysis] pdf -note Lecture Slides 2017 Intro BKOS Sweep Line Scribe Notes |
| Mon | Feb 19 | Gary | Lecture 15: Computational Geometry: Segment Intersection using Sweep Line | [ClassNotes]
pdf
-note Lecture Slides 2017 Intro BKOS Sweep Line Scribe Notes |
| Wed | Feb 21 | Gary | Lecture 16: Linear Programming: 2D Random Incremental | [ClassNotes]
pdf
-note -- 2D-LP -- Scribe Notes |
| Fri | Feb 23 | Gary | Lecture 17: Sorting, Convex Hull, and 2D Random Incremental Convex Hull | [ClassNotes]
pdf
-note CH Intro Scribe Notes |
| Mon | Feb 26 | Gary | Lecture 18: 2D-Closest Pair using Hashing | [ClassNotes]
pdf
-note -- Har-Peled-Chap-1 -- Scribe Notes |
| Wed | Feb 28 | Gary | Lecture 19: Linear Programming: Introduction | [ClassNotes]
pdf
-note -- Notes from CMU 15-859(E) Lecture 1 (Anupam Gupta) -- [CLRS 29.1-2, 26.3] |
| Fri | Mar 02 | Midterm review | ||
| Mon | Mar 05 | SCS open House - No Class | ||
| Wed | Mar 07 | Midterm - In Class Test | ||
| Fri | Mar 09 | Spring Break - No Class | ||
| Mon | Mar 12 | Spring Break - No Class | ||
| Wed | Mar 14 | Spring Break - No Class | ||
| Fri | Mar 16 | Spring Break - No Class | ||
| Mon | Mar 19 | Gary | Lecture 20: Max Flow I: Introduction and Ford-Fulkerson | [ClassNotes]
pdf
-note -- [Readings: Kozen Chapter 16] -- Scribe Notes |
| Wed | Mar 21 | Gary | Lecture 21: Max Flow II: Preflow-Push | pdf -note -- Kleinberg-Tardos 7.4 |
| Fri | Mar 23 | Gary | Lecture 22: Preflow-Push analysis | pdf -note |
| Mon | Mar 26 | Gary | Lecture 23: Linear Programming Duality and Max Flow | pdf -note -- Notes from CMU 15-859(E) Lecture 5 (Anupam Gupta) -- Notes from CMU 15-859(E) Lecture 6 (Anupam Gupta) -- Trevisan Chap 5,6,15 -- Gordon's Notes -- Scribe Notes |
| Wed | Mar 28 | Gary | Lecture 24: Basis Pursuit and the Johnson–Lindenstrauss | [ClassNotes]
pdf
-note -- Matousek's notes -- Scribe Notes |
| Fri | Mar 30 | Ellango | Lecture 25: FFT | ClassNotes-s18 -- [Readings: Kozen Chapter 35 and CLRS Chapter 30] -- Scribe Notes |
| Mon | Apr 02 | Gary | Lecture 26: Brunn-Minkowski | [ClassNotes]
pdf
-note --Har-Peled-Chap-19 |
| Wed | Apr 04 | Gary | Lecture 27: Dimensionality reduction and the Johnson-Lindenstrauss Lemma | [ClassNotes]
pdf
-note -- 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 -- Scribe Notes |
| Fri | Apr 06 | Gary | Lecture 28: Resistive Model of a Graph | [ClassNotes]
pdf
-note -- Doyle and Snell -- Bollobas Random Walk Chap IX |
| Mon | Apr 09 | Gary | Lecture 29: Random Walks and Electricity I | [ClassNotes]
pdf
-note -- Lovasz's Survey -- Scribe Notes |
| Wed | Apr 11 | Gary | Lecture 30: Random Walks with Restarts and Spilling Paint | [ClassNotes]
pdf
-note - Spielman's Notes - Berkhin Painting - Andersen and Chung |
| Fri | Apr 13 | Gary | Lecture 31: A Little Paint Spilling | [ClassNotes]
pdf
-note |
| Mon | Apr 16 | Gary | Lecture 32: Parallel Algorithms: Parallel models, Work and Time | [ClassNotes]
pdf
-note -- Blelloch Chap 1 -- Scribe Notes |
| Wed | Apr 18 | Jonah Sherman | Lecture 33: Special Lecture in GHC 6115. | Guest lecture: Approximating Undirected Multicommodity Flow in Nearly-Linear Time. |
| Fri | Apr 20 | Spring Carnival - No Class | ||
| Mon | Apr 23 | Gary | Lecture 34: Parallel Algorithms I: Prefix-sum, List-ranking, Parallel Tree Contraction | [ClassNotes]
pdf
-note -- Synthesis of Parallel Algorithms -- Scribe Notes |
| Wed | Apr 25 | Gary | Lecture 35: Parallel Algorithms II: Maximal Independent Set | [ClassNotes]
pdf
-note -- [Readings-Out of Date: Kozen Chapters 36 and 37] -- Scribe Notes |
| Fri | Apr 27 | Gary | Lecture 36: Parallel Algorithms III: Parallel Tree Contraction, More List-Ranking | [ClassNotes-Tree Contration]
pdf
-note -- ClassNotes-Opt List Ranking -- Synthesis of Parallel Algorithms -- Scribe Notes |
| Mon | Apr 30 | Gary | Lecture 37: Sparsest Graph Cut I | [ClassNotes]
pdf
-note -- Readings: Trevisan Lecture 4 -- Anupam Gupta's lecture notes from CMU 15-854B Spring 2008 -- Scribe Notes |
| Wed | May 02 | Gary | Lecture 38: Sparsest Graph Cut II | ClassNotes-s17 -- ClassNotes-s16 -- Readings: Trevisan Lecture 4 -- Anupam Gupta's lecture notes -- Section 3 of Sanjeev Arora's lecture notes |
| Fri | May 04 | Gary | Lecture 39: Online Algorithms: Paging | ClassNotes-s17 -- ClassNotes-s16 -- Sleator's Notes -- CMU 15-451 notes |