Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithmen und Wahrscheinlichkeit

Frühjahrssemester 2018, ETH Zürich

Dozenten: Prof. Angelika Steger
Prof. Emo Welzl
Vorlesung: Dienstag, 13:15 - 15:00 Uhr und Donnerstag, 10:15 - 12:00 Uhr, jeweils in HG F1, bei Bedarf mit Videoübertragung in HG F3
Übungen: Donnerstag, 15:15 - 17:00 Uhr. (Die Einschreibung ist inzwischen geschlossen.)

Weitere Informationen zur Vorlesung und verbindliche Informationen zur Prüfung finden Sie im Vorlesungsverzeichnis.

Letzte Änderungen/News:

  • 06.08.: Die Fragestunde findet am Fr, 10.08., um 10:15 in CAB G 51 statt.
  • 06.08.: Prüfungsinformationen um Schritt-für-Schritt-Anleitung fürs Login ergänzt.
  • 31.07.: Aufgrund der Nachfrage haben wir Lösungen zu den Übungs-Computeraufgaben hinzugefügt.
  • 20.07.: Fehler korrigiert: Durch einen Bug wurden in der Skript-Version vom 21.06. die vorigen Skriptänderungen rückgängig gemacht. Das betrifft insbesondere die Graphiken in Sektion 3.1.2.
  • 11.07.: Fehler korrigiert: Musterlösung zur Klausur HS18, 2b fehlte; Musterlösung zu Minitest 6, Frage 8 war falsch.
  • 21.06.: Skript Update: Typos, Landau-Notation am Anfang hinzugefügt, falsche Verwendung von log statt ln beseitigt.
  • 21.06.: Template für Computeraufgabe "Unequal Wedding" hinzugefügt (Link im pdf).
  • 11.06.: Prüfungsinformationen hinzugefügt.
  • 11.06.: Lösung zu Minitest 6 online.
  • 10.06.: Information zur Berechnung der Bonusnote hinzugefügt.
  • 06.06.: Übungsaufgaben zur Vorbereitung auf die Programmierprüfung hinzugefügt (inklusive ehemaliger Prüfungsaufgaben).

Prüfung

Die schriftliche Prüfung findet am Mo, 13. August statt. Die Programmierprüfung ist am Do, 16. August.

Prüfungsmaterial und Vorbereitung

Prüfungsrelevant ist das Material, das in Vorlesung und Übungen besprochen wurde, und das von Skript, Übungen oder Minitests abgedeckt wird.

Vor der Prüfung werden wir am 10.08. eine Fragestunde anbieten, für allfällige Fragen oder Unklarheiten, die während der Prüfungsvorbereitung auftauchen. Uhrzeit und Ort werden wir noch bekannt geben.

Alte Klausuren:

Probeklausur FS 17 Lösung Probeklausur FS 17
Klausur FS 17 Lösung Klausur FS 17
Klausur HS 18 Lösung Klausur HS 18

Note

Die Klausurnote setzt sich zu 70% aus dem Ergebnis der schriftlichen und zu 30% aus dem Ergebnis der Porgrammierprüfung zusammen. Falls die Bonusnote besser ist als die Klausurnote, so wird die Endnote als gewichtetes Mittel aus der Klausurnote und der Bonusnote berechnet (70% zu 30%). Andernfalls wird die Klausurnote als Endnote genommen.

Hilfsmittel

Hilfsmittel sind keine erlaubt, mit folgenden Ausnahmen:

  • Sie dürfen Ihr eigenes Schreibzeug und eine einfache Uhr (keine Smartphones oder Smartwatches) benutzen. Papier wird gestellt. Während der schriftlichen Klausur werden wir ausserdem eine Formelsammlung zur Verfügung stellen. Bei der Programmierprüfung wird ausserdem noch ein Deckblatt und eine Schritt-für-Schritt-Anleitung zum Einloggen auf den Klausurrechnern an Ihrem Platz liegen. Während der Programmierprüfung wird eine Template-Datei (im Wesentlichen das Main.java-template auf dieser Homepage) vorhanden sein. Ausserdem werden Sie Zugriff auf diese Java-Dokumentation haben (Zugriff nur aus dem ethz-Netzwerk bzw. über vpn).
  • Essen und Trinken sind in vernünftigem Umfang erlaubt (insbesondere darf keine Geruchs- oder Geräuschbelästigung davon ausgehen). Flüssigkeiten sind nur in fest verschliessbaren Behältern erlaubt (keine Tassen, Becher etc).
  • Ohropax und vergleichbare Produkte sind erlaubt, jedoch keine Kopfhörer und kein Kapselgehörschutz.
  • Sie müssen während der Klausur Ihren Studierendenausweis (Legi) dabei haben und (für die Programmierprüfung) Ihr nethz-Passwort auswendig kennen. Wir werden tolerieren, wenn jemand das Passwort auf einem kleinen Zettel mitführt, sofern der Zettel unmittelbar nach Login weggesteckt wird. USB-Sticks sind nicht als Hilfsmittel zum Einloggen erlaubt!
  • Wer weitere Hilfsmittel benötigt (Wörterbuch, Lupe, ...), möge diese bis spätestens 29. Juli per E-Mail bei Johannes Lengler anmelden.

Übungen

An dieser Stelle werden jeden Donnerstag (in Ausnahmefällen Dienstags) Programmieraufgaben bzw. theoretische Aufgaben online gestellt. Sie haben jeweils eine Woche Zeit zur Bearbeitung der Aufgaben. Programmieraufgaben können Sie direkt an einen online-judge schicken. Theoretische Aufgaben werden in den Übungen abgegeben. Wir werden ausserdem Beispiellösungen für alle Übungsblätter vorbereiten und auf dieser Webseite veröffentlichen.

Erster Übungstermin ist Donnerstag, der 22. Februar.

Programmieraufgaben:

Die Programmierübung 0 gibt keine Bonuspunkte und dient Ihnen als Wiederholung.

Ihre Datei sollte Main.java heissen und die Klasse Main enthalten. (Grossschreibung beachten!) Diese Klasse sollte nicht public sein, benutzen Sie also "class Main { ... }" statt "public class Main { ... }".

Scoreboard

You can find a sample main class here.

Unlike the Algorithmen und Datenstrukturen lecture, you are allowed to use packages from the Java libraries (e.g. java.util.HashMap, java.util.PriorityQueue, etc.) unless explicitly stated otherwise on the exercise sheet.

Important: Judge is running on Java 1.6 (or Java 6). None of the exercises will require any advanced features of more up-to-date versions of Java (like lambda expressions).

Woche Datum Übung Submission link Input Output Solutions
1 Di,
20.02.18
Programmierübung 0 Sum It - Submission Input Output Solution
1 Di,
22.02.18
Programmierübung 1 MST - Submission Input Output Solution
2 Di,
08.03.18
Programmierübung 2 Password - Submission Input Output Solution
3 Di,
22.03.18
Programmierübung 3 Winter Season - Submission Input Output Solution
4 Di,
12.04.18
Programmierübung 4 Random Divisors - Submission Input Output Solution
5 Di,
26.04.18
Programmierübung 5 Primality Testing - Submission Input Output Solution
6 Di,
17.05.18
Programmierübung 6 Min Cut - Submission Input Output Solution
7 Di,
31.05.18
Programmierübung 7 Santa Claus - Submission Input Output Solution

The following exercises are provided for practice but do not give bonus points. Exercises marked with an asterisk have appeared in exams in previous years.

Übung Submission link Input Output Solutions
Christmas Tree (*) Christmas Tree - Submission Input Output Solution
Dining Table Dining Table - Submission Input Output Solution
Dominoes Dominoes - Submission Input Output Solution
Important Stops Important Stops - Submission Input Output Solution
Island Tribes Island Tribes - Submission Input Output Solution
Jackpot Jackpot - Submission Input Output Solution
Roulette Roulette - Submission Input Output Solution
Shrinking Array (*) Shrinking Array - Submission Input Output Solution
Unequal Wedding (*) Unequal Wedding - Submission Input Output Solution
Volume Estimation Volume Estimation - Submission Input Output Solution

Theoretische Aufgaben:

Aufwärmübung Lösung Aufwärmübung
Theoretische Übung 1 Lösung 1
Theoretische Übung 2 Lösung 2
Theoretische Übung 3 Lösung 3
Theoretische Übung 4 Lösung 4
Theoretische Übung 5 Lösung 5
Theoretische Übung 6 Lösung 6
Theoretische Übung 7 Lösung 7
Theoretische Übung 8 Lösung 8
Theoretische Übung 9 Lösung 9
Theoretische Übung 10 Lösung 10
Theoretische Übung 11 Lösung 11
Theoretische Übung 12 Lösung 12
Theoretische Übung 13 Lösung 13

Minitests:

Minitest 1 Lösung Minitest 1
Minitest 2 Lösung Minitest 2
Minitest 3 Lösung Minitest 3
Minitest 4 Lösung Minitest 4
Minitest 5 Lösung Minitest 5
Minitest 6 Lösung Minitest 6

Einschreibung in die Übungsstunden

Sie können sich ab der ersten Vorlesungswoche selbstständig für eine Übungsstunde anmelden. Ein späterer Wechsel ist in der Regel nicht möglich.
Wichtig: Melden Sie sich bis spätestens Mittwoch, 21. Februar, für eine Übungsgruppe an. Die Anmeldung zu einer Übungsstunde funktioniert nur, wenn Sie die Vorlesung in myStudies belegt haben.

Melden Sie sich bei Problemen mit der Anmeldung bitte umgehend an Johannes Lengler.

Ablauf der Übungen

In der ersten Übungsstunde werden Sie einer Arbeitsgruppe von zwei bis drei Personen zugeteilt. Die Arbeitsgruppen werden im Laufe des Semesters mehrmals neu eingeteilt. Sie bearbeiten die theoretischen Übungen (nicht die Programmieraufgaben!) innerhalb einer Woche gemeinsam in Ihrer Arbeitsgruppe und geben in der folgenden Übungsstunde eine gemeinsame Lösung ab. Sie dürfen sich bei der Lösung der Aufgaben Inspiration aus anderen Quellen besorgen (Literatur, Kommilitonen, Forum). Allerdings empfehlen wir stark, dass Sie vorher ernsthaft versuchen, die Aufgaben selbständig zu lösen. In jedem Fall erwarten wir, dass Sie nur eigenständig formulierte Lösungen einreichen, selbst wenn Sie Ideen aus anderen Quellen bezogen haben. Ausserdem müssen alle Mitglieder der Arbeitsgruppe die Lösungen verstanden haben. Wir werden bei Verdacht während der Übungsstunde überprüfen, ob Sie die abgegebene Lösung verstanden haben.

Die abgegebenen Lösungen werden prinzipiell von der Assistentin bis zur darauf folgenden Woche korrigiert. Ausserdem wählen wir jede zweite Woche eine Aufgabe aus, für die die eingereichte Lösung einer Arbeitsgruppe von einer anderen Arbeitsgruppe während der Übungsstunde korrigiert wird. Die Assistentin wird die Korrektur bis zur darauf folgenden Übungsstunde ebenfalls bewerten. In den anderen Wochen wird es zu Beginn der Übungen Mini-Tests geben. Ansonsten werden während der Übungsstunde die aktuellen Übungsaufgaben bzw. die Mini-Tests besprochen und allfällige Fragen zur Vorlesung geklärt.

Die Programmierabgaben werden einzeln (nicht in Arbeitsgruppen!) gelöst und innerhalb einer Woche an einen Judge geschickt, der den Code testet. Beachten Sie, dass Sie nur selbständig geschriebenen Code einschicken dürfen! Sie haben beliebig viele Versuche, einen korrekten Code abzuliefern. Auch bei den Programmieraufgabe kann von Ihnen während der Übungsstunde verlangt werden, dass Sie die Ideen Ihres Codes erklären.

Bonuspunkte

Ihre Bonuspunkte können Sie während des Semesters hier einsehen.

Sowohl für das Lösen eines Übungsblattes als auch für die Korrektur während der Übungsstunde können Bonuspunkte erarbeitet werden. Sie bekommen Bonuspunkte für

  • das gemeinsame Lösen und Abgeben des Übungsblattes;
  • die gemeinsame Korrektur eines abgegebenen Übungsblattes in der Übungsstunde (nur wenn Sie selber ein Blatt abgegeben haben!);
  • die Mini-Tests;
  • das individuelle (!) Lösen der Programmieraufgaben.
Sie bekommen nur dann Bonuspunkte für abgegebene Übungsblätter und für Korrekturen, wenn Sie auch persönlich daran mitgearbeitet haben.

Am Ende des Semesters wird aus allen vier Typen von Bonuspunkten (Lösen, Korrektur, Minitests, Programmieren) eine "Bonusnote" ermittelt. Sie fliesst in die Endnote ein, sofern ihre Berücksichtigung vorteilhaft ist. Die Endnote ist das Maximum aus der Note der Sessionsprüfung und dem gewichteten Mittel der Bonusnote (30%) und der Note der Sessionsprüfung (70%).

Bonusnote

Für jede der fünf Kategorien (Kleines Theorieblatt, Grosses Theorieblatt, Korrektur, Programmier-Aufgabe, Minitest) ergibt sich eine individuelle Note (nicht auf 0.25 gerundet) wie folgt. Pro Kategorie wird das schlechteste Ergebnis gestrichen. Die Note 6 erhält man mit 100% der möglichen Punkte (z.B. Kategorie Kleines Theorieblatt: 7 Übungsblätter à je 2 Bonuspunkten, somit sind mit Streichresultat 12 Punkte möglich), die Note 4 mit 50% der möglichen Punkte und die Note 1 mit 0 Punkten. Zwischen diesen drei Eckwerten wird jeweils linear interpoliert. Die Bonusnote (ebenfalls ungerundet), setzt sich dann aus dem gewichteten Mittel dieser fünf Kategorien-Noten zusammen, wobei die Kategorie Grosses Theorieblat Gewicht 2/6 besitzt und alle anderen Kategorien Gewicht 1/6.

Skript

Die Vorlesung wird teils an der Tafel und teils mit Slides abgehalten. Die Slides werden wir jeweils kurz nach der Vorlesung online stellen. Ausserdem wird es ein Skript geben, das im Laufe des Semesters online gestellt wird.

Skript

Fragensammlung zu Kapitel 1 zur Vorbereitung der Minitests.

Fragensammlung zu Kapitel 2 zur Vorbereitung der Minitests.

Fragensammlung zu Kapitel 3 zur Vorbereitung der Minitests.

Voraussetzungen: Graphen und Bäume
Vorlesung 1:
- Wiederholung Graphen: Pfade, Wege, Kreise
- Minimale Spannbäume (MST)
- Blaue/Rote Regel
Slides: lang kurz
Vorlesung 2:
- Algorithmen von Prim und Kruskal
- Union-Find-Datenstruktur
- Shannons Switching Game
- k-zusammenhängend, k-kanten-zusammenhängend
- Satz von Menger
- Artikulationsknoten, Brücken
- Tiefensuche, Breitensuche
Slides: lang kurz
Vorlesung 3:
- Effizientes Suchen von Artikulationsknoten und Brücken
- Hamiltonkreise, Eulertouren
- Dirac's theorem
- P und NP
Slides: lang kurz
Vorlesung 4:
- Eulertouren
- Effizientes entscheiden, ob ein Graph eulersch ist.
- 2-Approximation des Problems des Handlungsreisenden (TSP)
Slides: lang kurz
Vorlesung 5:
- Matchings
- inklusions-maximal und kardinalitäts-maximal
- Greedy-Algorithmus
- augmentierende Pfade
(Tafel-Vorlesung)
Vorlesung 6:
- bipartite Graphen
- 3/2-Approximation für metrisches TSP
- Satz von Hall
Slides: kurz
Vorlesung 7:
- Satz von König
- Färbungen, chromatische Zahl
Slides: lang kurz
Vorlesung 8:
- Greedy-Algorithmus zur Graphfärbung
- Satz von Brooks
Slides: kurz
Vorlesung 9:
- Definition Wahrscheinlichkeitsraum / Laplace-Raum
- Prinzip der Inklusion/Exklusion
- Bedingte Wahrscheinlickeit
- Satz der totalen Wahrscheinlickeit
- Geburtstagsparadox / Balls into Bins
Slides: kurz
Vorlesung 10:
- Satz von Bayes
- Unabhängigkeit von Ereignissen
- Zufallsvariablen
- Erwartungswert
Slides: lang kurz
Vorlesung 11:
- Dichte von Zufallsvariablen
- Verteilungsfunktion von Zufallsvariablen
- Bedingter Erwartungswert
(Tafel-Vorlesung)
Vorlesung 12:
- Indikator Zufallsvariablen
- Varianz
- Standardabweichung
- Coupon Collector Problem
Slides: lang kurz
Vorlesung 13:
- Coupon Collector Problem
- Diskrete Verteilungen: Bernoulli, Binomial, gemeotrisch, Poisson
- mehrere Zufallsvariablen
- Unabhängigkeit von Zufallsvariablen
Slides: kurz
Vorlesung 14:
- Unabhängigkeit von Zufallsvariablen (Fortsetzung)
- Waldsche Identität
- Faltung
Slides: kurz
Vorlesung 15:
- Ungleichungen von Markov, Chebyshev, Chernoff
Slides: kurz
Vorlesung 16:
- Primzahltest
- Wiederholung von randomisierten Algorithmen zur Vergrösserung der Erfolgswahrscheinlichkeit
- Quickselect
Slides: kurz
Vorlesung 17:
- einseitiger/zweiseitiger Fehler
- Monte Carlo-Algorithmen und Las Vegas-Algorithmen
- Analyse von Quickselect und Quicksort
Slides: kurz
Vorlesung 18:
- Target Shooting
- Hashing
Slides: kurz
Vorlesung 19:
- lange Pfade, bunte Pfade
(Tafel-Vorlesung)
Vorlesung 20:
- Kantenkontraktionen
- minimale Schnitte
(Tafel-Vorlesung)
Vorlesung 21 (Flüsse in Netzwerken I):
- maxflow-mincut-Theorem
(Tafel-Vorlesung)
Vorlesung 22 (Flüsse in Netzwerken II):
- Restnetzwerk, augmentierende Pfade
- Ford-Fulkerson-Algorithmus
- Minimale Schnitte als Flussproblem
- Maximales Matching als Flussproblem
(Tafel-Vorlesung)
Vorlesung 23 (Flüsse in Netzwerken II):
- Anwendung von Flüssen: Bildsegmentierung
- Maximale Flüsse als konvexes Optimierungsproblem
- konvexe Optimierung, lineare Programmierung
(Tafel-Vorlesung)
Vorlesung 24:
- kleinster umschliessender Kreis
(Tafel-Vorlesung)
Vorlesung 25:
- kleinster umschliessender Kreis (Fortsetzung)
- Sampling Lemma, Verletzer, extreme Elemente
- Laufzeitreduktion auf Linearzeit durch Randomised_Reduce
(Tafel-Vorlesung)
Vorlesung 26:
- konvexe Hülle
- Jarvis Wrap
- Randomized Incremental Construction
(Tafel-Vorlesung)

Literatur

Es gibt kein Buch, das den Vorlesungsstoff komplett abdeckt. Die folgenden Bücher können jedoch als Sekundärliteratur hilfreich sein.
  • T. Schickinger, A. Steger: Diskrete Strukturen 2: Wahrscheinlichkeitstheorie und Statistik, Springer, 2013
  • T. Ottmann , P. Widmayer: Algorithmen und Datenstrukturen, Spektrum, 2002
  • T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
  • H.J. Prömel, A. Steger: The Steiner Tree Problem: A Tour Through Graphs, Algorithms and Complexity, Vieweg, 2002
  • R. Sedgewick: Algorithmen in C++, Pearson, 2003
  • S Baase, A. van Gelder: Computer Algorithms, Addison Wesley, 2000
  • G. Brassard, P. Bratley: Fundamentals of Algorithms, Prentice Hall, 1996
  • J. Kleinberg, E. Tardos: Algorithm Design, Addison Wesley, 2005

Kontakt

Die Übungen werden von Johannes Lengler organisiert, die Programmieraufgaben (Anfragen falls möglich bitte auf Englisch) von Asier Mujika und Miloš Trujić.