|
Lecturer(s)
|
-
Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
-
Večerka Arnošt, RNDr.
|
|
Course content
|
<ol> <li>Algorithms and their complexity. <li>Data structures, linear data structures: lists, stack, front and their implementation, tree data structures. <li>Sorting problem, internal sorting methods: insertion sort , Shellsort, bubble sort, Quicksort, selection sort, Heapsort. <li>External sorting, principle of external sorting by merging method, polyphase merge sort. <li>Searching in linear data structures: sequential search in an array or list of randomly ordered items, binary search in a sorted array. <li>Search trees, AVL-trees, insertion of an item into AVL-tree, deletion of an item from AVL-tree. <li>Binary search trees, search operation, AVL-trees, insertion of an item into AVL-tree, deletion of an item from AVL-tree, balanced trees, their structure, search operation, insertion, and deletion of items in balanced trees. <li>Hashing, computation of the hash function, hash table organization. Methods for conflict resolution: open addressing, separate chaining. </ol>
|
|
Learning activities and teaching methods
|
|
Lecture, Dialogic Lecture (Discussion, Dialog, Brainstorming)
|
|
Learning outcomes
|
Make students familiar with basic data structures and algorithms.
1. Knowledge Describe the problem of sorting.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral exam
Understanding data structures. Understanding searching and sorting algorithms.
|
|
Recommended literature
|
-
Aho, A.V., Hopcroft, J.E., Ullman, J.D. (1983). Data Structures and Algorithms. Addison-Wesley.
-
Bhargava, A. Y. (2016). Algorithms.. Manning Publications Co.
-
CORMEN, T. H., LEISERSON C. E., RIVEST D. L., STEIN C. (2001). Introduction to Algorithms, Second Edition. MIT Press.
-
Knuth, D. (1997). The Art of Computer Programming, Volume 1, Fundamental Algorithms, Third Edition. Addison-Wesley.
-
KNUTH, D. (2005). The Art of Computer Programming, Volume 3, Sorting and Searching, Second Edition. Addison-Wesley.
-
SEDGEWICK, R. (2003). Algoritmy v C, části 1- 4: základy, datové struktury, třídění, vyhledávání. Praha, Softpress.
|