Subjects

Your browser does not support JavaScript, or its support is disabled. Some features may not be available.

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

Opinion survey results Examination dates Schedule Noticeboard

Annotation -

Last update: doc. 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: doc. Mgr. Jan Kynčl, Ph.D. (30.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

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.