Prerequisities

There are no formal requirements. However you are expected to know basic graph algorithms and datastructures, to the  extent covered by the course IV003 Algorithms and Data Structures II. More specifically, these graph algorithms and datastructures:

• Graph searching: DFS, BFS.
• Network flows: Ford-Fulkerson, Golderg (push-relabel).
• Minimum spanning trees: Kruskal, Jarník (Prim), Borůvka.
• Shortest paths: Bellman-Ford, Dijkstra.
• Datastructures: heaps (incl. Fibonacci), disjoint set (union-find), ...

Exam

There will be only a final written exam, no grading throughout the semester. The questions will be in English, but (on some dates) you are allowed to answer in Czech if you prefer to. 

Final exam: there will be one chance to take the exam in the last week of the semester, otherwise multiple dates in the exam period, as usual.

You are allowed to complete the course with colloqium (k) or zápočet (z) if you prefer to.

Tutorials

2 hrs every second week of the semester. Attendance is compulsory, but you are allowed to miss one without giving any reason.

Tutors: Jan Obdržálek, Frédéric Dupont Dupuis

Literature

There is no single book which covers the entire course. For each lecture I'll be giving a list of papers/book chapters which cover the topic. The papers will be mostly research or survey paper freely available to students of this course. Some general books:

• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms
• J. Kleinberg, E. Tardös: Algorithm Design
• D. Kozen: Design and Analysis of Algorithms
• R. Tarjan: Data Structures and Network Algorithms