[Colloquium] REMINDER: Talk by Janos Simon Today

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, October 20, 2009
Time: 3:00 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Janos Simon

From:		University of Chicago

Web page:	http://www.cs.uchicago.edu/people/simon

Title: Sorting by Random Insertion

Abstract: We analyze the number of comparisons made by the following  
randomized sorting algorithm: While the array is not sorted, choose a  
pair of elements and compare them. At each stage we choose uniformly  
at random among the pairs whose relationship was not determined by the  
previous stages. We obtain matching asymptotic upper and lower bounds.

Joint work with Mark Braverman.

The reception will be held prior to the talk in RY 255 at 2:30.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20091020/55c1c0cd/attachment.htm