Randomized algorithms
Ects : 3
Enseignant responsable :
Volume horaire : 15Description du contenu de l'enseignement :
One of the powerful tools in the Theory of Algorithms is randomization. Often times a hard algorithmic problem (even with a provable lower bound) admits an algorithm whose expected running time is extremely fast despite the fact that its worst-case running time be large. Other times, one can solve a difficult opimisation problem reasonably quickly in the worst case if one is willing to allow a small probability of error. Randomized algorithms come to aid in these situations – in these algorithms some or all of the steps taken are random, and the goal is to show that the random choices are quite efficient. Using randomized algorithms, one can often get a simpler and an easier implementable algorithm even for problems for which there are polynomial time algorithms. In this course, we will see instances of all the aforementioned phenomena.
Selected Topics (we likely will not be able to cover everything in the list):
- Sampling and fingerprinting, applications to hashing and data analysis
- Las Vegas vs. Monte Carlo
- Randomized QuickSort/Median
- Karger ’ s Minimum Cut Algorithm
- Coupon Collector, Balls and Bins, Poisson Approximation
- Testing perfect matchings in graphs
- Concentration of measure: martingales and the Azuma/Hoeffding inequalities
- Color-coding Method.
Pré-requis obligatoires :
General math/cs maturity. Strong knowledge of probability theory and algorithms would certainly be quite helpful, but strictly speaking is not required. A preliminary first course notions of probability theory will be assumed.
Bibliographie, lectures recommandées
- Motwani, Raghavan, Randomized algorithms.
- Mitzenmacher, Upfal, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis.