Lecturer(s)
|
-
Kavička Antonín, prof. Ing. Ph.D.
-
Fikejz Jan, Ing. Ph.D.
|
Course content
|
String encoding (Huffman encoding trees, Lempel-Ziv encodings) Data type String and searching algorithms (Knuth-Morris-Pratt algorithm, Karp-Rabin algorithm, string-matching automaton) Rrefix trees (trie) and their implementations (de la Briandais tree) Advanced heaps (Binomial heap, Fibonacci heap, Pairing heap) and their implementations Table implementations using search trees (AVL-tree, Treap, Splay-tree, 2-3 tree, (a-b)-tree, B-tree) Data structures stored within external memory (block transfers, buffers) Sequential files and random access files Heap-files and hash-files Ordered files and indexed sequential files Hierarchical organization of indexed files (B+-tree) Dense multi-indexed files
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming), Skills training
|
Learning outcomes
|
The main goal of the course is to familiarize students with advanced data structures and relevant algorithms as essentials of sophisticated software applications.
Passing the course enables to manage advanced data structures, their applications and efficient implementations, which support creation of high-quality software products.
|
Prerequisites
|
There is expected fundamental knowledge of basic abstract data types and their implementations & applications.
|
Assessment methods and criteria
|
Oral examination, Written examination, Home assignment evaluation
Given assignment approves that a student attended lessons in a required scale and fulfilled qualified requirements (elaboration of software works focused on implementation of selected advanced data structures and relevant algorithms).
|
Recommended literature
|
-
Cenek, Petr. Optimalizace dopravních a spojových procesů. Žilina: Vysoká škola dopravy a spojov, 1994. ISBN 80-7100-197-X.
-
Cormen, T. H. et al. Introduction to algorithms. Boston: MIT Press, 2001. ISBN 0-262-03293-7.
-
Lewis, H. R., Denenberg, L. Data structures and their algorithms. Berkley, Adison-Wesley, 1997. ISBN 978-0673397362.
-
Volek, Josef. Operační výzkum I. Pardubice: Univerzita Pardubice, 2002. ISBN 80-7194-410-6.
-
Wirth, N. Algoritmy a štruktúry údajov. Bratislava, Alfa, 1988.
-
Wróblewski, Piotr. Algoritmy : datové struktury a programovací techniky. Brno: Computer Press, 2004. ISBN 80-251-0343-9.
|