Date 
Topic 
Reading Due 
HW 
Jan. 18 Th

Probability I (basics)

[MR95] Ch. 3, Appendix C; [MU05] Ch. 3; [CLRS01] Appendix C;
Babai I



Jan. 23 Th

Probability II (concentration inequalities)

[MU05] Ch. 4


HW 1, due 1/30

Jan. 25 Th

Probability III (balls and bins)

[MU05] Ch. 5


Jan. 30 Tu

MinCut, MaxCut, Fingerprinting

[CLRS01] Ch. 28


Feb. 1 Th

Linear Algebra review

Babai II


Feb. 6 Tu

Markov Chains I (cover time)

[MR95] Sec 6.16.5, Lovasz I


Feb. 8 Th

Markov Chains II (mixing time)

[MU05] Ch. 7, Ch. 10


Feb. 13 Tu

Markov Chains III (counting)

[MR95] Ch. 11


Feb. 15 Th

Markov Chains IV (coupling)

[MU05] Ch. 11


Feb. 20 Tu

Markov Chains V (path coupling)



Feb. 22 Th

Markov Chains VI (canonical paths)

[J03] Ch. 5


Feb. 27 Tu

Fourier Transform I (basics)

[CLRS01] Ch. 30


Mar. 1 Th

Fourier Transform II (expanders)

here Sec. 2.1  2.4


Mar. 6 Tu

Fourier Transform III



Mar. 8 Th

MIDTERM



(spring break)

Mar. 20 Tu

Algorithms in Number Theory I (basics)

[CLRS01] Ch. 31


Mar. 22 Th

Algorithms in Number Theory II (primality)

[MR95] Ch. 14


Mar. 27 Tu

Algorithms in Number Theory III (FFT)



Mar. 29 Th

Algorithms in Number Theory III (LLL)



Apr. 3 Tu

Linear Programming I (duality, simplex method)

[CLRS01] Ch. 29, [DPV06] Ch. 7


Apr. 5 Th

Linear Programming II



Apr. 10 Tu

Semidefinite Programming

Lovasz II


Apr. 12 Th

Metric Embeddings I

Indyk,
Gupta


Apr. 17 Tu

Metric Embeddings II



Apr. 19 Th

Metric Embeddings III



Apr. 24 Tu

Multicommodity flows

[CLRS01] Ch. 26, LLR95


Apr. 26 Th

Computational Algebra (Groebner basis)



May. 1 Tu

String Matching

[CLRS01] Ch. 32


May. 9 We

FINAL EXAM (7:15pm, CSC 601)


