Schedule

Please keep in mind that this is very preliminary and will change.

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