Skip to content
- In this module we give an introduction to the course I/O-efficient algorithms. We discuss the so-called I/O-model, which consists of an internal memory of limited size, an external memory of unlimited size and where data transfer between these two happens in blocks of a given size. We give a simple example showing that the actual running time of an algorithm working on data in external memory is greatly influenced by its I/O-behavior. Finally, we discuss the basics of analyzing algorithms in the I/O-model.
- Designing cache-aware and cache-oblivious algorithms
- In this module we discuss two techniques to design I/O-efficient algorithms, using the matrix-transposition problem as a running example. The first technique is a "tile-based" approach and leads to a cache-aware algorithm. The second technique uses a recursive approach and leads to a cache-oblivious algorithm.
- Replacement Policies
- When we want to read something from external memory while the internal memory is full we need to make room by evicting a block from internal memory. The block which should be evicted is decided by the replacement policy. In this module we introduce LRU and some other some well-known replacement policies, and investigate the I/O-efficiency of LRU compared to an optimal replacement policy.
- I/O-efficient sorting
- In this module we analyze the I/O-efficiency of MergeSort and discuss how to adapt it to make it more I/O-efficient.
- I/O-efficient data structures
- In this module we introduce some I/O-efficient data structures: B-trees and buffer trees, and an I/O-efficient priority queue based on buffer trees.
- Time-Forward Processing
- In this module we discuss time-forward processing, a technique that can be used to evaluate so-called local functions on a directed acyclic graph.