Mofarah-Fathi, Leila (2010) Formal algorithm design approaches for dynamic programming and greedy algorithms. Masters thesis, Memorial University of Newfoundland.
- 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.
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.
|Item Type:||Thesis (Masters)|
|Additional Information:||Includes bibliographical references (leaves 101-105).|
|Department(s):||Engineering and Applied Science, Faculty of|
|Library of Congress Subject Heading:||Algorithms--Methodology; Dynamic programming; Mathematical optimization|
Actions (login required)