Algorithms
| Code | Completion | Credits | Range | Language |
|---|---|---|---|---|
| B4B33ALG | Z,ZK | 6 | 2P+2C | Czech |
- Relations:
- During a review of study plans, the course BE5B33ALG can be substituted for the course B4B33ALG.
- In order to register for the course B4B33ALG, the student must have registered for the required number of courses in the group BEZBM no later than in the same semester.
- It is not possible to register for the course B4B33ALG if the student is concurrently registered for or has previously completed the course BE5B33ALG (mutually exclusive courses).
- Course guarantor:
- Daniel Průša
- Lecturer:
- Robert Pěnička, Daniel Průša
- Tutor:
- Jiří Němeček, Robert Pěnička, Daniel Průša, Jan Ševic, Pavel Šindler, Peter Vataščin
- 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 non-trivial algorithms and to evaluate their effectivity.
- 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, 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
- Syllabus of tutorials:
-
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
- Study Objective:
-
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.
- 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, Mcgraw-Hill Higher Education, 2006,
[3] Robert Sedgewick: Algoritms in v C, parts 1-4, Addison-Wesley Professional; 3rd edition (1997)
- Note:
- Further information:
- https://alg.fel.cvut.cz/
- Time-table for winter semester 2025/2026:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Mon Tue Wed Thu Fri - Time-table for summer semester 2025/2026:
- Time-table is not available yet
- The course is a part of the following study plans:
-
- Open Informatics - Computer Science 2016 (compulsory course in the program)
- Open Informatics - Internet of Things 2016 (compulsory course in the program)
- Open Informatics - Software 2016 (compulsory course in the program)
- Open Informatics - Computer Games and Graphics 2016 (compulsory course in the program)
- Open Informatics (compulsory course in the program)
- Medical electronics and bioinformatics (compulsory elective course)
- Open Informatics (compulsory course in the program)
- Open Informatics - Artificial Intelligence and Computer Science 2018 (compulsory course in the program)
- Open Informatics - Internet of Things 2018 (compulsory course in the program)
- Open Informatics - Software 2018 (compulsory course in the program)
- Open Informatics - Computer Games and Graphics 2018 (compulsory course in the program)
- Open Informatics (compulsory course in the program)
- Open Informatics - Artificial Intelligence and Computer Science 2025 (compulsory course in the program)
- Open Informatics - Internet of Things 2025 (compulsory course in the program)
- Open Informatics - Software 2025 (compulsory course in the program)
- Open Informatics - Computer Games and Graphics 2025 (compulsory course in the program)