SCS DISTINGUISHED ALUMNI LECTURE SERIES
The Hank Suz-Chi Wan Memorial Lecture

Jon L. Bentley
Lucent/Bell Labs

Algorithm Engineering:
From Practice to Theory and Back

Thursday, March 20, 1997

4:00 pm, Wean Hall 7500

3:30 pm - Refreshments Outside Wean Hall 7500

Abstract
It started with a bug report: the venerable system sort was taking weeks instead of minutes on certain inputs. We examined qsorts in several C libraries, and all had similar flaws. We therefore had to engineer a new qsort; this talk describes the process and the result, the fastest known qsort. Along the way, experimental observations led to new theory: a three-way partitioning algorithm and a characterization of the running time of Quicksort in terms of the entropy of its input. Extending the techniques led to new algorithms for sorting and searching strings. Their implementations are competitive with the best known programs for the tasks. (This work was performed jointly with Doug McIlroy of Bell Labs and Bob Sedgewick of Princeton.)

BIOGRAPHY
Jon Bentley is a Member of Technical Staff in the Computing Sciences Research Center at Bell Laboratories. His research interests include computer programming, algorithm design, and the design of software tools and interfaces. He was a member of the teams that developed AT&T's Computer Telephone 8130 and Project instantAnswers.

Bentley received a B.S. degree from Stanford University in 1974, and M.S. and Ph.D. degrees from the University of North Carolina in 1976. Prior to joining Bell Labs in 1982, he was an Associate Prof ssor of Computer Science and Mathematics at Carnegie-Mellon University. Since joining the Labs, he has been a visiting faculty member at the United States Military Academy at West Point and at Princeton University.


SCS Distinguished Lecture Schedule
SCS Calendar of Events