max planck institut
mpii logo Minerva of the Max Planck Society

Probabilistic Method & Randomized Algorithms (SS 2011)

Basic Information

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).


Lecture Notes

Results of final exam

More Courses of the Algorithms and Complexity Group
Search MPII (type ? for help)