Modular Algorithm Analysis

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

• Michel Schellekens, University College Cork
• Friday 23 February 2018, 14:00-15:00
• FW26.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.