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.