Computer Science Department - Technische Universität München Chair for Efficient Algorithms

Randomized Algorithms (WS 02/03)

• Lecturer:
  Prof. Dr. Angelika Steger,
  Stefanie Gerke, Ph.D.

• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  core course, topic algorithms

• Time and Place:
  Mon 15h c.t. - 16:45, lecture hall MW 1250
  Thu 10h c.t. - 11:45, lecture hall MW 0250
  First lecture: Thu 17.10.02

• Exercises:
  2 hours per week exercises accompanying the lectures
  Di 16h c.t. - 17:45, lecture hall MI 00.07.014
  Teaching Assistant: Alexander Offtermatt-Souza
  Course Certificate: To get a course certificate students must get at least 40% on the homework assignments and pass the final exam.

• News:
  Due to the strike of Munich's public transportation company MVV the homework may also be handed in on Tuesday December 17, 2002 during the exercises or on Thursday December 19, 2002 in class. Attention! There had been an error in assignment 10 exercise 3. Get the new version!
  Attention! There had been an error in assignment 11 exercise 2. Get the new version!
  The results of the exam are in the display cabinet 03.09. The date for insight in the exam will be announced soon.

• Exam:
  The Exam will take place on Thursday, 6.2.2003 10:15-13:15h in lecture hall MW 0250.
  Please bring an ID a student ID with you.
  Everything which consists of paper may be used during the exam (books, notes etc).
  You will have 180 minutes.
  Immatrikulation numbers of admitted students: see the exercises page.

• Audience:
  graduate students of computer science
  students with computer science as minor

• Prerequisites:
  1st and 2nd year courses
  Course Efficient Algorithms and Datastructures I advantagious, but not necessary.

• Recommended for:
  Fundamental knowledge in topic Algorithms

• Contents:
  During the last years efficient algorithms have been discovered for various problems which outperfom deterministic algorithms with respect to system and/or time resources. Often randomized algorithms are also much easier to implement and analyze than their deterministic counterparts.
  In this lecture we will present basic principles for the design of randomized algorithms. The course is based in the book Randomized Algorithms by Motwani and Raghavan.

• Related and Advanced Lectures:
  Efficient Algorithms and Datastructures I

• Lecture Notes:
  The lecture notes of Max Pühler and Benjamin Helfmann are available here. But these are not "nonofficial".

• References:
  

  R. Motwani, P. Raghavan:

  Randomized Algorithms
  Cambridge University Press, 1995

• Office Hours:
  look here