BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Modular Algorithm Analysis - Michel Schellekens\, University Colle
 ge Cork
DTSTART:20180223T140000Z
DTEND:20180223T150000Z
UID:TALK95341@talks.cam.ac.uk
CONTACT:Victor Gomes
DESCRIPTION:In Vol III of The Art of Computer Programming\, Sorting and Se
 arching\, 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 obtai
 n. Basic examples include Quicksort and Heapsort\, the first of which allo
 ws for exact time analysis\, the latter of which does not.\n\nAlgorithms t
 end to be studied on an individual basis. We take a more language-oriented
  view and discuss timing-modularity for sequential\n algorithm execution. 
 The property of random bag preservation\, related to Vaughan Pratt's pomse
 ts\, separates algorithms whose exact time is derivable in a compositional
  way from those whose time-derivation remains hard or impossible. We illus
 trate the redesign of an algorithm from the latter class to a variant belo
 nging to the former and sketch MOQA'a suite of random bag preserving opera
 tions and higher level constructs. MOQA supports modular quantitative anal
 ysis\, including (semi-)automated derivation of worst-case time\, average-
 case time and second moments. MOQA-programs\, with some additional book ke
 eping\, are fully reversible. \n\nWe conclude with an overview of ongoing 
 and future work in this area.
LOCATION:FW26
END:VEVENT
END:VCALENDAR