Lecturers: Alexander Clifton and Jan Volec
TA: Daniela Černá
Course starts: Mo 16.11 at 9:15
Location: Dejvice campus – FIT, Thákurova 9, 160 00 Prague (Faculty of Information Technology, Czech Technical University)
Room: T9:364 (see Plan of the 3rd floor)
Covered topics: Probabilistic Method, Method of conditional probabilities, Karger-Stein's Algorithm, Lovasz Local Lemma, Entropy compression and Moser-Tardos Algorithm.
References: Randomized Algorithms by Motwani & Raghavan, The Probabilistic Method by Alon & Spencer.
| Morning schedule | Topic of the lecture | Afternoon schedule |
|---|---|---|
| Mo 16.11 9:30-12:30 | Introduction, Basic applications of Probabilistic Method | 14:15-15:45 – Exercises |
| Tu 17.11 9:30-12:30 | Dominating sets in graphs with large minimum degree, Method of conditional probabilities | 14:15-15:45 – Exercises |
| We 18.11 9:30-12:30 | Karger's and Karger-Stein's Aglorithms | 14:15-15:45 – Exercises |
| Th 19.11 9:30-12:30 | Lovasz Local Lemma (symmetric and general form) | 14:15-15:45 – Exercises |
| Fr 20.11 9:30-12:30 | Entropy compression and Moser-Tardos Algorithm | 14:15-14:45 – Q&A 14:45-15:45 – Final Test |
Fr 20.11 17:00-19:00 – Farewell dinner at Rector's office (Jugoslavských partyzánů 3, 160 00 Prague; see Google maps)