Formal algorithm design approaches for dynamic programming and greedy algorithms

Mofarah-Fathi, Leila (2010) Formal algorithm design approaches for dynamic programming and greedy algorithms. Masters thesis, Memorial University of Newfoundland.

[English] PDF - Accepted Version Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission. Download (5MB)

Abstract

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.

Actions (login required)

View Item