Datenstrukturen und Algorithmen (252-0002-00L, 252-0002-AAL)


Vorlesung am D-MATH (CSE) der ETH Zürich, FS 2019 , Felix Friedrich

Remarks for Students of the virtual course 252-0002-AAL

The lecture slides of this physical course are offered both in German and English and are reasonably elaborate. The literature hints provided below will help to understand the material but the slides are otherwise intended to be self-contained.

The exercises (offered in English) are also an important part of the course. It is needless to say that we recommend to work through them -- without looking at the solutions in the first place!

If you find errors in the translation, please provide feedback to me. The translation was done on the fly when preparing the German slides and thus might contain some flaws.

If you want to take the real course, you will have to wait for spring semester. Then the course is offered with (German spoken) lectures and (German or English spoken) recitation sessions again.

Kind regards, Felix Friedrich.

Datum Mitteilung
18.12.2019 published August 2019 exam. See below (Alte Prüfungen). Please find the electronic online part of the exams here
8.1.2020

In order to get access to the master solutions of the moodle mock exams, we have now made the corresponding code-expert course accessible. You can subscribe to this course here .

Termine

VorlesungMontag 10:15 - 12:00 ML F 36
Donnerstag 08:15 - 10:00 ML E 12
ÜbungenFreitag 08:15-10:00, 10:15-12:00Verschiedene Räume (s.u.)

Lernziel und Überblick

Es 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.

Lernziel: Verstä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 Programmiersprache C++(14).

Vorrausetzung: Vorlesung Informatik I (D-ITET) oder gleichwertige Kenntnisse. Folien und Skript zur Vorlesung Informatik I finden Sie hier

Zeitplan, Folien und Übungen

Dies ist ein Plan und als solcher unterliegt er Änderungen -- auch und insbesondere nach Semesterbeginn.

Termin Datum Thema Folien und Handout Übungen, Lösungsskizzen PPrerequisites to unlock bonus exercises BBonus exercises
1 MO 18.02. Begriff des Algorithmus, Effizienz von Algorithmen, Random Access Machine Modell, Asymptotik: O-Notation, Omega, Theta, Organisation: [de] [en]
Slides 1: [de] [en]
Handout 1: [de] [en]
Einschreibung / Enrollment Skiplist
2 DO 21.02. Korrektheit und Effizienz von Algorithmen an Beispielen: Altägyptische Multiplikation, Schnelle Multiplikation grosser Zahlen; Entwurf von Algorithmen: Maximum Subarray (naiv, Präfixsummen, Divide and Conquer, linear) Slides 2: [de] [en]
Handout 2: [de] [en]
O, Theta and Omega, asymptotic running times and 2d prefix sum
Slides: [de] [en]
3 MO 25.02. Suchen und Auswählen Lineare Suche, Binäre Suche, untere Schranken für das Suchen, Das Auswahlproblem, Randomisierte Berechnung des Medians, Auswahl in linearer Zeit Slides 3:[de] [en]
Handout 3:[de] [en]
---
4 DO 28.02. C++ Vertieft (I) Kurzwiederholung (Vektoren, Zeiger und Iteratoren), Bereichsbasiertes for, Schlüsselwort auto, eine Klasse für Vektoren, Subskript-Operator, Move-Konstruktion, Iteration. Slides 4:[de] [en]
Handout 4:[de] [en]
Induction Proofs, Running Times, Median Algorithms, Vectors
Slides: [de] [en]
5 MO 04.03. Sortieren I: Insertion-Sort, Selection-Sort, Bubble-Sort, Shell-Sort
Sortieren II: Heapsort: implizite Repräsentation vom Heap im Array, Heapbilden in Linearzeit, Mergesort, Quicksort: Schlüsselvergleiche im besten/schlechtesten Fall.
Slides 5:[de] [en]
Handout 5:[de] [en]
--- Skiplist
6 DO 07.03. Fortsetzung Sortieren II
Slides 6: [de] [en]
Handout 6:[de] [en]
Compare Sort Algorithms, Vector Implementation and Heap-Sort
Slides: [de] [en]
7 MO 11.03. Sortieren III: Schlüsselbewegungen und Speicherbedarf beim Quicksort, Quicksort randomisiert, Untere Schranken, Radixsort. C++ II: Templates.
Slides 7:[de] [en]
Handout 7:[de] [en]
--- AVL Tree
8 DO 14.03. Elementare Datenstrukturen Stapel, Warteschlange, Implementationsvarianten der verkettete Liste
Amortisierte Analyse beim Multistack
Wörterbücher : Amortisierte Analyse Move-To-Front, Skipliste
Slides 8:[de] [en]
Handout 8:[de] [en]
Amortized Analysis Dynamic Array, Vector Template
Slides: [de] [en]
9 MO 18.03. Wörterbücher II: Hashing Hashtabellen, Pre-Hashing, Kollisionsauflösung durch Verkettung, Einfaches Gleichmässiges Hashing, Übliche Hashfunktionen,
Slides 9:[de] [en]
Handout 9:[de] [en]
---
10 DO 21.03. Hashing ctd Tabellenvergrösserung, offene Hashverfahren (Sondieren), Gleichmässiges Hashing, Universelles Hashing, Perfektes Hashing. Hashing: Open Hashing, Cockoo Hashing, Division Method, Rabin-Karp
Slides: [de] [en]
11 MO 25.03. (Perfect Hashing ctd.) C++ III Funktoren und Lambda. Slides 10:[de] [en]
Handout 10:[de] [en]
--- AVL Tree
12 DO 28.03. Wörterbücher III: Bäume Natürliche Suchbäume, AVL Bäume
Slides 11:[de] [en]
Handout 11:[de] [en]
Binary Search Trees, AVL Trees and Heaps, Functors and Lambdas
Slides: [de] [en]
13 MO 01.04. AVL Bäume ctd. Quadtrees Kollisionsdetektion, Bildsegmentierung Slides 12:[de] [en]
Handout 12:[de] [en]
--- Max-Flow Edmonds-Karp
14 DO 04.04. Quadtrees ctd.
Dynamische Programmierung I Fibonacci, Rod-Cutting
Slides 13:[de] [en]
Handout 13:[de] [en]
Quadtrees: Image Segmentation, Dynamic Programming: Mars Rover, Signal Approximation
Slides: [de] [en]
15 MO 08.04. Dynamische Programmierung I ctd Längste aufsteigende Teilfolge, Editierdistanz (inkl. Längste Gemeinsame Teilfolge), Matrixkettenmultiplikation, Matrixmultiplikation nach Strassen ---
16 DO 11.04. Dynamische Programmierung II Subset Sum Problem, Rucksackproblem, Greedy Algorithmus, Lösungen mit dynamischer Programmierung Dynamic Programming III FPTAS
Slides 14:[de] [en]
Handout 14:[de] [en]
DP
Slides: [de] [en]
17 MO 15.04. Greedy Algorithmen Dynamic Programming vs. Greedy. Gebrochenes Rucksackproblem, Huffman Coding Slides 15: [de] [en]
Handout 15:[de] [en]
[handwritten]
---
18 DO 18.04. Graphenalgorithmen I Notation, Repräsentationsarten, Traversieren (DFS, BFS), Topologisches Sortieren Slides 16:[de] [en]
Handout 16:[de] [en]
[handwritten]
Hufmann Coding, Graph Traversal, Topological Sorting
- MO 22.04. -- Ostern -- --- -- Ostern --
- DO 25.04. -- Ostern -- --- -- Ostern --
19 MO 29.04 Graphenalgorithmen II: Kürzeste Wege Dijkstras Algorithmus auf Distanzgraphen, Algorithmus von Bellman-Ford Slides 17:[de] [en]
Handout 17:[de] [en]
[handwritten]
--- Max-Flow Edmonds Karp
20 DO 02.05. Graphenalgorithmen II: Kürzeste Wege Algorithmus von Floyd-Warshall, Algorithmus von Johnson
Shortest Paths: Path planning in labyrinths, graph distances, Dijkstra, Closeness Centrality
Slides: [de] [en]
21 MO 06.05. Graphenalgorithmen III: Minimale Spannbäume Greedy, Algorithmus von Kruskal, Allgemeine Regeln, Union-Find Struktur, Algorithmus von Jarnik,Prim,Dijkstra, Fibonacci Heaps Slides 18:[de] [en]
Handout 18:[de] [en]
[handwritten]
--- Parallel Programming
22 DO 09.05. Graphenalgorithmen IV: Flüsse in Graphen Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching Slides 19:[de] [en]
Handout 19:[de] [en]
[handwritten]
Minimum Spanning Trees, Union Find, Manual Max-Flow
Slides: [de] [en]
23 MO 13.05. Graphenalgorithmen IV: Flüsse in Graphen (ctd.) Flussnetzwerk, Maximaler Fluss, Schnitt, Restnetzwerk, Max-flow Min-cut Theorem, Ford-Fulkerson Methode, Edmonds-Karp Algorithmus, Maximales Bipartites Matching
Parallele Programmierung I Moore's Law und The Free Lunch, Parallele Ausführung, Hardware Architekturen,
Slides 20:[de] [en]
Handout 20:[de] [en]
---
24 Do 16.05. Parallele Programmierung I (ctd.) Klassifikation nach Flynn, Multi-Threading, Threads in C++, Parallelität und Nebenläufigkeit, Skalierbarkeit: Amdahl und Gustafson, Daten- und Taskparallelität, Scheduling [handwritten] Applying Max Flow, Speedup and Task Parallelism, C++ Threads
Slides: [de] [en]
25 MO 20.05. Parallele Programmierung II Gemeinsamer Speicher, Concurrency, Mutual Exclusion und Race Conditions Data-Race, Interleavings, Memory-Reordering
Slides 21:[de] [en]
Handout 21:[de] [en]
---
26 DO 23.05. Parallele Programmierung III Deadlocks, Deadlock Erkennung und Vermeidung, Producer / Consumer, Monitore und Condition Variablen, Condition Variablen in C++, Slides 22:[de] [en]
Handout 22:[de] [en]
Race Conditions, Deadlock and Starvation, Condition Variables, Lock Granularity
Slides: [de] [en]
27 Mo 27.05. Parallele Programmierung IV C++ Futures, Atomare Register und RMW Operationen, Idee der Lock-freien Programmierung Slides 23:[de] [en]
Handout 23:[de] [en]
Alle Folien dieser Vorlesung / all slides of this course:
Overlays: [de] [en]
Handout: [de] [en]
Handout 2x2:[de] [en]
---
- DO 30.05. -- Auffahrt -- --- Slides: [de] [en]

Übungen

Einschreibung für die Übungen

Die Einschreibung zum Übungssystem erfolgt online. Weitere Informationen während der ersten Vorlesung.

Orte und Zeiten

Die Übungsgruppen sind derzeit wie folgt zugeteilt:

Zeit Ort Assistent Sprache
Fr, 08:15 - 10:00 CAB G 57 Philippe Schlattner english
Fr, 10:15 - 12:00 CAB G 59 Jan Stratmann deutsch
Fr, 10:15 - 12:00 HG D 1.2 Robin Worreby deutsch
Fr, 10:15 - 12:00 RZ F 21 Robin Vogtland deutsch

*: Engl. Übungsgruppe

Kontakt

Felix Friedrich (Dozent)

Diskussionsforum: Slack Link (invite link)

Zur Prüfung

Prüfungsstoff für die Endprüfung, welche in der Prüfungssession Sommer 2017 stattfinden wird, schliesst Vorlesungsinhalt und Übungsinhalte ein.

Die Prüfung ist schriftlich. Erlaubte Hilfsmittel: Vier A4 Seiten (zwei A4 Blätter), handgeschrieben oder min. Fontgrösse 11 Pkt.

Alte Prüfungen

Zum Einsehen alter Prüfungen, erklären Sie bitte Ihr Einverständnis: In order to download old exams, please agree to the following

Alte Prüfung ANDERER Vorlesungen Old exams of OTHER courses

Literatur

  • Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011, auch online / download.
  • Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein: Algorithmen - Eine Einführung, Oldenbourg, 2010
  • Cormen, Leiserson, Rivest, and Stein: Introduction to Algorithms, 3rd ed., MIT Press, 2009. ISBN 978-0-262-03384-8 (recommended english text book)
  • Maurice Herlihy, Nir Shavit, The Art of Multiprocessor Programming, Elsevier, 2012.
  • Anthony Willians, C++ Concurrency in Action, Manning, 2012
  • B. Stroustrup, The C++ Programming Language (4th Edition) Addison-Wesley, 2013.
  • Genaue Behandlung der zugrundeliegenden Mathematik im Buch Concrete Mathematics von Graham, Knuth und Patashnik. [Geht weit über die benötigten Mittel der Vorlesung hinaus].

Remarks for Students of the virtual course 252-0002-AAL

The lecture slides of this physical course are offered both in German and English and are reasonably elaborate. The literature hints provided below will help to understand the material but the slides are otherwise intended to be self-contained.

The exercises (offered in English) are also an important part of the course. It is needless to say that we recommend to work through them -- without looking at the solutions in the first place!

If you want to take the real course, you can do so in the spring semester. The course is offered with (German spoken) lectures and (German or English spoken) recitation sessions.

Kind regards, Felix Friedrich.