Course: Algorithms and Data Structures

« Back
Course title Algorithms and Data Structures
Course code KI/DSA
Organizational form of instruction Lecture + Lesson
Level of course Bachelor
Year of study 2
Semester Summer
Number of ECTS credits 5
Language of instruction Czech
Status of course Compulsory
Form of instruction Face-to-face
Work placements This is not an internship
Recommended optional programme components None
Lecturer(s)
  • Sýkorová Květuše, Mgr.
  • Oliva Karel, doc. RNDr. Dr.
  • Š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, only 3 absences are allowed) - presentation of solution of chosen problems in 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.


Study plans that include the course
Faculty Study plan (Version) Category of Branch/Specialization Recommended year of study Recommended semester
Faculty: Faculty of Science Study plan (Version): Information Sciences (double subject) (A14) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Information Systems (A14) Category: Informatics courses 1 Recommended year of study:1, Recommended semester: Summer
Faculty: Faculty of Science Study plan (Version): Information Sciences (double subject) (A14) Category: Informatics courses 2 Recommended year of study:2, Recommended semester: Summer