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

External Memory Algorithms (WS 07/08)

• Lecturer:
  Dr. Riko Jacob

• Module: IN2159

• Area:
  2+2 lectures per week in area III (Theoretical Computer Science)

• Time and Place:
  Mon 14:00 - 15:30, lecture hall 00.13.009A

• Exercises:
  2 hours per week exercises accompanying the lectures
  Tue 12:30 - 14:00, lecture hall 03.11.018
  Teaching Assistant: Michael Schnupp
  Course Certificate: To get a course certificate students must pass the final exam.

• Exam:
  

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

• ECTS: 5 points

• Prerequisites:
  1st and 2nd year courses
  Course Efficient Algorithms and Datastructures I advantagious, but not necessary.

• Contents:
  
  • I/O-model, cache oblivious model
  • elementary I/O algorithms (scanning, sorting, permuting)
  • I/O data structures (list, array, B-tree)
  • I/O graph algorithms (DFS, BFS, shortest path, minimum spanning tree)
  • lower bounds in the I/O model
  • geometric I/O algorithms
  • string algorithms and data structures in the I/O model
  • connection to algorithms for parallel architectures

• Related and Advanced Lectures:
  Efficient Algorithms and Datastructures I

• Lecture Notes:

• References:
  

• Office Hours:
  look here