Sidebar

This is an old revision of the document!

MA-INF 1213: Randomized Algorithms & Probabilistic Analysis 2018

Notice

The first round of oral exams will take place on the 18th, 19th and 20th of July.

Lecture

When Where Start Lecturer
Tuesday, 10:15-11:45
Thursday, 12:15-13:45
CP1-HSZ / HS 3
CP1-HSZ / HS 4
April 12th (Thursday) Röglin (June-),
Schmidt (-June)

Tutorials

When Where Start Lecturer
Tuesday, 14:15-15:45 INF / Room 2.050 April 17th Rösner
Wednesday, 14:15-15:45 INF / Room 2.050 April 18th Rösner

Problem Sets

• Problem Set 1 (hand in until April 16th, to be discussed April 17th and April 18th)
• Problem Set 2 (hand in until April 23th, to be discussed April 24th and April 25th)
• Problem Set 3 (hand in until April 30th, to be discussed May 2nd and May 8th)
• Problem Set 4 (hand in until May 7th, to be discussed May 9th and May 15th)
• Due to the holidays on May 1st and May 10th there is no new exercise sheet on May 7th. Problem Set 5 will be released May 14th.
• Problem Set 5 (hand in until May 28th, to be discussed May 29th and May 30th)
• Problem Set 6 (hand in until June 4th, to be discussed June 5th and June 6th)
• Problem Set 7 (hand in until June 11th, to be discussed June 12th and June 13th)
• Problem Set 8 (hand in until June 18th, to be discussed June 19th and June 20th)
• Problem Set 9 (hand in until June 25th, to be discussed June 26th and June 27th)
• Problem Set 10 (hand in until July 2nd, to be discussed July 3rd and July 4th)
• Problem Set 11 (hand in until July 9nd, to be discussed July 10th and July 11th)

Schedule

Date Contents
April 121 Discrete Event Spaces and Probabilities
1.1 Discrete Probability Spaces
1.2 Independent Events & Conditional Probability
April 171.2 (continued) Conditional Probability
1.3 Applications
1.3.1 Minimum Cut, Karger's Contract Algorithm
April 191.3.1 (continued) Karger's Contract algorithm
1.3.1 FastCut
April 241.3.1 (continued) FastCut
1.3.1 Reservoir Sampling
April 262.1 Random Variables and Expected Values
2.1.1 Integer Random Variables
May 1no lecture
May 32.1.2 Conditional Expectation
2.2 Binomial and Geometric Distribution
2.3 Applications
2.3.1 Randomized QuickSort
May 82.3.2 Randomized Approximation Algorithms
May 10no lecture
May 153 Concentration Bounds: Markov's Inequality
3.1 Variances and Chebyshev's Inequality
3.3 Applications: Introduction to sublinear algorithms
May 173.3.1 A sublinear algorithm
May 22no lecture
May 24no lecture
May 293.2 Chernoff/Rubin bounds
4.1 Useful math
4.2 Applications
4.2.1 An Algorithm for 2-SAT
May 31no lecture
June 54.2.2 Algorithms for 3-SAT
June 76 Knapsack Problem and Multiobjective Optimization
6.1 Nemhauser-Ullmann Algorithm
June 12 6.2 Number of Pareto-optimal Solutions
June 14 6.2 (continued) Number of Pareto-optimal Solutions
June 19 6.3 Multiobjective Optimization
6.4 Core Algorithms
June 21 7 Smoothed Complexity of Binary Optimization Problems
June 26 7 (continued) Smoothed Complexity of Binary Optimization Problems
June 28 8 Successive Shortest Path Algorithm
Slides
July 3 9 The 2-Opt Algorithm for the TSP
9.1 Overview of Results
9.2 Polynomial Bound for phi-Perturbed Graphs
July 5 9.3 Improved Analysis
July 10 no lecture
July 12 10 The k-Means Method
Slides

Course Material

The Lecture Notes cover the lecture. Part I is largely based on the following two books:

• [MR95] Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. ISBN: 978-0521474658, Cambridge University Press, 1995.
• [MU05] Michael Mitzenmacher and Eli Upfal. Probability and Computing. ISBN: 978-0521835404, Cambridge University Press, 2005.

Content

The lecture has two parts. First, we consider the design and analysis of randomized algorithms. Many algorithmic problems can be solved more efficiently when allowing randomized decisions. Additionally, randomized algorithms are often easier to design and analyze than their (known) deterministic counterparts. For example, we will see an elegant algorithm for the minimum cut problem. Randomized algorithms can also be more robust on average, like randomized Quicksort.

The analysis of randomized algorithms builds on a set of powerful tools. We will get to know basic tools from probabily theory, very useful tail inequalities and techniques to analyze random walks and Markov chains. We apply these techniques to develop and analyze algorithms for important algorithmic problems like sorting and k-SAT.

Statements on randomized algorithms are either proven to hold on expectation or with high probability over the random choices. This deviates from the classical algorithm analysis but is still a worst-case analysis in its core. In the second part of the lecture, we learn about probabilistic analysis of algorithms. There are a number of important problems and algorithms for which worst-case analysis does not provide useful or empirically accurate results. One prominent example is the simplex method for linear programming whose worst-case running time is exponential while in fact it runs in near-linear time on almost all inputs of interest. Another example is the knapsack problem. While this problem is NP-hard, it is a very easy optimization problem in practice and even very large instances with millions of items can be solved efficiently. The reason for this discrepancy between worst-case analysis and empirical observations is that for many algorithms worst-case instances have an artificial structure and hardly ever occur in practical applications.

In smoothed analysis, one does not study the worst-case behavior of an algorithm but its (expected) behavior on random or randomly perturbed inputs. We will prove, for example, that there are algorithms for the knapsack problem whose expected running time is polynomial if the profits or weights are slightly perturbed at random. This shows that instances on which these algorithms require exponential running time are fragile with respect to random perturbations and even a small amount of randomness suffices to rule out such instances with high probability. Hence, it can be seen as an explanation for why these algorithms work well in practice. We will also apply smoothed analysis to the simplex method, clustering problems, the traveling salesman problem, etc.