Table of Contents
Analysis of Algorithms (48h, 6 ECTS)
First lesson: Wednesday 13 September 2023, at 16h15 Organizer: Élie de Panafieu Calendar for 2023 – 2024Part 1
Part 2
ObjectivesThis 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 contextfree 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 coursesThis 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.291. Detailed outline
Notes and referencesThe 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 examsExercises are proposed at the end of each lesson and corrected at the beginning of the next one. A training session is organized before the midterm 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. LanguageThe course will be in English, unless all students speak french. The handout notes are in English. Teachers
