Session 11

10:25-10:45 Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals

Haim Kaplan, Princeton University; Ron Shamir, Tel Aviv University, Israel; and Robert Tarjan, Princeton University

10:50-11:10 Randomized Sorting in O(nloglog n) Time and Linear Space using Addition, Shift, and Bit-Wise Boolean Operations

Mikkel Thorup, University of Copenhagen, Denmark

11:15-11:35 Fast Algorithms for Sorting and Searching Strings

Jon L. Bentley, Bell Laboratories; and Robert Sedgewick, Princeton University

11:40-12:00 The Influence of Caches on the Performance of Sorting

Anthony LaMarca and Richard E. Ladner, University of Washington

12:05-12:25 Runtime Prediction of Real Programs on Real Machines

Ulrich Finkler and Kurt Mehlhorn, Max-Planck-Institüt für Informatik, Germany

Registration | Hotel Information | Transportation | Program-at-a-Glance | Author Index