After successful completion of the course, students are able to follow current developments in the research on algorithms and complexity, building on existing knowledge to algorithms and data structures and tying in with complexity theory and various application domains (e.g. network design, geometric problems, algorithms on planar graphs.) Students will be able to - explain notions and basic problems from the course; - describe formally and explain intuitively fine-grained complexity assumptions and their consequences; - describe formally and intuitively, analyze and prove properties of algorithms for selected hard problems; - design and analyze their own algorithms for unknown algorithmic problems using techniques from the course; - describe and explain the frontiers of current results in algorithms and complexity - gain understanding of current results and their context on their own.
In WS2024, the course will focus on Approximation Algorithms based on Local Search.
The course addresses recent developments in algorithms research, their context within existing literature and the frontiers of current knowledge.
In WS2024, the course will focus on Approximation Algorithms based on Local Search. Topics will include, e.g., search complexity classes, theoretical analysis of local search algorithms in terms of lower and upper bound guarantees for solution quality and running time. The considered problems will include Max-Cut and the Traveling Salesman Problem, among others.
The course is held in lectures covering topics at the frontierof algorithms and complexity research. They take place in a seminar-like setting and are interactive, so students are expected to engage in classroom discussion. Every technique introduced in the course is demonstrated on several examples.
The grade is based on a short oral exam on the topics covered by the course. The students are allowed to choose one topic to focus on during the exam. In particular, the exam can also be taken in the form of a presentation of a current research article covering a topic from the course.