Randomized Algorithms and Probabilistic Methods

Lecturer

Prof. Dr. Angelika Steger

Assistants

Hafsteinn Einarsson , Marcelo Matheus Gauy and Andreas Noever

Time and Place

Lecture: Tuesday 13:15 - 14:00 in CAB G 51 and Thursday 08:15 - 10:00 in CAB G 51

Exercises: Tuesday, 16:15 - 18:00 in CAB G 51

Exam: Saturday 12th of December, 10:00 - 13:00, Room: HG F 1.

Participants

Students of Computer Science or Mathematics in the 5th semester or later. Knowledge of topics covered in the lecture "Algorithms, Probability, and Computing" is not required; both courses can be attended in parallel.

Exam/Grades

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

• 70% final written exam. Duration: 3 hours. Open book exam - you are allowed to consult any books, handouts, and personal notes. The use of electronic devices is not allowed. A sample exam can be found here. Exams from previous years: HS13
• 30% graded homework. In week 4, 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 7KE, and 0KE otherwise.

Exercises

For the most part of the semester, the exercise sessions will alternate between two formats. In even weeks (say), the focus will be on graded homework (GHW) - the solutions to the previous set of GHW problems will be presented, and you will get some hints for the new GHW sheet. In odd weeks, you will solve some (ungraded) exercises in class to practice the material taught in the lecture.

The exercise classes are an integral part of the course, and we strongly recommend you to attend them regularly.

Handouts

This pdf contains a short introduction to big-oh notation, asymptotics and it also contains some useful inequalities.

Topics

Introduction

• Randomized algorithms (MinCut, primality test)
• Probabilistic methods (Longest Path, SAT)

Linearity of expectation

• Coupon Collector problem
• 7/8-approximation algorithm for Max-3-SAT

Markov and Chebyshev inequalities

• Random graphs
• Calculating the median in linear time

First and second moment method

• Threshold phenomena in random graphs

Chernoff bounds

• Target shooting
• Routing in the hypercube

Negative Correlation

• Load balancing in networks ("balls and bins")

Janson and Azuma inequalities

• Subgraphs in random graphs
• Wilf's algorithm (3- coloring of graphs)

Markov chains

• Gambler's Ruin problems
• Algorithm for 3-SAT

Outlook (if time permits)

• Generating functions
• Randomized rounding
• Average case analysis
• ...

Literature

• Lecture notes will be sold as hard copies at the beginning of the course.
• Randomized Algorithms , Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)
• Probability and Computing , Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)