SubjectsSubjects(version: 901)
Course, academic year 2021/2022
Data Structures 2 - NTIN067
Title: Datové struktury 2
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2020
Semester: summer
E-Credits: 3
Hours per week, examination: summer s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
Virtual mobility / capacity: no
State of the course: taught
Language: Czech
Teaching methods: full-time
Guarantor: RNDr. Jiří Fink, Ph.D.
Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN066
Annotation -
Last update: T_KTI (25.04.2016)
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.
Aim of the course - Czech
Last update: T_KTI (25.04.2016)

Naučit pokročilejší datové struktury a metody jejich návrhu a analýzy.

Course completion requirements - Czech
Last update: Mgr. Martin Mareš, Ph.D. (02.03.2018)

Předmět je zakončen zkouškou, u níž se ověřuje porozumění látce z přednášky a schopnost aplikovat ji na řešení obdobných problémů.

Literature -
Last update: T_KTI (26.04.2016)

D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005

K. Mehlhorn: Data Structures and Algorithms I -- Sorting and Searching, Springer-Verlag, 1984

Syllabus -
Last update: T_KTI (25.04.2016)

Static dictionaries:

• FKS perfect hashing

• deterministic dictionaries (Hagerup, Miltersen, Pagh)

• reduction of universe

Integer data structures:

• van Emde-Boas trees

• x-fast a y-fast trees

• Fusion trees

Graph data structures:

• heavy-light decomposition of trees

• path updates based on lazy evaluation

• Link-Cut trees (Sleator, Tarjan)

• incremental connectivity (Union-Find)

General transforms of data structures:

• semidynamization and dynamization

• persistence

Cache-oblivious structures:

• Ordered File Maintenance

• B-trees

Succinct data structures:

• strings over non-binary alphabets

• succinct representation of trees

Computation in stream model:

• determinisitic search for frequent elements

• randomized search for frequent elements

• estimating the number of distinct elements

Charles University | Information system of Charles University |