Algorithms

Relations:

It is not possible to register for the course BE5B33ALG if the student is concurrently registered for or has already completed the course B4B33ALG (mutually exclusive courses).

In order to register for the course BE5B33ALG, the student must have registered for the required number of courses in the group BEZBM no later than in the same semester.

The requirement for course BE5B33ALG can be fulfilled by substitution with the course B4B33ALG.

Course guarantor:

Daniel Průša

Lecturer:

Robert Pěnička

Tutor:

Robert Pěnička, Daniel Průša, Martin Zoula

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 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.

Requirements:

Programming 1

Syllabus of lectures:

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

Syllabus of tutorials:

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

Study Objective:

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.

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://cw.fel.cvut.cz/wiki/courses/BE5B33ALG

Time-table for winter semester 2025/2026:

Time-table is not available yet

Time-table for summer semester 2025/2026:

Time-table is not available yet

The course is a part of the following study plans:

• Electrical Engineering and Computer Science (EECS) (compulsory course in the program)
• Electrical Engineering and Computer Science (EECS) (compulsory elective course)