Schedule, Lecture Notes, and Assignments

For preamble.tex go here  

Date

Topic & Lecture Notes

Assignments

Supplementary Reading & Section Notes

Mon 1/26

Course overview.
Spectrum of the adjacency matrix. lec1-postlec.pdf

First class survey
PS0, ps0.tex, preamble.tex (due Fri 2/6)

Wed 1/28

Graph coloring

lec2-postlec.pdf

sec0.pdf

Mon 2/2

Cayley graphs

lec3-postlec.pdf

Wed 2/4

Random walks on undirected graphs lec4-postlec.pdf

Mon 2/9

Random walks on directed graphs.

lec5-postlec.pdf

PS1, ps1.tex (due Fri 2/20)

Wed 2/11

Applications of random walks

lec6-postlec.pdf

sec1.pdf

Mon 2/16

No class (President's Day)

ps0-solutions

Wed 2/18

The Laplacian

lec7-postlec.pdf

Mon 2/23

Combinatorial Interpretations of the Laplacian

lec8-postlec.pdf

PS2, ps2.tex, ps2-digraph-exp-time.png (due Fri 3/6)

Wed 2/25

Proof of Cheeger, and statements of some Cheeger variants

lec9-postlec.pdf

sec2.pdf

Mon 3/2

Cheeger variants & the Power Method

lec10-postlec.pdf, video

ps1-solutions

Wed 3/4

Expander graphs

lec11-postlec.pdf, video

Mon 3/9

Expansion of random graphs

lec12-postlec.pdf, video

PS3, ps3.tex (due Mon 3/30)

Wed 3/11

Applications of &
random walks on expanders

lec13-postlec.pdf,  video

Form a project group and submit revised topic ideas (due Wed 4/1)

sec3.pdf

Mon 3/16

No class (Spring break)

Wed 3/18

No class (Spring break)

Mon 3/23

Explicit constructions of expanders 

lec14-prelec.pdf

Wed 3/25

Zig-zag proof, Undirected S-T Connectivity in Logspace

Mon 3/30

Resistor networks,
Schur complements

Wed 4/1

Matrix-Tree Theorem,
leverage scores

Detailed project description (due Fri 4/10)

Mon 4/6

Spectral sparsification

ps4, ps4.tex (due 4/17)

Wed 4/8

Iterative methods for solving linear systems

Mon 4/13

Square-sparsification and efficient Laplacian solvers

Wed 4/15

TBD

Mon 4/20

TBD

Draft project papers due Fri 5/1

Wed 4/22

TBD

Mon 4/27

TBD

Wed 4/29

Conclusions

Fri 5/8

Project presentations

Revised project papers due Tue 5/12