Emo Welzl: Catalogue data in Autumn Semester 2014

Name Prof. Dr. Emo Welzl
Inst. f. Theoretische Informatik
ETH Zürich, CAB G 39.2
Universitätstrasse 6
8092 Zürich
Telephone+41 44 632 73 70
Fax+41 44 632 10 63
DepartmentComputer Science
RelationshipFull Professor

252-0057-00LTheoretical Computer Science Information 8 credits4V + 2U + 1AJ. Hromkovic, E. Welzl
AbstractConcepts to cope with: a) what can be accomplished in a fully automated fashion (algorithmically solvable) b) How to measure the inherent difficulty of tasks (problems) c) What is randomness and how can it be useful? d) What is nondeterminism and what role does it play in CS? e) How to represent infinite objects by finite automata and grammars?
ObjectiveLearning the basic concepts of computer science along their historical development
ContentThis lecture gives an introduction to theoretical computer science, presenting the basic concepts and methods of computer science in its historical context. We present computer science as an interdisciplinary science which, on the one hand, investigates the border between the possible and the impossible and the quantitative laws of information processing, and, on the other hand, designs, analyzes, verifies, and implements computer systems.

The main topics of the lecture are:

- alphabets, words, languages, measuring the information content of words, representation of algorithmic tasks
- finite automata, regular and context-free grammars
- Turing machines and computability
- complexity theory and NP-completeness
- design of algorithms for hard problems
Lecture notesThe lecture is covered in detail by the textbook "Theoretical Computer Science".
LiteratureBasic literature:

1. J. Hromkovic: Theoretische Informatik. 5th edition, Teubner 2014.

2. J. Hromkovic: Theoretical Computer Science. Springer 2004.

Further reading:

3. M. Sipser: Introduction to the Theory of Computation, PWS Publ. Comp.1997
4. J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation (3rd Edition), Addison-Wesley 2006.
5. I. Wegener: Theoretische Informatik. Teubner.

More exercises and examples in:

6. A. Asteroth, Ch. Baier: Theoretische Informatik
Prerequisites / NoticeDuring the semester, two non-obligatory test exams will be offered.
252-0209-00LAlgorithms, Probability, and Computing Information 8 credits4V + 2U + 1AE. Welzl, T.  Holenstein, 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-0860-00LDiscrete Mathematics4 credits2V + 1UE. Welzl, J. Lengler
AbstractFoundations of Discrete Mathematics; combinatorics (elementary counting), graph theory (paths, walks, euler circuits, matchings, trees, planar graphs), algebra (modular arithmetic, groups, fields), applications (network flows, cryptography, coding theory).
Objectivesee above
252-1425-00LGeometry: Combinatorics and Algorithms Information 6 credits2V + 2U + 1AB. Gärtner, M. Hoffmann, E. Welzl
AbstractGeometric 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?)
ObjectiveThe 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.
ContentPlanar 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.
Lecture notesyes
LiteratureMark 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 / NoticePrerequisites: 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-00LSeminar in Theoretical Computer Science Information 2 credits2SE. Welzl, B. Gärtner, M. Hoffmann, J. Lengler
AbstractPresentation of recent publications in theoretical computer science, including results by diploma, masters and doctoral candidates.
ObjectiveThe goal is to introduce students to current research, and to enable them to read, understand, and present scientific papers.
263-0006-00LAlgorithms Lab Information 6 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-4200-00LSeminar SAT Information 2 credits2SE. Welzl
AbstractStudy and presentation of research papers from the literature on "Boolean Satisfiability-Combinatorics and Algorithms".
ObjectiveGoal of this seminar is to study and present, in continuation of the course "Boolean Satisfiability-Combinatorics and Algorithms", research papers from the literature.
LiteratureA list of papers for presentations will be distributed at the beginning of the seminar.
Prerequisites / NoticeThe seminar builds heavily on the material covered in the course "Boolean Satisfiability-Combinatorics and Algorithms." Successful completion of that course is a prerequisite for participation in the seminar.
263-4203-00LGeometry: Combinatorics and Algorithms Information
Does not take place this semester.
2 credits2SB. Gärtner, E. Welzl
AbstractThis seminar is held once a year and complements the courses Computational Geometry and Geometric Graphs: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.
ObjectiveEach student is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

* getting an overview of the related literature;
* understanding and working out the background/motivation:
why and where are the questions addressed relevant?
* understanding the contents of the paper in all details;
* selecting parts suitable for the presentation;
* presenting the selected parts in such a way that an audience
with some basic background in geometry and graph theory can easily understand and appreciate it.
Prerequisites / NoticeTo attend the seminar, some basic knowledge in (discrete and computational) geometry and graphs and algorithms is required. Thus, previous participation in some of the courses "Graphs and Algorithms", "Computational Geometry", "Geometric Graphs: Combinatorics & Algorithms", or similar courses is strongly encouraged. It is also possible to take this seminar in parallel to the lecture "Computational Geometry".