Lecturer: Jan Volec
Tutor: Alexander Clifton
Course starts: Mo 17.11, 9:00
Location: Dejvice campus – FEL, Technická 1902/2, 160 00 Prague (Faculty of Electrical Engineering, Czech Technical University)
Room: T2:H1-130
Covered topics: Probabilistic Method, Karger-Stein's Algorithm, Method of conditional probabilities, Lovasz Local Lemma, Entropy compression and Moser-Tardos Algorithm.
References: Randomized Algorithms by Motwani & Raghavan, The Probabilistic Method by Alon & Spencer.
Day | Part 1 ‑ Lecture | Part 2 ‑ Exercises |
---|---|---|
Mo 17.11 | 9:30-12:30 Introduction, Basic applications of Probabilistic Method | 14:00-15:30 |
Tu 18.11 | 9:30-12:30 Method of conditional probabilities, Karger's Algorithm | 14:00-15:30 |
We 19.11 | 9:30-12:30 Karger-Stein's Aglorithm, Lovasz Local Lemma (symmetric form) | N/A |
Th 20.11 | 9:30-12:30 Lovasz Local Lemma (general form) | 14:00-15:30 |
Fr 21.11 | 9:30-12:30 Entropy compression and Moser-Tardos Algorithm | 14:00-14:25 Q&A 14:30-15:30 Final Test |
We 19.11 15:15 – Excursion to Technical Museum (Kostelní 42, 170 00 Prague; see Google maps)
Fr 21.11 17:00-19:00 – Farewell dinner at Rector's office (Jugoslavských partyzánů 3, 160 00 Prague; see Google maps)