Peter Widmayer: Katalogdaten im Herbstsemester 2014

Auszeichnung: Die Goldene Eule
NameHerr Prof. em. Dr. Peter Widmayer
LehrgebietInformatik
Adresse
Inst. f. Theoretische Informatik
ETH Zürich, CAB H 39.2
Universitätstrasse 6
8092 Zürich
SWITZERLAND
E-Mailwidmayer@inf.ethz.ch
DepartementInformatik
BeziehungProfessor emeritus

NummerTitelECTSUmfangDozierende
252-0002-AALData Structures and Algorithms Information
Die Lerneinheit kann nur von MSc Studierenden mit Zulassungsauflagen belegt werden.
7 KP15RP. Widmayer
KurzbeschreibungThis 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.
LernzielAn understanding of the design and analysis of fundamental algorithms and data structures.
252-0209-00LAlgorithms, Probability, and Computing Information 8 KP4V + 2U + 1AE. Welzl, T.  Holenstein, P. Widmayer
KurzbeschreibungAdvanced 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).
LernzielStudying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
SkriptWill be handed out.
LiteraturIntroduction 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-00LAlgorithms and Complexity (HS)1 KP1SJ. Hromkovic, P. Widmayer
KurzbeschreibungThe seminar treats selected problems of current interest in the area of algorithms and complexity.
LernzielDevelop an understanding of selected problems of current interest in the area of algorithms and complexity.
InhaltThis seminar treats selected problems of current interest in the area of algorithms and complexity.
SkriptNone
LiteraturResearch papers, to be chosen in the seminar.
Voraussetzungen / BesonderesPrerequisites: Basic understanding of algorithms and complexity.
252-1407-00LAlgorithmic Game Theory Information 7 KP3V + 2U + 1AP. Widmayer
KurzbeschreibungGame 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.
LernzielLearning 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.
InhaltThe 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 behaviour and interaction of such selfish users and programs. Classical 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 classical game theoretic concepts.
- Existence of stable solutions (equilibria), algorithms for computing equilibria, computational complexity.
- The cost difference between an optimum under central control and an equilibrium under selfish agents, known as the "price of anarchy".
- Auction-like mechanisms and algorithms that "direct" the actions of selfish agents into a certain desired equilibrium situation.
- Selected current research topics of Algorithmic Game Theory, such as Web-Search Based Keyword Auctions, or Information Cascading in Social Networks
SkriptNo lecture notes.
Literatur"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.
Voraussetzungen / BesonderesAudience: 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-00LAlgorithms Lab Information 6 KP4P + 1AA. Steger, E. Welzl, P. Widmayer
KurzbeschreibungStudents 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.
LernzielThe 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).
LiteraturT. 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.