I/O-efficient Algorithms and Data Structures

Język wykładowy Angielski
Semestr Letni
Status W ofercie
Opiekun Przemysław Uznański
Liczba godzin 30 (wyk.) 30 (ćw-prac.)
Rodzaj I2.Z - zastosowania inf.
ECTS 6
Polecany dla I roku No
Egzamin Yes

Opis przedmiotu:

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.