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 5/30 -- Michel Schellekens

Weiyun Ma wyma at
Tue May 28 22:05:33 PDT 2019

Hi all,

Michel Schellekens has kindly offered to speak at theory lunch this Thursday. He will tell us about "Modular Algorithm Analysis *by example*." (See abstract below.)

As always, please join us from noon to 1pm at 463A.


Modular Algorithm Analysis *by example*

Speaker: Michel Schellekens

Timing modularity guarantees that the running time of an algorithm is a combination of the times of its parts. The property, when it holds, drastically simplifies timing, supporting recurrence equation extraction for worst-case time, average case time and second moments. We focus on modularity of the average-case time for comparison-based algorithms that gather information by comparing data. The Modular Quantitative Analysis framework (MOQA) provides a mathematical model of computation for the modular analysis of comparison-based algorithms.

The model of computation consists of: (a) modelling data structures as partially-ordered finite sets; (b) modelling data on these by topological sorts; (c) considering computation states as finite multisets of such data; (d) analysing algorithms by their induced transformations on states. In this view, an abstract specification of a sorting algorithm has input state given by any possible permutation of a finite set of elements (represented, according to (a) and (b), by a discrete partially-ordered set together with its topological sorts given by all permutations) and output state a sorted list of elements (represented, again according to (a) and (b), by a linearly-ordered finite set with its unique topological sort).

Series-parallel (SP) orders form an important, and computationally tractable, class of data structures. These include trees and play a role in sorting, sequencing, and scheduling. We focus on the least MOQA fragment sufficient to support modular time analysis over SP-orders. The fragment is based on the “diffusion operation” which generalizes well-known data structure operations, including the heap creation operation and insertion sort’s insert operation. Both rely on repeated push-ups or push-downs that “diffuse” data (i.e. topological sorts) of a pair of data structures over a larger whole. The final data must respect the newly created order, i.e. form a new topological sort–which is guaranteed for the diffusion operation. The talk introduces the main ideas of modular algorithmic analysis by example and the recurrence equations involved.



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

More information about the theory-seminar mailing list