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

Fundamental Algorithms (WS 07/08)

Lectures in English

• Lecturer:
  Dmytro Chibisov

• Module: IN2157

• Area:
  2 lectures per week in Master of Science in Computational Science and Engineering (Compulsory course).
  1 tutorial per week (Optional).

• Time and Place:
  Lecture: Tuesday, 11:45-13:15, room MI 00.08.038
  Tutorial: Wednesday 11:00-12:30, room MI 03.11.018
  

• Audience:
  Students in Computational Science and Engineering (Master of Science).

• ECTS: 3 points

• Prerequisites:
  Basic knowledge in computer science.

• Contents:
  
  • Fundamentals
    models of computation, complexity measures, Landau notation
  • Sorting
    insertion-/merge-/heap-/quick-sort
  • Searching and Trees
    binary search, search trees, AVL trees, (2,3)-trees
  • Heaps and Priority Queues
    
  • Graph Algorithms
    depth first search, breath first search, shortest path problems, minimum spanning trees
  • Arithmetic Problems
    euclidean algorithm, multiplication of integers,

• Related and Advanced Lectures:
  
  • Fundamental Algorithms '06/'07
  • Fundamental Algorithms '05/'06
  • Fundamental Algorithms '02/'03
  • Grundlegende Algorithmen '05/'06 (in German)
  • Efficient Algorithms and Data Structures (in German)

• Lecture Notes:
  
  • 23.10.2007
  • 30.10.2007
  • 6.11.2007
  • 13.11.2007
  • 20.11.2007
  • 27.11.2007
  • 04.12.2007
  • 11.12.2007
  • 18.12.2007
  • 08.01.2008
  • 15.01.2008
  • 22.01.2008
  • 29.01.2008 and 5.02.2008

• References:
  
  • Volker Heun
    Grundlegende Algorithmen
    2. Auflage, Vieweg Verlag, 2003

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein.
    Introduction to Algorithms.
    2. Print, MIT Press, Cambridge, MA, 2001.

  • Robert Sedgewick.
    Algorithms.
    2. Print, Pearson Education, Munich, 2002.

• Exams:
  February 12th, 10:00 in room MW 0350
  
  Assisting material is allowed, but limited to one DIN A4 sheet of paper with your own notes and reminders. It has to be handwritten by yourself, copies or printed versions are not accepted. Except for this sheet, no other utilities (as lecture notes, calculators, notebooks, ...) are permitted.

• Office Hours:
  by appointment