Manuel Wettstein: Catalogue data in Spring Semester 2024 
Name  Dr. Manuel Wettstein 
Address  Gärtner, Bernd (Tit.Prof.) ETH Zürich, CAB G 19.1 Universitätstrasse 6 8092 Zürich SWITZERLAND 
manuelwe@inf.ethz.ch  
Department  Computer Science 
Relationship  Lecturer 
Number  Title  ECTS  Hours  Lecturers  

252084200L  Introduction to Programming and Problem Solving Belegungsfrist: 16.02.2024  3 credits  2V + 1U  D. Komm, M. Dahinden, M. Wettstein  
Abstract  Core concepts of Computer Science and their implementation in Python.  
Learning objective  The goals of the course are consolidating the knowledge about the programming language Python on the one hand, and learning about core concepts of computer science that are essential in algorithm design on the other hand. The focus is on computational thinking, that is, the ability to solve problems systematically by developing algorithms. Different strategies are introduced, analyzed theoretically, and implemented in Python. The combination of theory and practice is central in this course.  
Content   Repetition of basic programming concepts such as variables, lists, control structures, and loops  Reading in and visualizing data  Complexity theory  Sorting and searching  Dynamic programming  Recursion  Graph algorithms  
Lecture notes  Moodle: https://moodleapp2.let.ethz.ch/course/view.php?id=21917 Lecture website: https://courses.csedu.inf.ethz.ch/ppl2024/  
Literature  The slides will be available for download on the course website.  
Prerequisites / Notice  Recommendation:  Foundations of Computer Science (252085200) or  Application Oriented Programming Using Python (252084002)  
Competencies 
 
252491100L  Algorithms for Geometric Problems The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar.  2 credits  2S  R. Kralovic, M. Wettstein  
Abstract  We discuss a selection of simple combinatorial algorithms for geometric problems. Such algorithms and problems are characterized by the fact that they deal with geometric primitives such as points and lines, for example in the Euclidean plane.  
Learning objective  To get an overview over some of the fundamental problems in computational geometry. To get a taste of the relevant techniques and the challenges that arise when designing algorithms for geometric problems. To get some experience in giving a clear, accurate, and hopefully exciting presentation in front of a live audience.  
Content  In this seminar, we will give an overview over some of the basic problems and techniques that are relevant to the field of computational geometry. That is, we will study combinatorial algorithms for problems where either the input or the output (or both) consists of geometric objects such as points, line segments, triangles, circles, polygons, triangulations, convex hulls, and more. For the sake of easy visualization, we will mostly consider problems in two (or maybe three) spatial dimensions. Each participant will study one specific topic from either a scientific publication or a section/chapter of a textbook, and will give a presentation about it. The available topics will be selected in such a way that they are easy to understand and appreciate for anyone who is familiar with the basic ideas and techniques of algorithm design, as taught in the Bachelor's program.  
Literature  Suitable topics from textbooks and original research articles will be provided during the kickoff meeting.  
Prerequisites / Notice  The participants should be familiar with the contents of the lectures "Algorithmen und Datenstrukturen", "Algorithmen und Wahrscheinlichkeit", and "Theoretische Informatik". Having already passed the lecture "Algorithms, Probability, and Computing" would be ideal, but it is not a strict requirement. Previous knowledge in computational geometry is not required. Starting from the beginning of April, there will be weekly meetings with up to two student presentations.  
Competencies 
 
272030200L  Approximation and Online Algorithms  5 credits  2V + 1U + 1A  H.‑J. Böckenhauer, D. Komm, M. Wettstein  
Abstract  This lecture deals with approximative algorithms for hard optimization problems and algorithmic approaches for solving online problems as well as the limits of these approaches.  
Learning objective  Get a systematic overview of different methods for designing approximative algorithms for hard optimization problems and online problems. Get to know methods for showing the limitations of these approaches.  
Content  Approximation algorithms are one of the most succesful techniques to attack hard optimization problems. Here, we study the socalled approximation ratio, i.e., the ratio of the cost of the computed approximating solution and an optimal one (which is not computable efficiently). For an online problem, the whole instance is not known in advance, but it arrives pieceweise and for every such piece a corresponding part of the definite output must be given. The quality of an algorithm for such an online problem is measured by the competitive ratio, i.e., the ratio of the cost of the computed solution and the cost of an optimal solution that could be given if the whole input was known in advance. The contents of this lecture are  the classification of optimization problems by the reachable approximation ratio,  systematic methods to design approximation algorithms (e.g., greedy strategies, dynamic programming, linear programming relaxation),  methods to show nonapproximability,  classic online problem like paging or scheduling problems and corresponding algorithms,  randomized online algorithms,  the design and analysis principles for online algorithms, and  limits of the competitive ratio and the advice complexity as a way to do a deeper analysis of the complexity of online problems.  
Literature  The lecture is based on the following books: J. Hromkovic: Algorithmics for Hard Problems, Springer, 2004 D. Komm: An Introduction to Online Computation: Determinism, Randomization, Advice, Springer, 2016 Additional literature: A. Borodin, R. ElYaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998  
Competencies 
