Tentative Schedule

This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Date Day Topic Notes
1 Sep 12 M Introduction and Course topics, Introduced Graph Laplacian, Effective Resistance, and Random Walks.
[ Doyle and Snell: Random Walks and Electric Networks | Class Notes | Scribe:]
First Day of Class
2 Sep 14 W Resistance, Energy and Rayleigh's Monotonicity Law, and Commute Time
[ Class Notes | Class Notes ] ]
3 Sep 16 F Random Walks, Mixing Rates, and Eigenvectors
[ Lovasz: Random Walks on Graphs: A Survey : | Class Notes ]
Hwk 1 out [PDF]
4 Sep 19 M Random Walks, Mixing Rates, and Coupling
[ Lovasz: Random Walks on Graphs: A Survey : | Class Notes ]
5 Sep 21 W Mixing and Bounding Lambda_2 for Laplacians using path embedding.
[ Class Notes]
6 Sep 23 F Diffusion, Spring-Mass Systems, Laplacians, and Matrix Exponentials
[ Strang 5.4 | Class Notes]
7 Sep 26 M Solving Linear Systems and Nested Dissection
[ Class Notes]
8 Sep 28 W More Nested Dissection, Minimum Degree Heuristic, and Fractals
[ Gilbert and Tarjan | Lipton, Rose, and Tarjan | Class Notes | Fractal Example]
9 Sep 30 F Eigenvalues of directed graphs and the Perron-Frobenius Theorem
[ Godsil and Royle: | Class Notes]
Hwk 1 due (Solutions PDF)
10 Oct 03 M Graph Cuts and Eigenvalues: Cheeger inequality
[ Guattery's Notes | Class Notes]

Hwk 2 out [PDF]
11 Oct 05 W The Cheeger inequality Continued
12 Oct 07 F Guest Lecture by Nick Harvey: Gragh Maximum Cut
13 Oct 10 M Solving Linear Systems: The Basic Iterative Method, Extrapolated Method, Chebyshev acceleration
[ Hageman and Young Chapters 3-4 | Yousef Saad's Book Chapters 4-7 | Class Notes]
14 Oct 12 W Conjugate Gradient Method and Steepest Descent
[ Trefethen and Bau Chapter 38 | Yousef Saad's Book Chap 5 | Class Notes]
15 Oct 14 F Conjugate Gradient Method and Steepest Descent Continued
16 Oct 17 M Preconditioned Conjugate Gradient Method and Low Stretch Spanning Trees
[ Spielman's Class Lecture 16 | Class Notes]
Hwk 2 due (Solutions PDF)
Hwk 3 out [PDF]
17 Oct 19 W Ahlswede-Winter Thm, Graph Sparsification and Effective resistance
[ Spielman-Strivastava | Harvey's CMU Lecture | Sparification Paper | Romanv Notes on AW | Class Notes ]
Oct 21 F Mid-Semester Break
Oct 24 M FOCS Conference
18 Oct 26 W Proof of Ahlswede-Winter Thm
[ Harvey's Notes from Waterloo | Class Notes ]
19 Oct 28 F O(m log n) Lapacian Solver
[ O(m log n) Time Solver | O(m log^2 n) Time Solver | Class Notes ]
20 Oct 31 M O(m log n) Lapacian Solver: Continued
[ Class Notes ]
Hwk 3 due (Solutions PDF)
21 Nov 02 W Fiedler's Thm and Generalized Laplacian's
[ Godsil and Royle Chapter 13 | Class Notes ]
22 Nov 04 F Spectral Methods for Planar Separators
[ Spielman Teng | Class Notes ]
Hwk 4 out [PDF]
23 Nov 07 M Eigenvalues and Vectors by Iterative Methods
[ Trefethen and Bau Chapter 27 | Inverse Powering, see page 19 | Class Notes ]
24 Nov 09 W Fiedler's Thm Continued and Planar Embeddings
[ Spielman's Tutorial | Class Notes ]
25 Nov 11 F Arnoldi Iteration and Lanczos Algorithm
[ Trefethen and Bau Chapter 33 | Class Notes ]
26 Nov 14 M Arnoldi Iteration and Lanczos Algorithm and Symmetric Diagonally Dominate Systems
[ Trefethen and Bau Chapter 36 | Class Notes A/L | Class Notes on SDD ]
27 Nov 16 W Eigenvalues and Vectors for Symmetric Tridiagonal Systems
[ Trefethen and Bau Chapter 30 | Class Notes ]
28 Nov 18 F Counting and Generating Random Spanning Trees
[ Even: Trees Chapter 2 | Broder: Generating Random Spanning Trees | Aldous: Generating Random Spanning Trees | Class Notes ]
29 Nov 21 M Generating Random Spanning Trees
[ Class Notes ]
Hwk 4 due (Solutions PDF)
Nov 23 W Thanksgiving Holiday
Nov 25 F Thanksgiving Holiday
30 Nov 28 M Faster Random Walks and Generating Random Spanning Trees
[ Wilson: Generating Random Spanning Trees | Propp and Wilson: Generating Random Spanning Trees | Madry's Thesis, see Chap 7 | Class Notes ]
31 Nov 30 W Spectral Rounding
[ ]
32 Dec 02 F Random Walks with Restarts
[ Local Graph Partitioning using PageRank Vectors | Class Notes ]
33 Dec 05 M Maximum Flow via Electrical Flow
[ Melhorn MaxFlow Slides | ]
34 Dec 07 W Shortest Paths via Interior Point Methods
[ Goemans LP Notes, See 23-40 | Freund LP Paper | ]
35 Dec 09 F Homework Review
[ ]
Last Day of Class