Day  Date  Instr  Topics Covered  Notes and Readings  Assignments 

Wed  Sep 05  Gary  Lecture 1: Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Energy.  [ClassNotesIntro]
pdf
note [ClassNotes] pdf note  Doyle and Snell: Random Walks and Electric Networks [ScribeNotes] pdf 

Fri  Sep 07  Gary  Lecture 2: Energy and Rayleigh's Monotonicity Law, and Random Walks on Graphs  [ClassNotes]
pdf
note [ScribeNotes] pdf 

Mon  Sep 10  Gary  Lecture 3: Random Walks on Graphs and Mixing  [ClassNotes]
pdf
note 

Wed  Sep 12  Gary  Lecture 4: Perron Frobenius and Symmetric Perron Frobenius.  [ClassNotes]
pdf
note  Spielman3 

Fri  Sep 14  Gary  Lecture 5: Mixing Rates for Random Walks continued  [ClassNotes]
pdf
note  Strang 5.4 

Mon  Sep 17  Gary  Lecture 6: Bounding Eigenvalues, CourantFischer, and Path Embedding.  [ClassNotes]
pdf
note  Spielman4 

Wed  Sep 19  Gary  Lecture 7: Laplacians, Differential Equations, and Matrix Exponentials  [ClassNotes]
pdf
note  Strang 5.4 

Fri  Sep 21  Gary  Lecture 8: Graph Sparsifiers and AhlswedeWinter Thm  [ClassNotes]
pdf
note  Spielman/Strivastava  Using AW 

Mon  Sep 24  Gary  Lecture 9: Matrix Chernoff Bounds, AhlswedeWinter, Tropp  [ClassNotes]
pdf
note  Using AW 

Wed  Sep 26  Gary  Lecture 10: GoldenThompson using Weylâ€™s Majorant Theorem  [ClassNotes]
pdf
note  VershyninNotes 

Fri  Sep 28  Gary  Lecture 11: Graph Cuts and Eigenvalues: Cheeger inequality  [ClassNotes]
pdf
note  Guattery's Notes 

Mon  Oct 01  Gary  Lecture 12: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration  [ClassNotes]
pdf
note  Hageman and Young 34  Saad 47 

Wed  Oct 03  Gary  Lecture 13: Conjugate Gradient Method and Steepest Descent  [ClassNotes]
pdf
note  Trefethen and Bau Chapter 38  Saad Chap 5  Painless CG 

Fri  Oct 05  Gary  Lecture 14: Conjugate Gradient Method Continued  
Mon  Oct 08  Gary  Lecture 15: Direct Linear Solvers"  [ClassNotes]
pdf
note  [CLRS Chap 28] 

Wed  Oct 10  Gary  Lecture 16: Nested Dissection for Planar Graphs   [CLRS Chap 28]  
Fri  Oct 12  Gary  Lecture 17: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees  [ClassNotes]
pdf
note  Lecture 19 Spielman 

Mon  Oct 15  Gary  Lecture 18: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees continued  [ClassNotes]
pdf
note  Lecture 19 Spielman 

Wed  Oct 17  Gary  Lecture 19: Fiedler's Thm and Generalized Laplacian's  [ClassNotes]
pdf
note  Spielman Lecture 7  Godsil Royle Chap 13 

Fri  Oct 19  Midsemester Break  No Class  
Mon  Oct 22  Gary  Lecture 20: Eigenvalues and Vectors by Iterative Methods  [ClassNotes]
pdf
note  Inverse Powering, see page 19  Trefethen and Bau Chapter 27 

Wed  Oct 24  Gary  Lecture 21: Continued: Eigenvalues and Vectors by Iterative Methods   Inverse Powering, see page 19  Trefethen and Bau Chapter 27  
Fri  Oct 26  Presidential Inauguration Day  No Class  
Mon  Oct 29  Gary  Lecture 22: Arnoldi Iteration and Lanczos Algorithm  [ClassNotes]
pdf
note  Trefethen Bau Chap 33  Trefethen Bau Chap 36 

Wed  Oct 31  Gary  Lecture 23: Arnoldi Iteration and Lanczos Algorithm Cont  [ClassNotes]
pdf
note  Trefethen Bau Chap 33  Trefethen Bau Chap 36 

Fri  Nov 02  Gary  Lecture 24: I: Graph Maximum Cut via Spectral  [ClassNotes]
pdf
note  Williamson Lecture 8  Williamson Lecture 9 

Mon  Nov 05  Gary  Lecture 25: II: Graph Maximum Cut via Spectral  [ClassNotes]
pdf
note  Williamson Lecture 8  Williamson Lecture 9 

Wed  Nov 07  Gary  Lecture 26: III: Graph Maximum Cut via Spectral  [ClassNotes]
pdf
note  Williamson Lecture 8  Williamson Lecture 9 

Fri  Nov 09  Gary  Lecture 27: Solving Graph Laplacians in Nearly O(m log n) time  [ClassNotes]
pdf
note  CACM 

Mon  Nov 12  Gary  Lecture 28: Homework Review Problem set 1  
Wed  Nov 14  Gary  Lecture 29: Homework Review Problem set 2  
Fri  Nov 16  Gary  Lecture 30: Solving Symmetric Diagonally Dominate  [ClassNotes]
pdf
note 

Mon  Nov 19  Gary  Lecture 31: Random Walks and Matching  [ClassNotes]
pdf
note  Spielman Notes on Matching 

Wed  Nov 21  Thanksgiving  No Class  
Fri  Nov 23  Thanksgiving  No Class  
Mon  Nov 26  Gary  Lecture 32: Counting Random Trees  [ClassNotesCounting]
pdf
note [ClassNotesGenerating] pdf note  Even Trees Chapter 2 

Wed  Nov 28  Gary  Lecture 33: The Markov Chain Tree Theorem  [ClassNotesGenerating]
pdf
note  Broder Generating Random Spanning Tree  Aldous Generating Random Spanning Trees 

Fri  Nov 30  Gary  Lecture 34: Generating Random Trees  [ClassNotesGenerating]
pdf
note  Broder Generating Random Spanning Tree  Aldous Generating Random Spanning Trees 

Mon  Dec 03  Gary  Lecture 35: Parallel Low Diameter Graph Decomposition using Delayed Start Times  [ClassNotesExponential Distribution ]
pdf
note [ClassNotesLow Diameter] pdf note 

Wed  Dec 05  Gary  Lecture 36: Random Walks with Restarts and Spilling Paint  [ClassNotes]
pdf
note Berkhin Painting  Andersen and Chung  Spielman's Notes 

Fri  Dec 07  Gary  Lecture 37: Random Walks with Restarts and Spilling Paintcontinued 