Schedule

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

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