16th Estonian Winter School in Computer Science (EWSCS)
XVI Eesti Arvutiteaduse Talvekool

Palmse, Estonia, February 27 -March 4, 2011

Martin Hofmann

Institut für Informatik
Ludwig-Maximilians-Universität München

Amortized resource analysis


Resource analysis aims at automatically determining and upper bound on the resource usage of a program as a function of its input size. Resources in this context can be runtime, heap- and stack size, number of occurrences of certain events, etc.

The amortized approach to resource analysis works by associating "credits" with elements of data structures and to "pay" for each consumption of resource from the credits currently available. In this way composite programs and programs with intermediate data structures can be analysed more conveniently than would otherwise be the case.

Amortization was introduced by Tarjan in the 70s in the context of manual complexity analyis of algorithms. More recently, it has been used for type-based automatic resource analysis.

The course describes the key concepts with simple examples and then moves on to survey some recent papers, notably the inference of multivariate polynomial resource bounds for functional programs and a type-based resource analysis of Java-like object-oriented programs.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 7, 2011 13:27 EET by local organizers, ewscs11(at)cs.ioc.ee
EWSCS'11 page: http://cs.ioc.ee/ewscs/2011/