Speaker: Conrado Martinez, Universitat Politecnica de Catalunya, Spain 
Time:    Tuesday, April 6, 11:00-12:00
Place:   room HP 4351, Herzberg Building, Carleton University
Title:   "Forty years of Quicksort and Quickselect: a personal view"

Since their inception in the early sixties by C.A.R. Hoare, quicksort and 
quickselect are among the dozen or so most fundamental algorithms in computer 
science. Being primary and highly successful examples of divide-and-conquer 
design principle, these two algorithms combine beauty, efficiency, simplicity 
and practicality to provide solution to two basic problems: sorting and 
selection. They also rank among the most carefully analyzed algorithms ever, 
yet after four decades of deep study they still pose amazing and interesting 
mathematical challenges.

In this talk, I will briefly summarize some of the research efforts conducted 
on quicksort and quickselect, and I will present some new contributions to 
the understanding of these two important algorithms.