SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Data Structures I - NTIN066
Title in English: Datové struktury I
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: both
E-Credits: 5
Hours per week, examination: 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: 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.
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: NTIN105, NTIN067
Annotation -
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)
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 -
Last update: Mgr. Martin Mareš, Ph.D. (01.03.2019)

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.

Code submitted as a part of the assignment must not contain personal data.

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 -
Last update: Mgr. Martin Mareš, Ph.D. (01.03.2019)

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

Syllabus -
Last update: doc. RNDr. Pavel Töpfer, CSc. (14.01.2019)

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.

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