Peter Widmayer: Catalogue data in Autumn Semester 2018 |  |
| Name | Prof. em. Dr. Peter Widmayer |
| Field | Informatik |
| Address | Inst. f. Theoretische Informatik ETH Zürich, CAB H 39.2 Universitätstrasse 6 8092 Zürich SWITZERLAND |
| widmayer@inf.ethz.ch | |
| Department | Computer Science |
| Relationship | Professor emeritus |
| Number | Title | ECTS | Hours | Lecturers | |
|---|---|---|---|---|---|
| 252-0209-00L | Algorithms, Probability, and Computing  | 8 credits | 4V + 2U + 1A | E. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer | |
| 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-0933-00L | Algorithms and Complexity (HS) | 1 credit | 1S | J. Hromkovic, P. Widmayer | |
| Abstract | The seminar treats selected problems of current interest in the area of algorithms and complexity. | ||||
| Learning objective | Develop an understanding of selected problems of current interest in the area of algorithms and complexity. | ||||
| Content | This seminar treats selected problems of current interest in the area of algorithms and complexity. | ||||
| Lecture notes | None | ||||
| Literature | Research papers, to be chosen in the seminar. | ||||
| Prerequisites / Notice | Prerequisites: Basic understanding of algorithms and complexity. | ||||
| 252-4230-00L | Advanced Algorithms and Data Structures  Number of participants limited to 24. As a prerequisite, students must have more than just basic knowledge on algorithms and data structures. If you have enjoyed the class "Algorithms, Probability and Computing", this seminar is just right for you! 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. Takes place for the last time! | 2 credits | 2S | P. Widmayer, S. Leucci, P. Uznanski | |
| Abstract | We will look into modern approaches of algorithms and data structures. A few breakthrough and highly influential papers from the general area of algorithms, from the past 20 years will be selected for students to study. | ||||
| Learning objective | Develop an understanding of modern techniques and paradigms in the design of algorithms and data structures. | ||||
| Content | Topics include (but are not exhausted by): -graph algorithms, -text algorithms, -approximation algorithms, -algebra in algorithms, -streaming algorithms, -conditional lower bounds, -sparsification, -randomness in algorithms, -sampling. | ||||
| Prerequisites / Notice | Algorithms and Data Structures, or equivalent. | ||||
| 263-0006-00L | Algorithms Lab Only for master students, otherwise a special permission by the student administration of D-INFK is required. | 8 credits | 4P + 3A | A. Steger, E. Welzl, P. Widmayer | |
| Abstract | Students learn how to solve algorithmic problems given by a textual description (understanding problem setting, finding appropriate modeling, choosing suitable algorithms, and implementing them). Knowledge of basic algorithms and data structures is assumed; more advanced material and usage of standard libraries for combinatorial algorithms are introduced in tutorials. | ||||
| Learning objective | The objective of this course is to learn how to solve algorithmic problems given by a textual description. This includes appropriate problem modeling, choice of suitable (combinatorial) algorithms, and implementing them (using C/C++, STL, CGAL, and BGL). | ||||
| Literature | T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990. J. Hromkovic, Teubner: Theoretische Informatik, Springer, 2004 (English: Theoretical Computer Science, Springer 2003). J. Kleinberg, É. Tardos: Algorithm Design, Addison Wesley, 2006. H. R. Lewis, C. H. Papadimitriou: Elements of the Theory of Computation, Prentice Hall, 1998. T. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2012. R. Sedgewick: Algorithms in C++: Graph Algorithms, Addison-Wesley, 2001. | ||||