MA015 Graph Algorithms

Faculty of Informatics
Autumn 2014
Extent and Intensity
2/1. 3 credit(s) (plus extra credits for completion). Recommended Type of Completion: zk (examination). Other types of completion: k (colloquium).
Teacher(s)
doc. RNDr. Libor Polák, CSc. (lecturer)
Alexandru Popa, Ph.D. (seminar tutor)
Mgr. David Kruml, Ph.D. (assistant)
Guaranteed by
doc. RNDr. Libor Polák, CSc.
Faculty of Informatics
Contact Person: doc. RNDr. Libor Polák, CSc.
Supplier department: Faculty of Science
Timetable
Mon 14:00–15:50 D2
  • Timetable of Seminar Groups:
MA015/01: Wed 12:00–12:50 C525, A. Popa
MA015/02: Wed 13:00–13:50 A319, A. Popa
MA015/03: Wed 14:00–14:50 A218, A. Popa
MA015/04: Mon 16:00–16:50 B410, L. Polák
Prerequisites
MB005 Foundations of mathematics ||( MB101 Linear models && MB102 Calculus )||( PřF:M1120 Discrete Mathematics )||PROGRAM(N-IN)||PROGRAM(N-AP)
Ability of communication about basic mathematical objects and algorithms.
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 23 fields of study the course is directly associated with, display
Course objectives
The students will understand numerous basic algorithms concerning search in graphs, spanning trees, shortest paths in deep. They will be able to design own correct algorithms to new problems end estimate their complexities.
Syllabus
  • Elementary graph algorithms (representations of graphs, breadth-first search, depth-first search, topological sort, strongly connected components).
  • Minimum spanning trees (growing a minimum spanning tree, the algorithms of Kruskal and Prim).
  • Single-source shortest paths (shortest paths and relaxation, Dijkstra's algorithm, the Bellman--Ford algorithm, single--source shortest paths in directed acyclic graphs).
  • All-pairs shortest paths (shortest paths and matrix multiplication, the Floyd-Warshall algorithm, Johnson's algorithm for sparse graphs).
  • Maximum flow (flow networks, the Ford-Fulkerson method, maximum bipartite matching).
  • Data structures for graph algorithms (binary heaps, priority queues, data structures for disjoint sets).
Literature
  • CORMEN, Thomas H., Charles Eric LEISERSON and Ronald L. RIVEST. Introduction to algorithms. Cambridge: MIT Press, 1990, xi, 1028. ISBN 0262031418. info
Teaching methods
Once a week a two hour standard lecture. In consequential seminars (one hour) students report on problems which are given them in advance.
Assessment methods
Written exam. 30% of points are given for a solution of a concrete problem using one of given algorithms. The essential part is a pre-processed new problem. The students complete the missing part of the algorithm, they demonstrate it on a concrete data, they prove its correctness and they estimate its complexity.
Language of instruction
Czech
Further Comments
Study Materials
The course is taught annually.
Teacher's information
http://www.math.muni.cz/~polak/grafy.html
The course is also listed under the following terms Spring 2003, Autumn 2003, Autumn 2004, Autumn 2005, Autumn 2006, Autumn 2007, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Autumn 2012, Autumn 2013, Autumn 2015, Autumn 2016, Autumn 2017, Autumn 2018, Autumn 2019, Autumn 2020, Autumn 2021, Autumn 2022, Autumn 2023, Autumn 2024.
  • Enrolment Statistics (Autumn 2014, recent)
  • Permalink: https://is.muni.cz/course/fi/autumn2014/MA015