## A Modular Calculus for the Average Cost of Data StructuringA Modular Calculus for the Average Cost of Data Structuring introduces MOQA, a new domain-specific programming language which guarantees the average-case time analysis of its programs to be modular.Time in this context refers to a broad notion of cost, which can be used to estimate the actual running time, but also other quantitative information such as power consumption, while modularity means that the average time of a program can be easily computed from the times of its constituents--something that no programming language of this scope has been able to guarantee so far. MOQA principles can be incorporated in any standard programming language. MOQA supports tracking of data and their distributions throughout computations, based on the notion of random bag preservation. This allows a unified approach to average-case time analysis, and resolves fundamental bottleneck problems in the area. The main techniques are illustrated in an accompanying Flash tutorial, where the visual nature of this method can provide new teaching ideas for algorithms courses. This volume, with forewords by Greg Bollella and Dana Scott, presents novel programs based on the new advances in this area, including the first randomness-preserving version of Heapsort. Programs are provided, along with derivations of their average-case time, to illustrate the radically different approach to average-case timing. The automated static timing tool applies the Modular Calculus to extract the average-case running time of programs directly from their MOQA code. A Modular Calculus for the Average Cost of Data Structuring is designed for a professional audience composed of researchers and practitioners in industry, with an interest in algorithmic analysis and also static timing and power analysis--areas of growing importance. It is also suitable as an advanced-level text or reference book for students in computer science, electrical engineering and mathematics. Michel Schellekens obtained his PhD from Carnegie Mellon University, following which he worked as a Marie Curie Fellow at Imperial College London. Currently he is an Associate Professor at the Department of Computer Science in University College Cork - National University of Ireland, Cork, where he leads the Centre for Efficiency-Oriented Languages (CEOL) as a Science Foundation Ireland Principal Investigator. |

### What people are saying - Write a review

### Contents

Introduction | 1 |

11 Static AverageCase Analysis | 2 |

113 The Main Bottleneck for Static AverageCase Analysis | 3 |

12 Removing the Bottleneck for Static AverageCase Analysis | 4 |

123 The Meaning of Static Timing in our Context | 5 |

13 The MOQA Language 131 General Description | 6 |

14 Tracking Distributions | 12 |

142 SDistributions | 13 |

AverageCase Time of Basic MOQA Operations Joint with D Early | 132 |

62 AverageCase Time | 134 |

622 PushUp and PushDown | 135 |

63 SeriesParallel Partial Orders | 137 |

632 SeriesParallel Composition Laws for Delete | 141 |

641 Calculating the τ Function | 144 |

642 Inductively Deﬁned Structures | 145 |

643 Combinatorial Identities | 147 |

15 Random Bag Preservation | 14 |

16 The Necessity of Guaranteeing Random Bag Preservation | 17 |

17 A Sufficient Condition for Random Bag Preservation | 20 |

an Illustration of Random Bag Preservation | 21 |

the General Case | 26 |

182 Conditionals Loops Recursion | 28 |

191 AverageCase Time is IOCompositional | 29 |

110 Related work and advantages of MOQA | 30 |

111 Related Areas | 32 |

1111 Bridging Semantics and Complexity | 33 |

1112 Implications for RealTime Languages | 36 |

Introductory Notions | 39 |

21 Partial Orders Hasse Diagrams | 40 |

22 SeriesParallel Orders | 41 |

23 Trees Heaps | 43 |

24 Basic Sorting Algorithms | 44 |

25 Uniform Distribution and Bags | 47 |

26 Timing Measures | 49 |

Compositionality | 51 |

32 IOCompositionality | 52 |

33 Strict Semi IOCompositionality for WorstCase and BestCase Time | 54 |

34 AverageCase Time is IOCompositional | 56 |

35 From IOCompositionality to LinearCompositionality | 57 |

Random Bag Preservation and Isolated Subsets 41 Random Structures | 65 |

42 Floor and Ceiling Functions | 70 |

43 Free Sets of Labels | 71 |

44 Free Swaps on Random Structures | 73 |

45 Random Bag Preserving Functions | 74 |

46 Isolated Subsets | 79 |

461 Strictly Isolated Subsets | 82 |

462 Simplified Deﬁnitions for SPOrders | 90 |

Basic MOQA Operations | 95 |

51 The Fundamental Data Structuring Problem | 96 |

521 The Product of two Finite Partial Orders | 97 |

522 The Product of Two DataLabelings | 98 |

523 The Binary Random Product | 106 |

53 Random Deletion and Percolation | 108 |

532 Percolation and Deletion of Arbitrary Labels | 110 |

54 The Random Projection | 118 |

55 The Random Split | 120 |

552 Random Split of a Random Structure | 121 |

56 Top and Bot Operations | 125 |

57 Contractive Operations Revisited | 127 |

59 MOQAConstructible Random Bags | 128 |

510 MOQAConstructible Random Bags are SeriesParallel | 129 |

512 Partitions and separative functions | 130 |

The MOQA Language | 149 |

71 Conventions | 150 |

72 Variables | 151 |

74 Arithmetical Expressions | 153 |

75 Boolean Expressions | 154 |

76 Boolean Statements | 157 |

762 Computing Probabilities of Boolean Statements | 159 |

763 Reduction to Prime DNFs | 160 |

764 Probabilities for Prime Conjunctions | 161 |

77 Random Structure Expressions | 164 |

78 Random Conditional Statements | 165 |

79 Recursion | 167 |

710 MOQA Programs | 171 |

711 Randomness Preservation | 172 |

712 Compositional Determination of AverageCase Time | 173 |

713 LinearCompositionality for MOQA Programs | 174 |

Examples of MOQA Programs | 179 |

83 Mergesort | 180 |

85 Percolating Heapsort | 182 |

852 PseudoCode for Percolating Heapsort | 184 |

86 Treapgen | 185 |

862 Treaps in MOQA | 186 |

863 TreapGeneration | 189 |

87 Treapsort | 190 |

AverageCase Analysis of MOQA programs | 192 |

92 Mergesort | 195 |

94 Percolating Heapsort | 197 |

95 Treapgen | 200 |

96 Treapsort | 201 |

97 Quickselect | 206 |

Joint with D Hickey and M Boubekeur | 209 |

102 DistriTrack Architecture | 211 |

1022 The Analyser | 213 |

103 Random Bag Trackers | 215 |

1032 Collective Representations | 216 |

104 Calculating the ACET | 218 |

105 Preliminary Evaluation Study | 219 |

1052 Evaluation Study Description | 220 |

Conclusion and Future Work | 224 |

Appendix Proof of the State Theorem | 229 |

A2 Canonical State | 230 |

A3 Canonical State Algorithm | 234 |

237 | |

242 | |

### Other editions - View all

A Modular Calculus for the Average Cost of Data Structuring Michel Schellekens No preview available - 2014 |

A Modular Calculus for the Average Cost of Data Structuring Michel Schellekens No preview available - 2008 |