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

Efficient Algorithms and Data Structures I
(WS 07/08)

• Lecturer:
  Prof. Dr. Ernst W. Mayr

• Module: IN2003

• Area:
  4+2 lectures per week in area III (Theoretical Computer Science)
  core course, area Algorithms and Scientific Computing (AWR)

• Time and Place:
  Monday, 08:30-10:00, lecture hall 2
  Friday, 08:30-10:00, lecture hall 2

• Exercises (web page [in German]):
  2 hours per week exercises accompanying the lectures
  Teaching Assistant: Matthias Baumgart
  

• Course Certificate:
  To get a course certificate students must pass the exams (midterm and final) and achieve at least 40% of the points on the problems sets.

• Exams:
  Please see German Webpage for details.

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

• ECTS: 8 points

• 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

• Slides:
  

  October:	October 15, 2007	October 19, 2007
  	October 22, 2007	October 26, 2007
  	October 29, 2007
  November:		November 2, 2007
  	November 5, 2007	November 9, 2007
  	November 12, 2007	November 16, 2007
  	November 19, 2007	November 23, 2007
  	November 26, 2007	November 30, 2007
  December:	December 3, 2007	December 7, 2007
  	December 10, 2007	December 14, 2007
  	December 17, 2007	December 21, 2007
  January:	January 7, 2008	January 11, 2008
  	January 14, 2008	January 18, 2008
  	January 21, 2008	January 25, 2008
  	January 28, 2008
  February:		February 1, 2008
  	February 4, 2008	February 8, 2008
  Complete (pdf, 2,2MB)

• Related and Advanced Lectures:
  Efficient Algorithms and Data Structures II
  Internet Algorithmics

• Lecture Notes:
  See the WS 98/99 lecture notes.

• References:
  
  • Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
    Introduction to Algorithms.
    2nd edition, The MIT Press, Cambridge, MA, 2001.

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

  • Volker Heun.
    Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen.
    2nd edition, Vieweg, Braunschweig-Wiesbaden, 2003.

  • Donald E. Knuth.
    The Art of Computer Programming: Fundamental Algorithms.
    3rd edition, Addison-Wesley, Reading, MA, 1997.

  • Donald E. Knuth.
    The Art of Computer Programming: Sorting and Searching.
    2nd edition, Addison-Wesley, Reading, MA, 1997.

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

  • Robert Sedgewick.
    Algorithmen.
    2nd edition, Pearson Education, München, 2002.

• Office Hours:
  look here