Felix Friedrich Wicker: Katalogdaten im Frühjahrssemester 2022

NameHerr Dr. Felix Friedrich Wicker
Adresse
Dep. Informatik
ETH Zürich, CAB H 33.3
Universitätstrasse 6
8092 Zürich
SWITZERLAND
Telefon+41 44 632 83 12
E-Mailfelix.friedrich@inf.ethz.ch
DepartementInformatik
BeziehungDozent

NummerTitelECTSUmfangDozierende
252-0002-AALData Structures and Algorithms Information
Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben.

Alle anderen Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen.
8 KP15RF. Friedrich Wicker
KurzbeschreibungThe course provides the foundations for the design and analysis of algorithms.
Classical problems ranging from sorting up to problems on graphs are used to discuss common data structures, algorithms and algorithm design paradigms.
The course also comprises an introduction to parallel and concurrent programming and the programming model of C++ is discussed in some depth.
LernzielAn understanding of the analysis and design of fundamental and common algorithms and data structures.
Deeper insight into a modern programming model by means of the programming language C++.
Knowledge regarding chances, problems and limits of parallel and concurrent programming.
InhaltData structures and algorithms: mathematical tools for the analysis of algorithms (asymptotic function growth, recurrence equations, recurrence trees), informal proofs of algorithm correctness (invariants and code transformation), design paradigms for the development of algorithms (induction, divide-and-conquer, backtracking and dynamic programming), classical algorithmic problems (searching, selection and sorting), data structures for different purposes (linked lists, hash tables, balanced search trees, quad trees, heaps, union-find), further tools for runtime analysis (generating functions, amortized analysis. The relationship and tight coupling between algorithms and data structures is illustrated with graph algorithms (traversals, topological sort, closure, shortest paths, minimum spanning trees, max flow).

Programming model of C++: correct and efficient memory handling, generic programming with templates, exception handling, functional approaches with functors and lambda expressions.

Parallel programming: structure of parallel architectures (multicore, vectorization, pipelining) concepts of parallel programming (Amdahl's and Gustavson's laws, task/data parallelism, scheduling), problems of concurrency (data races, bad interleavings, memory reordering), process synchronisation and communication in a shared memory system (mutual exclusion, semaphores, monitors, condition variables), progress conditions (freedom from deadlock, starvation, lock- and wait-freedom). The concepts are underpinned with examples of concurrent and parallel programs and with parallel algorithms, implemented in C++.

In general, the concepts provided in the course are motivated and illustrated with practically relevant algorithms and applications.

Exercises are carried out in Code-Expert, an online IDE and exercise management system.

All required mathematical tools above high school level are covered, including a basic introduction to graph theory.
LiteraturCormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. ISBN 978-0-262-03384-8 (recommended text)

B. Stroustrup, The C++ Programming Language (4th Edition) Addison-Wesley, 2013.

Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2012.
Voraussetzungen / BesonderesPrerequisites:
Lecture Series 252-0856-00L Computer Science or equivalent knowledge in programming with C++.

Please note that this is a self study (virtual) course, which implies that (in the autumn semester) there are no physical lectures or exercise sessions offered. If you want to attend the real course, please go to 252-0002-00L in the spring semester.
252-0002-00LDatenstrukturen & Algorithmen Information 8 KP4V + 2UF. Friedrich Wicker
KurzbeschreibungEs werden grundlegende Entwurfsmuster für Algorithmen (z.B. Induktion, divide-and-conquer, backtracking, dynamische Programmierung), klassische algorithmische Probleme (Suchen, Sortieren) und Datenstrukturen (Listen, Hashverfahren, Suchbäume) behandelt. Ausserdem enthält der Kurs eine Einführung in das parallele Programmieren. Das Programmiermodell von C++ wird vertieft behandelt.
LernzielVerständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Wissen um die Chancen, Probleme und Grenzen der parallelen und nebenläufigen Programmierung. Vertiefter Einblick in ein modernes Programmiermodell anhand der Prorgammiersprache C++.
InhaltEs werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert.

Im Teil über parallele Programmierung werden Konzepte der parallelen Architekturen besprochen (Multicore, Vektorisierung, Pipelining). Konzepte und Grundlagen der Parallelisierung werden behandelt (Gesetze von Amdahl und Gustavson, Task- und Datenparallelität, Scheduling). Probleme der Nebenläufigkeit werden diskutiert (Wettlaufsituationen, Speicherordnung). Prozesssynchronisation und -kommunikation in einem System mit geteiltem Speicher werden erklärt (Gegenseitiger Ausschluss, Semaphoren, Mutexe, Monitore). Fortschrittseigenschaften werden analysiert (Deadlock-Freiheit, Starvation-Freiheit, Lock-/Wait-Freiheit). Die erlernten Konzepte werden mit Beispielen zur nebenläufigen und parallelen Programmierung und mit Parallelen Algorithmen untermauert.

Das Programmiermodell von C++ wird vertieft behandelt. Das RAII Prinzip (Resource Allocation is Initialization) wird erklärt, Exception Handling, Funktoren und Lambda Ausdrücke und die generische Programmierung mit Templates sind weitere Beispiele dieses Kapitels. Die Implementation von parallelen und nebenläufigen Algorithmen mit C++ ist auch Teil der Übungen (Threads, Tasks, Mutexes, Condition Variables, Promises und Futures).

Übungen werden in der Online-IDE und Übungsmanagementsystem Code-Expert durchgeführt

Alle benötigten mathematischen Tools ausserhalb des Schulwissens werden im Kurs behandelt, einschliesslich einer grundlegenden Einführung zur Graphentheorie.
LiteraturTh. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010

Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2012.

B. Stroustrup, The C++ Programming Language (4th Edition) Addison-Wesley, 2013.
Voraussetzungen / BesonderesVoraussetzung:
Vorlesung 252-0835-00L Informatik I 252-0835-00L oder äquivalente Kenntnisse in der Programmierung mit C++.
252-0232-AALSoftware Engineering Information
Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben.

Alle anderen Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen.
6 KP13RF. Friedrich Wicker, M. Schwerhoff
KurzbeschreibungThis course introduces both theoretical and applied aspects of software engineering. It covers:

- Software Architecture
- Informal and formal Modeling
- Design Patterns
- Software Engineering Principles
- Code Refactoring
- Program Testing
LernzielThe course has two main objectives:

- Obtain an end-to-end (both, theoretical and practical) understanding of the core techniques used for building quality software.
- Be able to apply these techniques in practice.
InhaltWhile the lecture will provide the theoretical foundations for the various aspects of software engineering, the students will apply those techniques in project work that will span over the whole semester - involving all aspects of software engineering, from understanding requirements over design and implementation to deployment and change requests.
LiteraturWill be announced in the lecture
252-0232-00LSoftware Engineering Information 6 KP2V + 1UF. Friedrich Wicker, M. Schwerhoff, H. Lehner
KurzbeschreibungThis course introduces both theoretical and applied aspects of software engineering. It covers:

- Software Architecture
- Informal and formal Modeling
- Design Patterns
- Software Engineering Principles
- Code Refactoring
- Program Testing
LernzielThe course has two main objectives:

- Obtain an end-to-end (both, theoretical and practical) understanding of the core techniques used for building quality software.
- Be able to apply these techniques in practice.
InhaltWhile the lecture will provide the theoretical foundations for the various aspects of software engineering, the students will apply those techniques in project work that will span over the whole semester - involving all aspects of software engineering, from understanding requirements over design and implementation to deployment and change requests.
Skriptno lecture notes
LiteraturWill be announced in the lecture
252-0846-AALComputer Science II Information
Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben.

Alle anderen Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen.
4 KP9RF. Friedrich Wicker, R. Sasse
KurzbeschreibungThis course provides the foundations of programming and working with data. Computer Science II particularly stresses code efficiency and provides the basis for understanding, design, and analysis of algorithms and data structures. In terms of working with data, foundations required for understanding experimental data and notation and basic concepts for machine learning are covered.
LernzielBased on the knowledge covered by the lecture Computer Science I, the primary educational objective of this course is the constructive knowledge of data structures and algorithms. After successfully attending the course, students have a good command of the mechanisms to construct a program in Python and to work with multidimensional data using Python libraries. Students particularly understand how an algorithmic problem can be solved with a sufficiently efficient computer program. Secondary educational objectives are formal thinking, the power of abstraction, and appropriate modeling capabilities.
InhaltIntroduction of Python: from Java to Python, advanced concepts and built-in data structures in Python; parsing data, operating on data using Numpy and visualization using Matplotlib; linear regression, classification and (k-means) clustering, mathematical tools for the analysis of algorithms (asymptotic function growth, recurrence equations, recurrence trees), classical algorithmic problems (searching, selection and sorting), design paradigms for the development of algorithms (divide-and-conquer and dynamic programming), data structures for different purposes (linked lists, trees, heaps, hash-tables). The relationship and tight coupling between algorithms and data structures is illustrated with graph algorithms (traversals, topological sort, closure, shortest paths).

In general, the concepts provided in the course are motivated and illustrated with practically relevant algorithms and applications.
Exercises are carried out in Code-Expert, an online IDE and exercise management system. Programming language used in this course is Python.
SkriptThe slides will be available for download on the course home page.
LiteraturT. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms , 3rd ed., MIT Press, 2009
Voraussetzungen / BesonderesPreliminaries: course 252-0845 Computer Science or equivalent knowledge in programming.
252-0856-AALComputer Science Information
Belegung ist NUR erlaubt für MSc Studierende, die diese Lerneinheit als Auflagenfach verfügt haben.

Alle andere Studierenden (u.a. auch Mobilitätsstudierende, Doktorierende) können diese Lerneinheit NICHT belegen.
4 KP9RF. Friedrich Wicker, M. Schwerhoff
KurzbeschreibungDie Vorlesung bietet eine Einführung in das Programmieren mit einem Fokus auf systematischem algorithmischem Problemlösen. Lehrsprache ist C++. Es wird keine Programmiererfahrung vorausgesetzt.
LernzielPrimäres Lernziel der Vorlesung ist die Befähigung zum Programmieren mit C++. Studenten beherrschen nach erfolgreichem Abschluss der Vorlesung die Mechanismen zum Erstellen eines Programms, sie kennen die fundamentalen Kontrollstrukturen, Datenstrukturen und verstehen, wie man ein algorithmisches Problem in ein Programm abbildet. Sie haben eine Vorstellung davon, was "hinter den Kulissen" passiert, wenn ein Programm übersetzt und ausgeführt wird.
Sekundäre Lernziele der Vorlesung sind das Computer-basierte, algorithmische Denken, Verständnis der Möglichkeiten und der Grenzen der Programmierung und die Vermittlung der Denkart eines Computerwissenschaftlers.
InhaltWir behandeln fundamentale Datentypen, Ausdrücke und Anweisungen, (Grenzen der) Computerarithmetik, Kontrollanweisungen, Funktionen, Felder, zusammengesetze Strukturen und Zeiger. Im Teil zur Objektorientierung werden Klassen, Vererbung und Polymorhpie behandelt, es werden exemplarisch einfache dynamische Datentypen eingeführt.
Die Konzepte der Vorlesung werden jeweils durch Algorithmen und Anwendungen motiviert und illustriert.
SkriptEin Skript in englischer Sprache wird semesterbegleitend herausgegeben. Das Skript und die Folien werden auf der Vorlesungshomepage zum Herunterladen bereitgestellt.
LiteraturBjarne Stroustrup: Einführung in die Programmierung mit C++, Pearson Studium, 2010
Stephen Prata: C++ Primer Plus, Sixth Edition, Addison Wesley, 2012
Andrew Koenig and Barbara E. Moo: Accelerated C++, Addison-Wesley, 2000.
Voraussetzungen / BesonderesDieser virtuelle Kurs zum Selbststudium wird im Herbstsemester auch als physikalischer Kurs angeboten. Studenten ist empfohlen die Vorlesung und Übungen des physikalischen Kurses 252-0856-00L zu besuchen.