Topics in Algorithm Design

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

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.