ANALYTIC COMBINATORICS & ALGORITHMS. Philippe Flajolet, Course at UPC 03/2004

ANALYTIC COMBINATORICS & ALGORITHMS.
Philippe Flajolet, Course at UPC: March 22-26, 2004

Welcome to these pages! Here are some informations.

Abstract: The course revolves around the process of analysing algorithms (i.e., predicting their performance on average/in probability) in the case of important algorithms and data structures of computer science (sorting, searching, hashing, probabilistic methods). There will be a pragmatic presentation of generating functions as central to the modelling process, of combinatorial enumeration principles, and of asymptotic analysis beased on an elementary use of complex variable methods (analytic functions). An original aspect will be the support of the computer algebra Maple that makes it possible for the student to develop concrete analyses by herself and proceeed with the optimal dimensioning of some important parameters in given application contexts.
Classroom [as of March 20th]:
Hours: 16:00-16:50 and 17:10-18:00.

Plan of the course

Will be adjusted on-line depending... There will be 10 lectures

1. Ordinary generating functions & unlabelled structures
2. Exponential generating functions & labelled structures
3. Bivariate generating functions & probability distributions
4. Complex analysis, rational and meromorphic asymptotics
5.Applications of rational and meromorphic asymptotics
6. Singularity analysis
7. Applications of singularity analysis
8. Saddle point methods
9. Mellin transforms
10. Parameters and limit laws

References

The three major references are (in order of relevance for this course):

Analytic Combinatorics, Book project by Flajolet and Sedgewick.
- Analytic Combinatorics---Symbolic Combinatorics (Chapters 1,2,3 of Analytic Combinatorics) is available from here. Covers Lectures 1,2,3.
- Analytic Combinatorics---Complex Asymptotic Methods, preliminary version here in [PS | PDF]. This is material for Lectures 4,5,6,7.
- Get Saddle Point Asymptotics, Mellin Transform Asymptotics, Multivariate Asymptotics and Limit Distributions This is material for Lectures 8,9,10.
An Introduction to the Analysis of Algorithms, by Flajolet and Sedgewick (1996).
- See details here.
Average-Case Analysis of Algorithms and Data Structures, by J. S. Vitter and Ph. Flajolet.
- Available from my Publications pages [Go to Year 1990].

We shall mostly use (a small but significant subset of) Analytic Combinatorics, and draw occasional examples of algorithmic analyses from the other two publications.

Computer algebra

This is a good way to get a hands on experience with generating functions, complex functions, and asymptotics, etc. I plan to suggest a few uses MAPLE for self-practice. Details will depend on interest and of participants and availability/quality of software environment.

Local contact

Via Kim Gabarró

Office hours: 11h30-12h30, Building C5, 2nd floor, Office 219.

E-mail: Philippe dot Flajolet At inria dot fr

Additional on-line informations

Exercises with Maple I

Good Luck!