The goal of this research is to understand the performance characteristics of fundamental algorithms that are likely to be broadly applicable. The primary focus is on analytic techniques that can result in precise performance predictions, on essential characteristics of specific implementations and their impact on practical situations, and on tools that can help uncover important properties of algorithms. Not all algorithms can be analyzed to the point that we can accurately predict their performance (indeed, most cannot). It is precisely for this reason that much algorithm design is done at the "complexity" level, where characteristics of machines, implementations, and input models can be ignored in the search for an algorithm with good or "optimal" worst-case performance characteristics. Research from this approach has mushroomed in recent years: scores of fundamental new algorithms for a wide variety of new and old applications have been devised. Unfortunately, it is too often the case that such algorithms are not useful in practice, because they have intricate worst-case avoidance mechanisms that add to overhead. This research will continue the study of methods that prove empirically to be useful in practice, to focus design efforts on improving the performance of such methods or devising demonstrably better methods, and to focus analysis efforts on techniques that can accurately predict performance.
