Efficient Algorithms and Data Structures I

  • Lecturer:
    Prof. Dr. Christian Scheideler
  • Area:
    4+2 lectures per week in area III (Theoretical Computer Science)
    core course, topic algorithms
  • Time and Place:
    Tuesday, 8:00-10:00, MI 00.13.009A
    Thursday, 08:00-10:00, MI 00.13.009A
  • Exercises (web page [in German]):
    2 hours per week exercises accompanying the lectures
    Teaching Assistant: Jonas Pfoh
  • Course Certificate:
    To get a course certificate students must 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:
    • Algorithm Analysis
    • Basic Data Structures
    • Search Trees and Skip Lists
    • Sorting, Sets, and Selection
    • Fundamental Techniques
    • Algorithms on Graphs
    • Network Flow and Matching
    • Network Algorithms
    • Text Processing
  • Related and Advanced Lectures:
    Efficient Algorithms and Data Structures II
    Internet Algorithmics
  • Lecture Notes:
    See the WS 98/99 lecture notes by Prof. Mayr. Additional chapters:
    1. Perfect Hashing (in postscript and pdf)
  • References:
    The course outline can be found in the following book:
    • Michael T. Goodrich, Roberto Tamassia.
      Algorithm Design: Foundations, Analysis, and Internet Examples.
      John Wiley & Sons, Inc., 2002.
    Complementary and additional in-depth material can be taken from:
    • Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein.
      Introduction to Algorithms.
      2nd edition, The MIT Press, Cambridge, MA, 2001.
    • 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.
      Spektrum Akademischer Verlag, Heidelberg, 2001.
    • Robert Sedgewick.
      2nd edition, Pearson Education, München, 2002.
  • Office Hours:
    look here