Lect. |
Date |
Topics |
Readings |

1 |
1/23 |
Introduction; events & probability | MU Sections 1.1-1.2 |

2 |
1/28 |
Verifying matrix multiplication; Minimum cut | MU Sections 1.3-1.4 |

3 |
1/30 |
Random variables and expectation | MU Section 2.1 |

4 |
2/4 |
Binomial and geometric distributions; coupon collecting; Quicksort | MU Sections 2.2, 2.4-5 |

5 |
2/6 |
Markov's inequality; variance; Chebyshev's inequality | MU Sections 3.1-3 |

6 |
2/11 |
Chebyshev's inequality; Coupon collecting bounds | MU Sections 3.3 |

7 |
2/13 |
Randomized median finding, generating functions (notes) | MU Section 3.4 |

8 |
2/20 |
no class | |

9 |
2/25 |
Chernoff bounds; set balancing | MU Sections 4.2-4 |

10 |
2/27 |
Proof of Chernoff bounds; randomized routing | MU Sections 4.2, 4.5 |

3/3 |
Midterm 1 in class | ||

11 |
3/5 |
Wrap-up routing, Intro. to statistical testing | MU Section 4.5 |

12 |
3/10 |
Stats: Hypothesis Testing | Online notes |

13 |
3/12 |
Stats: Permutation Tests and Bootstrapping | Online notes |

14 |
3/17 |
Birthday problem | MU Sections 5.1 |

15 |
3/19 |
Poisson distribution and Bloom Filters | MU Sections 5.3, 5.5 |

16 |
3/31 |
Random graphs; Hamiltonian cycle algorithm | MU Section 5.5 |

17 |
4/2 |
Hamiltonian cycle algorithm | MU Sections 5.6 |

18 |
4/7 |
Probabilistic method; method of conditional expectations | MU Sections 6.2, 6.3 |

19 |
4/9 |
More on the probabilistic method; thresholds in random graphs | MU Section 6.4, 6.5 |

20 |
4/14 |
Markov chains; 2-SAT | MU Section 7.1 |

21 |
4/16 |
Markov chains: gambler's ruin, stationary distributions, fundamental theorem | MU Sections 7.2-3 |

4/21 |
Midterm 2 in class | ||

22 |
4/23 |
Markov chains: examples; card shuffling, random walks, simple queue, cover time | MU Sections 7.3-4 |

23 |
4/28 |
Markov chain Monte Carlo; Metropolis algorithm | MU Sections 10.3 (no details), 10.4 |

24 |
4/30 |
Martingales | MU Sections 12.1-2 |

25 |
5/5 |
Tail bounds for Martingales | MU Section 12.4 |

26 |
5/7 |
||

27 |
5/12 |
Applications of Martingales | MU Section 12.5 |