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.)
    • Hagerup, T., Miltersen, P. B., & Pagh, R: Deterministic dictionaries. Journal of Algorithms, 41(1), 69-85, 2001. On-line
    • Lectures by Martin Mareš 24.2. a 2.3.
  • Integer data structures: van Emde-Boas, x-fast, y-fast and Fusion tress and bit tricks on RAM (4.3. a 11.3.)
    • Lectures by Martin Mareš 9.3. and 16.3.
    • Lectures by Erik Demaine L11 and L12
  • 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
Slides from lectures and their compact version are regularly updated.