Data Structures I - NTIX066

• Title: Datové struktury I
• Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2022
• Semester: both
• E-Credits: 5
• Hours per week, examination: 2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: Czech
• Teaching methods: full-time
• Additional information: https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I/
• Note: you can enroll for the course in winter and in summer semester
• Guarantor: RNDr. Jiří Fink, Ph.D.; Mgr. Martin Mareš, Ph.D.; doc. Mgr. Petr Gregor, Ph.D.
• Class: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Softwarové systémy; Informatika Mgr. - Matematická lingvistika; Informatika Mgr. - Diskrétní modely a algoritmy
• Classification: Informatics > Theoretical Computer Science
• Incompatibility : NTIN066
• Interchangeability : NTIN066
• Is incompatible with: NTIN066
• Is interchangeable with: NTIN066

Annotation

English

The basic course about construction of efficient data structures, mandatory for Master's students. Search trees, heaps, hashing. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior and analysis of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithms and Data Structures I and II and Programming I and II from the bachelor study.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, haldy, hešování. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury. Chování a analýza datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na Algoritmy a datové struktury I a II a Programování I a II bakalářského studia.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Aim of the course

Naučit pokročilejší datové struktury včetně teoretické analýzy a experimentů s chováním na reálných počítačích.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Course completion requirements

English

It is necessary to obtain class credit and pass the exam.

Class credit is given for reaching the required number of points for assignments solved during the semester.

The character of the assignments does not allow repeated attempts to obtain credit.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

Ke splnění předmětu je nutné získat zápočet a složit zkoušku.

Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru. Vzhledem k povaze domácích úkolů nejsou náhradní termíny zápočtu přípustné.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Literature

English

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, Berlin, 1984

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

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

A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011

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

Last update: Jedelský Petr, Mgr. (01.03.2021)

Requirements to the exam

English

The exam is oral with written preparation. To pass the exam, understanding of material presented at the lecture is required.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

Zkouška je ústní s písemnou přípravou. Zkouší se porozumění teorii prezentované na přednášce.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Syllabus

English

Trees

• (a,b)-trees and their variants

• Move-to-Front strategy for lists, Splay trees

• other solutions: AVL trees, red-black trees, BB-alpha trees

Heaps

• regular heaps

• binomial heaps

• Fibonacci heaps

Techniques for memory hierarchy

• I/O model, cache-oblivious analysis, LRU strategy for on-line paging

• examples: matrix transposition and multiplication, van Emde-Boas tree layout

• cache-aware techniques

Hashing

• collisions and their resolution, analysis for uniformly distributed data

• selecting a hash function: universal hashing, good hash functions

• cuckoo hashing

Multidimensional data structures

• KD trees

• range trees

Warning: The course will be given since 2018/19 in English only in the summer term (instead of the winter term in previous years) and in Czech only in the winter term.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

Haldy

• regulární halda

• binomiální halda

• Fibonacciho halda

Stromy

• (a,b)-stromy a jejich varianty

• strategie Move-to-Front pro seznamy, Splay stromy

• přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromy

Techniky pro paměťovou hierarchii

• I/O model, cache-oblivious analýza, strategie LRU pro on-line stránkování

• příklady: transpozice a násobení matic, van Emde-Boasovo rozložení vyhledávacích stromů

• cache-aware techniky

Hašování

• řešení kolizí, analýza pro uniformně rozdělená data

• výběr hešovací funkce: univerzální hešování a dobré hešovací funkce

• kukačkové hešování

Vícerozměrné datové struktury

• KD stromy

• range trees (intervalové stromy)

Upozornění: Předmět se bude vyučovat od 2018/19 v českém jazyce pouze v zimním semestru a v anglickém jazyce pouze v letním semestru.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Entry requirements

English

Knowledge on the level of the undergraduate Algorithms and data structures.

Last update: Jedelský Petr, Mgr. (01.03.2021)

Czech

Predpoklady: Znalosti na úrovni bakalářské přednášky Algoritmy a datové struktury.

Last update: Jedelský Petr, Mgr. (01.03.2021)