Lecturer(s)
|
-
Chládek Petr, Mgr. Ph.D.
-
Houda Michal, 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. Viz https://moodle.ef.jcu.cz/course/view.php?id=1827
|
Learning activities and teaching methods
|
Monologic (reading, lecture, briefing), Dialogic (discussion, interview, brainstorming)
|
Learning outcomes
|
The course is aimed at algorithmic problems on discrete structures. The computational complexity and various applications are emphasized. The course is instructed in English.
The ability of algorithmisation of a gertain class of practical problems. The utilization of IT for solving problems on discrete structures. The student is able to communicate in English.
|
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.
|