Heads & Tails

Corresponding entry in Aachen Campus, Bonn University (Lecture, Tutorial).

Lecture

Tutorial

Time & Place

Monday, 13⁰⁰-14³⁰ sharp, b-it bitmax
Thursday, 13⁰⁰-14³⁰ sharp, b-it bitmax
Tutorial: Monday, 14⁴⁵-16¹⁵ sharp, b-it bitmax

First meeting: Thursday, 16 April 2009.

Note that the timing information given here overrides any times and dates given on other pages (like the university calendar of the University of Bonn)!

Exam

First exam: 12 August 2009, 11⁰⁰ - 14⁰⁰, b-it bitmax.
Second exam: 15 September 2009, 11⁰⁰ - 14⁰⁰, b-it bitmax.

Excursion

On Thursday, 30 April 2009 we have the unique opportunity to visit the Eurocrypt 2009.

We will meet at 8:45h in the morning in the Martim Hotel Cologne at Heumarkt 20, 50667 Cologne. As I do not yet know the location: our meeting point is in front of the room where the first lecture takes place, leftmost rear entry. Travel information can be found on the conference's website.

Note that the first talk starts at 9:00h, so please be on time.

Allocation

4+2 SWS, 8 credits. Optionally, 3+2 SWS, 6 credits.

Successful completion of the course yields 8 credit points. For students who only want 6 credit points, a breakpoint at about 3/4 of the teaching time will be defined, and only the course material up to that point will be relevant for their exams and grades.

Media Informatics: Computer and Communication Technology.
Recommendation for University of Bonn - Computer Science: A or A1, respectively.

Prerequisites

None.

Randomness has become an important tool in the design of efficient algorithms. But what is a random bit? 0? 1? The necessary quality of randomness depends on the application: In cryptography such bits have to satisfy more requirements than when they are used for Monte-Carlo simulations in particle physics (from where their computational use originated). Cryptographic protocols require random help, and their security depends on the quality of the randomness used.

In the course we will discuss various aspects of randomness used for algorithmic purposes. Here are some examples:

Finger-printing huge databases, congestion-avoiding routing in networks
Testing integers for primality.
Sources of true randomness: Rolling dice by computer (and playing poker).
Distilling excellent randomness out of a miserable source of randomness: turning a loaded die into an (almost) fair one.
Extending a small amount of true randomness to a huge amount of pseudorandomne
ss; the latter is just as good for computational purposes.

Notes and Exercises

FINALLY there are lecture notes available (pdf). If you find any missprints etc, please tell us!

Sheet 1 (pdf),
Sheet 2 (pdf),
Sheet 3 (pdf),
Sheet 4 (pdf),
Sheet 5 (pdf),
Sheet 6 (pdf),
Sheet 7 (pdf),
Sheet 8 (pdf),
Sheet 9 (pdf),
Sheet 10 (pdf),
Sheet 11 (pdf),
Sheet 12 (pdf).

Mailinglist

You have the possibility to join a mailing list for the course by sending an email to with the subject or body 'subscribe' (do not include the quotes; body must be non-empty). Those who have registered for the course will be added automatically to the mailing list.

Literature

Randomized Algorithms, Motwani, Raghavan, Cambridge University Press, 0-521-47465-4