External Memory Algorithms (Summer 2009)

  • Lecturer:
    Dr. Riko Jacob

  • Module: IN2159

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

  • Time and Place:
    Wednesday 13:30-15:00, Room 03.11.18

  • Exercises:
    2 hours per week exercises accompanying the lectures
    Course Certificate: To get a course certificate students must pass the final 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 advantageous, 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