Programming Research Group Technical Monograph PRG-122

Sharon Curtis

April 1996, 137 pages

The main contribution of this thesis is a study of the dynamic programming and greedy strategies for solving combinatorial optimization problems. The study is carried out in the context of a calculus of relations, and generalises previous work by using a loop operator in the imperative programming style for feasible solutions, rather than the fold and unfold operators of the functional programming style. The relationship between fold operators and loop operators is explored, and it is shown how to convert from the former to the latter.

This fresh approach provides additional insights into the relationship between dynamic programming and greedy algorithms, and helps to unify previously distinct approaches to solving combinatorial optimization problems. Some of the solutions discovered are new and solve problems which had previously proved difficult. The material is illustrated with a selection of problems and solutions that is a mixture of old and new.

Another contribution is the invention of a new calculus, called the graph calculus, which is a useful tool for reasoning in the relational calculus and other non-relational calculi. The graph calculus represents formulae by formal pictures, and this enables proofs to be expressed more simply. It is also more powerful than standard point-free reasoning, and its simple intuitive basis aids greater understanding of the structure of formulae and certain proofs.