2.15 Analysis of Algorithms MPRI
Lecturer: Lucas Gerin

2.15 Analysis of Algorithms

4th Part: Probabilistic approach (Lectures 14 to 17)

Online review

Table of contents

• Lecture 14: Probabilistic toolbox
  • Events and random variables
  • Conditioning
  • Inequalities and deviations
• Lecture 15: The Probabilistic Method
  • The 1st moment method
  • The 2d moment method
• Lecture 16: Balls in Bins
  • Collisions and birthday paradox
  • The cupon collector problem
  • Maximal load
• Lecture 17: Data stream algorithms
  • Prehistory: Morris' counting algorithm
  • Cardinality estimation: HitCounting and MinCount
  • CVM's algorithm

References

[Bre17] P.Brémaud. Discrete Probability Models and Methods. Springer (2017).

[Doe18] B.Doerr. Probabilistic Tools for the Analysis of Randomized Optimization Heuristics (2018).

[FS09] P.Flajolet, R.Sedgewick. Analytic Combinatorics. Cambridge University Press (2009).

[MU95] M.Mitzenmacher, E.Upfal. Probability and computing: randomized algorithms and probabilistic analysis . Cambridge University Press (1995).

Lecture 14: Probabilistic Toolbox

14.1. Events and random variables

• Probability spaces and events
• Union bound

Application. Randomized algorithm for checking a polynomial identity. Ref: [MU95] p.1.

14.2. Conditioning

• Conditional probability, conditionial expectation
• Law of total expectations

Application. Analysis of QuickSelect. Ref: Adapted from the blog 11011110.

14.3. Inequalities and deviations

• Markov, Chebyshev

Application. An (optimal) Randomized algorithm for the mean. Ref: [MU95] p.59.

Lecture 15: The Probabilistic Method

15.1. The 1st moment method

15.2. The 2d moment

Lecture 16: Balls in bins

16.1. Collisions and the birthday paradox

16.2. The coupon collector

16.3. Maximal load

Lecture 17: Data streams algorithms

17.1. Prehistory: Morris' counting algorithm

17.2. Cardinality estimation: HitCounting and MinCount

17.3. CVM's algorithm