Benjamin Doerr: Teaching

Randomized Algorithms (Selected Topics) (winter 08/09)

PD Dr. Benjamin Doerr, Anna Huber, and Daniel Johannsen.

Time:	Tue & Thu, 16-19 (often shorter, negotiable, see below)
Start:	Tuesday, October 21, 2008
Room:	024 in the MPI building (E1 4)
Wiki:	Randalg2008/09 WIKI
Content:	Randomized methods can be a surprisingly powerful tool to find good algorithms, both from the theoretical viewpoint and the application one. In the course, we shall discuss several particular topics in this area, some of which are simply "good to know" and most of which got increased attention in the last few years. In other words, this is not an encyclopedic coverage of the randomized algorithms, but rather an in-depth course on selected topics.
Course concept:	We shall try a modified teaching concept. Our starting point is the observation that in the classical lecture concept, there is little interaction between teachers and students. This is already visible from regarding how the time related to a two-hours session is spent: The lecturer takes 2-4 hours preparing the lecture (at home), then presents the outcome of this to the students in a highly compressed form, and finally the students take 2-4 hours understanding (decompressing) the content (again on themselves). Hence teacher and students spend most of the time separately. In addition, the 2 hours of lecture typically are not too interactive either, simply because students often are overrun by the new content. While we do agree that learning needs quite some thinking about the content on your own, we feel that expertise of the teacher is not really used efficiently in the current concept. One way to overcome this is to omit the compression/decompression phase in classical university lecturing. Ideally, this should result in the following timing: Teacher prepares lecture (0-2 hours), interactive teaching (4 hours), student reiterate content at home (0-2 hours). Hence with identical workloads, hopefully a more efficient teaching is gained. To have some flexibility in timing, we reserve the time-slots Tuesday and Thursday 16-19 for both the lecture and the exercises, though the average time used will be shorter. Also note that, depending on the preferences of the participants, we might add extra lectures in November and December and thus finish before the Christmas break. All timing issues are negotiable in the first lecture.
Credit:	There will be exercises (both on-line and homework) included in the lecture. Taking part in these as well as contributing activly to the lecture yields admission to a final, oral examination, which determines the grade. The course counts as special lecture (2 hours) with exercises (2 hours), which earns you 6 LPs. The interactive concept of the lecture allows that some participants earn credit as a seminar (7LP). Of course, they have to lecture to an extent comparable with a classical seminar. Whether you aim for credit as special lecture or seminar, we will ensure that the workload to earn the credit is comparable to a special lecture or seminar in the classical style.
Prerequisites:	No particular prerequisites are needed. The art of this area is to use simple probabilistic methods to gain surprisingly strong results. An intuitive understanding of probability theory should suffice. However, this is a theory lecture, so some familiarity and fun with proving things is necessary.
Admission:	To facilitate discussion and interaction, we reserve the right to limit the number of participants. This will be discussed at the beginning of the first lecture. If you plan to participate, but cannot come to this lecture, contact Benjamin Doerr in advance.