May 26, 2018
Language for specifying dynamic programming algorithms
Dynamic programming is a simple yet powerful technique for solving optimisation problems. When the problem at hand can be split in smaller problems, such that the smaller solutions of an optimal solution are themselves optimal, dynamic programming can be used to avoid re-calculating solutions to shared sub- problems.
Simple problems are both easily specified and easily implemented, but for complex problems translating the specification of the problem into the implementation of the dynamic programming algorithm becomes tedious and error prone. The goal of DPROG is to alleviate this by automatically translating the specification of the problem into an implementation of the solution.
The DPROG language is designed to be close to the ``mathematical’’ notation used for expressing recurrences, thus making it easier to specify the problem. Using the DPROG compiler, the manual implementation step can be completely avoided.