ANALYTIC COMBINATORICS & ALGORITHMS.
Philippe Flajolet, Course at UPC 03/2004
ANALYTIC COMBINATORICS & ALGORITHMS.
Philippe Flajolet, Course at UPC: March 2226, 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:0016:50 and 17:1018:00.
Plan of the course
Will be adjusted online 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 CombinatoricsSymbolic
Combinatorics (Chapters 1,2,3 of Analytic
Combinatorics) is available from here.
Covers Lectures 1,2,3.
 Analytic CombinatoricsComplex 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).
 AverageCase Analysis of Algorithms and Data Structures,
by J. S. Vitter and Ph. Flajolet.
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 selfpractice. Details will depend on interest and
of participants and availability/quality of software environment.
Local contact
Via Kim Gabarró
Office hours: 11h3012h30, Building C5, 2nd floor, Office
219.
Email: Philippe dot Flajolet At inria dot fr
Additional online informations
Good Luck!