The course gives 5.0 credit units (at Chalmers or at GU).
Instructor: Olle Häggström, email olleh@math.chalmers.se
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
|
|
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.
Literature:
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!)