Randomized Algorithms and Probabilistic Methods
Lecturer
Prof. Dr. Angelika Steger
and
Prof. Dr. Emo Welzl
Assistants
Hafsteinn Einarsson
,
Marcelo Matheus Gauy
and
Pascal Pfister
Time and Place
Lecture:
Tuesday 13:15 - 14:00 in CAB G 51 and Thursday 08:15 - 10:00 in CAB G 51
Exercise Class: Tuesday, 16:15 - 18:00 in CAB G 51
Exam: Saturday, December 17th, 10:00 - 13:00 ,
Room: 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
-
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.
Exercise Sheet 1
Exercise Sheet 2
Graded Homework 1
Exercise Sheet 3
Exercise Sheet 4
Exercise Sheet 5
Graded Homework 2
Exercise Sheet 6
Exercise Sheet 7
Graded Homework 3
Exercise Sheet 8
Exercise Sheet 9
Exercise Sheet 10
Handouts
This pdf contains a short introduction to big-oh notation,
asymptotics and it also contains some useful inequalities.
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/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, Azuma and Talagrand inequalities
- Subgraphs in random graphs
- Wilf's algorithm (3-coloring of graphs)
- longest increasing subsecquence
Markov chains
- Gambler's Ruin problems
- Drift Analysis
- Algorithm for 3-SAT
- Couplings of Markov chains
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. If you want to buy a hard copy of the lecture notes, please contact
Pascal by Mail.
-
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 (1995)
-
Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)