NOTE: This webpage contains old information. Contact Rossitza Dodunekova (director of undergraduate studies in mathematical statistics) to find out about next year's course.

RANDOMIZED ALGORITHMS (randomiserade algoritmer)

period IV (March-May), 2002

Click here to download this year's home exam! (in ps-format)

Course code: TMS080 (at Chalmers) and MSN42 (at GU).

The course gives 5.0 credit units (at Chalmers or at GU).

Instructor: Olle Häggström, email

Email list: I maintain an email list for information pertaining to the course. Anyone interested in taking this course should contact me by email, and I will then put you on the email list.

The course will be given as a supervised self-study course this year; see below for more information on this.

Course content: That randomization (the use of random numbers in computer algorithms) in many situations leads to better and faster algorithms, is a fundamental but fairly recent insight. The purpose of the course is to communicate this insight, and to provide familiarity with randomized algorithms and their mathematical foundations. Topics covered are
  • Mathematical foundations, including probabilistic methods and Markov chains.

  • Randomized algorithms for, e.g., sorting, Monte Carlo integration, stochastic simulation, approximate counting, and various combinatorial and/or geometrical optimization problems.

  • Analysis of the complexity of randomized algorithms.
A large part of the course consists of a project, where the students have the opportunity to apply the above to some concrete application, or to deepen their theoretical knowledge in some specific direction (or both!).

There are NO LECTURES in this year's course. Instead, students are expected to read the course material (see below) on their own. A few times during the course, I will arrange meetings with the whole group of students where we can discuss the contents of the course. The first such meeting will be on Friday, March 22 at 13:15-15:00 in room MD 7, Matematiskt Centrum.

It will also be possible to set up individual meetings with me, and I expect that a lot of issues will be possible to resolve by email. In fact, email will be the only reliable way to get in touch with me, because I will be away (in Stockholm) during most of the course. When I am in Göteborg (mostly on Mondays and Fridays), my office phone number is 031-772 5311.

I believe that to take the course in this way requires somewhat more self-discipline compared to a traditional course. But if you can handle that aspect, then I think it will not be more difficult than an ordinary course.


Examination consists of two parts:

Project: A main part of the course is to do a project, either individually or in groups of 2-3 students. Projects can be chosen from a list of project proposals, but suggestions for other projects are also welcome. Each student is required to have selected a project (after consulting me) no later than Wednesday, April 10. Oral presentations of projects takes place on Tuesday, May 21, at time 10:00-11:45 in room S4, and at time 13:15-17:00 (on the same day) in room MD9, Matematiskt Centrum.

Home exam: On Wednesday, May 22, I will post a home exam on this webpage. Deadline for handing it in will be on Thursday, May 30.

I cannot, of course, strictly forbid you to speak to each other during the home exam. But I do require that each student thinks through and solves each problem on his/her own. It is OK if one or two little hints for solutions pass from one student to the other, but it is NOT acceptable to copy directly another student's solutions. Everyone should be prepared to defend his or her solutions, and I reserve the right to carry out an oral examination in cases of doubt (hopefully this will not happen!).

The home exam consists of five problems, one of which may (or may not) involve a programming exercise. Each of the five problems gives four points, in total 20 points. To pass the exam, 10 points are required. (In very special cases, an exceptionally well done project may compensate for a result slightly below the official threshold.)

Here is this year's home exam (in postscript).

Here is last year's home exam (in postscript).

Grades (3, 4 or 5 for Chalmers students, and G or VG for GU students) are based both on the score on the home exam and on the quality of the project and project presentation.

Prerequisites: Necessary prerequisites for the course, are to have taken (and passed!)

Last modified: Tue Aug 27 17:15:31 MET DST 2002