US-Austria Cooperative Research: Analysis of Data Structures for Digital Search

该奖项支持普渡大学的Wojciech Szpankowski博士， 与Peter Kirschenhofer博士合作进行计算机科学研究 以及代数与离散系的赫尔穆特·德辛格 维也纳技术大学数学系。 他们正在开发 算法和数据结构分析的理论方法， 从应用数学的几个领域中提取。 他们计划 运用这些方法深入分析一般情况 数字搜索算法的行为。 合作是必要的 因为他们想要解决的问题需要不同的专业知识， 数学的几个领域。 的主要职责 奥地利合作者在该项目中利用其专业知识， 渐近逼近和组合分析，而博士。 Szpankowski贡献了随机建模和一般 问题公式化 算法和数据结构的分析是一个快速发展的 理论计算机科学领域，对实际应用有很大影响 问题 算法的性能成本，包括 数据结构的存储要求和 某些子程序的执行时间通常用以下术语来描述： 最坏情况下的行为和平均情况下的行为。 数字树 搜索是数据存储和检索的主要方法之一。 数字搜索的平均案例行为研究 树将有助于改进数据结构的选择和设计 新的分析技术将在其他领域发挥作用。

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.