String Matching, Amortization and Parallel Algorithms

将在算法设计和分析的几个领域中解决一些基本问题。计划在三个方面开展工作。第一，模式匹配，特别是一维字符串匹配。一个主要目标是获得字符串匹配算法性能的严格界限(通过比较来衡量)。第二，摊销和摊销树的表现。这项工作将致力于进一步发展与展开树相关的猜想，如分裂猜想、遍历猜想和最优性猜想。第三，并行算法。目标是获得运行速度尽可能快的工作最优算法。对图的连通性和Voronoi图这两个问题的未来工作进行了描述。

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.