Algorithms

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:

Marko Genyk-Berezovskyj

Lecturer:

Marko Genyk-Berezovskyj, Daniel Průša

Tutor:

Marko Genyk-Berezovskyj, Jiří Němeček, 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, 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

10. Linked lists, linearly-linked list

11. Tree construction, tree search

12. Test, consultation to semester task

13. Algorithms of linear algebra and geometry, mathematical analysis

14. Credit

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

Time-table for winter semester 2024/2025:

	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	roomKN:E-310 Ševic J. 11:00–12:30 (lecture parallel1 parallel nr.105) Karlovo nám.
Tue	roomKN:E-132 Němeček J. 11:00–12:30 (lecture parallel1 parallel nr.102) Karlovo nám. roomKN:E-230 Ševic J. 16:15–17:45 (lecture parallel1 parallel nr.101) Karlovo nám. roomKN:E-230 Němeček J. 12:45–14:15 (lecture parallel1 parallel nr.104) Karlovo nám.
Wed	roomKN:E-230 Šindler P. 07:30–09:00 (lecture parallel1 parallel nr.106) Karlovo nám. roomKN:E-230 Šindler P. 09:15–10:45 (lecture parallel1 parallel nr.103) Karlovo nám.
Thu
Fri	roomT2:C3-132 Genyk-Berezovskyj M. Průša D. 11:00–12:30 (lecture parallel1) Dejvice roomKN:E-327 Vataščin P. 14:30–16:00 (lecture parallel1 parallel nr.107) Karlovo nám. roomKN:E-107 Genyk-Berezovskyj M. Průša D. 11:00–12:30 (lecture parallel1) Karlovo nám. roomKN:E-327 Šindler P. 12:45–14:15 (lecture parallel1 parallel nr.108) Karlovo nám.

Time-table for summer semester 2024/2025:

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)