18.434 - randomized algorithms___spring 2011

Course information

Information sheet.

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.