Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Web page:
https://alg.fel.cvut.cz/
Anotation:
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 non-trivial algorithms and to evaluate their effectivity.
Study targets:
The goal of the course is to learn the ability to implemet various kinds of basic tasks of computer science. Main topics are sorting and searching algorithms and corresponding data stractures for these tasks. The emphasis is given to the algorithmical aspect of the tasks and efectivity of the practical solution.
Course outlines:
| 1. | | Order of growth of functions, asymptotic complexity of an algorithm |
| 2. | | Recursion, recurrence, Master theorem |
| 3. | | Trees, binary trees, backtracking |
| 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, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort |
| 8. | | Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort |
| 9. | | Dynamic programming, structure of optimal solutions, recursion elimination, tabulation, longest path in a DAG |
| 10. | | Dynamic programming, longest common subsequence, optimal matrix multiplication |
| 11. | | Dynamic programming, optimal BST, knapsack problem |
| 12. | | Hashing, open and chained tables, double hashing |
| 13. | | Hashing, coalesced hashing, universal hashing |
| 14. | | Median finding, sorting multidimensional data |
Exercises outline:
| 1. | | Order of growth of functions, asymptotic complexity of an algorithm |
| 2. | | Recursion, recurrence, Master theorem |
| 3. | | Trees, binary trees, backtracking |
| 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, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort |
| 8. | | Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort |
| 9. | | Dynamic programming, structure of optimal solutions, recursion elimination, tabulation, longest path in a DAG |
| 10. | | Dynamic programming, longest common subsequence, optimal matrix multiplication |
| 11. | | Dynamic programming, optimal BST, knapsack problem |
| 12. | | Hashing, open and chained tables, double hashing |
| 13. | | Hashing, coalesced hashing, universal hashing |
| 14. | | Median finding, sorting multidimensional data |
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) |
Requirements:
Programming 1
Keywords:
Asymptotic complexity, recursive algorithms, binary trees, searching, hashing, sorting, dynamic programming.
Subject is included into these academic programs:
| Page updated 12.5.2026 17:51:59, semester: L/2029-30, Z/2025-6, Z/2026-7, L/2025-6, L/2026-7, Z,L/2027-8, Z,L/2028-9, Send comments about the content to the Administrators of the Academic Programs |
Proposal and Realization: I. Halaška (K336), J. Novák (K336) |