The following courses are taught by staff members of our group.
Many real-world algorithmic problems cannot be solved efficiently using traditional algorithmic tools, for example because the problems are NP-hard, or because the data does not fit into main memory or is not completely available when the computation starts. The goal of this course is to become familiar with important algorithmic concepts and techniques needed to effectively deal with such problems.
The data structures course (2IL50) teaches how to store data in memory so that it can be analyzed and manipulated in a provably efficient way. This follow-up course Algorithms focuses on the design and analysis of provably efficient algorithms to solve optimization problems such as finding shortest paths in a network, or comparing the similarity of two strings of DNA. We also study computational complexity theory to prove that some problems cannot be solved efficiently.
A significant part of today's data is geographic, has a geographic component (is geo-referenced), or benefits from geographic interpretation. To analyze these data requires advanced algorithmic tools. This course takes a data-driven perspective on algorithm design for geographic data. The course has three parts:
The goal of this Capita Selecta is to treat a number of modern topics that did not yet find a place in the regular courses. The form, contents and way of examination is dependent on the topic and will be determined separately for each student attending this course. In case of interest in this course it is advisable to contact the responsible teacher.
The main objective of this course is to learn basic skills and knowledge to design efficient algorithms and data structures and to analyze their complexity. Students will learn about basic algorithms and data structures, and how to select an algorithm or data structure for a given task.
In addition, students will learn how to design simple algorithms using techniques like incremental algorithms and divide&conquer and how to evaluate algorithms and data structures in terms of their efficiency.
How can we automatically put labels (like city names) on a map such that the labels do not overlap? How can we compute train schedules that optimally use the available tracks and trains? How can we reconstruct 3D objects from laster scans? These are just a few examples of challenging problems that require efficient algorithmic solutions and effective software implementations of those solutions. In this course you will attack such an algorithmic problem in a team of five or six students.
Students learn in Algorithms (2ILC0) that many computational problems are NP-hard. It is widely believed that for such problems, no algorithm exists that always finds the optimal solution efficiently (in polynomial time). One way to deal with NP-hard problems is to use approximation algorithms, as discussed in Advanced Algorithms (2IMA10), or to apply heuristics. However, it is of great practical and theoretical relevance to investigate under which circumstances computing exact solutions is still feasible. This leads to the concept of parameterized algorithms, and parameterized complexity. The idea is to do a more refined complexity analysis, which not only takes the input size (n) into account, but also a second parameter (k) which somehow captures the "structure" or "difficulty" of the input instance. The goal is then to develop so-called FPT algorithms (for Fixed-Parameter Tractable), for which the exponential dependency of the running time (which is most likely unavoidable for NP-hard problems) is not on the input size n, but only on the parameter k. Such algorithms are provably efficient on "easy instances", despite the NP-hardness of the problem. There is a wide variety of algorithmic techniques for designing FPT algorithms for NP-hard problems. However, there are also problems for which (for the given parameterization) FPT algorithms do not exist (under appropriate complexity-theoretic assumptions such as P!=NP). The goal of the course is to teach techniques to design FPT algorithms, as well as techniques that can be used to prove that FPT algorithms do not exist.
In many areas of computer science such as robotics, computer graphics, virtual reality, and geographic information systems, it is necessary to store, analyze, and create or manipulate spatial data. This course deals with the algorithmic aspects of these tasks: we study techniques and concepts needed for the design and analysis of geometric algorithms and data structures. Each technique and concept will be illustrated on the basis of a problem arising in one of the application areas mentioned above.
What is a proof, or in other words: how do you establish the truth? How do you distinguish good, reliable literature from bad, unreliable sources? What are essential elements of a good title, abstract, and introduction for your Master's theses and presentation, so that you can capture the readers' interest? Can you summarize and present numbers in charts and tables in such a way that the data, not the statistical methods and the graphic design, determine what trends you observe? How can you deal with conflicting ethical norms that society imposes on you as a researcher or engineer? These are the main questions addressed in this course.
The course covers problems, techniques and results from a specific area of algorithm design. For example, in the past years we discussed how to draw graphs automatically such that certain aesthetic or technical criteria are optimized, and how to place observation or cell phone towers on a terrain for best coverage. For up-to-date information about this year's topics, check the course website or contact the instructor.