Dynamic programming is a very general, powerful, and robust problem solving paradigm in artificial intelligence and computer science. Dynamic programming is an algorithm schema that includes a number of well-known systematic search algorithms in Artifical Intelligence, including breadth-first search, Dijkstra''s algorithm, A*, value iteration and policy iteration for Markov decision processes, as well as many polynomial-time algorithms for combinatorial problems, and pseudo-polynomial-time algorithms for numeric NP-complete problems. These algorithms are extremely robust, in that they are guaranteed to find a solution to a problem if one exists, and often an optimal solution.
Most dynamic programming algorithms are limited in the size of problems they can solve by the amount of storage available. While semiconductor memory costs about $100 per gigabyte, magnetic disk storage costs less than 40 cents per gigabyte, and single disks with one terabyte of storage are now available. In practice, the available storage on a modern workstation can be increased by three orders of magnitude with multiple disks, at moderate cost. Unfortunately, you can''t simply replace memory with disk storage in a dynamic programming algorithm. The reason is that it takes about ten milliseconds to access a single byte on disk, compared to about 100 nanoseconds for main memory. However, large blocks of data on disk can be read or written sequentially at high speed. This work will develop, implement, and experiment with dynamic programming algorithms that store their data on magnetic disk. The main research challenge is to design these algorithms so that all data access is sequential. By shifting the resource bottleneck from space to time, parallelizing these algorithms to run on multiple processors or multiple cores becomes an additional research challenge. The PI has had some success with this paradigm, implementing large-scale breadth-first and heuristic searches that run for months at a time. The techniques will be broadened to cover other classes of dynamic programming algorithms. The proposed challenge problems include numeric NP-complete problems, finding the radius and diameter of various problem spaces, and amino acid and DNA sequence alignment in computational biology. If successful, in addition to engaging students at UCLA, the work can have impact throughout computer science. The idea of extending memory with disk storage is potentially applicable to any memory-intensive algorithm and can be used to speed up computations that reside entirely in memory by improving cache performance.
