max planck institut
mpii logo Minerva of the Max Planck Society

Randomized Methods in Computer Science (Winter 2012/13)

Lecturer:   Prof. Dr. Benjamin Doerr
Time: Wed 9-12 (lecture and exercises)

Room: 24 (in the MPI building E1.4)

Content: Similar to this syllabus, which I created for a different university: pdf

Audience: CS students who completed their mathematics courses.

Lecture details:
Date Topic Exercises
October 17 Overview, Max-3-SAT, Mastermind with n positions and n colors 1st Exercise Sheet: [pdf]
Notions: Discrete probability space, independence of events, conditional probabilities, random variables, expectation, and independence of random variables.
Basic theorems: The union bound, the law of total probability, and linearity of expectation.
Formal proof of the Max-3-SAT result, coupon collector (probability bound), Mastermind with two colors (probability of distinguishing two secrets), finding triangles in random graphs.
literature (register with the lecturer to receive the password)
October 23 First moment method 2nd Exercise Sheet: [pdf]
Solution to problem 4: [pdf]
October 31 Concentration of measure, large deviation bounds: Markov, Chebyshev, Chernoff (multiplicative deviations)
3rd Exercise Sheet: [pdf]
November 7 Randomized rumor spreading 4th Exercise Sheet: [pdf]
Solution to problem 1: [pdf], problem 2: [pdf]
November 14 Dealing with dependencies
Summary of basic methods
5th Exercise Sheet: [pdf]
November 21 Power of dependencies 6th Exercise Sheet: [pdf]
November 28 Introduction to randomized search heuristics, evolotionary algorithms 7th Exercise Sheet: [pdf]
December 5 No lecture. Reading assignment: literature 8th Exercise Sheet: [pdf]
December 12 Wald's equation, drift analysis
9th Exercise Sheet: [pdf]
December 19 EA for combinatorial optimization problems, crossover 10th Exercise Sheet: [pdf]
January 11
[moved because of SODA]
Wald's equation, additive drift, multiplicative drift
literature1 literature2 literature3
11th Exercise Sheet: [pdf]
January 16 Lower bounds, Yao's Minimax Principle, entropy compression
January 23 No lecture, because I'm in Dagstuhl.
Instead: Reading assignment "Mastermind with Many Colors"
January 30 Random graphs 12th Exercise Sheet: [pdf]
February 6 Random graphs II

Registration: Please register as soon as possible by sending an email to the lecturer. This has no implication except that you'll receive emails with important announcements. If you want to take the course for credit, you also must register in the HisPos system within the first two weeks of the term. You can undo this registration anytime up to three weeks before the final exam (without any negative consequences other than not being able to take the exam).

Exams/Credit: This is a 2h/week special lecture. It comes with 1 or 2 hours of exercises (your choice). Consequently, if you pass the final exam, you earn 5 or 6 credit points.

The final exam will be on February 26, 2013. Any participant registered for the course in the HisPos system can participate. There will be a re-exam on April 11, in the afternoon. Again, any participant registered in the HisPos system can participate. If you take both exams, the better of the two grades counts. The exams will be oral, please register for both exams via email.

Literature: M. Mitzenmacher and E. Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, 2005. amazon

N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 1992. amazon

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995. link

Search MPII (type ? for help)