WikiMPRI

First lesson: Monday 22 September 2025, at 16h15
building Sophie Germain, room 1002

Organizer: Élie de Panafieu

Part 1

• 22/09 unlabeled objects (Pablo Rotondo)
• 29/09 unlabeled objects (Pablo Rotondo)
• 06/10 unlabeled objects (Pablo Rotondo)
• 13/10 unlabeled objects (Pablo Rotondo)
• 20/10 labeled objects (Élie de Panafieu)
• 27/10 no lecture (holiday)
• 03/11 labeled objects (Élie de Panafieu)
• 10/11 labeled objects (Élie de Panafieu)
• 17/11 labeled objects (Élie de Panafieu)
• 24/11 or 01/12 mid-term exam

Part 2

• 08/12 probabilistic approach (Marie Albenque)
• 15/12 probabilistic approach (Marie Albenque)
• 22/12 no lecture (holiday)
• 29/12 no lecture (holiday)
• 05/01 probabilistic approach (Marie Albenque)
• 12/01 probabilistic approach (Marie Albenque)
• 19/01 analysis of tries (Florent Koechlin)
• 26/01 analysis of tries (Florent Koechlin)
• 02/02 analysis of tries (Florent Koechlin)
• 09/02 analysis of tries (Florent Koechlin)
• 16/02 analysis of tries (Florent Koechlin)
• 23/02 training session
• 02/03 or 09/03 final exam

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.

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.

• Rational models (Pablo Rotondo) 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, mappings, graphs. Applications to the birthday paradox, the coupon collector problem, the analysis of partitioning algorithms
• Probabilistic approach (Marie Albenque) Introduction to randomization and probabilistic techniques. These tools play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols.

1. Probabilistic Toolbox (Events / Mean / Deviations, Conditioning)
2. The Probabilistic method (First and second moment and algorithmic applications, Random graphs)
3. Balls-in-bins and random allocations (Birthday paradox and Coupon collector process, Maximal load)
4. Probabilistic algorithms for data streams (Approximate counting, Cardinality estimation with HyperLogLog)

• Advanced analytic combinatorics (Florent Koechlin) Mellin transform, depoissonization, statistics of tries and algorithmic questions reducing to it.

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 are proposed at the end of each lesson and corrected at the beginning of the next one. A training session is organized 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.

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