Wolfgang Merkle gives a course on Randomized Algorithms
Over the next two weeks the School of Computer Science will offer students the opportunity to take a short course on randomized algorithms. The course will be given by a visitor from Heidelberg, Wolfgang Merkle, who is both a strong scientist and a lively lecturer.
The course is offered for both masters students and advanced undergraduate students. It will be held from Thursday September 4 to Friday September 12, including Saturday September 6, for a total of 16 lectures.
The exact schedule will be decided in consultation with the participants. The course gives two credits (ECTS).
An introductory presentation will given on Monday September 1, 12:30-13.00, in room K-5.
Course description:
In contrast to a usual deterministic algorithm, for a randomized algorithm the behavior of the algorithm is not determined by its input but depends in addition on randomly chosen bits that can be accessed by the algorithm, e.g., for different choices of these random bits, the running time or even the result of the algorithm may differ.
Randomized algorithms play an important role in today's computer science. On the one hand, they are used in practice and for example are essential to all cryptographic applications. On the other hand, randomized algorithms can serve as a heuristic when trying to construct deterministic algorithms and in fact in the last two decade this way some of the most important results in algorithmics have been obtained.
The course is an introduction to the theory of randomized algorithms and exhibits selected randomized algorithms in various areas of computer science, as well as methods for the derandomization of randomized algorithms, which are discussed in a context of simple graph problems. Furthermore, some related material is covered, such as the probabilistic method in combinatorics and the application of randomization in the analysis of deterministic or other algorithms.
The course requires only some basic understanding of discrete probability spaces and some elementary facts from probability theory like linearity of expectation, these prerequisites will be briefly recalled at the beginning.
For most or all of the lectures there will be transparencies that contain essentially all the material covered.
