|DATE:||Wednesday, March 28th|
|TIME:||4:30 PM - 5:30 PM|
|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.