| 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.