SubjectsSubjects(version: 850)
Course, academic year 2019/2020
   Login via CAS
Advanced Data Structures - NTIN098
Title in English: Pokročilé datové struktury
Guaranteed by: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
Faculty: Faculty of Mathematics and Physics
Actual: from 2016
Semester: winter
E-Credits: 3
Hours per week, examination: winter s.:2/0 Ex [hours/week]
Capacity: unlimited
Min. number of students: unlimited
State of the course: cancelled
Language: Czech, English
Teaching methods: full-time
Guarantor: prof. RNDr. Václav Koubek, DrSc.
RNDr. Jan Bulánek, Ph.D.
Mgr. Vladimír Čunát
Class: Informatika Mgr. - Teoretická informatika
Classification: Informatics > Theoretical Computer Science
Annotation -
Last update: T_KTI (07.05.2012)
The course covers more advanced topics from the area of data structures. It is a continuation of the basic courses - Algorithms and Data Structures and Data Structures. The planned topics include randomized data structures (Bloom filters, hashing, etc.), effective implementations of dictionaries (i.e. Y-fast trie, van Emde Boas Trees), models of hierarchic memories mainly Cache-Aware and Cache-Oblivious models and finally persistent data structures. The course is intended to students from upper classes and graduate students and a basic knowledge of probability theory is required.
Literature -
Last update: T_KTI (07.05.2012)
  • Mehta, D. P., Sahni, S.: Handbook of data structures, Chapman & Hall, 2005
  • Papers on relevant topics from proceedings and journals SODA, JACM, J. Algorithms, ICALP, FOCS, STOC

Syllabus -
Last update: prof. RNDr. Václav Koubek, DrSc. (05.10.2015)
  • Bloom filters
  • advanced and two-way heaps
  • trie and representation of trie, sparse matrices and sparse lists
  • randomized binary search trees
  • Cache Oblivious models (Funnel Sort, Distribution Sort)
  • two-choices and universal family of functions
  • Linear probing universal hashing
  • interpolation and quadratic search
  • perfect hashing and universal family of functions
 
Charles University | Information system of Charles University | http://www.cuni.cz/UKEN-329.html