[FOM] Springer Book: Modular Averager-Case Time Analysis

[Michel Schellekens]

The following recently published book may be of interest to FOM
subscribers.

A Modular Calculus for the Average Cost of Data Structuring
http://www.springer.com/computer/foundations/book/978-0-387-73383-8

The book introduces a new mathematical theory of random bag preservation
which provides a  unified foundation for algorithmic analysis, as an
alternative to the collection of ad hoc methods available in this area.
Mathematicians with an interest in finite partial orders, linear
extensions and random structures or foundations of Computer Science in
general, may find this work of interest.

Best wishes,
Michel Schellekens

A Modular Calculus for the Average Cost of Data Structuring

Schellekens, Michel
2008, XXIV, 246 p. 20 illus. With CD-ROM., Hardcover
ISBN: 978-0-387-73383-8


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.

Written for:

Researchers and students interested in algorithm analysis, static
analysis, real-time programming, programming language semantics

Keywords:

    * random structures
    * real-time languages
    * series-parallel data structures
    * software timing/power analysis
    * sorting and search algorithms
    * static analysis




-- 

Prof. M. P. Schellekens                 

Science Foundation Ireland Investigator
Director of Centre for Efficiency-Oriented Languages (CEOL)

National University of Ireland, Cork (UCC)
Department of Computer Science
Center for Efficiency-Oriented Languages (CEOL)
Lancaster Hall
Little Hanover Street 6
Cork, Ireland
WWW: http://www.ceol.ucc.ie/
Tel. + 353 (0)21 490 1917