| Day | Date | Instr | Topics Covered | Notes and Readings |
|---|---|---|---|---|
| Mon | Jan 14 | Medical Break - No Class | ||
| Wed | Jan 16 | Gary | Lecture 1: Introduction and Strassen's Algorithm | [ClassNotes]
pdf
-note -- Lec 1 Kozen -- Optional Reading: Mathematical Background -- Old Scribe Notes |
| Fri | Jan 18 | Gary | Lecture 2: Binomial Heaps | [ClassNotes]
pdf
-note -- Lec 8 Kozen -- Old Scribe Notes |
| Mon | Jan 21 | Martin Luther King Day; - No Class | ||
| Wed | Jan 23 | Gary | Lecture 3: Fibonacci Heap | [Classnotes]
pdf
-note -- Lec 9 Kozen -- Old Scribe Notes |
| Fri | Jan 25 | Gary | Lecture 4: BST Introduction and Treaps | [Classnotes]
pdf
-note -- Lec 13 Kozen -- Old Scribe Notes |
| Mon | Jan 28 | Gary | Lecture 5: Splay Trees I | [Classnotes]
pdf
-note -- Sleator's Notes -- Lec 12 Kozen -- Old Scribe Notes |
| Wed | Jan 30 | Cold Weather Day - No Class | ||
| Fri | Feb 01 | Gary | Lecture 6: Splay Trees II and Optimality Conjecture | [Classnotes]
pdf
-note -- Sleator's Notes on Static Optimality -- Goemans' Notes -- Old Scribe Notes |
| Mon | Feb 04 | David | Lecture 7: Van Emde Boas Trees | [Classnotes] pdf -- CLRS Chp 20 -- Scribe Notes |
| Wed | Feb 06 | Gary | Lecture 8: Dynamic Programming I: Fitting Functions to Data | [Classnotes]
pdf
-note -- KT Chp 6.3 |
| Fri | Feb 08 | Gary | Lecture 9: Dynamic Programming II: Inference on Graphical Models | [Classnotes]
pdf
-note -- Mezard and Montanari Chapters 9 and 14 -- Old Scribe Notes |
| Mon | Feb 11 | Gary | Lecture 10: Graph Algorithms: Depth-First Search | [Classnotes]
pdf
-note -- [Readings: Kozen Chaper 4 and CLRS Sections 22.3-22.4] -- Old Scribe Notes |
| Wed | Feb 13 | Gary | Lecture 11: Graph Algorithms: Strongly Connected Components | [Classnotes]
pdf
-note -- Sleator's notes -- [CLRS Section 22.5] -- Old Scribe Notes |
| Fri | Feb 15 | Gary | Lecture 12: Probability Review | [Classnotes]
pdf
-note -- Old Scribe Notes -- Scribe Notes |
| Mon | Feb 18 | Gary | Lecture 13: Low Diameter Decomposition using Exponential Delays | [Classnotes]
pdf
-note Dasgupta's Notes Old Scribe Notes |
| Wed | Feb 20 | Gary | Lecture 14: Graph Spanners via Low Diameter Decomposition | [Classnotes]
pdf
-note Shen Chen Xu's Talk Old Scribe Notes |
| Fri | Feb 22 | Gary | Lecture 15: Computational Geometry: Introduction and Segment Intersection using Sweep Line | [Classnotes]
pdf
-note [ClassNotes-BackwardAnalysis] pdf -note Lecture Slides 2017 Intro BKOS Sweep Line Old Scribe Notes |
| Mon | Feb 25 | Gary | Lecture 16: Linear Programming: Backward Analysis and 2D Random Incremental | [ClassNotes-BackwardAnalysis]
pdf
[Classnotes]
pdf
-note -- 2D-LP -- Old Scribe Notes |
| Wed | Feb 27 | Gary | Lecture 17: Sorting, Convex Hull, and 2D Random Incremental Convex Hull | [Classnotes]
pdf
-note CH Intro Old Scribe Notes |
| Fri | Mar 01 | Midterm Review | ||
| Mon | Mar 04 | SCS Open House - No Class | ||
| Wed | Mar 06 | Midterm - In Class Test | ||
| Fri | Mar 08 | Spring Break - No Class | ||
| Mon | Mar 11 | Spring Break - No Class | ||
| Wed | Mar 13 | Spring Break - No Class | ||
| Fri | Mar 15 | Spring Break - No Class | ||
| Mon | Mar 18 | Gary | Lecture 18: 2D-Closest Pair using Hashing | [Classnotes]
pdf
-note -- Har-Peled-Chap-1 -- Old Scribe Notes |
| Wed | Mar 20 | 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 22 | Gary | Lecture 20: Max Flow I: Introduction and Ford-Fulkerson | [Classnotes]
pdf
-note -- [Readings: Kozen Chapter 16] -- Old Scribe Notes |
| Mon | Mar 25 | Gary | Lecture 21: Max Flow II: Preflow-Push | pdf -note -- Kleinberg-Tardos 7.4 |
| Wed | Mar 27 | Gary | Lecture 22: Preflow-Push analysis | pdf -note |
| Fri | Mar 29 | 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 -- Old Scribe Notes |
| Mon | Apr 01 | Gary | Lecture 24: Basis Pursuit and the Johnson–Lindenstrauss | [Classnotes]
pdf
-note -- Matousek's notes -- Rudelson and Vershynin's notes -- Old Scribe Notes |
| Wed | Apr 03 | Gary | Lecture 25: Fast Fourier Transform FFT | [Classnotes]
pdf
-note -- [Readings: Kozen Chapter 35 and CLRS Chapter 30] -- Old Scribe Notes |
| Fri | Apr 05 | Gary | Lecture 26: Brunn-Minkowski | [Classnotes]
pdf
-note --Har-Peled-Chap-19 |
| Mon | Apr 08 | Gary | Lecture 27: Brunn-Minkowski II | [Classnotes]
pdf
-note --Har-Peled-Chap-19 |
| Wed | Apr 10 | Gary | Lecture 28: 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 -- Old Scribe Notes |
| Fri | Apr 12 | Spring Carnival - No Class | ||
| Mon | Apr 15 | Gary | Lecture 29: Resistive Model of a Graph | [Classnotes]
pdf
-note -- Doyle and Snell -- Bollobas Random Walk Chap IX |
| Wed | Apr 17 | Gary | Lecture 30: Random Walks and Electricity I | [Classnotes]
pdf
-note -- Lovasz's Survey -- Old Scribe Notes |
| Fri | Apr 19 | Gary | Lecture 31: Random Walks with Restarts and Spilling Paint | [Classnotes]
pdf
-note - Spielman's Notes - Berkhin Painting - Andersen and Chung |
| Mon | Apr 22 | Gary | Lecture 32: A Little Paint Spilling | [Classnotes]
pdf
-note |
| Wed | Apr 24 | Gary | Lecture 33: Parallel Algorithms: Parallel models, Work and Time | [Classnotes]
pdf
-note -- Blelloch Chap 1 -- Old Scribe Notes |
| Fri | Apr 26 | Gary | Lecture 34: Parallel Algorithms I: Prefix-sum, List-ranking, Parallel Tree Contraction | [Classnotes]
pdf
-note -- Synthesis of Parallel Algorithms -- Old Scribe Notes |
| Mon | Apr 29 | Gary | Lecture 35: Parallel Algorithms II: Maximal Independent Set | [OldClassnotes]
pdf
-note -- [Readings-Out of Date: Kozen Chapters 36 and 37] -- Old Scribe Notes |
| Wed | May 01 | 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 -- Old Scribe Notes |
| Fri | May 03 | David | Lecture 37: Approximate Max-Multicommodity-Flow Min-Cut and Sparsest Graph Cut | [ClassNotes] pdf -- Dana Randall's lecture notes |