Syllabus

• Complexity of problems and algorithms
• Basics of algorithm analysis,  amortized analysis
• Data structures:  Fibonacci heaps, data structures for disjoint sets
• Divide-and-Conquer: the maximum element problem, finding the closest pair of points  
• Dynamic programming: scheduling, edit distance, shortest paths, knapsack problem, subset sum problem 
• Greedy algorithms: scheduling, shortest paths, spanning trees
• Network flow
• String matching 

Prerequisites and entrance test

The course can be enrolled only after completion of the course IB002 Algoritmy a datové struktury I. Enrolment for students with a bachelor degree from other universities is possible on the assumption they have a basic command of algorithms and data structures encompassing the course IB002 (please, apply for the enrolment permission in the Information System).

All students are kindly asked to fill the ROPOT  (odpovědník) Vstupní test  (not later than on Monday, February 24). Completion of the ROPOT is compulsory, however, the results do not count towards the grade. The main purpose of the ROPOT is to self-evaluate your knowledge about algorithms required for the enrolment. If you are not successful, please consider enrolling the course IB002. In case you do not answer the ROPOT, -10 points will be added to your evaluation of the written test. 

Course completion requirements 

Sets of problems 

During the term, the student solves three sets of problems. The maximum number of points one can acquire from these sets is 200. 

Written test

The maximum number of points one can acquire from the written test is 100.  To complete the course it is necessary to acquire at least 60 of the 100 points.   

Both written test and sets can be completed in Czech/Slovak language.

Grading scheme

Grades are proportionate to the sum of points from sets of problems and written test.  
>= 260 points  --- grade A
>= 240 points  --- grade B
>= 220 points  --- grade C
>= 200 points  --- grade D
>= 180 points  --- grade E
<= 179 points  --- grade F