Analysis of data structures - NTIN105

• Title: Analýza datových struktur
• Guaranteed by: Department of Applied Mathematics (32-KAM)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2021
• Semester: winter
• E-Credits: 2
• Hours per week, examination: winter s.:0/1, C [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: cancelled
• Language: Czech, English
• Teaching methods: full-time
• Guarantor: Mgr. Martin Mareš, Ph.D.
• Class: Informatika Mgr. - volitelný
• Classification: Informatics > Theoretical Computer Science
• Co-requisite : NTIN066

Annotation

English

Extends the exercise classes for Data Structures I (NTIN066) by deeper theoretical analysis of data structure behavior.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (30.04.2018)

Czech

Doplňuje cvičení z Datových struktur I (NTIN066) o hlubší partie týkající se teoretické analýzy chování datových struktur.

Last update: Kynčl Jan, doc. Mgr., Ph.D. (30.04.2018)

Course completion requirements

English

Class credit is awarded for active participation in the classes. In cases of insufficient participation, it can be augmented by a final project.

Last update: Mareš Martin, Mgr., Ph.D. (15.10.2018)

Czech

Zápočet se uděluje za aktivní účast na semináři. V případě nižší aktivity ji lze nahradit vyřešením zápočtové úlohy.

Last update: Mareš Martin, Mgr., Ph.D. (15.10.2018)

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: Kynčl Jan, doc. Mgr., Ph.D. (30.04.2018)

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: Kynčl Jan, doc. Mgr., Ph.D. (30.04.2018)