Object-oriented algorithm analysis and design with Java

Abstract

This paper presents a new approach to algorithm design and analysis that benefits from the OO characteristics of Java. It consists of first defining the inheritance structure of a collection of algorithms, at different levels of abstraction. Then, correctness proofs and complexity measures are designed for the various levels of abstraction. The goal is to prove as many properties as possible at each abstract level, assuming the implementations of the methods called upon will be correct. Thus, when a more specialized algorithm is derived from a more abstract one, proofs and complexity analysis can be reused, and simply need to be completed by proving that the properties assumed for the concrete methods indeed hold. The approach is illustrated with several inheritance trees: for sorting, graph algorithms, string matching, and network flow. Each tree, at the bottom of the hierarchy, yields well-known algorithms in the respective area. Instead of using pseudo-code to describe these trees, Java is used to make the process more precise and useful, encouraging the design and analysis of algorithms, and also experimentation with new variants. The implementation presented in this paper takes advantage of Java's organization to build the inheritance trees for the classes, and Java's interfaces, collections, comparators, and iterators. (C) 2004 Elsevier B.V. All rights reserved.