Lecturers: Alexander Clifton and Jan Volec
TA: Daniela Černá
Course starts: Mo 16.11 at 9:15
Location: Karlovo náměstí 13, 120 00 Prague (Faculty of Electrical Engineering, Czech Technical University) – Google maps
Room: A-215 – see The interactive building navigator
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 (Alexander) | 14:15-15:45 – Exercises |
| Tu 17.11 9:30-12:30 | Dominating sets in graphs with large minimum degree, Method of conditional probabilities (Alexander) | 14:15-15:45 – Exercises |
| We 18.11 9:30-12:30 | Karger's and Karger-Stein's Aglorithms (Jan) | 14:15-15:45 – Exercises |
| Th 19.11 9:30-12:30 | Lovasz Local Lemma – symmetric and general form (Alexander) | 14:15-15:45 – Exercises |
| Fr 20.11 9:30-12:30 | Entropy compression and Moser-Tardos Algorithm (Jan) | 14:00-14:25 – Q&A 14:30-15:30 – 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)