SubjectsSubjects(version: 825)
Course, academic year 2017/2018
   Login via CAS
Data Structures I - NTIN066
Czech title: Datové struktury I
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2017 to 2017
Semester: winter
E-Credits: 5
Hours per week, examination: winter s.:2/1 C+Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Additional information: http://mj.ucw.cz/vyuka/ds1/
Guarantor: RNDr. Jiří Fink, Ph.D.
Mgr. Martin Mareš, 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
Is co-requisite for: NTIN067
Annotation -
Last update: T_KTI (25.04.2016)

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.
Aim of the course - Czech
Last update: T_KTI (25.04.2016)

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

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

Ke splnění předmětu je nutné získat zápočet a následně složit zkoušku. K získání zápočtu je potřeba získat požadovaný počet 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é.

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

Requirements to the exam - Czech
Last update: Mgr. Martin Mareš, Ph.D. (11.10.2017)

Je třeba rozumět teorii z přednášky.

Syllabus -
Last update: RNDr. Jan Hric (27.04.2018)

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

Entry requirements -
Last update: T_KTI (28.04.2015)

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

 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html