Curriculum M1 MPRI at ENS Paris-Saclay

DONA: Distributed and Online Algorithms

Description: This advanced algorithms course aims to provide a foundation in probability as applied to classical and online algorithms, as well as the principles of distributed algorithms. Upon completion of this course, students will be able to: (1) Analyze randomized algorithms by examining their expected execution time and error probability. (2) Explain and apply competitive analysis to online algorithms. (3) Understand the fundamentals of reasoning about distributed algorithms and their constraints.

See real-time course progression for up-to-date information, including examination modalities.

Outline:

  1. Algorithms and probability: expected complexity analysis, high-probability analysis (e.g., randomized quicksort, skip lists, universal hashing, perfect hashing)
  2. Online algorithms: formalization, probabilistic analysis, competitive analysis (e.g., secretary problem, cache management)
  3. Distributed algorithms: modeling (communication modes, synchrony, faults, Byzantine processes), graph algorithms (e.g., BFS tree construction, maximal independent set construction, coloring), consensus (FLP impossibility, approximate consensus, randomized consensus)


References:

  • Michael Mitzenmacher et Eli Upfal. Probability and Computing : Randomization and Probabilistic Techniques in Algorithms and Data Analysis. 2e éd. Cambridge : Cambridge University Press, 2017.
  • Rajeev Motwani et Prabhakar Raghavan. Randomized Algorithms. Cambridge : Cambridge University Press, 1995.
  • Web site of instructors ...