Course Contents
Graph theory, growth of functions and asymptotic analysis of complexity, algorithms for spanning trees, shortest paths, matchings in bipartite graphs and flows in directed graphs, NP-completeness, searching and sorting.
Possible additional topics: coding/cryptography, more graph algorithms, e.g., min-cost flows
Literature
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to algorithms, 2. Auflage, B&T, 2001.
B. Korte, J. Vygen: Combinatorial Optimization, Springer 2012.
J. Matoušek, J. Nešetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
Preconditions
recommended: Analysis, Linear Algebra
Online Offerings
Moodle
Graph theory, growth of functions and asymptotic analysis of complexity, algorithms for spanning trees, shortest paths, matchings in bipartite graphs and flows in directed graphs, NP-completeness, searching and sorting.
Possible additional topics: coding/cryptography, more graph algorithms, e.g., min-cost flows
Literature
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to algorithms, 2. Auflage, B&T, 2001.
B. Korte, J. Vygen: Combinatorial Optimization, Springer 2012.
J. Matoušek, J. Nešetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
Preconditions
recommended: Analysis, Linear Algebra
Online Offerings
Moodle
- Lehrende: Yann Disser
- Lehrende: Nils Mosis
Semester: ST 2024