Pearls of Algorithms
Part 2: Probabilistic Analysis and Randomized Algorithms
General Information
What | When | Where | Lecturer |
---|---|---|---|
Lectures | Monday, 14:30 - 16:00
Wednesday, 8:30 - 10:00 |
AVZ III / A207
AVZ III / HS 2 |
Heiko Röglin |
Tutorials | Monday, 12:30 - 14:00
Wednesday, 10:15 - 11:45 |
AVZ III / A6b
AVZ III / A6b |
Matthias Kretschmer |
Part 1 of this lecture was given by Norbert Blum
Part 3 of this lecture was given by Marek Karpinski and Mathias Hauptmann
Contents
Date | Contents | Course Materials |
---|---|---|
November 14 | 1. Basic Probability Theory and Randomized Algorithms
1.1 Discrete Probability Spaces
1.2 Independent Events and Conditional Probability
|
Chapter 1 in [MU05] |
November 16 | 1.3 Verifying Matrix Multiplication
|
Chapter 1 in [MU05] |
November 21 | 1.4 Application: A Randomized Min-Cut Algorithm
1.4.1 Contract Algorithm
|
Chapter 1 in [MU05] |
November 23 | 1.4.2 FastCut Algorithm
|
Chapter 10.2 in [MR95] |
November 28 | 1.5 Discrete Random Variables and Expectation
1.5.1 Application: Quicksort
|
Chapter 2 in [MU05] |
November 30 | 1.5.2 Application: Coupon Collector's Problem
1.5.3 Markov's Inequality
1.6 Continuous Distributions
|
Chapter 2 in [MU05]
Chapter 3.1 in [MU05]
Chapter 8.1 in [MU05] |
December 5 | 2. Smoothed Analysis
2.1 Introduction to Smoothed Analysis
|
|
December 7 | no lecture due to Dies Academicus
|
|
December 12 | 2.2 Smoothed Analysis of the 2-Opt Algorithm for the TSP
|
|
December 14 | 2.3 Smoothed Analysis of the Knapsack Problem
|
Problem Sets
- Problem Set 2.1 (to be discussed on Nov 21 and Nov 23)
- Problem Set 2.2 (to be discussed on Nov 28 and Nov 30)
- Problem Set 2.3 (to be discussed on Dec 5)
- Problem Set 2.4 (to be discussed on Dec 12 and Dec 14)
Exams
Students can take the oral exam with Professor Blum, Professor Karpinski, 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 8 and February 9. Re-exams will be on March 29. Students should send an email to Heiko Röglin to schedule the exam.
References
There are lecture notes available for "2. Smoothed Analysis".
The following two books, which are available in the reading room (AVZ III / A125), 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.