MA-INF 1213: Randomized Algorithms & Probabilistic Analysis 2020

Notice

The start of the lecture is postponed until April 21st.

In view of the current circumstances the lecture will be held digitally (through recordings). Please keep an eye on this website and the discussion board on eCampus page of the lecture for further announcements. We're planning on using eCampus the as a central hub, so please join us there!

Lecture

Until further notice, the class is recorded and may be downloaded/viewed on eCampus. We host a weekly Zoom meeting in the Thursday time slot (each Thursday, 12:15h) where we answer your questions. Please see the eCampus discussion board for further details.

When Where Start Lecturer
Tuesday, 10:15-11:45
Thursday, 12:15-13:45
Recordings on eCampus April 21st (Tuesday) Röglin (June-),
Schmidt (-June)

Tutorials

When Where Start Lecturer
Tuesday, 14:15-15:45 Recordings on eCampus and Zoom sessions (see eCampus for details) April 28th Ioannis Psarros
Wednesday, 14:15-15:45 April 29th Ioannis Psarros

Problem Sets

  • Problem Set 1 (hand in until April 27th, to be discussed April 28th and April 29th)
  • Problem Set 2 (hand in until May 4th, to be discussed May 5th and May 6th)
  • Problem Set 3 (hand in until May 11th, to be discussed May 12th and May 13th)
  • Problem Set 4 (hand in until May 18th, to be discussed May 19th and May 20th)
  • Problem Set 5 (hand in until May 25th, to be discussed May 26th and May 27th)
  • Problem Set 6 (hand in until June 1st, to be discussed June 2nd and June 3rd)
  • Problem Set 7 (hand in until June 8th, to be discussed June 9th and June 10th)
  • Problem Set 8 (hand in until June 15th, to be discussed June 16th and June 17th)
  • Problem Set 9 (hand in until June 22th, to be discussed June 23th and June 24th)
  • Problem Set 10 (hand in until June 29th, to be discussed June 30th and July 1st)
  • Problem Set 11 (hand in until July 6th, to be discussed July 7th and July 8th)

Schedule

The lectures are available as a recording on eCampus.

Date Contents
April 211 Discrete Event Spaces and Probabilities
1.1 Discrete Probability Spaces
April 231.2 Independent Events & Conditional Probability
1.3 Applications
1.3.1 Minimum Cut, Karger's Contract algorithm
April 281.3.1 Karger's Contract algorithm (cont'd), Fastcut
April 301.3.1 Fast Cut (cont'd), 1.3.2 Reservoir Sampling
May 05 2.1 Random Variables and Expected Values
May 07 2.1 (cont'd): Conditional Expected Values
2.2 Binomial and Geometric Distributions
2.3.1 Randomized Quicksort
May 12 2.3.2 Randomized Approximation Algorithms
May 14 3 Concentration Bounds
3.1 Variance and Chebychev's Inequality
3.3.1 Introduction to Sublinear Algorithms
May 19 3.2 Chernoff/Rubin Bounds
3.3.1 Estimating the Number of Connected Components (without outlook on MSTs)
3.3.3. Routing in Hypercubes
May 26 3.3.3. Routing in Hypercubes (cont'd)
May 28 4.1 Stirling's formula and the Binomial Theorem
4.2.1 A Local Search Algorithm for 2-SAT
June 2 4.2.2 A Local Search Algorithm for 3-SAT
June 4 6 Knapsack Problem and Multiobjective Optimization
6.1 Nemhauser-Ullmann Algorithm
June 9 6.2 Number of Pareto-optimal Solutions
June 11 6.2 Number of Pareto-optimal Solutions
June 16 6.2 Number of Pareto-optimal Solutions
June 18 6.3 Multiobjective Optimization
6.4 Core Algorithms
June 23 7 Smoothed Complexity of Binary Optimization Problems
June 25 7 Smoothed Complexity of Binary Optimization Problems
June 30 9 The 2-Opt Algorithm for the TSP
9.1 Overview of Results
9.2 Polynomial Bound for phi-Perturbed Graphs
July 2 9.3 Improved Analysis
July 7 10 The k-Means Method

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.

Please also see the eCampus page of the lecture.

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.


Page Tools