Summary of Study |
Summary of Branches |
All Subject Groups |
All Subjects |
List of Roles |
Explanatory Notes
Instructions
Web page:
https://cw.fel.cvut.cz/wiki/courses/BE5B33ALG
Anotation:
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.
Study targets:
The course is concerned with the ability to implement effectively solutions of various problems arising in elementary computer science. Main topics of the course include sorting and searching algorithms and related data structures. The course stresses correct algorithms choice and effective implementation as an unique tool for successful problems solving.
Course outlines:
| 1. | | Order of growth of functions, asymptotic complexity of an algorithm |
| 2. | | Trees, binary trees, recursion |
| 3. | | More recursion and backtracking examples |
| 4. | | Graph, graph representation, basic graph processing |
| 5. | | Queue, stack, breadth/depth first search |
| 6. | | Array search, binary search tree |
| 7. | | AVL trees and B-trees |
| 8. | | Sorting, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort |
| 9. | | Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort |
| 10. | | Dynamic programming, tabulation, longest path in a DAG, optimal matrix multiplication |
| 11. | | Dynamic programming, longest common subsequence, optimal BST, knapsack problem |
| 12. | | Complexity of recursive algorithms, Master theorem |
| 13. | | Hashing, open and chained tables, double hashing, coalesced hashing |
| 14. | | Reserve |
Exercises outline:
| 1. | | Order of growth of functions, asymptotic complexity of an algorithm |
| 2. | | Trees, binary trees, recursion |
| 3. | | More recursion and backtracking examples |
| 4. | | Graph, graph representation, basic graph processing |
| 5. | | Queue, stack, breadth/depth first search |
| 6. | | Array search, binary search tree |
| 7. | | AVL trees and B-trees |
| 8. | | Sorting, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort |
| 9. | | Sorting, Merge Sort, Heap, Heap Sort, Radix Sort, Counting Sort |
| 10. | | Dynamic programming, tabulation, longest path in a DAG, optimal matrix multiplication |
| 11. | | Dynamic programming, longest common subsequence, optimal BST, knapsack problem |
| 12. | | Complexity of recursive algorithms, Master theorem |
| 13. | | Hashing, open and chained tables, double hashing, coalesced hashing |
| 14. | | Reserve |
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 14.4.2026 09:53:14, semester: L/2027-8, Z,L/2026-7, Z/2027-8, Z,L/2025-6, L/2029-30, 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) |