Sep 26, 2020   11:15 a.m. Edita
Academic information system

Course syllabus B-AZA - Analysis and complexity of algorithms (FEEIT - WS 2019/2020)

     Information sheet          ECTS          Syllabus          

     Slovak          English          

Slovak University of Technology in Bratislava
Faculty: Faculty of Electrical Engineering and Information Technology
Course unit code: B-AZA
Course unit title:
Analysis and complexity of algorithms
Mode of delivery, planned learning activities and teaching methods:
2 hours weekly (on-site method)
2 hours weekly (on-site method)

Credits allocated:
Recommended semester/trimester:
Applied Informatics - bachelor (compulsory), 5. semester
Level of study: 1.
Prerequisites for registration:
Assesment methods:
There are 2 written tests during the semester, 20 points per each. It is necessary to obtain at least 20 points from these tests (to get the opportunity to write the exam).
Then 60 points can be obtained at the written exam. To get the degree A, it is neccesary to obtain at least 92 points, at least 83 points to get degree B, at least 74 points to get degree C, at least 65 points to get degree D, and at least 56 points to get degree E. The credits are not assigned to a student, that obtained less than 56 points.
Learning outcomes of the course unit:
The students get konwledge on basic algorithms in computer science, graph theory, number theory, and cryptology. The students get practical experiences in analysis of algorithms and determination of their computational complexity. The students are able to analyse algorithms, determine their computational/memory complexities and can compare the complexity of algorithms.
Course contents:
1. Algorithm. Computational complexity. Comparing the growth of functions.
2. Sums.
3. Recurrences.
4. Sorting.
5. Independent sets and graph colouring.
6. Maximum flow I.
7. Matrix operations.
8. Number-theoretic algorithms.
9. String matching I.
10. String matching II.
11. Complexity classes I.
12. Complexity classes II.
Recommended or required reading:
Agnarsson, G., Greenlaw, R.: Graph Theory. Modeling, Applications, and Algorithms. Pearson Education, 2007.
Cormen, T.H., Leiserson, C.E., Rivest, R.R., Stein, C.: Introduction to Algorithms. 2nd edition, MIT Press, 2003.
Hromkovič, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. 2nd edition, Springer, 2004.
Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, 1994.
Wilf, H.S.: Algorithms and Complexity. J. Wiley, New York, 1986.

Language of instruction:
slovak or english
Courses evaluation:
Assessed students in total: 851

6,9 %
8,1 %13,9 %23,4 %
36,7 %
11,0 %
Name of lecturer(s):
doc. Ing. Milan Vojvoda, PhD. (examiner, instructor, lecturer, person responsible for course) - slovak, english
Last modification:
6. 5. 2019
doc. Ing. Milan Vojvoda, PhD. and programme supervisor

Last modification made by RNDr. Marian Puškár on 05/06/2019.

Type of output: