CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2023/2024

# Algorithms

Code Completion Credits Range Language
BE5B33ALG Z,ZK 6 2P+2C English

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.

Garant předmětu:
Marko Genyk-Berezovskyj
Lecturer:
Marko Genyk-Berezovskyj
Tutor:
Marko Genyk-Berezovskyj
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. Recursion, recurrence, Master theorem

3. Trees, binary trees, backracking

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, 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.One-dimensional 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

11.Tree construction, tree search

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, 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 2023/2024:
 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 roomKN:E-126Genyk-Berezovskyj M.12:45–14:15(lecture parallel1)Karlovo nám.Trnkova posluchárna K5roomKN:E-126Genyk-Berezovskyj M.14:30–16:00(lecture parallel1parallel nr.101)Karlovo nám.Trnkova posluchárna K5
Time-table for summer semester 2023/2024:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2024-04-23
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/en/predmet4356206.html