FI:MA015 Graph Algorithms - Course Information

MA015 Graph Algorithms

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)
RNDr. Václav Brožek, Ph.D. (seminar tutor)
prof. RNDr. Luboš Brim, CSc. (assistant)

Guaranteed by

doc. RNDr. Libor Polák, CSc.
Departments – Faculty of Science
Contact Person: doc. RNDr. Libor Polák, CSc.

Timetable

Tue 14:00–15:50 A107

• Timetable of Seminar Groups:

MA015/01: Tue 16:00–16:50 B003, L. Polák
MA015/02: Thu 12:00–12:50 B410, V. Brožek
MA015/03: Tue 17:00–17:50 B003, V. Brožek

Prerequisites

MB005 Foundations of mathematics ||( MB101 Mathematics I && MB102 Mathematics II )|| M005 Foundations of mathematics
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

• Applied Informatics (programme FI, N-AP)
• Information Technology Security (programme FI, N-IN)
• Bioinformatics (programme FI, N-AP)
• Information Systems (programme FI, N-IN)
• Informatics (programme FI, M-IN)
• Informatics (programme FI, N-IN)
• Mathematical Informatics (programme FI, B-IN)
• Parallel and Distributed Systems (programme FI, N-IN)
• Computer Graphics (programme FI, N-IN)
• Computer Networks and Communication (programme FI, N-IN)
• Computer Systems (programme FI, N-IN)
• Embedded Systems (eng.) (programme FI, N-IN)
• Theoretical Informatics (programme FI, N-IN)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-SS)
• Upper Secondary School Teacher Training in Informatics (programme FI, M-TV)
• Upper Secondary School Teacher Training in Informatics (programme FI, N-SS) (2)
• Artificial Intelligence and Natural Language Processing (programme FI, N-IN)
• Image Processing (programme FI, N-AP)

Course objectives

Basic graph algorithms are presented: searches, algorithms for minimal spanning trees, various algorithms for shortest paths and flows in nets.In all cases we prove the correctness and estimate the complexity.

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

Assessment methods (in Czech)

Standardní přednáška. Ve cvičení studenti referují řešení předem zadaných úloh. Zkouška je písemná.

Language of instruction

Czech

Further Comments

The course is taught annually.

Teacher's information

http://www.math.muni.cz/~polak/grafy.html

• Enrolment Statistics (Autumn 2007, recent)
  
• Permalink: https://is.muni.cz/course/fi/autumn2007/MA015