Description:

In the course, the algorithms development is constructed with minimum dependency to programming language; nevertheless the lectures and seminars are based on Python. Basic data types a data structures, basic algorithms, recursive functions, abstract data types, stack, queues, trees, searching, sorting, special application algorithms, Dynamic programming. Students are able to design and construct non-trivial algorithms and to evaluate their affectivity.

Contents:

1. Order of growth of functions, asymptotic complexity of an algorithm
2. Recursion, recurrence, Master theorem
3. Trees, binary trees, backracking
4. Queue, graph, Depth-first and Breadth-first search in a tree and in a general graph
5. Searching in arrays, binary search trees
6. AVL trees and B-trees
7. Sorting, Insert Sort, SelectionSort, Bubble Sort, QuickSort
8. Sorting, Merge Sort, Halda, Heap Sort
9. Sorting, Radix sort, Counting Sort, Bucket Sort
10. Hashing, open and chained tables, double hashing
11. Hashing, coalesced hashing, universal hashing
12. Dynamic programming, optimal solution structure, memoization, optimal BST
13. Dynamic programming, longest common subsequence, optimal matrich chain multiplication, knapsack problem
14. Sorting multidimensional data, realistic sorting algorithms performance

Seminar contents:

1. Introductory test, repeating of the ways of program construction in development environment, examples of functions and procedures, parameters, simple classes, assignment of semester task
2. One-dimensional array processing
3. Sorting and searching in 1D array algorithms
4. Multidimensional array processing algorithms
5. Text and string algorithms
6. Experimentation with space and complexity of algorithms
7. Sequential files
8. Implementation of abstract data types
9. Recursion and iteration
10. Linked lists, linearly-linked list
11. Tree construction, tree search
12. Test, consultation to semester task
13. Algorithms of linear algebra and geometry, mathematical analysis
14. Credit

Recommended literature:

[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009,

[2] S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: Algorithms, Mcgraw-Hill Higher Education, 2006,

[3] Robert Sedgewick: Algoritms in v C, parts 1-4, Addison-Wesley Professional; 3rd edition (1997)

Keywords:

Asymptotic complexity, recursive algorithms, binary trees, searching, hashing, sorting, dynamic programming.

Abbreviations used:

Semester:

• W ... winter semester (usually October - February)
• S ... spring semester (usually March - June)
• W,S ... both semesters

Mode of completion of the course:

• A ... Assessment (no grade is given to this course but credits are awarded. You will receive only P (Passed) of F (Failed) and number of credits)
• GA ... Graded Assessment (a grade is awarded for this course)
• EX ... Examination (a grade is awarded for this course)
• A, EX ... Examination (the award of Assessment is a precondition for taking the Examination in the given subject, a grade is awarded for this course)

Weekly load (hours per week):

• P ... lecture
• C ... seminar
• L ... laboratory
• R ... proseminar
• S ... seminar