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

Efficient Algorithms and Datastructures II (SS 05)

First lecture on April 12, 2005

• Lecturer:
  Dr. Sven Kosub

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

• Time and Location:
  Tuesday, 10:15-11:45, MI 00.04.011
  Friday, 12:15-13:45, MI 00.04.011

• Exercises:
  2 hours per week exercises accompanying the lectures
  Wednesday, 10:15-11:45, MI 00.03.009A
  Teaching Assistant: Stefan Eckhardt

• Course Certificate:
  To get a course certificate students must get at least 40% on the homework assignments and pass the final 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:
  In-depth knowledge in topic Algorithms

• Contents:
  The lectures deal in particular with the following topics:
  • Algorithms on graphs
  • Algorithms for network flows and matchings
  • Linear programming
  • Approximative algorithms
  • Heuristic algorithms

• Related and Advanced Lectures:
  Internet algorithmics

• Lecture Notes:
  Not available.

• References:
  Contents of this course are essentially covered by the following books:
  1. Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
     Introduction to Algorithms.
     2nd edition, The MIT Press, Cambridge, MA, 2001.

  2. Michael T. Goodrich, Roberto Tamassia.
     Algorithm Design: Foundations, Analysis, and Internet Examples.
     John Wiley & Sons, Inc., 2002.

  3. Christos H. Papadimitriou, Kenneth Steiglitz.
     Combinatorial optimization: Algorithms and complexity.
     Prentice-Hall, Englewood Cliffs, NJ, 1982.

  4. Uwe Schöning.
     Algorithmik.
     Spektrum Akademischer Verlag, Heidelberg, 2001.

  5. Steven S. Skiena.
     The Algorithm Design Manual.
     Springer-Verlag, New York, 1998.

  6. Robert E. Tarjan.
     Data Structures and Network Algorithms.
     CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, PA, 1983.

• Office Hours:
  look here