University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > Modular Algorithm Analysis

Modular Algorithm Analysis

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Victor Gomes.

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.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2024, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity