|
Lecturer(s)
|
-
Fikejz Jan, Ing. Ph.D.
-
Novotný Radek, Ing. Ph.D.
|
|
Course content
|
1. String encoding (Huffman encoding trees, Lempel-Ziv encodings) 2. Data type String and searching algorithms (Knuth-Morris-Pratt algorithm, Karp-Rabin algorithm, string-matching automaton) 3. Prefix trees (trie) and their implementations (de la Briandais tree) 4. Advanced heaps (Binomial heap, Fibonacci heap, Pairing heap) and their implementations 5. Table implementations using binary search trees (AVL-tree, Treap, Splay-tree) 6. Table implementations using k-way search trees (2-3 tree, a-b trees, B-tree) 7. Complexity analysis of algorithms and appliactions of heuristics within data structures (amortized analysis, worst-case analysis, move-to front and transpositions heuristics) 8. Data structures stored within external memory (block transfers, buffers) 9. Sequential files and random access files 10. Heap-files and hash-files 11. Ordered files and indexed sequential files 12. Hierarchical organization of indexed files (B+-tree) 13. Dense multi-indexed files
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming), Skills training
- Contact teaching
- 52 hours per semester
- Term paper
- 45 hours per semester
- Home preparation for classes
- 20 hours per semester
- Preparation for an exam
- 33 hours per semester
|
|
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, P., Klima, V., Janáček, J. Optimalizace dopravních a spojových procesů. Žilina, 1994.
-
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. ISBN 978-0673397362.
-
Wirth, N. Algoritmy a štruktúry údajov. ALFA Bratislava, 1987.
-
Wróblewski, Piotr. Algoritmy : datové struktury a programovací techniky. Brno: Computer Press, 2004. ISBN 80-251-0343-9.
|