SUBJECT

Title

Design, analysis and implementation of algorithms and data structures I

Type of instruction

lecture

Level

master

Part of degree program
Credits

3+3

Recommended in

Semesters 1-4

Typically offered in

Autumn/Spring semester

Course description
  • Maximum adjacency ordering and its applications. Sparse certificates for connectivity. Minimum cost arborescence. Degree constrained orientations of graphs. 2-SAT. Tree-width, applications. Gomory-Hu tree and its application. Steiner tree and traveling salesperson.
  • Minimum cost flow and circulation, minimum mean cycle.
  • Matching in non-bipartite graphs, factor-critical graphs, Edmonds’ algorithm. Structure theorem of Gallai and Edmonds. T-joins, the problem of Chinese postman.
  • On-line algorithms, competitive ratio.
Readings
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, McGraw-Hill, 2002.
  • A. Schrijver: Combinatorial Optimization, Springer-Verlag, 2002.
  • Robert Endre Tarjan: Data Structures and Network Algorithms , Society for Industrial and Applied Mathematics, 1983.
  • Berg-Kreveld-Overmars-Schwarzkopf: Computational Geometry: Algorithms and Applications , Springer-Verlag, 1997.