Randomized methods are one of the key tools in computer science, clearly not limited to their best-known use in randomized algorithms. Our aims for this course are twofold:
(i) We shall give an introduction to the diverse applications of
randomized methods in computer science.
- Liar games and guessing games (Mastermind) and their applications to noisy communication and privacy problems,
- random graphs and social networks,
- epidemic algorithms building on the random gossip paradigm (nodes contact random neighbors to exchange information),
- evolutionary algorithms.
(ii) Parallel to this, we shall develop a small, but powerful set of mathematical tools that suffice to understand most uses of randomness in computer science:
- the coupon collector theorem,
- simple Chernoff bounds,
- a number of tricks to deal with dependencies.
Requirements: The beauty of this field is that relatively simple uses of randomness yield surprisingly powerful results. In such, no deep probability theory prerequisites are needed. However, naturally, this topic does require the use of elementary discrete probabilities. So if you are afraid of statements like "if you roll a 6-sided die, the expect result is 3.5" or "the expected number of die rolls until you see a "one" is 6", then you should not take this course (in the past, the course saw attendees having difficulties here, that's why I stress this fact). A basic knowledge of algorithms and their analysis, e.g., as taught in INF421, is also helpful. Finally, this is not a mathematics course (by far not), but we use mathematical arguments to understand things. The course comes with PC, not with TD. It is thus in style similar to INF421 if you remove the homeworks and the optional programming project. I am stressing these points not to shy you away, but because in the past (few) students misunderstood the course description. Personally, I am happy if you take the course.
Evaluation mechanism: Written exam (3h) and two short tests (20min), each of which can mildly increase the final grade.
Languange: Everything is in English. For the exam, answers in French are equally accepted.