Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] [theory-lunch] Theory lunch 08/24 -- Michel Schellekens

Hongyang Zhang hongyang90 at
Mon Aug 21 19:35:52 PDT 2017

Hi Everyone

Prof. Michel Schellekens, who is visiting Don from Ireland, will tell us
about this work (see abstract below). He will also bring some Belgian
crepes -- if you missed them in early July, come and have a try! After this
week, we will take a break and start again around fall qtr.

If you are interested in coming, let me know so we get an estimate of how
much food to order -- everyone is welcome.


*Modular Algorithm Analysis *

In Vol III of TAOCP, 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 briefly 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 present an overview of research carried out during the first part of our
Stanford stay and plans for the second part (Apr-Aug, 2018).


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list