Traditional algorithms courses teach us that data is stored linearly, with each access costing constant time, regardless of its position and previous memory accesses. This is a major simplification of modern processors, where in fact memory consists of several levels where data might reside and with different access times for each one: fast but small caches, to RAM, to slow disks, where even modern caching consists of multiple levels.
In this course we will learn how to design algorithms and data structures taking advantage of this hierarchical structure. We will learn approaches such as: External Memory/Cache Oblivious/Write Optimized algorithms and data structures.
Additionally, the course will have an applied element in the form of C++ library for external memory algorithms: STXXL.
Students will be required to implement a selected algorithms, in the form of a project.
