This award supports Dr. Wojciech Szpankowski of Purdue University to collaborate in computer science research with Drs. Peter Kirschenhofer and Helmut Prodinger of the Department of Algebra and Discrete Mathematics of the Technical University of Vienna. They are developing theoretical methods for the analysis of algorithms and data structures, drawing from several areas of applied mathematics. They plan to apply these methods to an in-depth analysis of the average case behavior of digital search algorithms. Collaboration is necessary because the problems they want to attack require diverse expertise in several fields of mathematics. The primary responsibilities of the Austrian collaborators in this project involve their expertise in asymptotic approximation and combinatorial analysis, while Dr. Szpankowski contributes expertise in stochastic modelling and general problem formulation. The analysis of algorithms and data structures is a rapidly developing area in theoretical computer science with a strong impact on practical problems. The cost of performance of algorithms, including such factors as the storage requirements of data structures and the execution time of certain subroutines, is usually described in terms of worst case behavior and average case behavior. Digital tree search is one of the main approaches to data storage and retrieval. The proposed research on average case behavior of digital search trees will contribute to improved choice and design of data structures and the new analytical techniques will have relevance in other areas.
