A Modular Calculus for the Average Cost of Data Structuring

Front Cover
Springer Science & Business Media, Jun 17, 2008 - Computers - 245 pages
0 Reviews

A 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

We haven't found any reviews in the usual places.

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 Defined 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 Definitions 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
References
237
Index
242
Copyright

Other editions - View all

Common terms and phrases

Popular passages

Page xiii - A progress in our understanding of these questions should drastically affect the way in which we discover and explain the fundamental algorithms, as catalogued by Knuth [Knu731 and Ahoetal[AHU87].
Page xiii - The aim of this work is to present a new approach to the Average-Case Analysis of Algorithms, based on the novel notion of random bags and their preservation.

Bibliographic information