Data Structures II
This course extends NTIN066 Data Structures I. It covers more advanced techniques of design and analysis of data structures: deterministic representation of static sets, data structures for integers, basic data structures for graphs, dynamic cache-oblivious search trees, dynamization, persistence, succinct data structures, computation in stream model.Basic information
- Name: Data Structures II
- Code: NTIN067
- Hours per week, examination: summer semester 2/0 Ex
- Language: English or Czech
- Schedule
- Year: 2018/19
Lectures
- Static deterministic dictionaries (18.2. a 25.2.)
- Integer data structures: van Emde-Boas, x-fast, y-fast and Fusion tress and bit tricks on RAM (4.3. a 11.3.)
- Integer data structures: van Emde-Boas trees, x-fast and y-fast trees (4.3.)
- Tricks on Random Access Machine, Fusion trees (11.3.)
- Heavy-light decomposition (18.3.)
- Link-Cut trees, Dinic algorithm for networks flow (25.3.)
- Union-find (1.4. a 8.4.)
- Dynamization (15.4.)
- Persistence (22.4. a 29.4.)
- Succinct data structures (6.5.)
- Dodis, Patrascu, Thorup: Changing Base Without Losing Space, Proceedings of STOC, 2010