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.

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