SubjectsSubjects(version: 845)
Course, academic year 2018/2019
   Login via CAS
Analysis of data structures - NTIN105
Title in English: Analýza datových struktur
Guaranteed by: Department of Applied Mathematics (32-KAM)
Faculty: Faculty of Mathematics and Physics
Actual: from 2018 to 2018
Semester: both
E-Credits: 2
Hours per week, examination: 0/1 C [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Note: you can enroll for the course in winter and in summer semester
Guarantor: Mgr. Martin Mareš, Ph.D.
Class: Informatika Mgr. - volitelný
Classification: Informatics > Theoretical Computer Science
Co-requisite : NTIN066
Annotation -
Last update: Mgr. Jan Kynčl, Ph.D. (30.04.2018)
Extends the exercise classes for Data Structures I (NTIN066) by deeper theoretical analysis of data structure behavior.
Course completion requirements -
Last update: Mgr. Martin Mareš, Ph.D. (15.10.2018)

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

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


• (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.

Charles University | Information system of Charles University |