George Mason University
CSI/Statistics Colloquium Series
Seminar Announcement


Analysis of an Algorithm for Finding Order Statistics via Analytic Probability

Hosam Mahmoud
The George Washington University



ABSTRACT

Certain analytic techniques have proved effective in the study of averages for random discrete structures and algorithms. Typically one considers a generating function for the sequence of averages. One then sets up a functional equation (usually arising from a recurrence) and solves it asymptotically by a tool-kit that involves a variety of integral transforms. The behavior of the generating function near its dominant singularities captures the asymptotic nature of the averages. (Typically, non-dominant singularities contribute periodic oscillations.) To address distributions instead of only average-case analysis, these have been extended to bivariate generating functions. One still considers dominant singularities, which are now functions of a second variable. The analysis is most informative in the neighborhood of certain values for this second variable. The analysis therefore is viewed as a perturbation. We illustrate this route by a problem that arises in sorting algorithms. To find the limit distribution of a sum of dependent random variables, the analysis involves perturbation of Rice's integration method which will be explained in a tutorial introduction.


Friday, March 30, 2001
Student Union Building II (SUB II), Rooms 1 and 2
Seminar at 10:45 a.m.
Refreshments at 10:30 a.m.
For the 2001 Spring Seminar Schedule, go to
www.science.gmu.edu/statseminars