Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Analysis of Algorithms (48h, 6 ECTS)

First lesson: Wednesday 13 September 2023, at 16h15
building Sophie Germain, room 1002

Organizer: Élie de Panafieu

Calendar for 2023 – 2024

Part 1

  • 13/09 introduction (Vincent Jugé)
  • 20/09 ordinary generating functions (Élie de Panafieu)
  • 27/09 ordinary generating functions (Absence)
  • 04/10 exponential generating functions (Élie de Panafieu)
  • 11/10 exponential generating functions (Élie de Panafieu)
  • 18/10 exponential generating functions (Élie de Panafieu)
  • 25/10 graphs (Élie de Panafieu)
  • (holidays)
  • 08/11 graphs (Élie de Panafieu)
  • 15/11 exercises
  • 22/11 midterm exam

Part 2

  • 06/12 sorting algorithms (Vincent Jugé)
  • 13/12 sorting algorithms (Vincent Jugé)
  • (holidays)
  • 03/01 sorting algorithms (Vincent Jugé)
  • 10/01 constraint satisfaction problems (Éric Fusy)
  • 17/01 constraint satisfaction problems (Éric Fusy)
  • 24/01 random generation (Olivier Bodini)
  • 31/01 to be determined (Florent Koechlin)
  • 07/02 to be determined (Florent Koechlin)
  • 14/02 to be determined (Florent Koechlin)
  • 21/02 exercises
  • 06/03 exam

Objectives

This class presents techniques from combinatorics applied to the analysis of algorithms. The focus is on analytic combinatorics (french version). In this field, combinatorial constructions are translated into generating function relations. Information on the sequence enumerating the combinatorial objects are extracted through analytic tools. The techniques presented apply to the analysis of algorithms and to the study of random objects, such as permutations, partitions, words in rational or context-free languages, trees and graphs.

Mathematical analysis is used throughout the course. It is probably best to know before hand what a power series is. Knowing more advanced complex analysis is helpful, but not necessary. We are at the boundary of mathematics and computer science. As such, this class attracts students from both fields.

Related courses

This class is thematically linked to 2.10. While we focus on generating functions, module 2.10 emphasizes bijective proofs. Both approaches complement each other and combine well.

Other related modules are 2.11.1, 2.11.2, 2.17.1, 2.22, and 2.29-1.

Detailed outline

  • Rational models (Frédérique Bassino) Exact enumeration by ordinary generating functions. Elementary models for words and languages, link between automata, rational functions, linear systems and transfer matrices.
  • Labeled objects (Élie de Panafieu) Exact enumeration by exponential generating functions, and asymptotic extraction using singularity analysis and the saddle-point method. Study of random permutations, trees, set partitions, words and mappings. Applications to the birthday paradox, the coupon collector problem, the analysis of partitioning algorithms.
  • Graphs (Élie de Panafieu) Exact and asymptotic enumeration of various graph families (degree constraints, connectivity, directed acylic graphs). Tools for handling divergent series are introduced.
  • Analysis of sorting algorithms (Vincent Jugé) The focus is on the analysis and improvement of algorithms, as well as the choice of the random models. We will in particular study sorting algorithms where various settings can be explored to describe what a typical input should be.
  • Constraint satisfaction problems (Éric Fusy) Phase transition and constraints satisfaction problems, probabilistic approach, first and second moment methods.
  • (?) (Florent Koechlin)

Notes and references

The lectures are presented on the board or by slides and handout notes are provided.

The main reference of this module is the book of Flajolet and Sedgewick Analytic Combinatorics. Another reference book by the same authors is Introduction à l'analyse des algorithmes. Robert Sedgewick teaches the analysis of algorithms and analytic combinatorics on coursera (free).

Exercises and exams

Exercises are proposed at the end of each lesson and corrected at the beginning of the next one. A training session is organized before the mid-term exam, and another one before the exam.

During the exams, the only documents allowed are handwritten notes and the course handouts provided by the teachers. The final grade is calculated as the average of the midterm exam and the exam.

Language

The course will be in English, unless all students speak french. The handout notes are in English.

Teachers

Olivier Bodini PU Paris 13 LIPN
Éric Fusy DR Gustave Eiffel LIGM
Vincent Jugé MCF Gustave Eiffel LIGM
Florent Koechlin CR Paris 13 LIPN
Élie de Panafieu Chercheur Nokia Bell Labs Malin
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA