Mireille Bousquet-Melou, LaBRI, France
TITLE: On the shape of binary trees.
ABSTRACT: Take a random binary tree with n nodes, and embed it in Z^2 in a canonical way: that is, the root of the tree sits at the origin (0,0), and each right [left] son of a node lies one unit above and one unit to the right [left] of its father.
Using techniques from enumerative combinatorics and complex analysis, we shall study the typical shape of this canonical embedding for large binary trees of a given size. This includes questions like:
how high, how wide is the embedding? What are the horizontal and vertical profiles of the tree? That is, how many nodes lie at a given abscissa or ordinate?
The results dealing with the horizontal profile are not new, while those dealing with the vertical profile are recent Their original motivation lies in the connection between embeddings of binary trees and the ISE (Integrated SuperBrownian Excursion).

TITLE: Probabilistic Counting: from analysis to algorithms to programs
ABSTRACT: Many applications, from network management to data mining and data bases, require efficient methods for extracting automatically quantitative characteristics of large data ensembles. Specifically, there is interest in determining cardinalities (the number of distinct elements satisfying various criteria), empirical entropies, and more generally "frequency moments". This tutorial survey talk will start from a few highly efficient algorithms that make it possible to attain estimates of good quality (typicallly accurate within a few percents), based on fine properties of various probabilistic models. The lecturewill focus on the intertwinment of algorithmic design with a collection of general methods of analytic combinatorics, which have proved especially useful in this context, namely, generating functions, singularity analysis, Mellin trasforms, and analytic depoissonization