Analytic Combinatorics
Organizer and Chair:
Alfredo Viola (Universidad de la RepÃºblica, Uruguay)
[
PDF]
 JULIEN CLEMENT, GREYC, CNRS, University of Caen, FRANCE
A general framework for the realistic analysis of sorting and searching algorithms. Application to some popular algorithms [PDF] [SLIDES]

We describe a general framework for realistic analysis of sorting
and searching algorithms and apply it to the averagecase
analysis of five basic algorithms: three sorting algorithms
(\emph{QuickSort}, \emph{InsertionSort}, \emph{BubbleSort}) and two
selection algorithms (\emph{QuickMin} and
\emph{SelectionMin}). Usually, the analysis deals with the mean
number of key comparisons, but, here, we view keys as words produced
by the same source. The ``realistic'' cost of the algorithm is now
the total number of symbol comparisons performed by the algorithm,
and, in this context, the averagecase analysis aims to provide
estimates for the mean number of symbol comparisons used by the
algorithm.
 DANIELE GARDY, University of Versailles Saint Quentin
Some problems related to the enumeration of lambdaterms [PDF] [SLIDES]

Lambdaterms are basic objects of lambda calculus. Syntaxically, they can be seen as Motzkin trees on which we add arcs from some unary nodes to some leaves; equivalently they can be modelized by colored trees. Understanding their statistical behaviour, beginning with the number of terms of specific size, and graduating to shape parameters and to such lambda calculusrelated properties as being normalizable, turns out to be no simple task.
We consider here terms with bounded number of unary nodes or bounded unary height: we obtain enumeration results and the probability that a random term is normalisable.
 MARCOS KIWI, U. Chile
Towards the distribution of the size of the largest noncrossing matchings in random bipartite graphs [PDF] [SLIDES]

We consider the following question: When a randomly chosen regular bipartite multigraph is drawn in the plane in the ``standard way'', what is the distribution of its maximum size planar matchings (sets of noncrossing disjoint edges)? The problem is a generalization of the Longest Increasing Sequence (LIS) problem (also called Ulam's problem). We first generalize Gessel's identity. Then, among other things, we show how to count, for small values of $d$ and $r$, the number of $r$regular bipartite multigraphs with maximum planar matchings of size $d$.
Joint work with Martin Loebl (Charles U.)
 ALOIS PANHOLZER, TU Wien
Occurrences of exactly solvable PDEs in combinatorial problems [PDF] [SLIDES]

When applying generating functions techniques various combinatorial enumeration problems can be reformulated as searching for solutions of certain quasilinear first order partial differential equations. The general solution technique ``method of characteristics'' transforms such PDEs into ODEs after discovering characteristic curves, but the latter is not always feasible in a constructive way. However, for several interesting combinatorial questions this is indeed the case and one obtains fairly explicit generating functions solutions, which can be treated by analytic combinatorics methods. We illustrate this ``observation'' with a few examples related to patterns in mappings and trees, online decision making strategies and urn models.
 BRIGITTE VALLEE, GREYC Laboratory, CNRS and University of Caen
Typical depth of a digital search tree built on a general source [PDF] [SLIDES]

The digital search tree (dst) plays a central role in compression algorithms. Its probabilistic analysis is involved, even when the text is produced by a "simple" source. After the seminal paper of FlajoletSedgewick (1986) which deals with the simplest case, papers of Jacquet, Louchard, Prodinger Szpankowski, Tang performed the analysis of the main parameters of dst for general "simple" sources. Here, we perform a more realistic analysis, for general sources, in the flavour of previous works on tries or sorting algorithms. This a joint work with Kanal Hun, whose first steps were performed with Philippe Flajolet, during December 2010.