Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
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.
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ü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.
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 |
Es sind keine Hilfsmittel erlaubt, mit folgenden Ausnahmen:
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.
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:
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 |
| 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 |
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.
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.
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
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.
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 |
Die Challenge Aufgabe (siehe Vorlesung 6 und hier) wurde erfolgreich von Leonardi Galli gelöst. Herzlichen Glückwunsch und Guten Appetit!
What follows is a summary of the results of the AlgoWahr exam that took place in August 2019.
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.
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.
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.