Back to Departmental Colloquium: Spring 2005
Departmental Colloquium
Date: Thursday, Feb 3, 2005
Time: 4:15PM
Location: JWB 335
Special Colloquium Thursday
Additive Functionals of Random Trees
Title |
Additive Functionals of Random Trees |
Abstract |
In this talk I will motivate the study of functionals of random trees that satisfy recurrence relations of a simple additive form and describe recent progress in this area. Many important functionals including the space requirement, internal path length, number of leaves, and the so-called “shape functional” fall under this framework. Such functionals also represent the cost of divide-and-conquer algorithms (including QuickSort and Union–Find), where the inherent recursive nature of the algorithms lends itself naturally to such a formulation. In particular, I will describe limit laws of additive functionals on (i) m -ary search tress (natural generalizations of binary search trees) under the random permutation model and the uniform model, (ii) simply generated trees or conditioned Galton–Watson trees (which include ordered trees, d -ary trees, and Cayley trees). Several interesting techniques are employed and extended in this work, including the elementary but powerful “contraction method” and singularity analysis, a complex–analytic technique that relates asymptotics of sequences to singularities of their generating functions. |
Mathematical Biology
Computational Mathematics
Applied Mathematics