Department of Computer Science | Institute of Theoretical Computer Science

CADMO - Center for Algorithms, Discrete Mathematics and Optimization

Algorithmen und Wahrscheinlichkeit

Frühjahrssemester 2019, ETH Zürich

Dozenten: Prof. Angelika Steger
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.

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

Prüfung und Note

Die Prüfung besteht aus einer Computer-Prüfung (150min) und einer schriftlichen Prüfung (90min), die zusammen die Prüfungsnote ergeben. Ihre Endnote für den Kurs setzt sich aus der Prüfungsnote und der Bonusnote (siehe unten) zusammen und berechnet sich als runden(min(6, Prüfungsnote + Bonusnote)), wobei runden(.) auf Viertelnoten rundet.

Please note: In the exam, you will also be able to write your answers in English.

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 eine Fragestunde anbieten, für allfällige Unklarheiten, die während der Prüfungsvorbereitung auftauchen. This will take place in room H52 in CAB Friday August 9 between 13:15 and 14:15.

Alte Klausuren:

Here you can find Moodle quiz parts of old exams. There you will also be able to view the correct solutions after each finished attempt.

Für die schriftliche Klausur finden Sie hier einige Beispiele. Beachten Sie jedoch: Multiple-Choice Teil (Aufgabe 1) sind dieses Jahr Bestandteil der Onlineprüfung; die schriftliche Klausur wird daher keine solche Aufgaben enthalten.

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

Hilfsmittel

Es sind keine Hilfsmittel erlaubt, mit folgenden Ausnahmen:

  • Sie dürfen Ihr eigenes Schreibzeug und eine einfache Uhr (keine Smartphones oder Smartwatches) benutzen. Papier wird gestellt.
  • Die Formelsammlung wird an der schriftlichen Klausur und der Computer-Prüfung ausgedruckt zur Verfügung gestellt. Ebenfalls wir für die Computer-Prüfung ein Audruck der Aufgabenstellung der Programmieraufgaben zur Verfügung gestellt.
  • Während der Computer-Prüfunegn werden Sie keinen Zugriff auf die Java Dokumentation haben. Hingegen können Sie auf dieses Dokument, welches die Lösungen der diesjährigen Programmieraufgaben entält, zugreifen.
  • 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 Anders Martinsson 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 21. Februar.

Programmieraufgaben:

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

The online judging system for programming exercises we will use this term is Code Expert. You can enroll to the system here.

You can find the online documentation on Code Expert here. The following things are different to what is stated in the documentation:

  • The exercises and solutions are automatically judged after you submit it. There will be no 'code review' from any of the teaching assistants.
  • Only the best submission counts!
  • List may be extended...

Important: Solutions are available on Code Expert.

Important: The points obtained in the judge are divided by 100 to obtain the number of bonus points you get. For example, getting 80 points in one exercise in the judge, would mean you get 0.8 bonus points.

Important: Judge is running on Java 11.

Important: 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.

Woche Datum Übung Submission link Input Output
1 Di,
07.03.19
Programmierübung 0 Sum It - Submission
1 Di,
07.03.19
Programmierübung 1 Important stops - Submission

Password - Submission
Input

Input
Output

Output
2 Di,
21.03.19
Programmierübung 2 Christmas Tree - Submission

Random Divisors - Submission
Input

Input
Output

Output
3 Di,
04.04.19
Programmierübung 3 Bag of Colours - Submission

The sum of the dice - Submission

Winter Season - Submission
Input

Input

Input
Output

Output

Output
4 Di,
18.04.19
Programmierübung 4 Random Coins - Submission

Random Triangles - Submission

Min Cut - Submission
Input

Input

Input
Output

Output

Output
5 Di,
09.05.19
Programmierübung 5 Bicycle Auction - Submission

Santa Claus - Submission
Input

Input
Output

Output
5 Di,
23.05.19
Programmierübung 6 Garden of Roses - Submission

City Planning - Submission
Input

Input
Output

Output

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

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, 20. 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 Anders Martinsson.

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 und Bonusnote

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.

Ermittlung der Bonusnote: Für jede "Einheit" (kurzes Übungsblatt, langes Übungsblatt, Peer-Grading, Minitest, Programmieraufgabe) erhalten Sie zwischen 0 und 2 Bonuspunkte. Dabei werden die langen Übungsblätter doppelt gewichtet. Die Bonusnote wird anhand des Verhältnisses der von Ihnen erreichten Bonuspunkte zur maximal erreichbaren Anzahl an Bonuspunkten ermittelt. Beträgt das Verhältnis 80% oder mehr erhalten Sie eine Bonusnote von 0.25. Liegt das Verhältnis darunter, bei x% (x kleiner 80), dann ist die Bonusnote 0.25*x/80.

Skript

Die Vorlesung wird teils an der Tafel und teils mit Slides abgehalten. Die Slides werden wir jeweils kurz nach der Vorlesung online stellen. Zur Vorlesung gibt es ein Skript. Die jeweils aktuelle Version finden Sie hier:

Skript (Stand 23. Juli 2019) This version contains clarification of what is considered examinable content.

Fragensammlung (Stand 12. März 2019) zu Kapitel 1 zur Vorbereitung der Minitests

Fragensammlung (Stand 9. April 2019) zu Kapitel 2 zur Vorbereitung der Minitests

Fragensammlung (Stand 14. Mai 2019) zu Kapitel 3 zur Vorbereitung der Minitests

Voraussetzungen: Graphen, Bäume, Pfade
Vorlesung 1 (19.02.):
- k-zusammenhängend, k-kanten-zusammenhängend
- Satz von Menger
- Artikulationsknoten, Brücken
- Tiefensuche, Breitensuche
- Effizientes Suchen von Artikulationsknoten
Slides: erste Stunde, zweite Stunde
Vorlesung 2 (21.02.):
- Effizientes Suchen von Artikulationsknoten, forts.
- Hamiltonkreise, Eulertouren
- Effizientes entscheiden, ob ein Graph eulersch ist.
Slides: lang kurz
Vorlesung 3 (23.02.):
- Hamiltonkreise, Eulertouren forts
- Gray codes
- Dirac's theorem
Slides: lang kurz
Vorlesung 4 (28.02.):
- Suchen von Hamiltonkreise, Dynamische Programmierung
- P und NP
- 2-Approximation des Problems des Handlungsreisenden (TSP)
Slides: lang kurz
Vorlesung 5 (05.03.):
- Matchings
- Satz 1.49
- inklusions-maximal und kardinalitäts-maximal
- Greedy-Algorithmus und Satz 1.44
Slides
Vorlesung 6 (07.03.):
- 3/2-Approximation für metrisches TSP
- Satz von Hall
Slides
Vorlesung 7 (12.03.):
- Satz 1.48
- Färbungen, chromatische Zahl - Greedy-Algorithmus zur Graphfärbung
- Satz von Brooks
Slides
Vorlesung 8 (14.03):
- Definition Wahrscheinlichkeitsraum / Laplace-Raum
- Prinzip der Inklusion/Exklusion
- Bedingte Wahrscheinlickeit
Slides: lang kurz
Vorlesung 9 (19.03.):
- Definition Wahrscheinlichkeitsraum / Laplace-Raum
- Prinzip der Inklusion/Exklusion
- Bedingte Wahrscheinlickeit
- Satz der totalen Wahrscheinlickeit
- Geburtstagsparadox / Balls into Bins
Slides: lang kurz
Vorlesung 10 (21.03.):
- Satz von Bayes
- Unabhängigkeit von Ereignissen
- Zufallsvariablen
- Erwartungswert
Slides
Vorlesung 11 (26.03.):
- Dichte- und Verteilungsfunktion von Zufallsvariablen
- Binomialverteilung und Geometrische Verteilung
- Linearität des Erwartungswertes
Slides: lang kurz
Vorlesung 12 (28.03.):
- Dichtefunktion und Erwartungswert für Verteilungen: Bernoulli, Binomial, gemeotrisch
- Gedechtnislosigkeit
- Coupon Collector Problem
Slides: lang kurz
Vorlesung 13 (02.04.):
- Poisson-Verteilung
- Varianz
- mehrere Zufallsvariablen
- Unabhängigkeit von Zufallsvariablen
Slides: lang kurz
Vorlesung 14 (04.04.):
- Unabhängigkeit von Zufallsvariablen (Fortsetzung)
- Momente zusammengesetzter Zufallsvariablen
- Varianz für das Coupon-Collector Problem
- Faltung
Slides
Vorlesung 15 (09.04.):
- Waldsche Identität
- Ungleichungen von Markov, Chebyshev, Chernoff
Slides
Vorlesung 16 (11.04.):
- Monte Carlo-Algorithmen und Las Vegas-Algorithmen
- einseitiger/zweiseitiger Fehler
- Wiederholung von randomisierten Algorithmen zur Vergrösserung der Erfolgswahrscheinlichkeit
Slides
Vorlesung 17 (16.04.):
- Analyse von Quickselect
- Target Shooting
- Hashing
Slides
Vorlesung 18 (18.04.):
- Kargers Min-Cut Algorithmus
- Miller-Rabin Primzahltest
Slides
Vorlesung 19 (30.04.):
- lange Pfade, bunte Pfade
Slides
Vorlesung 20 (02.05.):
- Kurze lange Pfade, Zufallsfärbungen
- Flüsse in Netzwerken, Modellierung
Slides: lang kurz
Vorlesung 21 (Flüsse in Netzwerken I, 07.05.):
- Restnetzwerk, augmentierende Pfade
- Ford-Fulkerson-Algorithmus
- Minimale Schnitte als Flussproblem
Slides: lang kurz
Vorlesung 22 (Flüsse in Netzwerken II, 09.05.):
- maxflow-mincut-Theorem
- Maximales Matching als Flussproblem
Slides
Vorlesung 23 (Flüsse in Netzwerken III, 14.05.):
- Maximum matching and generalizations as flow problems
- Anwendung von Flüssen: Bildsegmentierung
- Finding internal-edge/vertex-disjoint paths in graphs
Slides
Vorlesung 24 (16.05.):
- kleinster umschliessender Kreis
Slides
Vorlesung 25 (21.05.):
- kleinster umschliessender Kreis (Fortsetzung)
- konvexe Hülle
Slides
Vorlesung 26 (24.05.):
- konvexe Hülle (Fortsetzung)
- Jarvis Wrap
- lokal Verbessern
- ebene Graphen und Triangulierungen
Slides
Vorlesung 27 (28.05.):
- Euler Relation
- LocalRepair
- Konvexe Hülle und Sortieren
Slides

Challenge Exercise

Die Challenge Aufgabe (siehe Vorlesung 6 und hier) wurde erfolgreich von Leonardi Galli gelöst. Herzlichen Glückwunsch und Guten Appetit!

 

Easter Chocoloate Bunny

 

Exam statistics

What follows is a summary of the results of the AlgoWahr exam that took place in August 2019.

Bar chart for grade distribution

This bar diagram shows the grade distribution from the exam in August 2019. A total of 331 students took the exam. 70% recieved a grade of 4 or more, and 26 students recieved a 6.

Scatter plot showing correlation between Moodle quiz score and exam grade

New for this year's computer exam was a multiple choice quiz in Moodle. Here, we see how the result from the multiple choice part correlates with the result from the whole exam.

Scatter plot showing correlation between exam grade and bonus points

Finally, here we see the correlation between bonus points recieved during the course and the result on the final exam. The total number of bonus points achievable in the course was 72. The horizontal line at 57.6 shows the minimum number of bonus points needed to recieve the maximum bonus grade of 0.25. A total of 169 out of 331 student taking the exam managed to achieve at least this many points. The average bonus grade was 0.215.

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 Anders Martinsson und Frederik Benzing organisiert, die Programmieraufgaben von Asier Mujika und Miloš Trujić. Alle Anfragen falls möglich bitte auf Englisch.