Mohsen Ghaffari: Katalogdaten im Herbstsemester 2017

NameHerr Dr. Mohsen Ghaffari
LehrgebietInformatik
E-Mailghaffari@inf.ethz.ch
URLhttps://people.inf.ethz.ch/gmohsen/
DepartementInformatik
BeziehungAssistenzprofessor (Tenure Track)

NummerTitelECTSUmfangDozierende
252-0209-00LAlgorithms, Probability, and Computing Information 8 KP4V + 2U + 1AE. Welzl, M. Ghaffari, A. Steger, D. Steurer, 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.
263-4500-00LAdvanced Algorithms Information 6 KP2V + 2U + 1AM. Ghaffari
KurzbeschreibungThis 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.
LernzielThis 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.
Inhaltthe 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, and a bried glance at MapReduce algorithms.
Voraussetzungen / BesonderesThis 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 consulte the instructor.