Thesis (Server


Doctoral dissertation | @PhdThesis{FriedrichPhD2007, ... | Doktorarbeit

Friedrich, Tobias

Use and Avoidance of Randomness

Universität des Saarlandes, December, 2007

Randomness is a crucial component in the design and analysis of many efficient algorithms.
This thesis covers three aspects of randomness in computer science.
In the first chapter we examine a deterministic analogue
to the random walk and prove that it resembles the random walk closely
on a two-dimensional grid, but not on regular trees. We also propose and analyse
a quasirandom analogue to the broadcasting model for disseminating information in networks
and show that it achieves similar or better broadcasting times with a greatly reduced use of random bits.

In the second chapter we present the first average-case analysis of three different
algorithms for maintaining a topological ordering of
the nodes of a directed acyclic graph under dynamic updates.
We prove an expected runtime
which is significantly less than the best known
worst-case bound for this problem.

We finish with a third chapter that deals with randomized search heuristics.
We examine the impact of different diversity mechanisms on the runtime of a
single-objective evolutionary algorithm. We also show how this can
exponentially slow down evolutionary algorithms for
multi-objective problems.

Download File(s):
Raimund Seidel
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:
AUTHOR = {Friedrich, Tobias},
TITLE = {Use and Avoidance of Randomness},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {2007},
TYPE = {Doctoral dissertation}
MONTH = {December},

Entry last modified by Tobias Friedrich, 02/28/2008
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Tobias Friedrich
01/15/2008 05:29:20 PM

Tobias Friedrich

Edit Date
01/15/2008 05:29:20 PM