Randomized Algorithms and Probabilistic Methods
Lecturer
Prof. Dr. Angelika Steger
Assistants
Frederik Benzing
,
Marcelo Matheus Gauy
,
Charlotte Knierim
and Ulysse Schaller
Time and Place
Lecture:
Tuesday 13:15  14:00 in CAB G 51 and Thursday 08:15  10:00 in CAB G 51
ATTENTION: The first lecture (18.09) will be held on HG E1.1
Exercise Class: Tuesday, 16:15  18:00 in CAB G 51
Exam: Saturday, 15.12, 10:00  13:00 in HG F1
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
HS14
HS15
and some corrections/hints for these exams.

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, individual writeup.
Following the DINFK 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.
Lecture Notes
The lecture notes can be found here.
Exercises
The exercise classes are an integral part of the course. Thus, we
strongly recommend you to attend them regularly and solve the weekly exercise sheets.
Exercise Sheet 1
Exercise Sheet 1 Solutions
Exercise Sheet 2
Exercise Sheet 2 Solutions
Exercise Sheet 3
Exercise Sheet 3 Solutions
Graded Homework Sheet 1
Common Mistakes 1
Exercise Sheet 4
Exercise Sheet 4 Solutions
Exercise Sheet 5
Exercise Sheet 5 Solutions
Graded Homework Sheet 2
Common Mistakes 2
Exercise Sheet 6
Exercise Sheet 6 Solutions
Exercise Sheet 7
Exercise Sheet 7 Solutions
Graded Homework Sheet 3
Common Mistakes 3
Exercise Sheet 8
Exercise Sheet 8 Solutions
Exercise Sheet 9
Exercise Sheet 9 Solutions
Handouts
This pdf contains a short introduction to bigoh notation,
asymptotics and it also contains some useful inequalities.
LaTex template. To save the LaTex template, you need to rightclick on the link and the "save then target" wherever you want to save it. Just clicking on the link will not be of much use, as you will just see the squeezed LaTex code.
Topics
Introduction
 Randomized algorithms (Longest Path, SAT)
 Probabilistic methods (Random Graphs without induced cliques/independent sets of size k)
Linearity of expectation
 Coupon Collector problem
 7/8approximation algorithm for Max3SAT
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, Azuma and Talagrand inequalities
 Subgraphs in random graphs
 Wilf's algorithm (3coloring of graphs)
 longest increasing subsecquence
Markov chains
 Gambler's Ruin problems
 Drift Analysis
 Algorithm for 3SAT
 Couplings of Markov chains
Outlook (if time permits)
 Generating functions
 Randomized rounding
 Average case analysis
 ...
Literature

The Probabilistic Method, 3rd Edition, Noga Alon and Joel H. Spencer, John Wiley & Sons (2008)

Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (2000)

Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)