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.
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 goal of this course is to practice solving a large algorithmic problem and to practice implementing and experimentally investigating solutions to algorithmic problems. A second goal is to practice various professional skills, such as working effectively in a team, planning, technical writing and presenting.
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.
In this course we study a topic that is on the cutting edge of algorithms research. We will study recent literature on the topic through lectures, given by the students and through writing a report on a specific aspect of the topic. Topics studied in this course vary and usually lie close to the algorithms group's research interests and to (some of) the topics of graduation projects that can be realized within the algorithms group. 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 page or contact the instructor.