SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
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
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 -
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)
Aim of the course - Czech

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 -

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)
Literature -

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)
Requirements to the exam -

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)
Syllabus -

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)
Entry requirements -

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

Last update: Jedelský Petr, Mgr. (01.03.2021)
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html