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.
