Work will be done on a number of fundamental problems in several areas of algorithm design and analysis. Work in three areas is planned. First, pattern matching and in particular, one-dimensional string matching. A major goal is to obtain tight bounds on the performance of string matching algorithms (measured in comparisons). Second, amortization and the performance of splay trees. This effort will be directed towards making further progress on conjectures relating to splay trees, conjectures such as the Split Conjecture, the Traversal Conjecture and the Optimality Conjecture. Third, parallel algorithms. The goal is to obtain work-optimal algorithms which run as fast as possible. Future work on two problems, graph connectivity and Voronoi Diagrams is described.
