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) literature	3rd Exercise Sheet: [pdf] literature
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] literature
November 28	Introduction to randomized search heuristics, evolotionary algorithms	7th Exercise Sheet: [pdf] literature
December 5	No lecture. Reading assignment: literature	8th Exercise Sheet: [pdf]
December 12	Wald's equation, drift analysis slides	9th Exercise Sheet: [pdf]
December 19	EA for combinatorial optimization problems, crossover	10th Exercise Sheet: [pdf] literature
January 11 [moved because of SODA]	Wald's equation, additive drift, multiplicative drift literature1 literature2 literature3	11th Exercise Sheet: [pdf] literature4
January 16	Lower bounds, Yao's Minimax Principle, entropy compression literature
January 23	No lecture, because I'm in Dagstuhl. Instead: Reading assignment "Mastermind with Many Colors"
January 30	Random graphs	12th Exercise Sheet: [pdf] literature
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