Bonn-Aachen International Center
for Information Technology





city life
cosec >students >Teaching >Summer 2009  

Heads & Tails

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


Prof. Joachim von zur Gathen


Daniel Loebenberger

Time & Place

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)!


First exam: 12 August 2009, 1100 - 1400, b-it bitmax.
Second exam: 15 September 2009, 1100 - 1400, b-it bitmax.


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.


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.




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:

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).


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.


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

Imprint, webmaster & more