About the course
It is going to be a 4-week crash-course introducing the basic aspects of I/O-efficient algorithms and data structures. The course will be held in Pacific National University (Khabarovsk) in the framework of a joint international program between Saarland university and Pacific National University. logos logos
  Lecturing
  · Instructor: Roman Dementiev
  · 12 lectures: Mo, Wed, Thu 11:00 and exercise sessions after every third lecture.
  · First lecture: 2 August, Oral Exam: 28 August
  Topics
  · 2 August: Introduction, PDM model, scanning, sorting, lower bound for sorting
  · 4 August: Pointer based searching, lower bounds for searching, external memory stack, queue, lists
  · 7 August: B-tree, batched dynamic problems, buffer trees
  · 9 August: I/O-efficient priority queue, EM distribution sorting, Multiway merge sort,
  · 10 August: Parallel disk sorting, asynchronous parallel disk sorting [paper]
  · 14 August: Time-forward processing, EM maximal independent set computation, coloring graphs of bounded degree
  · 16 August: List ranking, Euler tour technique, algorithms for trees, graph traversal
  · 17 August: I/O-efficient Breadth-First-Search, Munagala-Ranade and Melhorn-Meyer Algorithm, Engineering EM BFS algorithms [paper]
  · 21 August: External Memory Minimum Spanning Forests, Engineering EM MSF algorithms [paper], External Memory Coloring (heuristics for general graphs and 7-coloring planar graphs)
  · 23 August: External memory suffix array construction [paper]
  · 24 August: Cache-oblivious algorithms
  Assignments
  · Assignment 1
  · Assignment 2
  · Assignment 3
  · Assignment 4
  · Assignment 5