Search result: Catalogue data in Autumn Semester 2018

Number	Title	Type	ECTS	Hours	Lecturers
Computer Science Master
Focus Courses
Focus Courses in Theoretical Computer Science
Focus Elective Courses Theoretical Computer Science
252-0535-00L	Advanced Machine Learning	W	8 credits	3V + 2U + 2A	J. M. Buhmann
Abstract	Machine learning algorithms provide analytical methods to search data sets for characteristic patterns. Typical tasks include the classification of data, function fitting and clustering, with applications in image and speech analysis, bioinformatics and exploratory data analysis. This course is accompanied by practical machine learning projects.
Objective	Students will be familiarized with advanced concepts and algorithms for supervised and unsupervised learning; reinforce the statistics knowledge which is indispensible to solve modeling problems under uncertainty. Key concepts are the generalization ability of algorithms and systematic approaches to modeling and regularization. Machine learning projects will provide an opportunity to test the machine learning algorithms on real world data.
Content	The theory of fundamental machine learning concepts is presented in the lecture, and illustrated with relevant applications. Students can deepen their understanding by solving both pen-and-paper and programming exercises, where they implement and apply famous algorithms to real-world data. Topics covered in the lecture include: Fundamentals: What is data? Bayesian Learning Computational learning theory Supervised learning: Ensembles: Bagging and Boosting Max Margin methods Neural networks Unsupservised learning: Dimensionality reduction techniques Clustering Mixture Models Non-parametric density estimation Learning Dynamical Systems
Lecture notes	No lecture notes, but slides will be made available on the course webpage.
Literature	C. Bishop. Pattern Recognition and Machine Learning. Springer 2007. R. Duda, P. Hart, and D. Stork. Pattern Classification. John Wiley & Sons, second edition, 2001. T. Hastie, R. Tibshirani, and J. Friedman. The Elements of Statistical Learning: Data Mining, Inference and Prediction. Springer, 2001. L. Wasserman. All of Statistics: A Concise Course in Statistical Inference. Springer, 2004.
Prerequisites / Notice	The course requires solid basic knowledge in analysis, statistics and numerical methods for CSE as well as practical programming experience for solving assignments. Students should have followed at least "Introduction to Machine Learning" or an equivalent course offered by another institution.
252-1425-00L	Geometry: Combinatorics and Algorithms	W	6 credits	2V + 2U + 1A	E. Welzl, L. F. Barba Flores, M. Hoffmann
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.
Lecture notes	yes
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.
263-4110-00L	Interdisciplinary Algorithms Lab Number of participants limited to 12. In the Master Programme max. 10 credits can be accounted by Labs on top of the Interfocus Courses. Additional Labs will be listed on the Addendum.	W	5 credits	2P	A. Steger, D. Steurer, J. Lengler
Abstract	In this course students will develop solutions for algorithmic problems posed by researchers from other fields.
Objective	Students will learn that in order to tackle algorithmic problems from an interdisciplinary or applied context one needs to combine a solid understanding of algorithmic methodology with insights into the problem at hand to judge which side constraints are essential and which can be loosened.
Prerequisites / Notice	Students will work in teams. Ideally, skills of team members complement each other. Interested Bachelor students can apply for participation by sending an email to steger@inf.ethz.ch explaining motivation and transcripts.
263-4500-00L	Advanced Algorithms	W	6 credits	2V + 2U + 1A	M. Ghaffari, A. Krause
Abstract	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.
Objective	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.
Content	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.
Prerequisites / Notice	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.
401-3054-14L	Probabilistic Methods in Combinatorics	W	6 credits	2V + 1U	B. Sudakov
Abstract	This course provides a gentle introduction to the Probabilistic Method, with an emphasis on methodology. We will try to illustrate the main ideas by showing the application of probabilistic reasoning to various combinatorial problems.
Objective
Content	The topics covered in the class will include (but are not limited to): linearity of expectation, the second moment method, the local lemma, correlation inequalities, martingales, large deviation inequalities, Janson and Talagrand inequalities and pseudo-randomness.
Literature	- The Probabilistic Method, by N. Alon and J. H. Spencer, 3rd Edition, Wiley, 2008. - Random Graphs, by B. Bollobás, 2nd Edition, Cambridge University Press, 2001. - Random Graphs, by S. Janson, T. Luczak and A. Rucinski, Wiley, 2000. - Graph Coloring and the Probabilistic Method, by M. Molloy and B. Reed, Springer, 2002.
401-3901-00L	Mathematical Optimization	W	11 credits	4V + 2U	R. Weismantel
Abstract	Mathematical treatment of diverse optimization techniques.
Objective	Advanced optimization theory and algorithms.
Content	1) Linear optimization: The geometry of linear programming, the simplex method for solving linear programming problems, Farkas' Lemma and infeasibility certificates, duality theory of linear programming. 2) Nonlinear optimization: Lagrange relaxation techniques, Newton method and gradient schemes for convex optimization. 3) Integer optimization: Ties between linear and integer optimization, total unimodularity, complexity theory, cutting plane theory. 4) Combinatorial optimization: Network flow problems, structural results and algorithms for matroids, matchings, and, more generally, independence systems.
Literature	1) D. Bertsimas & R. Weismantel, "Optimization over Integers". Dynamic Ideas, 2005. 2) A. Schrijver, "Theory of Linear and Integer Programming". John Wiley, 1986. 3) D. Bertsimas & J.N. Tsitsiklis, "Introduction to Linear Optimization". Athena Scientific, 1997. 4) Y. Nesterov, "Introductory Lectures on Convex Optimization: a Basic Course". Kluwer Academic Publishers, 2003. 5) C.H. Papadimitriou, "Combinatorial Optimization". Prentice-Hall Inc., 1982.
Prerequisites / Notice	Linear algebra.

Page 1 of 1