Randomized Algorithms and Probabilistic Methods: Advanced Topics

Lecturer

Dr. Karl Bringmann, Dr. Johannes Lengler, and Dr. Tsur Luria

Assistants

Frank Mousset and Felix Weissenberger

Time and Place

Lecture: Monday, 13:15 - 15:00 in CHN D 44

Exercises: Thursday, 14:15 - 15:00 in ML J 34.1

Participants

Students of Computer Science or Mathematics who have attended Randomized Algorithms and Probabilistic Methods or a similar lecture.

Exam/Grades

Your final grade will be calculated as the the weighted average of:

• 70% oral exam.
  The exams take place during the exam session and consist of 20 minutes preparation followed by 20 minutes oral examination.
• 30% graded homework.
  In weeks 2, 7 and 10 of the term (roughly) we will hand out a specially marked exercise whose solution (typeset in LaTeX) is due two weeks later. These solutions will be graded; the grades will each account for 10% of your final grade. You are welcome to discuss these exercises with your colleagues, but we expect you to hand in your own writeup.

Following the new D-INFK guidelines for doctoral studies, PhD students get credit points according to the same rules that apply for Bachelor or Master students. That is, with a final grade of at least 4 (calculated as explained above) you will receive 5KP, and 0KP otherwise.

Exercises

Information about the exercises (graded and otherwise) will appear here.

Exercise 1: pdf Solution: pdf

Exercise 2: pdf Solution: pdf

First graded homework (due 11.03): pdf Solution: pdf

Exercise 3: pdf Solution: pdf

Exercise 4: pdf Solution: pdf

Exercise 5: pdf Solution: pdf

Second graded homework (due 23.4): pdf Solution: pdf

Exercise 6: pdf Solution pdf

Exercise 7: pdf Solution: pdf

Exercise 8: pdf Solution: pdf

Third graded homework (due 20.5): pdf Solution: pdf

Exercise 9: pdf Solution: pdf

Topics

Drift Analysis, Introduction to Rapidly Mixing Markov Chains, Mixing of Latin Squares, Mixing in the Truncated Cube, Volume Estimation, Expander Graphs, Differential Equation Method

Literature

Lecture notes will be distributed chapter for chapter in the lectures.

Chapters 1,2,3,4 (Drift Analysis, Rapidly mixing random walks, Expander graphs, Differential equation method): pdf (version July 9)