Aug 25, 2019   8:46 a.m. Ľudovít

# Course syllabus B-AZA - Analysis and complexity of algorithms (FEEIT - SS 2018/2019)

Information sheet          ECTS          Syllabus

Slovak          English

University: 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:
 lecture 2 hours weekly (on-site method) seminar 2 hours weekly (on-site method)

Credits allocated: 5

Recommended semester/trimester: -- item not defined --
Level of study: 1.
Prerequisites for registration: none

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

Notes:

Courses evaluation:
Assessed students in total: 669

ABCDEFX
6,9 %8,1 %12,9 %22,0 %37,1 %13,0 %
Name of lecturer(s): doc. Ing. Milan Vojvoda, PhD. (examiner, instructor, lecturer, person responsible for course) - slovak, english

Last modification: 21. 3. 2019
Supervisor: doc. Ing. Milan Vojvoda, PhD. and programme supervisor

Last modification made by RNDr. Marian Puškár on 03/21/2019.

 Type of output: PDF output (PDF)Document RTF (RTF)XML format for IS (XML IL)