2:00 PM-2:45 PM
Chair: William M. Coughran, Jr., Bell Laboratories, Lucent Technologies
Kresge Auditorium
Many computer programs access large tables of data by using a classical variant of hashing called "linear probing," also known to children as the game of "musical chairs." When the author first studied the characteristics of this simple method in 1962, he came to understand that the mathematical analysis of algorithms was a rich subject suitable for a lifetime of study. This talk surveys the mathematical analysis of algorithms by focussing on advances that have been in the analysis of linear probing from 1962 to 1997, and by noting surprising relations between this algorithm and other important algorithms and combinatorial problems, including the study of random graphs.
Donald E. Knuth
Professor Emeritus, Stanford University
AN97 Homepage | Program Updates|
Registration | Hotel and Dormitory Information | Transportation | Program-at-a-Glance | Program Overview