Course information

Schedule

Wed Feb 2 - Neil | Checking a matrix multiplication fast. |

Mon Feb 7 - Neil | A randomized min cut algorithm. From the basic algorithm, we covered (a little briefly) how to speed this up using recursion. |

Wed Feb 9 - Mariko | Analysis of the expected runtime of quicksort. The secretary problem. |

Wed Feb 9 - John | Markov's inequality and Chebyshev's inequality. An application of Chebyshev to a (completely non-probabilistic) problem in additive combinatorics - our first encounter with the probabilistic method. |

Mon Feb 14 - Danielle | Chernoff bounds. |

Mon Feb 14 - Maria | Some applications of Chernoff bounds. |

Tue Feb 22 - Amy | Introduction to balls and bins. |

Tue Feb 22 - Jillian | Poisson distributions, and their connection to balls-and-bins |

Wed Feb 23 - Alyssa | The Poisson approximation for balls-and-bins. |

Wed Feb 23 - Rostislav | Hashing. |

Mon Feb 28 - Ashu | Coupon collector. |

Mon Feb 28 - Caroline | Random graphs and the second moment method |

Assignments

You can use this latex template for your solution, but it is not a requirement.

- Assignment 1
- Assignment 2, due Friday 25 Feb. Here is the LaTeX source if you want it.
- Assignment 3, due Monday 21 March. Here is the LaTeX source if you want it. Here is a hint for question 2 b)., and a much more detailed hint.