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