|
Lecturer(s)
|
-
Oliva Karel, doc. RNDr. Dr.
-
Sýkorová Květuše, Mgr.
-
Škvor Jiří, RNDr. Ph.D.
|
|
Course content
|
1. Terminology, time complexity, memory complexity 2. Basic data structures - array, list, stack, queue 3. Sorting algorithms O(n^2) - SelectSort, InsertSort, BubbleSort 4. Sorting algorithms O(n^k) - ShellSort, KnuthSort, HeapSort 5. Sorting algorithms O(n.log_k n) - QuickSort, MergeSort 6. Sorting algorithms O(k.n) - RadixSort, BucketSort 7. Searching algorithms - Brute Force, Binary Search, Interpolation Search 8. Indexing - Dense Index, Sparse Index, Multilevel Index 9. Hashing - Close Hash Table, Open Hash Table, Perfect Hash, Rehash 10. Tree structures - properties, Binary Tree, Binary Search Tree 11. Tree structures - Digi Tree, B-Tree 12. Balanced tree structures - AVL-tree, Red-Black tree 13. Special tree structures - Trie, Splay, Treap, Randomized BST
|
|
Learning activities and teaching methods
|
|
unspecified
|
|
Learning outcomes
|
The course is targeted to the basic data structures, especially is focussed on the list, queue, stack, linked list, hash table, index, searching tree structures and on the algorithms over this structures. Attention is paid not only to the formal description of above mentioned structures and algorithms, but also to its practical implementation.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
unspecified
Credit requirements - active participation in tutorials (attendance) - presentation of solution of homework assignments (implementation of selected algorithms) in a chosen programming language (e.g. C#) and their explanation The exam is oral and takes about 20-30 minutes. Theoretical knowledge and the ability to describe and analyze the selected algorithms (including determination of their properties) are examined.
|
|
Recommended literature
|
-
D. E. Knuth. "The Art of Computer Programming - Sorting and Searching", Addison-Wesley, USA1998.
-
Keogh, J., Davidson, K. Datové struktury bez předchozích znalostí. ComputerPress, Brno, 2006. ISBN 80-251-0689-6.
-
Sedgewick, R. Algoritmy v C. SoftPress, Praha, 2003. ISBN 80-86497-56-9.
-
Wirth, N. Algoritmy a štruktúry údajov. Alfa, Bratislava, 1989. ISBN 80-05-00153-3.
-
Wróblewski, P. Algoritmy, datové struktury a programovací techniky. ComputerPress, Brno, 2004. ISBN 80-251-0343-9.
|