max planck institut
informatik
informatik
| Lecture time: | Tuesday 12-14 and Thursday 12-14 |
|---|---|
| Lecture rooms: | Tuesday @ E1.7 Room 3.23 and Thursday @ E1.7 Room 0.01 |
| Lecturers: | Jane Gao, Xavier Pérez-Giménez and Thomas Sauerwald |
| Tutorial time: | Wednesday 12-14 |
| Tutorial room: | E1.4 Room 021 |
| Tutor: | Ali Pourmiri |
| Audience: | The course counts as computer science lecture
(4 SWS, 9 CP). The lecture will be given in English. |
| Information: | There will be a short presentation of the course
at the kickoff meeting on Monday, April 11th. The first lecture will
take place on Tuesday, April 12nd. |
| Exercises: | We will hand out exercises every second week. For admission for the final exam, you have to (1) achieve at least 50% of the possible points and (2) present a solution at least twice in a tutorial. The points in the exercises do NOT count towards the final grade of the exam. |
| Final Exam: | TBD |
| Re-Exam: | TBD |
| Reference books: | Most of the course material is covered in
Alon and Spencer
and also
Mitzenmacher and Upfal.
Further references are
Molloy and Reed
and
Motwani and Raghavan. |
The Probabilistic Method is a widespread tool which has been applied in many areas of Mathematics and Computer Science. It is especially powerful in proving the existence of certain combinatorial structures that are hard to construct deterministically. The Probabilistic Method can be also used to design efficient randomized algorithms.
The first part of the course will introduce the basic probabilistic techniques (e.g., first and second moment method, concentration inequalities, derandomization, Lovasz Local Lemma) and some basic applications. In the second part we cover some specific topics in more details (e.g., randomized algorithms, random walks, property testing, random graphs).