ANALYTIC COMBINATORICS & ALGORITHMS.
Philippe Flajolet, Course at MSRI, Berkeley, June 2004
ANALYTIC COMBINATORICS & ALGORITHMS.
Philippe Flajolet, Course at UC Berkeley, June 2004
Welcome to these pages! We are talking here of the Summer Graduate
Programme of MSRI,
specifically the two weeks course:
-
Analysis of Algorithms and Information Theory:
[Page @ MSRI] and
[Page @Wojtek S]
June 2, 2004 to June 11, 2004
Organized by: P. Flajolet, G. Seroussi, W. Szpankowski, and
M. Weinberger
-
Principles of Analytic Combinatorics
Set of 10 lectures by Philippe Flajolet
Abstract: The goal of this set of lectures is the precise
quantification of properties of large random structures. These
include the basic combinatorial types of words, trees, graphs,
permutations, and mappings. Problems may be approached from
different angles, like probability theory and stochastic processes,
dynamical systems theory, or even statistical physics. In this
set of lectures, we shall provide an introduction to the combinatorial and
enumerative approach based on generating functions, as well as to
asymptotic methods relying on (elementary) complex analysis. This
chain is what has come to be known under the name of Analytic
Combinatorics. As we shall see, thanks to
analytic combinatorics, major characteristics of the basic
types can be quantified in a systematic manner. Applications to the
analysis of algorithms involving hashing, search trees, symbolic
manipulation, and
pattern-matching will
also be outlined.
Plan of the course
Will be adjusted on-line depending... The topics will include:
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. Parameters and limit laws
Context and other lecturers
The director of the course is Wojtek Szpankowski,
and there will be
10 hour sets of lectures given by him as well
as by G. Seroussi and M. Weinberger. The other parts of the course
should thus be expected to focus on topics related to data
compression and information theory. In this context, I will cover
the basic methodology underlying analytic methods and develop some
relevant examples.
References
We shall mostly use (a small but significant subset of) the future book
Analytic Combinatorics:
- Analytic Combinatorics, Book project by Flajolet and
Sedgewick.
-
Analytic Combinatorics---Symbolic
Combinatorics (Chapters 1,2,3 of Analytic
Combinatorics) is available from there.
Covers Items 1,2,3.
- Analytic Combinatorics---Complex
Asymptotic Methods (Chapters 4,5,6,7 of Analytic
Combinatorics) is available from
there.. Covers Items 4,5,6,7.
- Get
Multivariate Asymptotics and Limit Distributions
This
is material for Item 8.
Other useful references are:
- An Introduction to the Analysis of Algorithms,
by Flajolet and Sedgewick (1996).
- Odlyzko's chapter:
- Asymptotic enumeration methods, by A. M. Odlyzko, in
Handbook of
Combinatorics, vol. 2, R. L. Graham, M. Groetschel, and
L. Lovasz, eds., Elsevier, 1995, pp. 1063-1229.
- Average-Case Analysis of Algorithms and Data Structures,
by J. S. Vitter and Ph. Flajolet.
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.
Good Luck!