Topics in Algorithm Design

算法设计主题

• 批准号: 9821058
• 负责人: S. Rao Kosaraju
• 金额: $ 25.22万
• 依托单位: Johns Hopkins University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1999
• 资助国家: 美国
• 起止时间: 1999-09-01 至 2003-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9821058&HistoricalAwards=false
• 关键词: Topics; Algorithm; Design

This project investigates several algorithm design issues in the areas of Universal Graphs, Data Compression, Generalized Huffman trees, and Data Structures. The PI and his student have designed a new tree paradigm for the construction of small universal graphs for many classes of graphs. The technique permits a multistage decomposition of a graph while constraining the adjacency properties between blocks of the decomposition. The project refines and explores other applications of this technique. Within the area of data compression, an analysis of the worst case performance of several exciting new data compression schemes will be undertaken. In addition, design of fast algorithms for these schemes is challenging and worthwhile. Closely associated with data compression is the classic Huffman Coding problem. The project investigates the design of efficient algorithms for some natural generalizations of this coding problem. During the last two decades, the PI has developed several attractive procedures for transforming data structure-based algorithms which have good amortized speed into ones that have matching worst-case speed characteristics. These techniques are broadened to handle generalized dictionaries and other data structure problems.

本计画探讨通用图、资料压缩、广义霍夫曼树及资料结构等领域的演算法设计问题。 PI和他的学生设计了一个新的树范式，用于为许多类图构建小的通用图。 该技术允许一个多阶段的分解图，同时限制块之间的邻接属性的分解。 该项目改进并探索了这项技术的其他应用。 在数据压缩领域，将对几种令人兴奋的新数据压缩方案的最坏情况性能进行分析。 此外，这些方案的快速算法的设计是具有挑战性的和值得的。 与数据压缩密切相关的是经典的霍夫曼编码问题。 该项目研究设计有效的算法，一些自然的概括这个编码问题。 在过去的二十年中，PI已经开发了几个有吸引力的程序，用于将具有良好的摊销速度的基于数据结构的算法转换为具有匹配的最坏情况下的速度特性的算法。这些技术被扩展到处理广义字典和其他数据结构问题。