Pearls of Algorithms
Part 3: Probabilistic Analysis and Randomized Algorithms
General Information
What | When | Where | Lecturer |
---|---|---|---|
Lectures | Monday, 14:30 - 16:00
Wednesday, 8:15 - 9:45 |
HS III.03a / LBH
HS III.03a / LBH |
Heiko Röglin |
Tutorials | Wednesday, 12:30 - 14:00
Thursday, 12:30 - 14:00 |
LBH / II.57
LBH / II.57 |
Tobias Brunsch |
Part 1 of this lecture was given by Norbert Blum.
Part 2 of this lecture was given by Rolf Klein.
Part 4 of this lecture was given by Marek Karpinski.
Contents
Date | Contents | Course Materials |
---|---|---|
December 9 | 1. Basic Probability Theory and Randomized Algorithms
1.1 Discrete Probability Spaces
1.2 Independent Events and Conditional Probability
|
Chapter 1 in [MU05] |
December 11 | 1.3 Verifying Matrix Multiplication
1.4 Application: A Randomized Min-Cut Algorithm
|
Chapter 1 in [MU05] |
December 16 | 1.4.1 Contract Algorithm
|
Chapter 1 in [MU05] |
December 18 | 1.4.2 FastCut Algorithm
|
Chapter 10.2 in [MR95] |
January 6 | 2. Smoothed Analysis
2.1 Introduction to Smoothed Analysis
|
|
January 8 | 2.2 Smoothed Analysis of the 2-Opt Algorithm for the TSP
|
|
January 13 | 2.3 Smoothed Analysis of the Knapsack Problem
|
Problem Sets
- Problem Set 3.1 (to be discussed on Dec 18 and Dec 19)
- Problem Set 3.2 (to be discussed on Jan 8 and Jan 9)
- Problem Set 3.3 (to be discussed on Jan 15 and Jan 16)
Exams
Students can take the oral exam with Professor Blum, Professor Karpinski, Professor Klein, or Professor Röglin. The exam will cover the whole semester, regardless of which examiner is chosen.
Exams with Heiko Röglin can be taken on February 10 and February 12. Re-exams will be on March 21. Students should send an email to Antje Bertram to schedule the exam.
References
There are lecture notes available for "2. Smoothed Analysis".
The following two books cover the topics discussed in "1. Basic Probability Theory and Randomized Algorithms".- [MR95] Rajeev Motwani und Prabhakar Raghavan. Randomized Algorithms.ISBN: 978-0521474658, Cambridge University Press, 1995.
- [MU05] Michael Mitzenmacher und Eli Upfal. Probability and Computing.ISBN: 978-0521835404, Cambridge University Press, 2005.