In Monday's (March 23) Discrete Lunch, Abdullah will give a presentation about the probabilistic analysis of sorting algorithms. If one is interested in the situation where the input is a random permutation, this is a textbook topic (covered, e.g., in MTAT.05.008 Discrete Math, and MTAT.05.117 Randomness).
Abdullah will present the contents of a paper by Clement, Nguyen, and Vallee, which considers the situation where the input is a random list of strings, which have to be sorted lexicographically, and one is interested in the number of comparisons of symbols. This setting is considerably more complex and requires more sophisticated probabilistic machinery. Abdullah will explain all of that in detail.
Discrete Lunch >