| Randomness is a crucial component in the design and analysis of many efficient algorithms. The 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. |
