Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Datenstrukturen & Algorithmen

Auf dieser Seite finden Sie Informationen zur
Vorlesung Datenstrukturen & Algorithmen im Frühjahrssemester 2016 an der ETH Zürich.

Dozent: Prof. Peter Widmayer
Vorlesung: Donnerstag, 8:15 - 10:00 Uhr (HG E 7), Freitag, 10:15 - 12:00 Uhr (HG E 7)

Weitere Informationen zur Vorlesung finden Sie im Vorlesungsverzeichnis.

Shortcuts: Übungsblätter -- Exercise sheets

Bitte lesen Sie das Informationsblatt im internen Bereich. Dort finden Sie alle weiteren Informationen zur Einteilung der Übungsgruppen und eine Eclipse Projektvorlage für die Programmieraufgaben. Die Zugangsdaten sind in MyStudies unter "Lernmaterialien" ersichtlich.

Tricky Bonus Questions

Andreas Bärtschi und Daniel Graf haben im Laufe des Semesters ein paar besonders knifflige Aufgaben gesammelt: Bonus Questions. Wer die meisten Rätsel knackt, gewinnt mindestens einen Buchpreis (z.B. Datenstrukturen und Algorithmen von Widmayer, Ottmann oder Introduction to Algorithms von Cormen, Leierson, Rivest und Stein). Abgabeschluss ist der Tag der D&A-Prüfung. Viel Spass!

Vorlesung

Das Buch zur Vorlesung können Sie innerhalb des ETH-Netzes online lesen. Die Inhaltsangaben zur Vorlesung, Angaben zu Literatur und Links werden auf dieser Seite laufend aktualisiert.

Hier finden Sie ausserdem eine Liste der Prüfungen der vergangenen Jahre.

Datum behandelte Themen Literatur und Mitschrift (Disclaimer)
25.02.2016

Einführung. Algorithmenentwurf. Güte von Algorithmen.

  • Begriff des Algorithmus. Rolle der Algorithmik innerhalb der Informatik
  • Beispiel des Algorithmenentwurfs: Schnelle Multiplikation ganzer Zahlen, Karatsuba/Ofman 1962. Star ermitteln durch Fragen
  • Einheitskostenmodell. O-Notation, Omega, Theta

Kapitel 1.1-1.2 im Buch

Mitschrift
26.02.2016

Algorithmenentwurf durch einfache Induktion.

  • Maximum Subarray: Naive Lösung, Präfixsumen vorberechnen, Divide-and-Conquer, linear Scan

Kapitel 1.3

Mitschrift
03.03.2016

Suchen I: Suchen. Das Auswahlproblem.

  • Lineare Suche, binäre Suche, Interpolationssuche, obere und untere Schranken.
  • Randomisierte Berechnung des Medians. Berechnung des Medians nach Blum.

Kapitel 3.1 und 3.2

Folien
Mitschrift
04.03.2016

Suchen II: Hashing.

  • Prinzip des Hashing, Hashfunktionen, universelles Hashing.
  • Kollisionsauflösung durch Verkettung, offene Hashverfahren, Sondieren.

Kapitel 4.1 bis 4.3.2, 4.3.4

Notizen
Mitschrift
10.03.2016

Sortieren I: Elementare Verfahren. Heapsort.

  • Bubblesort, Odd-Even Transposition Sort, Sortieren durch Auswahl, Sortieren durch Einfügen.
  • Heapsort, implizite Repräsentation des Heap, Heapbilden in Linearzeit.

Kapitel 2.1 und 2.3

Mitschrift
11.03.2016

Sortieren II: Mergesort, Quicksort.

  • Mergesort.
  • Quicksort: Schlüsselvergleiche im besten und im schlechtesten Fall, Bewegungen im schlechtesten Fall. Zusätzlich benötigter Speicher. Schlüsselvergleiche bei randomisiertem Quicksort skizziert.

Kapitel 2.2 und 2.4

Mitschrift
17.03.2016

Sortieren III: Untere Schranken. Radixsort. Wörterbücher I: Elementare Konzepte.

  • Untere Schranke mit Entscheidungsbaum, mittlere Höhe eines Blatts im Binärbaum. Radix-Exchange-Sort.
  • Wörterbuch: Array, lineare Liste, Skipliste.

Kapitel 1.5.1 - 1.5.2, 1.6 - 1.7, 2.5, 2.8

Mitschrift
18.03.2016

Wörterbücher II: Natürliche Suchbäume. AVL-Bäume.

  • Natürlicher binärer Suchbaum (Durchlaufen, Suchen, Einfügen, Entfernen).
  • AVL-Bäume: Höhe,Einfügen.

Kapitel 5.1 und 5.2.1

Mitschrift
24.03.2016

Wörterbücher III: AVL-Bäume. Amortisierte Analyse. Selbstanordnung.

  • AVL-Bäume: Amortisierte Analyse des Einfügens.
  • Selbstanordnung in linearen Listen: Move-to-Front mit Analyse.

Kapitel 5.2.1 und 3.3

Mitschrift
07.04.2016

Dynamische Programmierung I.

  • Längste aufsteigende Teilfolge
  • Editierdistanz.
  • Matrixkettenmultiplikation

Kapitel 1.2.3
Cormen et al.: Kapitel 15

Mitschrift
08.04.2016

Dynamische Programmierung II.

  • Subset sum.
  • Rucksackproblem.
  • FPTAS.

Kapitel 7.2 und 7.3

Mitschrift
14.04.2016

Algorithmenentwurf: divide-and-conquer, dynamisches Programmieren, greedy

  • Matrixmultiplikation nach Strassen.
  • Häufigkeitsoptimale Suchbäume, Konstruktion mit dynamischer Programmierung.
  • Huffman Coding.

Kapitel 1.2.3 und 5.7
Cormen et al.: Kapitel 16.3
15.04.2016

Selbstanordnung in Suchbäumen: Splay Trees

  • Splay Trees.

Kapitel 5.4

Mitschrift
21.04.2016

Graphenalgorithmen 1.

  • Reflexive, transitive Hülle.
  • Traversieren: DFS, BFS.
  • Zusammenhangskomponenten.
  • Topologisches Sortieren.

Kapitel 9.1 bis 9.4

22.04.2016

Graphenalgorithmen 2.

  • Minimaler spannender Baum: Grundlage, Greedy-Verfahren, Kruskal mit Union-Find.

Kapitel 6.2 und 9.6

28.04.2016

Graphenalgorithmen 3.

  • Minimaler spannender Baum: Minimaler Spannbaum mit dem Algorithmus von Prim/Dijkstra.
  • Fibonacci-Heap (ohne Analyse).

Kapitel 6.1 und 9.6

29.04.2016

Graphenalgorithmen 4.

  • Analyse des Fibonacci Heaps.
  • Kürzeste Wege: Dijkstra, Ford, Bellman.

Kapitel 6.1 und 9.5.1 bis 9.5.2

06.05.2016

Graphenalgorithmen 5. Kürzeste Wege

  • One-to-all kürzeste Wege: Bellman; Bellman-Ford.
  • All-to-all kürzeste Wege: Floyd-Warshall; Johnson.
  • Heuristiken: Bidirektional, A*.

Kapitel 9.5.2 und 9.5.3

12.05.2016

Wunderbare Welt der Algorithmen.

  • Online-Algorithmen (Kuhproblem)
  • Streaming-Algorithmen (majority element)
  • verteilte Algorithmen (Chang's echo, two generals)
  • Approximationsalgorithmen (Christofides)



Mitschrift
13.05.2016

Backtracking, Branch-and-Bound.

  • Backtracking. Beispiele 4 Damen, SAT.
  • Branch-and-Bound. Beispiele MAX SAT, Knapsack, TSP.


Kapitel 7.5
ergänzende Unterlagen
19.05.2016

Flüsse in Netzen I.

  • Zunehmende-Wege-Algorithmus nach Ford, Fulkerson.
  • Max-Flow-Min-Cut Theorem.


Kapitel 9.7
20.05.2016

Flüsse in Netzen II.

  • Vergrössernde Wege durch Kapazitätenskalierung; kürzeste vergrössernde Wege nach Edmonds/Karp; nach Dinitz.
  • Matching in bipartiten Graphen.


Kapitel 9.7 und 9.8.1
26.05.2016

Geometrische Algorithmen I.

  • Konvexe Hülle für Punktmenge in der Ebene. Jarvis, Graham, linearer Scan.
  • Schnitt orthogonaler Liniensegmente.


Kapitel 8.1 und 8.2
01.06.2016

Geometrische Algorithmen II.

  • Schnitte beliebig orientierter Liniensegmente.
  • Intervalle als 2-dim Punkte.


Kapitel 8.3.2–8.5

Mitschrift
02.06.2016

Geometrische Algorithmen III.

  • Schnitt achsenparalleler Rechtecke: 2-dim range tree; Segmentbaum; tile tree/Intervallbaum; Prioritätssuchbaum.


Kapitel 8.3.3–8.5

Mitschrift
03.06.2016

Datenstrukturen für Externspeicher.

  • B-Bäume.


Kapitel 5.5

Weiterführende Literatur

Übungen

Die Übungen werden jeweils am Mittwoch von 15:15 bis 17:00 (für Studenten der Rechnergestützten Wissenschaften von 16:15 bis 18:00) durchgeführt. Verantwortlich für die Organisation der Übungen ist Thomas Tschager, CAB H39.1, email: thomas.tschager _at_ inf.ethz.ch.

Hinweise zu den Programmierübungen: Sie können mehrmals Lösungen zu einer Programmieraufgabe hochladen. Bitte beachten Sie, dass der Judge nur Lösungen akzeptiert, die eine Klasse class Main (groß geschrieben) enthält, welche nicht als public deklariert ist. Beachten Sie dazu auch die Vorlage und das Tutorial im internen Bereich.

Antonios Thomas bietet jeden Mittwoch von 12 bis 13 Uhr im Raum CAB G 15.2 eine Sprechstunde für Fragen zum Judge und den Programmieraufgaben an.

Übungsblätter Lösungen
Übungsblatt 1 Lösung 1
Übungsblatt 2 Lösung 2
Übungsblatt 3
Testdaten (Vorlage und Tutorials im internen Bereich)
Lösung einschicken
Lösung 3
Übungsblatt 4
Testdaten (Vorlage und Tutorials im internen Bereich)
Lösung einschicken
Lösung 4
Übungsblatt 5
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 5
Übungsblatt 6
Testdaten
Lösung einschicken
Lösung 6
Übungsblatt 7
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 7
Übungsblatt 8
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 8
Übungsblatt 9
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 9
Übungsblatt 10
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 10
Übungsblatt 11
Testdaten
Lösung einschicken
Lösung 11
Übungsblatt 12
Testdaten und Code-Vorlage
Lösung einschicken
Lösung 12
Übungsblatt 13
Testdaten
Lösung einschicken
Lösung 13
Übungsblatt 14
Testdaten
Lösung einschicken
Lösung 14 (überarbeitet!)

Mitschrift

Wir möchten eine Mitschrift für die Vorlesung in diesem Semester erstellen. Diese Mitschrift (inkl. Notizen und Folien) und ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich unter diesem Doodle-Link.

Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an grafdan _at_ inf.ethz.ch.


Information for English speaking students

Although the lecture and many readings are in German, there will be an exercise group in English. You may hand in both exercises and the final exam in English. When signing up for the final exam, please indicate that you require a translation of the exam in English.

We also provide a list of previous exams in English (where available) and German.

Date Topics Literature
25.02.2016

Introduction and Algorithm Design.

  • Introduction and Algorithm Design. Role of algorithms in computer science.
  • An example for the design of algorithms: fast multiplication of integers, Karatsuba/Ofman 1962. Finding a star by asking questions.
  • Uniform cost model. Growth of functions: big O notation, Omega, Theta.

Cormen et al.:
Chapter 1–3
26.02.2016

Algorithm Design by Induction.

  • Maximum subarray problem: naı̈ve algorithm, precomputation of prefix sums, divide and conquer, linear scan.

Cormen et al.:
Chapter 4.1
03.03.2016

Searching I: Searching. Computing the Median.

  • Linear search, binary search, interpolation search, upper and lower bounds.
  • Randomized median computation. Blum’s algorithm for computing the median.

Cormen et al.:
Problem 2.1-3, 2.2-3, 2.3-5
Chapter 9
04.03.2016

Searching II: Hashing.

  • Hash tables, hash functions, universal hashing.
  • Collision resolution by chaining, open hashing, probing.

Cormen et al.:
Chapter 11
10.03.2016

Sorting I: Elementary Sorting Methods. Heapsort.

  • Bubblesort, odd-even transposition sort, selection sort, insertion sort.
  • Heapsort, implicit representation of the heap, creating a heap in linear time.

Cormen et al.:
Chapter 2, Problem 2.2-2, 2-2,
Chapter 6
11.03.2016

Sorting II: Mergesort, Quicksort.

  • Mergesort.
  • Quicksort: key comparisons: best case, worst case; Movements: worst case; Additionally required memory. Key comparisons for randomized quicksort.

Cormen et al.:
Chapter 2.3.1 and 7
17.03.2016

Sorting III: Lower bounds. Radix sort. Dictionaries I: Basic concepts.

  • Lower bound for decision-based sorting: decision tree, average height of a leaf in a binary tree. Radix Exchange Sort.
  • Dictionaries: Array, linear list, skip list.

Cormen et al.:
Chapter 8.1, 8.3, 10.2
18.03.2016

Dictionaries II: Binary Search Trees, AVL Trees.

  • Binary search tree: traversal,searching, insertion, deletion.
  • AVL trees: height of the tree, insertion.

Cormen et al.:
Chapter 12.1-12.3

Goodrich et al.:
Chapter 3.2
24.03.2016

Dictionaries III: AVL Trees. Amortized Analysis. Self-Organizing Linear Lists.

  • AVL trees: Amortized analysis of the insert operation.
  • Self-organizing linear lists, move-to-front rule (with analysis).

Goodrich et al.:
Chapter 3.2

Cormen et al.:
Chapter 17, esp. Problem 17-5
07.04.2016

Dynamic Programming 1

  • Longest increasing subsequence
  • Edit distance.
  • Matrix chain multiplication.

Cormen et al.:
Chapter 15
08.04.2016

Dynamic Programming 2

  • Subset sum.
  • Knapsack problem.
  • FPTAS.

Cormen et al.:
Chapter 35.5

Vazirani:
Chapter 8.1 and 8.2
14.04.2016

Algorithm design: divide-and-conquer, dynamic programming, greedy

  • Matrix multiplication by Strassen.
  • Optimal search trees, construction with dynamic programming.
  • Huffman Coding.

Cormen et al.:
Chapter 4.2, 15.5 and 16.3
15.04.2016

Self-organizing search trees: Splay trees

  • Splay Trees.

Goodrich and Tamassia:
Chapter 3.4
21.04.2016

Graph Algorithms I

  • Reflexive and transitive closure.
  • Graph traversal: BFS, DFS.
  • Connected components.
  • Topological sorting.

Cormen et al.:
Chapter 22
22.04.2016

Graph Algorithms II

  • Minimum spanning trees: introduction, greedy algorithms, Kruskal’s algorithm with union find structure.

Cormen et al.:
Chapter 23
28.04.2016

Graph Algorithms III

  • Minimum spanning trees with Prim/Dijkstra.
  • Fibonacci heaps (w/o analysis)

Cormen et al.:
Chapter 19 and 23
29.04.2016

Graph Algorithms IV

  • Analysis of Fibonacci heaps
  • Shortest paths from a single source. Algorithm of Dijkstra, Ford, Bellman

Cormen et al.:
Chapter 19 and 24.1–24.3
06.05.2016

Graph Algorithms V. Shortest paths

  • One-to-all shortest paths: Bellman; Bellman-Ford.
  • All-to-all shortest paths: Floyd-Warshall; Johnson.
  • Heuristics: Bidirectional, A^*.

Cormen et al.:
Chapter 24.1, 25.2 and 25.3
12.05.2016

Wunderbare Welt der Algorithmen.

  • Online algorithms (lost-cow problem)
  • Streaming algorithms (majority element)
  • Distributed algorithms (Chang's echo, two generals)
  • Approximation algorithms (Christofides)



13.05.2016

Backtracking, Branch-and-Bound.

  • Backtracking. Examples 4 Damen, SAT.
  • Branch-and-Bound. Examples MAX SAT, Knapsack, TSP.


Skiena: Chapter 7.1
Wolsey, Ch. 7.1–7.2
19.05.2016

Flows in Networks I.

  • Augmenting path algorithm by Ford and Fulkerson.
  • Max-flow min-cut theorem.


Cormen et al.:
Chapter 26.1 and 26.2
20.05.2016

Flows in Networks II.

  • Augmenting path by capacity scaling; shortest augmenting paths (Edmonds and Karp), Dinic
  • Matchings in bipartite graphs.


Ahuja, Chapter 7.5
Cormen et al.:
Chapter 26.2 – 26.3, Problem 26.3-4
26.05.2016

Geometric Algorithms I.

  • Convex hull of points in the plane: Jarvis, Graham, linear scan.
  • Intersection of orthogonal line segments


deBerg, Ch. 1.1 – 1.2

Cormen et al.: Chapter 33.1 – 33.3
01.06.2016

Geometric Algorithms II.

  • Intersection of arbitrarily oriented line segments.
  • Intervals as 2-dimensional points


deBerg, Ch. 5.3, 10.1 – 10.3

Cormen et al.: Chapter 33.2
02.06.2016

Geometric Algorithms III.

  • Intersection of axis-parallel rectangles: 2-dimensional range trees; segment trees; tile trees/interval trees, and priority trees


deBerg, Ch. 5.3, 10.1 – 10.3
03.06.2016

External Memory Structures.

  • B-Trees


Cormen et al.:
Chapter 18

Literature

Exercises

Programming exercises: You can upload your solutions multiple times to the judge. Please note that your solutions needs to contain a class Main (not declared public).

Every Wednesday from 12:00 to 13:00 in CAB G 15.2 there will be a question and answer session for problems regarding the programming exercises and the judge.

Exercise sheets Example Solutions (in german)
Exercise sheet 1 Solution 1 (german)
Exercise sheet 2 Solution 2 (german)
Exercise sheet 3
Test cases (template and tutorials)
Submission link
Solution 3 (german)
Solution 3 - Programming Exercise
Exercise sheet 4
Test cases (template and tutorials)
Submission link
Solution 4 (german)
Solution 4 - Programming Exercise
Exercise sheet 5
Test cases and code template
Submission link
Solution 5 (german)
Exercise sheet 6
Test cases
Submission link
Solution 6 (german)
Exercise sheet 7
Test cases and code template
Submission link
Solution 7 (german)
Exercise sheet 8
Test cases and code template
Submission link
Solution 8 (german)
Solution 8 - Programming Exercise
Exercise sheet 9
Test cases and code template
Submission link
Solution 9 (german)
Exercise sheet 10
Test cases and code template
Submission link
Solution 10 (german)
Exercise sheet 11
Test cases
Submission link
Solution 11 (german)
Exercise sheet 12
Test cases and code template
Submission link
Solution 12 (german)
Exercise sheet 13
Test cases
Submission link
Solution 13 (german)
Exercise sheet 14
Test cases
Submission link
Solution 14 (german, new version!)