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-0002-AAL | Data Structures and Algorithms Enrolment ONLY for MSc students with a decree declaring this course unit as an additional admission requirement. Any other students (e.g. incoming exchange students, doctoral students) CANNOT enrol for this course unit. | 7 credits | 15R | P. Widmayer | |

Abstract | This course is about fundamental algorithm design paradigms (such as induction, divide-and-conquer, backtracking, dynamic programming), classic algorithmic problems (such as sorting and searching), and data structures (such as lists, hashing, search trees). The connection between algorithms and data structures is explained for geometric and graph problems. | ||||

Objective | An understanding of the design and analysis of fundamental algorithms and data structures. | ||||

252-0026-00L | Algorithms and Data Structures | 7 credits | 3V + 2U + 1A | P. Widmayer, M. Püschel | |

Abstract | This course is about fundamental algorithm design paradigms, classic algorithmic problems, and data structures. The connection between algorithms and data structures is explained for geometric and graph problems. For this purpose, fundamental graph theoretic concepts are introduced. | ||||

Objective | An understanding of the design and analysis of fundamental algorithms and data structures. | ||||

Content | Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt. | ||||

Literature | Th. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 | ||||

252-0209-00L | Algorithms, Probability, and Computing | 8 credits | 4V + 2U + 1A | E. Welzl, M. Ghaffari, A. Steger, 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). | ||||

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. | ||||

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-1407-00L | Algorithmic Game Theory | 7 credits | 3V + 2U + 1A | P. Widmayer, P. Penna | |

Abstract | Game theory provides a formal model to study the behavior and interaction of self-interested users and programs in large-scale distributed computer systems without central control. The course discusses algorithmic aspects of game theory. | ||||

Objective | Learning the basic concepts of game theory and mechanism design, acquiring the computational paradigm of self-interested agents, and using these concepts in the computational and algorithmic setting. | ||||

Content | The Internet is a typical example of a large-scale distributed computer system without central control, with users that are typically only interested in their own good. For instance, they are interested in getting high bandwidth for themselves, but don't care about others, and the same is true for computational load or download rates. Game theory provides a particularly well-suited model for the behavior and interaction of such selfish users and programs. Classic game theory dates back to the 1930s and typically does not consider algorithmic aspects at all. Only a few years back, algorithms and game theory have been considered together, in an attempt to reconcile selfish behavior of independent agents with the common good. This course discusses algorithmic aspects of game-theoretic models, with a focus on recent algorithmic and mathematical developments. Rather than giving an overview of such developments, the course aims to study selected important topics in depth. Outline: - Introduction to classic game-theoretic concepts. - Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity. - Speed of convergence of natural game playing dynamics such as best-response dynamics or regret minimization. - Techniques for bounding the quality-loss due to selfish behavior versus optimal outcomes under central control (a.k.a. the 'Price of Anarchy'). - Design and analysis of mechanisms that induce truthful behavior or near-optimal outcomes at equilibrium. - Selected current research topics, such as Google's Sponsored Search Auction, the U.S. FCC Spectrum Auction, Kidney Exchange. | ||||

Lecture notes | No lecture notes. | ||||

Literature | "Algorithmic Game Theory", edited by N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani, Cambridge University Press, 2008; "Game Theory and Strategy", Philip D. Straffin, The Mathematical Association of America, 5th printing, 2004 Several copies of both books are available in the Computer Science library. | ||||

Prerequisites / Notice | Audience: Although this is a Computer Science course, we encourage the participation from all students who are interested in this topic. Requirements: You should enjoy precise mathematical reasoning. You need to have passed a course on algorithms and complexity. No knowledge of game theory is required. | ||||

263-0006-00L | Algorithms Lab | 6 credits | 4P + 1A | 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. | ||||

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. | ||||

263-4311-00L | Seminar on Molecular Algorithms Limited number of participants | 2 credits | 2S | P. Widmayer | |

Abstract | Develop an understanding of selected topics in the area of molecular algorithms, and the practice of scient | ||||

Objective | Study and understanding of selected topics of interest in molecular algorithms such as: Computational Power of Molecular Algorithms, Molecular Algorithms for Solving Fundamental Tasks (Majority, Leader Election, Counting), Complexity Lower Bounds, Implementations of Algorithms in DNA. | ||||

Content | This seminar will familiarize the students with current research on molecualr algorithms, with a focus o algorithms executable in DNA. We will have an introductory lecture covering the basics of molecular computational models, and the underlying bio-chemical phenomena. Subsequently, we will read and present selected reseach papers, focusing on their algorithmic content. No prior knowledge of biology or chemistry will be required. | ||||

Literature | Selected research articles. | ||||

Prerequisites / Notice | The course will require a good understanding of Randomized Algorithms. Hence, you must have passed our "Randomized Algorithms" class (or have acquired equivalent knowledge, in exceptional cases). No prior knowledge of biology or chemistry will be assumed. The basics will be presented in an introductory lecture. |