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

Day Date Instr Topics Covered Notes and Readings Assignments
Mon Sep 09 Gary Lecture 1: Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks ClassNotes - Doyle and Snell: Random Walks and Electric Networks
Wed Sep 11 Gary Lecture 2: Resistance, Energy and Rayleigh's Monotonicity Law, and Commute Time ClassNotes
Fri Sep 13 Gary Lecture 3: Mixing Rates for Random Walks ClassNotes - Lovasz Notes
Mon Sep 16 Gary Lecture 4: Bounding Eigenvalues and Symmetric Perron Frobenius for Laplacians using path embedding. ClassNotes - Spielman-3
Wed Sep 18 Gary Lecture 5: Bounding Eigenvalues, Courant-Fischer, and Path Embedding. ClassNotes - Spielman-4
Fri Sep 20 Euiwoong Lecture 6: No Lecture
Mon Sep 23 Gary Lecture 7: Laplacians, Differential Equations, and Matrix Exponentials ClassNotes- Strang 5.4
Wed Sep 25 Gary Lecture 8: Graph Sparsifiers and Ahlswede-Winter Thm ClassNotes- Spielman/Strivastava - Using AW
Fri Sep 27 Richard Lecture 9: Statistical Leverage Scores and Row Sampling Slides- Arxiv paper
Mon Sep 30 Gary Lecture 10: Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration ClassNotes- Hageman and Young 3-4 - Saad 4-7
Wed Oct 02 Gary Lecture 11: Conjugate Gradient Method and Steepest Descent ClassNotes- Trefethen and Bau Chapter 38 - Saad Chap 5 - Painless CG
Fri Oct 04 Gary Lecture 12: Conjugate Gradient Method Continued -
Mon Oct 07 Gary Lecture 13: Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees ClassNotes- Lecture 19 Spielman
Wed Oct 09 Euiwoong Lecture 14: Homework Review -
Fri Oct 11 Rest Break - No Class
Mon Oct 14 Gary Lecture 15: Direct Linear Solvers" ClassNotes- [CLRS Chap 28]
Wed Oct 16 Gary Lecture 16: Graph Cuts and Eigenvalues: Cheeger inequality ClassNotes- Guattery's Notes
Fri Oct 18 Midsemester Break - No Class
Mon Oct 21 Gary Lecture 17: Eigenvalues and Vectors by Iterative Methods ClassNotes- Inverse Powering, see page 19 - Trefethen and Bau Chapter 27
Wed Oct 23 Gary Lecture 18: Fiedler's Thm and Generalized Laplacian's ClassNotes- Spielman Lecture 7 - Godsil Royle Chap 13
Fri Oct 25 Gary Lecture 19: Arnoldi Iteration and Lanczos Algorithm ClassNotes- Trefethen Bau Chap 33 - Trefethen Bau Chap 36
Mon Oct 28 FOCS Conference - No Class
Wed Oct 30 Gary Lecture 20: Solving Graph Laplacians in Nearly O(m log n) time ClassNotes- CACM
Fri Nov 01 Gary Lecture 21: Graph Laplacians Solver Cont., Symmetric Diagonally Dominate ClassNotes
Mon Nov 04 Gary Lecture 22: Symmetric Diagonally Dominate Solvers; Maximum Flow ClassNotes SDD- ClassNotes MaxFlow - Lee Rao Srivastava
Wed Nov 06 Gary Lecture 23: Maximum Flow via Electrical Flow Cont. ClassNotes
Fri Nov 08 Gary Lecture 24: Nesterov and MaxFlow ClassNotes
Mon Nov 11 Gary Lecture 25: Computing Minimum Energy Flow ClassNotes- KOSZ Min Flow
Wed Nov 13 Gary Lecture 26: Random Walks and Matching ClassNotes- Spielman Notes on Matching
Fri Nov 15 Gary Lecture 27: Counting and Generating Random Trees ClassNotes Counting- ClassNotes Generating - Even Trees Chapter 2 - Broder Generating Random Spanning Tree - Aldous Generating Random Spanning Trees
Mon Nov 18 Gary Lecture 28: Faster Random Walks and Generating Random Spanning Trees ClassNotes- Wilson: Generating Random Spanning Trees - Propp and Wilson: Generating Random Spanning Trees - Madry's Thesis, see Chap 7
Wed Nov 20 Jacub Lecture 29: Bartal Trees and Low Stretch Spanning Trees Slides - Paper
Fri Nov 22 Shen Chen Lecture 30: Parallel Low Diameter Graph Decomposition using Delayed Start Times -
Mon Nov 25 Gary Lecture 31: Random Walks with Restarts Spielman's Notes
Wed Nov 27 Thanksgiving - No Class
Fri Nov 29 Thanksgiving - No Class
Mon Dec 02 Gary Lecture 32: Random Walks with Restarts and Spilling Paint Berkhin Painting -
Wed Dec 04 Gary Lecture 33: Random Walks with Restarts and Spilling Paint-continued Andersen and Chung - ClassNotes
Fri Dec 06 Gary Lecture 34: Homework Review