Abstract

In Vol III of The Art of Computer Programming, Sorting and Searching, algorithms are discussed whose code is simple but whose analysis is not. Algorithms fall into two classes: those whose exact average-case time can be determined and those whose exact time is unknown/hard to obtain. Basic examples include Quicksort and Heapsort, the first of which allows for exact time analysis, the latter of which does not.

Algorithms tend to be studied on an individual basis. We take a more language-oriented view and discuss timing-modularity for sequential algorithm execution. The property of random bag preservation, related to Vaughan Pratt’s pomsets, separates algorithms whose exact time is derivable in a compositional way from those whose time-derivation remains hard or impossible. We illustrate the redesign of an algorithm from the latter class to a variant belonging to the former and sketch MOQA ’a suite of random bag preserving operations and higher level constructs. MOQA supports modular quantitative analysis, including (semi-)automated derivation of worst-case time, average-case time and second moments. MOQA -programs, with some additional book keeping, are fully reversible.

We conclude with an overview of ongoing and future work in this area.