Topics of lectures: 1. Data organization in internal and external memory, data types, ordinality. Structured data types. 2. Abstract data types (ADTs) - definition, meaning of ADTs. Classification according to several criteria, basic operations on ADTs (FIFO, LIFO, 4 types of lists, dynamic array, circular buffer, set, multiset). 3. Introduction to trees with emphasis on binary trees. 4. Importance and different types of binary tree traversal, implementation options, heap. 5. Algorithm - what is it, definition, criteria for algorithm classification, Divide & Conquer. 6. Asymptotic and amortized complexity - complexity theory, tips for determining complexity in practice, examples. 7. Recursion, types of recursion, benefits and risks. Backtracing, 8 queens puzzle. 8. Search algorithms - problem description, terminology. 9. Linear, binary interpolation searches, analysis of when to use linear search and when it is more convenient to sort and search binary. Prune and Search. 10. Binary search trees (BST) - theory, traversal, implementation and basic operations over BST. 11. Tree balancing. AVL trees, description of the problem, different types of rotations, criteria for implementation and use of each rotation, necessity of AVL balancing after insert and delete operations. 12. Sorting - description of the problem. Algorithm classification criteria. BogoSort, SelectSort, InsertSort, BubbleSort, ShakerSort (CoctailSort), CombSort, ShellSort, QuickSort, MergeSort, HeapSort. 13. Hashing, hash tables - terminology, introduction, hashing principle. Associative search, direct address search and hashing. Hashing functions and their types. Collisions, their occurrence and resolution. Chained and open hashing, linear probing, double hashing. 14. String search, pattern matching - terminology, natural search, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp. Error function, preprocessing. The content of the exercises corresponds to the lectures - practical examples are used to practice the techniques, principles and algorithms discussed in the lectures.
|