The courses "Foundations of Computer Science" cover material that all students of computer science should know. The courses are self study courses and based on material which we assume that students know from their Bachelor program. The main aim of these courses is to ensure that all our Master students have a solid knowledge all over computer science and not just in their area of expertise.

Flows in networks: algorithms of Ford-Fulkerson, Edmonds-Karp and Goldberg-Tarjan; matching problems: algorithm of Hopcroft-Karp, blossom algorithm of Edmonds; primal-dual method and its application for matching problems; planar graphs: linear testing algorithm, drawing of planar graphs; separators for trees and planar graphs and its applications; treewidth and tree decomposition.

Connectivity (block decomposition, Menger), Matching for bipartite graphs (Hall, König, Hopcroft-Karp algorithm, Hungarian method), Hamilton cycles (Dirac), Planar graphs (Euler’s formula, 5-coloring, planarity testing (in quadratic time)), Graph Coloring (Greedy, Brooks, Vizing, Hadwiger’s conjecture), Extremal Graph Theory (Ramsey, Turan)

Students present current or classical results from theoretical computer science.

Las-Vegas & Monte-Carlo alg; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks

Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks

The aim of the seminar is to study papers which bring the students to the forefront of today's research topics. Each semester we will focus on a different topic. This semester we study probabilistic results on networks and distributed algorithms.

The aim of the seminar is to study papers which bring the students to the forefront of today's research topics. This semester we will study selected papers of the conference Symposium on Discrete Algorithms (SODA22).

Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.

Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.