|
Lecturer(s)
|
-
Houda Michal, Mgr. Ph.D.
-
Chládek Petr, Mgr. Ph.D.
|
|
Course content
|
Topics: 1. Introduction, motivation problems, time and memory complexity of algorithms. 2. Search and sorting (direct and indirect methods and their complexity). 3. Data structures (binary trees, heaps, etc.). 4. Basic graph algorithms (representation of graphs, width search and depth search). 5. Search for the shortest path (Dijkstr algorithm, Floyd-Warshall algorithm, etc.). 6. Minimum spanning tree problem (Borůvka's, Kruskal's and Jarník's algorithms) . 7. Binary search trees (some operations with these data structures). 8. Divide and conquer algorithms (several methods using recursive techniques). 9. Search in text. 10. Flow networks (maximal flow problem, Hall's theorem) 11. Flow networks (Ford-Fulkerson's algorithm, Dinic's algorithm) 12. Complexity of problems, P and NP problems. 13. Discete Fourier transform.
|
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming)
- Class attendance
- 42 hours per semester
- Preparation for classes
- 36 hours per semester
- Semestral paper
- 40 hours per semester
- Preparation for credit
- 30 hours per semester
- Preparation for exam
- 20 hours per semester
|
|
Learning outcomes
|
The course is aimed at algorithmic problems on discrete structures. The computational complexity and various applications are emphasized.
The ability of algorithmisation of a gertain class of practical problems. The utilization of IT for solving problems on discrete structures.
|
|
Prerequisites
|
Basic knowledge of discrete mathematics and algorithm theory.
|
|
Assessment methods and criteria
|
Student performance assessment, Combined exam
Submission of 5 short tasks (programming of solution of certain problems using some of the discussed techniques). Active participation on practicals. Final oral exam (algorithmization of chosen problem). Instead of taking the final exam, student can also choose to work out a project (more sofisticated program, including documentation, which he/she presents to others).
|
|
Recommended literature
|
-
GAREZ, M. R. a D. S. JOHNSON. Computers and Intractibility. New York, 1979.
-
KREHER, L. D. Combinatorial Algorithms. New York, 1999.
-
KUČERA, L. Kombinatorické algoritmy. Praha, 1983.
-
Mareš M., Valla T. Průvodce labyrintem algoritmů. Praha, 2017. ISBN 978-80-88168-22-5.
-
Topfer, P. Algoritmy a programovací techniky. Praha, 2010. ISBN 978-80-7196-350-9.
|