A case for OO -- Java -- in teaching algorithm analysis
Sergio Rajsbaum, Elisa Viso · Principles and Practice of Programming in Java · 2003
This paper presents an approach to algorithm analysis that benefits from and exploits the OO characteristics of Java and the organization Java gives to build the inheritance trees of the classes and, finally, the use of interfaces, collections, and iterators. After defining the inheritance structure of a collection of algorithms -- for instance, graph exploration algorithms - and the different levels of abstraction, we design both the verification and measures of complexity for the abstract algorithms. We prove as many properties as possible at the abstract levels assuming the implementations of the methods called upon will be correct. We also derive a complexity measure in terms of the complexity measures of the abstract methods. When a concrete algorithm is derived, we reuse the proofs we already have, plus the measures, and simply complete them by proving that the properties assumed for the concrete methods indeed hold and obtaining the exact complexity for the method. We call this inheritance tree a generic algorithm.