Lecturer: Jan Volec
Course starts: Mo 15.11, 9:00
Location: Room T214 at Trojanova 13, 120 00 Prague (Faculty of Nuclear Engineering and Physical Sciences, Czech Technical University)
Covered topics: Probabilistic Method, Karger-Stein's Algorithm, Method of conditional probabilities, Lovasz Local Lemma, Entropy compression and Moser-Tardos Algorithm.
Course notes: TBA
References: Randomized Algorithms by Motwani & Raghavan, The Probabilistic Method by Alon & Spencer.
| Day | Part 1 ‑ Lecture | Part 2 ‑ Exercises |
|---|---|---|
| Mo 15.11 | 9:00-12:00 Introduction, Basic applications of Probabilistic Method | 13:30-15:00 |
| Tu 16.11 | 9:00-12:00 Method of conditional probabilities, Karger's Algorithm | 15:30-17:00 |
| We 17.11 | 9:00-12:00 Karger-Stein's Aglorithm, Lovasz Local Lemma (symmetric form) | 15:15 Excursion to Technical Museum (map) |
| Th 18.11 | 9:00-12:00 Lovasz Local Lemma (general form) | 15:40-17:00 |
| Fr 19.11 | 9:00-12:00 Entropy compression and Moser-Tardos Algorithm | 13:30-14:30 Q&A 14:30-15:30 Final Test |
Farewell dinner: Fr 19.11 17:00-20:00 at Rector's office (Jugoslavských partyzánů 3; see Google maps)