Instructor
Rong
Ge
D226 LSRC
Email: rongge@cs.duke.edu
Lectures: Wednesdays and Fridays 1:25 - 2:40 pm in LSRC D106
Office Hour: Wednesdays 3:00 - 5:00 pm in LSRC D226. Use Piazza for discussions/clarifications.
Textbook: Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan.
Optional Reading Material:
Concentration
of measure for the analysis of randomized algorithms by D.
Dubhashi and A. Panconesi.
Probability
and Computing by Michael Mitzenmacher and Eli Upfal.
Foundations
of Data Science by John
Hopcroft and Ravi Kannan.
Prerequisites: Familiarity with algorithms, probability and
linear algebra.
Evaluation:
The course grades will be determined based on:
Date | Contents | References | Future Reading |
1/15 | Intro: Randomness and Computation | Slides |
Random Quicksort, Chapter 1.2 |
Basic Properties of Random Variables | |||
1/20 | Linearity of Expectation, MAX 3-SAT, simple recursions | Chapter 1.4 | Slides by K. Wayne |
1/27 | Karger's randomized algorithm for MIN CUT | Chapter 1.1 | Wiki for the Karger-Stein Algorithm |
1/29 | Balls and bins | Chapter 3.1, 3.6 | |
2/3 | Hashing | Chapter 3.4, 8.4 | Chapter 8.5 |
2/5 | Biased Coin, distance of distributions | Chapter 3.2 Notes by Y. Mansour |
Pollard's Book Chapter |
Concentration Inequalities | |||
2/10 | Chernoff bounds | Chapter 4.1 | |
2/12 | Oblivious Routing | Chapter 4.2 | Lecture note by Sheideler |
2/17 | Power of two choices | Notes (A.
Gupta) Presentation |
|
2/19 | Martingales, Azuma's Inequality, Bounded Difference | Chapter 4.4 | |
Dimension Reductions | |||
2/24 | Dimension Reduction, Johnson-Lindenstrauss | Chapter 2.9 in Hopcroft Kannan book. | |
2/26 | MAX CUT, Goemans Williamson algorithm | MAXCUT PAPER | |
3/2 | Applications of Dimension Reduction: Streaming and Communication models | Chapter 7.1.4 in Hopcroft
Kannan book. Chapter 7.4 |
Chapter 7.1 in Hopcroft Kannan |
3/4 | Graph Sparsification I: Spectrum of graph, effective resistance | Chapter 6.4 | Lectures (especially lecture 1) by Nikhil Srivastava |
3/9 | Graph Sparsification II: matrix concentrations | ||
3/11 | Randomized Algorithms for matrices, SVD and CUR decomposition | Chapter 7.2-7.3 in Hopcroft Kannan book. | |
Markov Chains | |||
3/23 | Random walk on graph, stationary distributions | Chapter 6.2 | Chapter 6.1 Chapter 5.1 in Hopcroft Kannan |
3/25 | Resistor network revisited. |
Chapter 6.3 - 6.4 |
Chapter 5.2, 5.5 in Hopcroft Kannan |
3/30 | Expanders, fast mixing | Chapter 6.7 | Luca Trevisan's note |
4/1 | Hard side of Cheeger's inequality | Chapter 6.7 | Shayan Oveis Gharan's note |
4/6 | Approximate Counting I: DNF counting | Chapter 11.1-11.2 | |
4/8 | Approximate Counting II: Matchings, MCMC | Chapter 11.3 | Chapter 11.4 |
Special Topics | |||
4/13 | Near linear time Laplacian solvers | Slide by Lorenzo Orecchia | Paper |
4/15 | Randomized complexity classes, derandomization | Chapter 7.2 (for PIT) | Luca Trevisan's slides |
4/20 | Constructive Lovasz Local Lemma |
Chapter 5.5 | Lance Fortnow's Blog Post Ronitt Rubinfeld's Lecture Note (with longer but more general proof) |
4/28-29 | Take Home Final |