FI:MA015 Graph Algorithms - Course Information
MA015 Graph Algorithms
Faculty of InformaticsAutumn 2021
- Extent and Intensity
- 2/1/0. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
- Teacher(s)
- doc. Mgr. Jan Obdržálek, PhD. (lecturer)
- Guaranteed by
- doc. Mgr. Jan Obdržálek, PhD.
Department of Computer Science – Faculty of Informatics
Supplier department: Department of Computer Science – Faculty of Informatics - Timetable
- Mon 13. 9. to Mon 6. 12. Mon 12:00–13:50 A320
- Timetable of Seminar Groups:
- Prerequisites
- MB005 Foundations of mathematics ||( MB101 Mathematics I && MB102 Calculus )||( MB201 Linear models B && MB102 Calculus )||( MB101 Mathematics I && MB202 Calculus B )||( MB201 Linear models B && MB202 Calculus B )||( PřF:M1120 Discrete Mathematics )|| PROGRAM ( N - IN )|| PROGRAM ( N - AP )
Knowledge of basic graph algorithms and datastructures. Specifically, students should already understand the following datastructures and algorithms: Graphs searching: DFS, BFS. Network flows: Ford-Fulkerson. Minimum spanning trees: Boruvka, Jarnik (Prim), Kruskal. Shortest paths: Bellman-Ford, Dijkstra. Datastructures: priority queues, heaps (incl. Fibonacci), disjoint set (union-find) - Course Enrolment Limitations
- The course is also offered to the students of the fields other than those the course is directly associated with.
- fields of study / plans the course is directly associated with
- there are 26 fields of study the course is directly associated with, display
- Course objectives
- The course introduces graph important algorithms beyond the reach of standard algorithms and data structures courses. Covered algorithms span most of the important application areas of graphs algorithms.
- Learning outcomes
- At the end of the course students will under know and understand important graph algorithms beyond the reach of standard algorithms and data structures courses. Covered algorithms span most of the important application areas of graphs algorithms. The students also should be able to choose an algorithm best suited for a given task, modifying it when necessary, and estimate its complexity.
- Syllabus
- Minimum Spanning Trees. Quick overview of basic algorithms (Kruskal, Jarník [Prim], Borůvka) and their modifications. Advanced algorithms: Fredman-Tarjan, Gabow et al. Randomized algorithms: Karger-Klein-Tarjan. Arborescenses of directed graphs, Edmond's branching algorithm.
- Flows in Networks. Revision - Ford-Fulkerson. Edmonds-Karp, Dinic's algorithm (and its variants), MPM (three Indians) algorithm. Modifications for restricted networks.
- Minimum Cuts in Undirected Graphs. All pairs flows/cuts: Gomory-Hu trees. Global minimum cut: node identification algorithm (Nagamochi-Ibaraki), random algorithms (Karger, Karger-Stein)
- Matchings in General Graphs. Basic algorithm using augmenting paths. Perfect matchings: Edmond's blossom algorithm. Maximum matchings. Min-cost perfect matching: Hungarian algorithm.
- Dynamic Algorithms for Hard Problems. Dynamic programming on trees and circular-arc graphs. Tree-width; dynamic programming on tree-decompositions.
- Graph Isomorphism. Colour refinement. Individualisation-refinement algorithms. Tractable classes of graphs.
- Literature
- Teaching methods
- Lecture 2 hrs/week plus tutorial every other week.
- Assessment methods
- Written exam. To obtain A or B students also have to pass the second, oral part of the exam.
- Language of instruction
- English
- Further Comments
- Study Materials
The course is taught annually.
- Enrolment Statistics (Autumn 2021, recent)
- Permalink: https://is.muni.cz/course/fi/autumn2021/MA015