Algorithms
Code  Completion  Credits  Range  Language 

AD4B33ALG  Z,ZK  6  14KP+6KC  Czech 
 Lecturer:
 Tutor:
 Supervisor:
 Department of Cybernetics
 Synopsis:

In the course, the algorithms development is constructed with minimum dependency to programming language; nevertheless the lectures and seminars are based on Java. 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 nontrivial algorithms and to evaluate their affectivity.
 Requirements:

Programming 1
 Syllabus of lectures:

1. Order of growth of functions, asymptotic complexity of an algorithm
2. Recursion, recurrence, Master theorem
3. Trees, binary trees, backracking
4. Queue, graph, Depthfirst and Breadthfirst search in a tree and in a general graph
5. Searching in arrays, binary search trees
6. AVL trees and Btrees
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
 Syllabus of tutorials:

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.Onedimensional 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, linearlylinked list
11.Tree construction, tree search
12.Test, consultation to semester task
13. Algorithms of linear algebra and geometry, mathematical analysis
14.Credit
 Study Objective:

Semester project consists from empirical evaluation of searching and sorting algorithms, comparison of iterative and recursive algorithms and debugging of graphical output of selected algorithms of linear algebra and mathematical analysis. Three phases of supervision associated to constituted subtask of project with closing demonstration and defense
 Study materials:

[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, McgrawHill Higher Education, 2006,
[3] Robert Sedgewick: Algoritms in v C, parts 14, AddisonWesley Professional; 3rd edition (1997)
 Note:
 Further information:
 No timetable has been prepared for this course
 The course is a part of the following study plans:

 Otevřená informatika  Počítačové systémy (compulsory course in the program)
 Otevřená informatika  Informatika a počítačové vědy (compulsory course in the program)
 Otevřená informatika  Softwarové systémy (compulsory course in the program)
 Otevřená informatika, před rozřazením do oborů (compulsory course in the program)