Bernd Gärtner: Catalogue data in Autumn Semester 2023 
Name  Prof. Dr. Bernd Gärtner 
Address  Inst. f. Theoretische Informatik ETH Zürich, OAT Z 15 Andreasstrasse 5 8092 Zürich SWITZERLAND 
Telephone  +41 44 632 70 26 
Fax  +41 44 632 10 63 
gaertner@inf.ethz.ch  
URL  http://people.inf.ethz.ch/gaertner/ 
Department  Computer Science 
Relationship  Adjunct Professor 
Number  Title  ECTS  Hours  Lecturers  

252020900L  Algorithms, Probability, and Computing  8 credits  4V + 2U + 1A  B. Gärtner, R. Kyng, A. Steger, D. Steurer, E. Welzl  
Abstract  Advanced design and analysis methods for algorithms and data structures: Random(ized) Search Trees, Point Location, Minimum Cut, Linear Programming, Randomized Algebraic Algorithms (matchings), Probabilistically Checkable Proofs (introduction).  
Objective  Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.  
Lecture notes  Will be handed out.  
Literature  Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest; Randomized Algorithms by R. Motwani und P. Raghavan; Computational Geometry  Algorithms and Applications by M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf.  
252142500L  Geometry: Combinatorics and Algorithms  8 credits  3V + 2U + 2A  B. Gärtner, E. Welzl, M. Hoffmann, P. Schnider  
Abstract  Geometric structures are useful in many areas, and there is a need to understand their structural properties, and to work with them algorithmically. The lecture addresses theoretical foundations concerning geometric structures. Central objects of interest are triangulations. We study combinatorial (Does a certain object exist?) and algorithmic questions (Can we find a certain object efficiently?)  
Objective  The goal is to make students familiar with fundamental concepts, techniques and results in combinatorial and computational geometry, so as to enable them to model, analyze, and solve theoretical and practical problems in the area and in various application domains. In particular, we want to prepare students for conducting independent research, for instance, within the scope of a thesis project.  
Content  Planar and geometric graphs, embeddings and their representation (Whitney's Theorem, canonical orderings, DCEL), polygon triangulations and the art gallery theorem, convexity in R^d, planar convex hull algorithms (Jarvis Wrap, Graham Scan, Chan's Algorithm), point set triangulations, Delaunay triangulations (Lawson flips, lifting map, randomized incremental construction), Voronoi diagrams, the Crossing Lemma and incidence bounds, line arrangements (duality, Zone Theorem, hamsandwich cuts), 3SUM hardness, counting planar triangulations.  
Lecture notes  yes  
Literature  Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, Computational Geometry: Algorithms and Applications, Springer, 3rd ed., 2008. Satyan Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011. Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Teubner, 2004. Jiri Matousek, Lectures on Discrete Geometry, Springer, 2002. Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004.  
Prerequisites / Notice  Prerequisites: The course assumes basic knowledge of discrete mathematics and algorithms, as supplied in the first semesters of Bachelor Studies at ETH. Outlook: In the following spring semester there is a seminar "Geometry: Combinatorics and Algorithms" that builds on this course. There are ample possibilities for Semester, Bachelor and Master Thesis projects in the area.  
252420200L  Seminar in Theoretical Computer Science  2 credits  2S  E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, D. Steurer, B. Sudakov  
Abstract  Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.  
Objective  The goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers.  
Prerequisites / Notice  This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal restriction is: prior successful participation in a master level seminar in theoretical computer science.  
265010100L  Data Science  4 credits  3V  B. Gärtner  
Abstract  In this module, basic paradigms and techniques in working with data will be discussed, especially towards data security, managing data decentrally, and learning from data.  
Objective  Participants will understand some of the concepts in detail and see the mathematics behind them.  
Content  The module in particular covers cryptography and digital signatures, networking and distributed algorithms, distributed ledger technology, as well as machine learning (supervised and unsupervised learning). For each topic, there will be a handson and indepth introduction that allows participants to gain a technical understanding of key ideas. This is supported by simple and concrete examples as well as programming assignments.  
401013100L  Linear Algebra  7 credits  4V + 2U  A. Bandeira, B. Gärtner  
Abstract  Introduction to linear algebra: vectors and matrices, solving systems of linear equations, vector spaces and subspaces, orthogonality and least squares, determinants, eigenvalues and eigenvectors, singular value decomposition and linear transformations. Applications in and links to computer science will be presented in parallel.  
Objective   Understand and apply fundamental concepts of linear algebra  Learn about applications of linear algebra in computer science  
Content  Vectors and matrices, solving systems of linear equations, vector spaces and subspaces, orthogonality and least squares, determinants, eigenvalues and eigenvectors, singular value decomposition and linear transformations. Applications in and links to computer science.  
Literature  Gilbert Strang, Introduction to Linear Algebra, 6th Edition, Wellesley  Cambridge Press. Further literature and links can be found on the course webpage.  
Competencies 
