Speaker: Mohamed F. Ahmed
Day:  Wednesday, 04/18/2007
Room: ITEB 336
Time: 2:00-3:30pm

Title: Derivation of Randomized Sorting and Selection Algorithms

Abstract:
This paper systematically derives randomized algorithms (both sequential
and parallel) for sorting and selection from basic principles and
fundamental techniques like random sampling. It proves several sampling
lemmas which will find independent applications. The new algorithms
derived here are the most efficient known. From among other
results, it has an efficient algorithm for sequential sorting.
The problem of sorting has attracted so much attention because of
its vital importance. Sorting with as few comparisons as possible while
keeping the storage size minimum is a long standing open problem. This
problem is referred to as 'the minimum storage sorting' in the literature.
The previously best known minimum storage sorting algorithm is
due to Frazer and McKellar. The expected number of comparisons
made by this algorithm is n log n + O(n log log n). The algorithm is 
derived in this paper makes only an expected n log n + O(n omega(n))
number of comparisons, for any function omega(n) that tends to infinity. A
variant of this algorithm makes no more than n log n + O(n log log n) 
comparisons on any input of size n with overwhelming probability.  
The paper also proves high probability bounds for several randomized 
algorithms for which only expected bounds have been proven so far.