Formal algorithm design approaches for dynamic programming and greedy algorithms
Leila Mofarah-Fathi · Memorial University Research Repository (Memorial University) · 2010
In this thesis we present a formal study of greedy algorithms and dynamic programming in a predicative framework. A simple approach is presented based on specialization of an abstract algorithm representing an algorithm design approach. This provides not only reuse of the algorithm, but also reuse of its proof. Moreover, the simplicity and applicability of the design techniques are not sacrificed. For each method, a problem is parameterized to create a specification, which is then transformed to a concrete algorithm following the proposed process.