Synthesis of Fast Programs for Maximum Segment Sum Problems
Source: University of Texas
It is well-known that a naive algorithm can often be turned into an efficient program by applying appropriate semantic spreserving transformations. This technique has been used to derive programs to solve a variety of maximum-sum programs. One problem with this approach is that each problem variation requires a new set of transformations to be derived. An alternative approach to synthesis combines problem specifications with flexible algorithm theories to derive efficient algorithms. The authors show how this approach can be implemented in Haskell and applied to solve constraint satisfaction problems.