Dynamic programming is one of the older general algorithmic techniques that has been used widely in such diverse fields as molecular biology, control theory, economics and operations research, as well as in many areas in computer science, such as computational geometry, string editing and VLSI layouts. Until recently, most applications were tackled with the general dynamic programming technique. Recent years have witnessed a renewed interest in dynamic programming as researchers have begun to uncover that many of these applications satisfy additional conditions which can be exploited to yield significant improvements in both the sequential and the parallel complexity of some problems. This project examines methods for speeding up the dynamic programming technique. The PI will work to significantly improve the sequential and parallel solutions for classes of dynamic programming problems, and seek to find ways to identify and exploit extra constraints often found in many problems in a class. There will also be work on finding efficient solutions to some specific problems that fit into the dynamic programming framework. These problems are important in their own right, and furthermore, their solution should lead to useful insights in how to handle the more general cases.
