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]:
MON 22/march A2201
TUE 23/march A3002
WED 24/march A5001
THU 25/march A2201
FRI 26/march A3103

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
9. Mellin transforms
10. Parameters and limit laws

## References

The three major references are (in order of relevance for this course):
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