## Mohsen Ghaffari: Katalogdaten im Herbstsemester 2019 |

Name | Herr Dr. Mohsen Ghaffari |

Lehrgebiet | Informatik |

URL | https://people.inf.ethz.ch/gmohsen/ |

Departement | Informatik |

Beziehung | Assistenzprofessor (Tenure Track) |

Nummer | Titel | ECTS | Umfang | Dozierende | |
---|---|---|---|---|---|

252-0209-00L | Algorithms, Probability, and Computing | 8 KP | 4V + 2U + 1A | A. Steger, B. Gärtner, M. Ghaffari, D. Steurer | |

Kurzbeschreibung | 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). | ||||

Lernziel | Studying and understanding of fundamental advanced concepts in algorithms, data structures and complexity theory. | ||||

Skript | Will be handed out. | ||||

Literatur | 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-4202-00L | Seminar in Theoretical Computer Science | 2 KP | 2S | A. Steger, B. Gärtner, M. Ghaffari, M. Hoffmann, J. Lengler, D. Steurer, B. Sudakov | |

Kurzbeschreibung | Präsentation wichtiger und aktueller Arbeiten aus der theoretischen Informatik, sowie eigener Ergebnisse von Diplomanden und Doktoranden. | ||||

Lernziel | Das Lernziel ist, Studierende an die aktuelle Forschung heranzuführen und sie in die Lage zu versetzen, wissenschaftliche Arbeiten zu lesen, zu verstehen, und zu präsentieren. | ||||

Voraussetzungen / Besonderes | This seminar takes place as part of the joint research seminar of several theory groups. Intended participation is for students with excellent performance only. Formal minimal requirement is passing of one of the courses Algorithms, Probability, and Computing, Randomized Algorithms and Probabilistic Methods, Geometry: Combinatorics and Algorithms, Advanced Algorithms. (If you cannot fulfill this restriction, because this is your first term at ETH, but you believe that you satisfy equivalent criteria, please send an email with a detailed description of your reasoning to the organizers of the seminar.) | ||||

263-4500-00L | Advanced Algorithms | 6 KP | 2V + 2U + 1A | M. Ghaffari, A. Krause | |

Kurzbeschreibung | This 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. | ||||

Lernziel | This 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. | ||||

Inhalt | The 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. | ||||

Skript | https://people.inf.ethz.ch/gmohsen/AA19/ | ||||

Voraussetzungen / Besonderes | This 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. | ||||

263-4500-10L | Advanced Algorithms (with Project) Only for Data Science MSc. | 8 KP | 2V + 2U + 2P + 1A | M. Ghaffari, A. Krause | |

Kurzbeschreibung | This 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. | ||||

Lernziel | This 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. | ||||

Inhalt | the 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. | ||||

Skript | https://people.inf.ethz.ch/gmohsen/AA19/ | ||||

Voraussetzungen / Besonderes | This 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. | ||||

263-4505-00L | Algorithms for Large-Scale Graph Processing The deadline for deregistering expires at the end of the second week of the semester. Students who are still registered after that date, but do not attend the seminar, will officially fail the seminar. | 2 KP | 2S | M. Ghaffari | |

Kurzbeschreibung | This is a theory seminar, where we present and discuss recent algorithmic developments for processing large-scale graphs. In particular, we focus on Massively Parallel Computation (MPC) algorithms. MPC is a clean and general theoretical framework that captures the essential aspects of computational problems in large-scale processing settings such as MapReduce, Hadoop, Spark, Dryad, etc. | ||||

Lernziel | This seminar familiarizes students with foundational aspects of large-scale graph processing, and especially the related algorithmic tools and techniques. In particular, we discuss recent developments in the area of Massively Parallel Computation. This is a mathematical abstraction of practical large-scale processing settings such as MapReduce, and it has been receiving significant attention over the past few years. The seminar assumes no particular familiarity with parallel computation. However, we expect that all the students are comfortable with basics of algorithms design and analysis, as well as probability theory. In the course of the seminar, the students learn how to structure a scientific presentation (in English) which covers the key ideas of a paper, while omitting the less significant details. | ||||

Inhalt | The seminar will cover a number of the recent papers on Massively Parallel Computation. As mentioned above, no familiarity with parallel computation is needed and all the relevant background information will be explain by the instructor in the first lecture. | ||||

Literatur | The papers will be presented in the first session of the seminar. |