SubjectsSubjects(version: 953)
Course, academic year 2023/2024
   Login via CAS
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
Teaching methods: full-time
Guarantor: Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN066
Annotation -
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)
Course completion requirements -

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


• (a,b)-trees and their variants

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

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


• 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


• 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)
Charles University | Information system of Charles University |