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

Efficient Algorithms and Data Structures I
(WS 02/03)

• Lecturer:
  Prof. Dr. Ernst W. Mayr

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

• Time and Place:
  

  Di 8:30 - 10:00, lecture hall PH HS1
  Fr 11h c.t. - 12:45, lecture hall PH HS1

• Exercises(web page [in German]):
  2 hours per week exercises accompanying the lectures
  Mon 15h s.t. - 17:00, lecture hall PH HS1
  Teaching Assistant: Klaus Holzapfel
  

• Course Certificate:
  To get a course certificate students must
  • get at least 40% on the homework assignments and
  • pass the exams (midterm and final).

• Exams:
  Please see German Webpage for details.

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

• Prerequisites:
  1st and 2nd year courses

• Recommended for:
  Fundamental knowledge in topic Algorithms

• Contents:
  This lecture deals in particular with the following topics:
  1. Introduction
  2. Advanced Data Structures
  3. Selection and Sorting
  4. Minimum Spanning Trees
  5. Shortest Paths
  6. Graph Connectivity
  7. Matchings

• Related and Advanced Lectures:
  Efficient Algorithms and Data Structures II
  Randomized Algorithms

• Lecture Notes:
  See Lecture Notes

• References:
  

  Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman:

  The design and analysis of computer algorithms
  Addison-Wesley Publishing Company, Reading MA, 1976

  Thomas H. Cormen and Charles E. Leiserson and R.L. Rivest:

  Introduction to algorithms
  McGraw-Hill, 1990

  Donald E. Knuth:

  The art of computer programming Vol. 3 : Sorting and searching
  Addison-Wesley Publishing Company, Reading MA, 1973

  Kurt Mehlhorn:

  Data structures and algorithms 1 : Sorting and searching
  EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984

  Kurt Mehlhorn:

  Data structures and algorithms 2 : Graph algorithms and NP-Completeness
  EATCS Monographs on Theoretical Computer Science, Springer-Verlag, Berlin - Heidelberg - New York - London - Paris - Tokyo - Hong Kong, 1984

  T. Ottmann and P. Widmayer:

  Algorithmen und Datenstrukturen
  B.I. Wissenschaftsverlag, Mannheim, 1990

  Christos H. Papadimitriou, Kenneth Steiglitz:

  Combinatorial optimization : Algorithms and complexity
  Prentice-Hall, Englewood Cliffs, NJ, 1982

• Office Hours:
  look here