Data Structures and Algorithms

Semestr: Winter

Range: 2+2s

Completion:

Credits: 5

Programme type: Undefined

Study form:

Course language: English

Summary:

Complexity of algorithms. Sorting - taxonomy of methods, Shellsort, Heapsort, Quicksort, Radixsort, searching, hashing, binary search, binary trees, multidimensional trees, geometrical searching. Data type specification and implementation (vector, linked list,, array, table, list, relation, graph). Logical and physical structure of files, sorting sequential files. Recursion and recursive programming. Dynamic programming. Program design methodologies.

Keywords:

Introduction, order of function growth, asymptotic algorithm complexity, sorting, searching, divide and conquer approach, data structures, abstract data types, stack, queue, tree, binary search tree, hash table, recursion, dynamic programming, text searching, deterministic finite automaton, regular grammar, computational geometry.

Course syllabus:

1. Space and time complexity of algorithms
2. Classification of sorting methods. Sorting algorithms with complexity O(n2)
3. Sorting algorithms with complexity O(n.logn)
4. Searching problem. Address searching methods
5. Associative searching methods
6. Multidimensional searching, Multidimensional searching trees
7. Geometrical searching, geometrical algorithms
8. Specification and implementation of data types
9. Implementation of the string, stack, queue, array, table, list, and graph data types
10. File data type, logical and physical structure of files, file sorting
11. Recursive programming, implementation of recursive algorithms
12. Back tracking searching algorithms
13. Dynamic programming
14. Program design paradigms

Seminar syllabus:

1. Calculation of minimal, maximal and average complexity of algorithms
2. Select-Sort and Buble-Sort, their space and time complexities
3. Insert-Sort implemented in array and linked structures
4. Quick-Sort, Heap-Sort, Merge-Sort, and Radix-Sort
5. Address search methods, hashing
6. Binary search, binary search trees
7. K-dimensional search trees, interval and segment trees, proximity problem
8. Construction of convex hull of a set of points in 2D
9. Specification of data types
10. Implementation of data types
11. Updating and sorting sequential files
12. Backtracking algorithms
13. Complexity of recursive algorithms
14. Assessment

Literature:

1. Cormen,T.H., et al.: Introduction to ALGORITHMS, New York, McGraw-Hill 1990.
2. Manoocher, A.:Abstract Data Types and Algorithms, London, Macmillan Education Ltd.

Examiners:

Lecturers:

Instructors: