Back

# Randomized Algorithms

**
Wolfgang Merkle
**

Section: Computation

Level: Introductory

## Description

Given a graph, is there are a subset S of its vertices such that
at least half of the edges connect a vertex in S and a vertex not in
S? A simple argument from elementary probability theory shows that if
we flip a fair coin for each vertex in order to decide whether the
vertex should be in S or not, then with non-zero probability we obtain
a set S as desired (and thus, in particular, there is such a set
S). This way of tackling a problem is known as the probabilistic
method, a method that often yields surprisingly elegant and elementary
arguments even if explicit constructions apparently need to be rather
involved. Furthermore, as in the example above, the probabilistic
method frequently leads to randomized algorithms that are
comparatively simple and easy to verify.

The first part of the course gives an introduction to randomized
algorithms and to standard techniques for their derandomization. The
material will be presented by means of simple examples from graph
theory.

The second part of the course presents applications of the
probabilistic method to the construction of logical models and briefly
discusses related issues such as Rado-graphs and 0-1 laws.

## Prerequisites

The course requires only a rudimentary understanding of a few basic
concepts from probability theory such as expectation and independence
of random variables. These concepts will be shortly reviewed at the
beginning of the course. The second part on logic requires in addition
some basic understanding of first-order logic.

## Materials

lecture notes

## Lecturers

Dr. Wolfgang Merkle

Universität Heidelberg

Mathematisches Institut

Im Neuenheimer Feld 294

D-69120 Heidelberg

Tel. +49-6221-54 5409

Fax. +49-6221-54 4465

merkle@math.uni-heidelberg.de

http://math.uni-heidelberg.de/logic/merkle/merkle.html