Schedule

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

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