Day  Date  Instr  Topics Covered  Notes and Readings  Assignments 

Mon  Feb 01  Gary  Lecture 1: Introduction and Course topics.  [ClassNotesIntro]
pdf
note Recording 

Wed  Feb 03  Gary  Lecture 2: Introduced Graph Laplacian, Effective Resistance, and Rayleigh's Monotonicity Law.  [ClassNotes]
pdf
note  Doyle and Snell: Random Walks and Electric Networks [ScribeNotes] pdf Recording 

Fri  Feb 05  Gary  Lecture 3: Random Walks on Graphs and Cummute Time  [ClassNotes]
pdf
note [ScribeNotes] pdf Recording 

Mon  Feb 08  Gary  Lecture 4: Random Walks on Graphs and Mixing  [ClassNotes]
pdf
note Recording 

Wed  Feb 10  Gary  Lecture 5: Perron Frobenius and Symmetric Perron Frobenius.  [ClassNotes]
pdf
note  Spielman3 Recording 

Fri  Feb 12  Break Day  No Class  
Mon  Feb 15  Gary  Lecture 6: Differential Equations, Matrix Exponentials and Laplacians  [ClassNotes]
pdf
note  Strang 5.4 Recording 

Wed  Feb 17  Gary  Lecture 7: Bounding Eigenvalues, CourantFischer, and Path Embedding.  [ClassNotes]
pdf
note  Spielman4 [ScribeNotes] pdf Recording 

Fri  Feb 19  HW Presentation Day  
Mon  Feb 22  Gary  Lecture 8: Graph Sparsifiers and AhlswedeWinter Thm  [ClassNotes]
pdf
note  Spielman/Strivastava  Using AW [ScribeNotes] pdf Recording 

Wed  Feb 24  Court Hearing Day  No Class  
Fri  Feb 26  Gary  Lecture 9: Matrix Chernoff Bounds, AhlswedeWinter, Tropp  [ClassNotes]
pdf
note  Using AW Recording 

Mon  Mar 01  Gary  Lecture 10: GoldenThompson using Weylâ€™s Majorant Theorem  [ClassNotes]
pdf
note  VershyninNotes Recording 

Wed  Mar 03  Gary  Lecture 11: Graph Cuts and Eigenvalues: Cheeger inequality  [ClassNotes]
pdf
note  Guattery's Notes Recording 

Fri  Mar 05  Gary  Lecture 12: Direct Linear Solvers and Nested Dissection for Planar Graphs"  [ClassNotes]
pdf
note [ScribeNotes] pdf  [CLRS Chap 28] Recording 

Mon  Mar 08  Gary  Lecture 13: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration  [ClassNotes]
pdf
note  Hageman and Young 34  Saad 47 Recording 

Wed  Mar 10  Gary  Lecture 14: Conjugate Gradient Method and Steepest Descent  [ClassNotes]
pdf
note  Trefethen and Bau Chapter 38  Saad Chap 5  Painless CG Recording 

Fri  Mar 12  Junxing  Lecture 15: On Computing the MinDegree Elimination Ordering   Powerpoint Lecture  
Mon  Mar 15  Gary  Lecture 16: Conjugate Gradient Method Analysis  Recording  
Wed  Mar 17  Gary  Lecture 17: Fiedler's Thm and Generalized Laplacian's  [ClassNotes]
pdf
note  Spielman Lecture 7  Godsil Royle Chap 13 Recording 

Fri  Mar 19  MidSemester Break  No Class  
Mon  Mar 22  HW Presentation Day  
Wed  Mar 24  Gary  Lecture 18: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees  [ClassNotes]
pdf
note  Lecture 19 Spielman Recording 

Fri  Mar 26  Gary  Lecture 19: Eigenvalues and Vectors by Iterative Methods  [ClassNotes]
pdf
note  Inverse Powering, see page 19  Trefethen and Bau Chapter 27 Recording 

Mon  Mar 29  Gary  Lecture 20: Graph Maximum Cut via Spectral  [ClassNotes]
pdf
note  Williamson Lecture 8  Williamson Lecture 9 Recording 

Wed  Mar 31  Gary  Lecture 21: Graph Maximum Cut via Spectral  [ClassNotes]
pdf
note  Williamson Lecture 8  Williamson Lecture 9 Recording 

Fri  Apr 02  Gary  Lecture 22: Solving Graph Laplacians in Nearly O(m log n) time  [ClassNotes]
pdf
note  CACM No Recording 

Mon  Apr 05  Break Day  No Class  
Wed  Apr 07  Gary  Lecture 23: Solving Symmetric Diagonally Dominate Linear Systems  [ClassNotes]
pdf
note Recording 

Fri  Apr 09  HW Presentation Day  
Mon  Apr 12  Gary  Lecture 24: Random Walks with Restarts and Spilling Paint  [ClassNotes]
pdf
note Berkhin Painting  Andersen and Chung  Spielman's Notes Recording 

Wed  Apr 14  Gary  Lecture 25: Counting Random Trees  [ClassNotesCounting]
pdf
note [ClassNotesGenerating] pdf note  Even Trees Chapter 2 Recording 

Fri  Apr 16  Spring Carnival  No Class  
Mon  Apr 19  Gary  Lecture 26: The Markov Chain Tree Theorem  [ClassNotes]
pdf
note Recording 

Wed  Apr 21  Gary  Lecture 27: Generating Random Trees  [ClassNotesGenerating]
pdf
note  Broder Generating Random Spanning Tree  Aldous Generating Random Spanning Trees 

Fri  Apr 23  Gary  Lecture 28: Random Walks and Matching  [ClassNotes]
pdf
note  Spielman Notes on Matching Recording 

Mon  Apr 26  Gary  Lecture 29: Maximum Flow via Electrical Flow  [ClassNotes]
pdf
note  Lee Rao Srivastava Recording 

Wed  Apr 28  Gary  Lecture 30: Nesterov and LRS MaxFlow  [ClassNotes]
pdf
note  Lee Rao Srivastava Recording 

Fri  Apr 30  Study Day  No Class  
Mon  May 03  Gary  Lecture 31: Probablity 101, The Exponential Dist., Low Diameter Decomposition  [Classnotes]
pdf
note  LectureNotes Recording 

Wed  May 05  Gary  Lecture 32: Exp. Dist. and Spanners  [Classnotes]
pdf
note
 LectureNotes  Shen Chen's Talk Recording 

Fri  May 07  HW Presentation Day 