|
Lecturer(s)
|
-
Kavička Antonín, prof. Ing. Ph.D.
|
|
Course content
|
Data type String and searching algorithms (Knuth-Morris-Pratt algorithm, Karp-Rabin algorithm, string-matching automaton). String encoding (Huffman encoding trees, Lempel-Ziv encodings). Prefix trees (trie) and their implementations (de la Briandais tree). Advanced heaps (Binomial heap, Fibonacci heap, Pairing heap) and their implementations. AVL-tree - balanced binary search tree. Heap ordered binary search tree - Treap. Binary search tree based on move-to-front heuristic (Splay tree). Perfectly balanced trees (2-3 tree, B-tree). Basic principles of data structures stored within external memory, constraints of physical devices. Sequential files. Unordered random access file - Heap-file, Hash files. Sparse index, Indexed sequential files. B+-tree - file with hierarchical index. Dense-indexed files, Multi-indexed files within database applications.
|
|
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 familiarise students with the advanced data structures and relevant algorithms as essentials of the efficient programming.
Passing the course enables to manage advanced data structures, their applications and efficient implementations, which support of high-quality software products.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral examination, Written examination, Home assignment evaluation
Given assignment confirms that a student has attended lessons to the extent required and fulfilled qualified requirements (elaboration of three software works focused on programming of selected advanced data structures and relevant algorithms). Form, contents and length of the exam are determined in accordance with Study and Examining Rules of University of Pardubice. The exam consists of two parts, a written test and a theoretical exam. Student passes successfully the written test as well as the theoretical part of the exam if he/she obtains at minimum 50% of possible points in each part.
|
|
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.
|