Peter Widmayer: Catalogue data in Autumn Semester 2017

Award: The Golden Owl
Name Prof. em. Dr. Peter Widmayer
FieldInformatik
Address
Inst. f. Theoretische Informatik
ETH Zürich, CAB H 39.2
Universitätstrasse 6
8092 Zürich
SWITZERLAND
E-mailwidmayer@inf.ethz.ch
DepartmentComputer Science
RelationshipProfessor emeritus

NumberTitleECTSHoursLecturers
252-0026-00LAlgorithms and Data Structures Information 7 credits3V + 2U + 1AP. Widmayer, M. Püschel, D. Steurer
AbstractThis 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.
ObjectiveAn understanding of the design and analysis of fundamental algorithms and data structures.
ContentEs 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.
LiteratureTh. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
252-0209-00LAlgorithms, Probability, and Computing Information 8 credits4V + 2U + 1AE. Welzl, M. Ghaffari, A. Steger, D. Steurer, P. Widmayer
AbstractAdvanced 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).
ObjectiveStudying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory.
Lecture notesWill be handed out.
LiteratureIntroduction 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 credit1SJ. Hromkovic, P. Widmayer
AbstractThe seminar treats selected problems of current interest in the area of algorithms and complexity.
ObjectiveDevelop an understanding of selected problems of current interest in the area of algorithms and complexity.
ContentThis seminar treats selected problems of current interest in the area of algorithms and complexity.
Lecture notesNone
LiteratureResearch papers, to be chosen in the seminar.
Prerequisites / NoticePrerequisites: Basic understanding of algorithms and complexity.
263-0006-00LAlgorithms Lab
Only for master students, otherwise a special permission by the student administration of D-INFK is required.
8 credits4P + 1AA. Steger, E. Welzl, P. Widmayer
AbstractStudents 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.
ObjectiveThe 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).
LiteratureT. 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-00LSeminar on Molecular Algorithms Information
Does not take place this semester.
Limited number of participants
2 credits2SP. Widmayer
AbstractDevelop an understanding of selected topics in the area of molecular algorithms, and the practice of scient
ObjectiveStudy 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.
ContentThis 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.
LiteratureSelected research articles.
Prerequisites / NoticeThe 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.