Compositional Average-Case Timing.

We focus in this talk on a very basic question: how can one derive the average-case time of the sequential composition of two programs from the average-case time of these programs? The answer to this question is crucial to enable static average-case timing. Yet it is not answered in current textbooks. The problem with resolving this question is that it requires the tracking of the distributions of the data. This is currently not feasible. We show how distribution tracking can be achieved based on a redesign of standard data structuring operations. We outline the theory of Random Bags which formalizes the distributions of the data states. Random Bag Preservation of the operations guarantees the capacity to track the distributions throughout the computations. This approach has enabled the specification of the novel programming language MOQA (MOdular Quantitative Analysis), implemented in Java 5.0, and its associated timing tool DISTRI-TRACK. MOQA, essentially a suite of data structure operations for modular design, is guaranteed to be compositional w.r.t. the average-case time measure. This is not the case for general purpose programming languages and in particular for current languages geared towards automated average-case analysis. The approach links several, thus far largely separate, areas together, including Semantics, Complexity, Analysis of Algorithms and Real-Time Language design. The corresponding unified foundation for algorithmic analysis has led to the solution of bottle-neck problems in automated average-case timing (open problems on dynamic algorithms such as heapsort and deletions and insertions in binary search trees) and has given rise to novel algorithms. In this talk we focus on the analysis of the exact average-case time of heapsort as an application of the new approach. The talk focuses on the intuitions underlying the approach and should be accessible to anyone with a standard undergraduate background in the Analysis of Algorithms. The talk touches on some core issues which will be discussed in the book ``A Modular Calculus for the Average Cost of Data Structuring'', to appear with Springer.