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.