Bernd Gärtner: Catalogue data in Autumn Semester 2024 |
| 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 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 252-0209-00L | Algorithms, Probability, and Computing  | 8 credits | 4V + 2U + 1A | B. Gärtner, R. Kyng, A. Steger, D. Steurer | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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). | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 252-1425-00L | Geometry: Combinatorics and Algorithms | 8 credits | 3V + 2U + 2A | B. Gärtner, M. Hoffmann, P. Schnider, E. Welzl, M. Wettstein | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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?) | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning 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, ham-sandwich cuts), 3-SUM 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 252-4202-00L | Seminar in Theoretical Computer Science  | 2 credits | 2S | A. Steger, B. Gärtner, M. Hoffmann, J. Lengler, D. Steurer | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 275-0002-00L | Information, Data & Computers | 2 credits | 1V | B. Gärtner | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Abstract | This course provides an introduction to computer science concepts that are foundational for later work in the CAS and MAS programme. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning objective | Students understand fundamental notions of computer science: information, data, computation, programming, algorithm. Students learn about computers as a concept, how computers fundamentally work, and how this is shaping modern computing infrastructures. Students can explain the core ingredients of Data Science. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Content | We will cover how information is managed as data, and how we use computers to process data and generate new insights. Concrete questions we will address are: what is data, and how does it represent information? What is a computer, and how does it work? What is a computer program? What is a programming language? What is an algorithm? What is the role of AI in computer programming? What kind of computer systems do we have today, and why? What is Data Science? Through this, we will build a fundamental understanding of how computer and data science enable today's information society. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literature | Slides and links to extra material will be distributed during the course. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 401-0131-00L | Linear Algebra | 7 credits | 4V + 2U | B. Gärtner, R. Weismantel | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Learning 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. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Lecture notes | Will be handed out at the start of the semester. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Literature | Gilbert Strang, Introduction to Linear Algebra, 6th Edition, Wellesley - Cambridge Press. Further literature and links can be found on the course webpage. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Competencies |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||