CanaDAM 2013
Memorial University of Newfoundland, June 10 - 13, 2013

Analytic Combinatorics
Organizer and Chair: Alfredo Viola (Universidad de la República, Uruguay)

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 average-case 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 average--case 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 lambda-terms  [PDF] [SLIDES]

Lambda-terms 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 calculus-related 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.

Towards the distribution of the size of the largest non-crossing matchings in random bipartite graphs  [PDF] [SLIDES]

We consider the following question: When a randomly chosen regular bipartite multi-graph is drawn in the plane in the ``standard way'', what is the distribution of its maximum size planar matchings (sets of non-crossing 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 multi-graphs with maximum planar matchings of size $d$.

Joint work with Martin Loebl (Charles U.)

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, on-line 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 Flajolet-Sedgewick (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.

Event Sponsors

Atlantic Association for Research in the Mathematical Sciences Centre de recherches mathématiques The Fields Institute Pacific Institute for the Mathematical Sciences Canadian Mathematical Society Memorial University of Newfoundland