|
Lecturer(s)
|
-
Bažant Michael, doc. Ing. Ph.D.
|
|
Course content
|
The main topics of the course: *Data structures and algorithms applying hash techniques - abstract data type table/dictionary, principles of creating hash functions, static and dynamic (extendible) hashing, methods of solving collisions, universal hashing, hash files. *Indexed files - indices over base/data files (block-oriented), sparse and dense indices (fixed and unfixed records), linear indices (indexed sequential files), hierarchical indices - B-trees, multiple indices. *Selected data structures for storing multidimensional data - range tree, k-D tree, priority search tree, quad tree (octal tree), R-tree, grid file, interval searching within multidimensional data.
|
|
Learning activities and teaching methods
|
|
Monologic (reading, lecture, briefing), Methods of individual activities, Laboratory work
|
|
Learning outcomes
|
Theoretical principles of selected advanced data structures and their relevant algorithms are introduced. Essential attention is paid to designing and implementing efficient software solutions (namely from the viewpoint of computational complexity).
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral examination, Written examination, Home assignment evaluation
The student is supposed to create a software application within the frame of which selected data structures (incl. relevant algorithms) are implemented. The implemented structures correspond with the theoretical topics of the course. The student completes at least 3 consultations during the semester concerning the theoretical content of the course. The student will pass at least 1 consultations concerning the assigned practical problem.
|
|
Recommended literature
|
-
Bhattacharya, Arnab. Fundamentals of database indexing and searching. 2014. ISBN 978-1466582545.
-
Cormen, Thomas H. Introduction to algorithms. Cambridge, Mass.: Massachusetts Institute of Technology, 2001. ISBN 0-262-53196-8.
-
LEWIS, H. R.; DENENBERG, L. Data structures and their algorithms. Berkley, Adison-Wesley, 1997..
-
Samet, Hanan. Foundations of multidimensional and metric data structures. San Francisco: Morgan Kaufmann, 2006. ISBN 0-12-369-446-9.
|