# Stochastic analysis of algorithm (Session Three)

*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