Search result: Catalogue data in Autumn Semester 2019

Mathematics Master Information
Electives
For the Master's degree in Applied Mathematics the following additional condition (not manifest in myStudies) must be obeyed: At least 15 of the required 28 credits from core courses and electives must be acquired in areas of applied mathematics and further application-oriented fields.
Electives: Applied Mathematics and Further Application-Oriented Fields
¬
Auswahl: Theoretical Computer Science, Discrete Mathematics
NumberTitleTypeECTSHoursLecturers
263-4500-00LAdvanced Algorithms Information W6 credits2V + 2U + 1AM. Ghaffari, A. Krause
AbstractThis is an advanced course on the design and analysis of algorithms, covering a range of topics and techniques not studied in typical introductory courses on algorithms.
ObjectiveThis course is intended to familiarize students with (some of) the main tools and techniques developed over the last 15-20 years in algorithm design, which are by now among the key ingredients used in developing efficient algorithms.
ContentThe lectures will cover a range of topics, including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms.
Lecture notesLink
Prerequisites / NoticeThis course is designed for masters and doctoral students and it especially targets those interested in theoretical computer science, but it should also be accessible to last-year bachelor students.

Sufficient comfort with both (A) Algorithm Design & Analysis and (B) Probability & Concentrations. E.g., having passed the course Algorithms, Probability, and Computing (APC) is highly recommended, though not required formally. If you are not sure whether you're ready for this class or not, please consult the instructor.
252-1425-00LGeometry: Combinatorics and Algorithms Information W6 credits2V + 2U + 1AB. Gärtner, M. Hoffmann, M. Wettstein
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-0417-00LRandomized Algorithms and Probabilistic MethodsW8 credits3V + 2U + 2AA. Steger
AbstractLas 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
ObjectiveAfter 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.
ContentRandomized 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.
Lecture notesYes.
Literature- Randomized Algorithms, Rajeev Motwani and Prabhakar Raghavan, Cambridge University Press (1995)
- Probability and Computing, Michael Mitzenmacher and Eli Upfal, Cambridge University Press (2005)
  •  Page  1  of  1