First lesson: Monday 23 September 2024, at 12h45
building Sophie Germain, room 1002

Organizer: Élie de Panafieu

Part 1

• 23/09 analytic combinatorics (Marie Albenque)
• 30/09 analytic combinatorics (Marie Albenque)
• 07/10 analytic combinatorics (Marie Albenque)
• 14/10 analytic combinatorics (Marie Albenque)
• 21/10 sorting algorithms (Vincent Jugé)
• 28/10 sorting algorithms (Vincent Jugé)
• 04/11 sorting algorithms (Vincent Jugé)
• 11/11 NO LECTURE (public holiday)
• 18/11 sorting algorithms (Vincent Jugé)
• 25/11 mid-term exam

Part 2

• 09/12 analytic combinatorics (Florent Koechlin)
• 16/12 analytic combinatorics (Florent Koechlin)
• 21/12 → 05/01 winter break
• 06/01 analytic combinatorics (Florent Koechlin)
• 13/01 analytic combinatorics (Florent Koechlin)
• 20/01 analytic combinatorics (Florent Koechlin)
• 27/01 probabilistic approach (Lucas Gerin)
• 03/02 probabilistic approach (Lucas Gerin)
• 10/02 probabilistic approach (Lucas Gerin)
• 17/02 probabilistic approach (Lucas Gerin)
• 24/02 training session
• 10/03 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 (???) Exact enumeration by ordinary generating functions. Elementary models for words and languages, link between automata, rational functions, linear systems and transfer matrices.
• Labeled objects (???) 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 (Marie Albenque) 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.
• 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.