SUBJECT
Title
Design, analysis and implementation of algorithms and data structures I
Type of instruction
lecture
Level
master
Faculty
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.