School Seminars and Colloquia

Stochastic analysis of algorithm (Session Three)

BELZ Lecture Series

by Prof. Ludger Rueschendorf


Institution: University of Freiburg (Germany)
Date: Mon 1st August 2005
Time: 4:15 PM
Location: Room 210, Richard Berry Building

Abstract: A brief description of the course:

There are two ways in which stochastic elements and methods enter the
field of algorithms. Firstly it has turned out that for many problems
simple solution or approximation algorithms can be constructed whereas
deterministic algorithms are either very complicated, are not known, or do
not exist. Important classes of examples are divide and conquer type
algorithms or in a different direction Markov chain Monte Carlo
algorithms. A nice survey of randomized algorithms can be found in the
book of Motwani and Raghavan (1995). A second main area of stochastic
methods is the probabilistic analysis of recursive algorithms. Here the
analysis of some concrete algorithm is done w.r.t. an underlying
stochastic model implying that the relevant parameters of the algorithm
are considered as random variables. This course will be concentrated on
this topic. Stochastic recursive equations and algorithms arise in a
great variety of problems from computer science like in algorithms of
divide and conquer type but also in the probabilistic analysis of
(combinatorial) optimization problems and in many other problems having a
recursive structure. There is a close connection to random trees like
binary search trees, random recursive trees, uniform trees, or digital
trees. In the first part of this course this connection is investigated
and some probabilistic methods from extreme value theory, branching
processes, and random walks are applied for the analysis of the relevant
random trees. In the second part of the course we introduce the
contraction method which is a recent and very successful technique for the
analysis of recursive algorithms. By this method a unifying result was
obtained which can be stated roughly in the form: Some knowledge on the
first moments of the algorithm together with the recursive structure of
the algorithm imply a full probabilistic analysis. Several examples will
be discussed based on this approach.

For More Information: Kostya Borovkov tel. 8344-7992 email: k.borovkov@ms.unimelb.edu.au