Lecturer(s)
|
-
Maňák Martin, Mgr. Ph.D.
-
Kopčil Jakub
-
Pražák Ondřej, Ing.
|
Course content
|
1. Introduction to algorithmization, Turing machines, decision problems, algorithmic undecidability 2. Problem complexity classes P, NP, NP-completeness 3. Sorting, classical algorithms, their variants and analysis, complexity of the sorting problem 4. Divide and conquer, methods of solving recurrence relations 5. Dynamic programming I 6. Dynamic programming II 7. Backtracking method 8. Principles of graph algorithms I (Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal) 9. Principles of graph algorithms II (strongly connected components, network flows, cuts, Ford-Fulkerson) 10. Tree structures - representation of intervals, prefix sums, and disjoint sets 11. Compression (RLE, LZW, Huffman, arithmetic coding, DCT - JPEG, wavelets) 12. Text processing algorithms - substring search, Trie 13. Reserve
|
Learning activities and teaching methods
|
- unspecified
- 17 hours per semester
- Contact hours
- 65 hours per semester
- Preparation for formative assessments (2-20)
- 12 hours per semester
- Preparation for comprehensive test (10-40)
- 20 hours per semester
- Preparation for an examination (30-60)
- 42 hours per semester
|
prerequisite |
---|
Knowledge |
---|
asymptotic complexity |
fundamental knowledge how basic data structures work (array, heap, stack, queue, linked list, tree) and the complexity of related operations |
representation of graphs and basic graph search algorithms |
Skills |
---|
basic programming skills |
recursive function call |
common use of basic data structures |
Competences |
---|
N/A |
N/A |
N/A |
N/A |
N/A |
learning outcomes |
---|
Knowledge |
---|
general methods for algorithm design |
principles of algorithms and data structures discussed in the course |
complexity classes P and NP, NP-completeness, polynomial transformation, solution methods |
Skills |
---|
utilization of general methods for algorithm design |
analysis of computational complexity |
the ability to actually program an algorithm |
the ability to classify an algorithm with respect to the general design methods |
to recognize NP-complete problems |
Competences |
---|
N/A |
N/A |
teaching methods |
---|
Knowledge |
---|
Lecture with visual aids |
Task-based study method |
Skills demonstration |
Self-study of literature |
One-to-One tutorial |
Discussion |
Lecture |
Skills |
---|
Lecture |
Lecture supplemented with a discussion |
Interactive lecture |
Task-based study method |
Skills demonstration |
One-to-One tutorial |
Discussion |
Competences |
---|
Lecture |
Lecture supplemented with a discussion |
Interactive lecture |
Task-based study method |
Skills demonstration |
One-to-One tutorial |
Discussion |
assessment methods |
---|
Knowledge |
---|
Oral exam |
Skills |
---|
Written exam |
Test |
Continuous assessment |
Competences |
---|
Oral exam |
Written exam |
Test |
Continuous assessment |
Recommended literature
|
-
Halim, Steven; Halim, Felix. Competitive programming 3 : the new lower bound of programming contests : handbook for ACM ICPC and IOI contestants. [3.ed.]. [S.l.] : Lulu, 2013.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
|