McGill University - School of Computer Science

Algorithms Seminar Winter 2001

Everybody is welcome!

DATE: Wednesday, March 28th
TIME: 4:30 PM - 5:30 PM
PLACE: McConnell 320
TITLE: Probabilistic analysis of Quicksort
SPEAKER: Ralph Neininger, Universitat Freiburg

Many parameters of different versions of the quicksort algorithm have been analyzed from a probabilstic point of view, assuming that all permutations of the keys are equally likely. For example, for the number of key comparisons used by a standard version of Quicksort the mean, the variance, a limit law, and large deviation inequalities are known. For the derivation of the limit law the "contraction method" was used for the first time.

In this seminar a introduction to the contraction method is given and new limit laws for parameters of median of $2t+1$ versions of Quicksort are derived by this method.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.