Emo Welzl: Catalogue data in Autumn Semester 2016
|Name||Prof. Dr. Emo Welzl|
Inst. f. Theoretische Informatik
ETH Zürich, CAB G 39.2
|Telephone||+41 44 632 73 70|
|Fax||+41 44 632 10 63|
|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-0417-00L||Randomized Algorithms and Probabilistic Methods||7 credits||3V + 2U + 1A||A. Steger, E. Welzl|
|Abstract||Las Vegas & Monte Carlo algorithms; inequalities of Markov, Chebyshev, Chernoff; negative correlation; Markov chains: convergence, rapidly mixing; generating functions; Examples include: min cut, median, balls and bins, routing in hypercubes, 3SAT, card shuffling, random walks|
|Objective||After this course students will know fundamental techniques from probabilistic combinatorics for designing randomized algorithms and will be able to apply them to solve typical problems in these areas.|
|Content||Randomized Algorithms are algorithms that "flip coins" to take certain decisions. This concept extends the classical model of deterministic algorithms and has become very popular and useful within the last twenty years. In many cases, randomized algorithms are faster, simpler or just more elegant than deterministic ones. In the course, we will discuss basic principles and techniques and derive from them a number of randomized methods for problems in different areas.|
|Literature||- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)|
- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)
|252-1425-00L||Geometry: Combinatorics and Algorithms||6 credits||2V + 2U + 1A||B. Gärtner, E. Welzl, M. Hoffmann, A. Pilz|
|Abstract||Geometric structures are useful in many areas, and there is a need to understand their structural properties, and to work with them algorithmically. The lecture addresses theoretical foundations concerning geometric structures. Central objects of interest are triangulations. We study combinatorial (Does a certain object exist?) and algorithmic questions (Can we find a certain object efficiently?)|
|Objective||The goal is to make students familiar with fundamental concepts, techniques and results in combinatorial and computational geometry, so as to enable them to model, analyze, and solve theoretical and practical problems in the area and in various application domains.|
In particular, we want to prepare students for conducting independent research, for instance, within the scope of a thesis project.
|Content||Planar and geometric graphs, embeddings and their representation (Whitney's Theorem, canonical orderings, DCEL), polygon triangulations and the art gallery theorem, convexity in R^d, planar convex hull algorithms (Jarvis Wrap, Graham Scan, Chan's Algorithm), point set triangulations, Delaunay triangulations (Lawson flips, lifting map, randomized incremental construction), Voronoi diagrams, the Crossing Lemma and incidence bounds, line arrangements (duality, Zone Theorem, ham-sandwich cuts), 3-SUM hardness, counting planar triangulations.|
|Literature||Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Cheong, Computational Geometry: Algorithms and Applications, Springer, 3rd ed., 2008.|
Satyan Devadoss, Joseph O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011.
Stefan Felsner, Geometric Graphs and Arrangements: Some Chapters from Combinatorial Geometry, Teubner, 2004.
Jiri Matousek, Lectures on Discrete Geometry, Springer, 2002.
Takao Nishizeki, Md. Saidur Rahman, Planar Graph Drawing, World Scientific, 2004.
|Prerequisites / Notice||Prerequisites: The course assumes basic knowledge of discrete mathematics and algorithms, as supplied in the first semesters of Bachelor Studies at ETH.|
Outlook: In the following spring semester there is a seminar "Geometry: Combinatorics and Algorithms" that builds on this course. There are ample possibilities for Semester-, Bachelor- and Master Thesis projects in the area.
|252-4202-00L||Seminar in Theoretical Computer Science||2 credits||2S||E. Welzl, B. Gärtner, M. Hoffmann, J. Lengler, A. Steger, B. Sudakov|
|Abstract||Presentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.|
|Objective||The goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers.|
|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.