Department of Computer Science | Institute of Theoretical Computer Science
Department of Computer Science | Institute of Theoretical Computer Science
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.
Die schriftliche Prüfung findet am Mo, 13. August statt. Die Programmierprüfung ist am Do, 16. August.
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.
| Probeklausur FS 17 | Lösung Probeklausur FS 17 |
| Klausur FS 17 | Lösung Klausur FS 17 |
| Klausur HS 18 | Lösung Klausur HS 18 |
Hilfsmittel sind keine 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 22. Februar.
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 { ... }".
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.
| 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, 21. 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. 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%).
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.
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.
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) |