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

Randomized Algorithms (WS 06/07)

• Lecturer:
  Prof. Dr. Christian Scheideler

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

• Time and Place:
  Mon 12:30 - 14:00, lecture hall MI HS 2
  Fri 12:00 - 13:30, lecture hall MI HS 1

• Exercises:
  2 hours per week exercises accompanying the lectures
  Tue 12:15 - 13:45, lecture hall 00.13.009A
  Teaching Assistant: Johannes Nowak
  Course Certificate: To get a course certificate students must pass the final exam.

• Exam:
  

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

• Related and Advanced Lectures:
  Efficient Algorithms and Datastructures I

• Lecture Notes: The lecture will be based on two scripts (in German):
  • Randomized Algorithms by Christian Sohler (Universität Paderborn)
  • Randomized Algorithms by Thomas Hofmeister (Universität Dortmund)

• References:
  

  R. Motwani, P. Raghavan:

  Randomized Algorithms
  Cambridge University Press, 1995

• Office Hours:
  look here