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 | |||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-0842-00L | 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://moodle-app2.let.ethz.ch/course/view.php?id=21917 Lecture website: https://courses.csedu.inf.ethz.ch/ppl-2024/ | ||||||||||||||||||||||||||||||||||||||||||||
| Literature | The slides will be available for download on the course website. | ||||||||||||||||||||||||||||||||||||||||||||
| Prerequisites / Notice | Recommendation: - Foundations of Computer Science (252-0852-00) or - Application Oriented Programming Using Python (252-0840-02) | ||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| ||||||||||||||||||||||||||||||||||||||||||||
| 252-4911-00L | 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 kick-off 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 |
| ||||||||||||||||||||||||||||||||||||||||||||
| 272-0302-00L | 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 so-called 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 non-approximability, - 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. El-Yaniv: Online Computation and Competitive Analysis, Cambridge University Press, 1998 | ||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| ||||||||||||||||||||||||||||||||||||||||||||