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.

[img] [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.

Item Type: Thesis (Masters)
URI: http://research.library.mun.ca/id/eprint/9709
Item ID: 9709
Additional Information: Includes bibliographical references (leaves 101-105).
Department(s): Engineering and Applied Science, Faculty of
Date: 2010
Date Type: Submission
Library of Congress Subject Heading: Algorithms--Methodology; Dynamic programming; Mathematical optimization

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics