Peter Widmayer: Catalogue data in Spring Semester 2014 |  |
| 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 who need this course as additional requirement. | 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. | ||||
| Learning objective | An understanding of the design and analysis of fundamental algorithms and data structures. | ||||
| Prerequisites / Notice | This is a self-study course. The relevant topics are those of the underlying course taught in the previous spring semester. A course summary with literature in English is provided at: http://www.cadmo.ethz.ch/education/lectures/FS12/DA/ | ||||
| 252-0002-00L | Data Structures and Algorithms  | 7 credits | 4V + 2U | 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. | ||||
| Learning 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. | ||||
| Literature | Th. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011 | ||||
| Prerequisites / Notice | Voraussetzung: 252-0021-00L Einführung in die Programmierung | ||||
| 252-0934-00L | Algorithms and Complexity (FS) | 1 credit | 1S | P. Widmayer, J. Hromkovic | |
| Abstract | This 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-3002-00L | Algorithms for Database Systems | 2 credits | 2S | P. Widmayer, D. Kossmann | |
| Abstract | Query processing, optimization, stream-based systems, distributed and parallel databases, non-standard databases. | ||||
| Learning objective | Develop an understanding of selected problems of current interest in the area of algorithms for database systems. | ||||
| 252-4220-00L | A Taste of Research: Algorithms and Combinatorics | 2 credits | 2S | B. Gärtner, J. Matousek, A. Steger, E. Welzl, P. Widmayer | |
| Abstract | Students work together with lecturers on open problems in algorithms and combinatorics. | ||||
| Learning objective | The goal is to learn and practice important research techniques: literature search, understanding and presenting research papers, developing ideas in the group, testing of conjectures with the computer, writing down results. | ||||
| Content | Work on original research papers and open problems in the areas of algorithms and combinatorics. | ||||
| Lecture notes | Not available. | ||||
| Literature | Will be announced in the seminar and on the seminar's web page. | ||||
| Prerequisites / Notice | Passed first-year exam. | ||||
| 252-4302-00L | Seminar Algorithmic Game Theory | 2 credits | 2S | P. Widmayer, M. Mihalak | |
| Abstract | In the seminar we will get familiar with the current original research in the area of algorithmic game theory by reading and presenting selected research papers in that area. | ||||
| Learning objective | Develop an understanding of selected problems of current interest in the area of algorithmic game theory, and a practice of a scientific presentation. | ||||
| Content | Study and understanding of selected topics of current interest in algorithmic game theory such as: Complexity Results (class PPAD, PLS, NP), Sponsored Search, Approximation Algorithms via Algorithmic Game Theory, Price of Anarchy, New paradigms of computation (e.g., envy-fee, truthful), Mechanism Design. | ||||
| Literature | Selected research articles. | ||||
| Prerequisites / Notice | You must have passed our "Algorithmic Game Theory" class (or have acquired equivalent knowledge, in exceptional cases). | ||||