Algorithmen und Wahrscheinlichkeit

Frühjahrssemester 2020, ETH Zürich

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

Letzte Änderungen/News:

• Dear students: This is the webpage for AlgoWahr 2020, before we went online. Click here for the AlgoWahr 2021 website.

• Der Kursinhalt ist von nun an auf Moodle zu finden, alle wichtigen Änderungen werden dort kommuniziert.
• Minitest finden von nun an auf Moodle statt. Jeweils von 15:10-15:30 am Donnerstag (am 12.03.; 26.03.; 09.04.; 30.04.; 14.05.; 28.05.).
• 05.03 The first programming assignment is now available through CodeExpert. Please note that only submitted solutions will be awarded bonus points.
• 05.03 The first programming assignment will be available through CodeExpert later today (Thursday). Please see below if you still have issues logging in.
• 25.02 The first minitest will take place at the beginning of exercise class this Thursday (27.02). To help you prepare, we have published a list of sample questions (see below under the title 'Minitest').
• 25.02 Some students have reported issues logging into CodeExpert. Technical questions or problems with the Code Expert system should be submited directly to expert@inf.ethz.ch.
• 20.01 The course homepage is alive!

Prüfung

Die Prüfung besteht aus einer Computer-Prüfung (150min) und einer schriftlichen Prüfung (90min).

Sie dürfen Ihre Antworten auf Deutsch oder auf Englisch schreiben.

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.

Alte Klausuren:

Für die schriftliche Klausur finden Sie hier einige Beispiele. Please note that, since 2019, the multiple choice part of the exam have been moved from the written exam to the computer exam.

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

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.

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.
• 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 20. Februar.

Programmieraufgaben:

The online judging system for programming exercises we will use this term is Code Expert. You can enroll to the system here. You have two simple exercises to test the environment ('Sum it' and 'Toppling Dominoes'). These exercises do not give any bonus points.

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 will be available through Code Expert.
• 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.
• Judge is running on Java 11.
• 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.
• NEW! Questions regarding exercises can and should be submitted through the messaging system of Code Expert. This will be the only way of asking questions during the computer part of the exam.
• NEW! Technical questions or problems with the Code Expert system should be submitted directly to expert@inf.ethz.ch.

Woche	Datum	Übung	Submission link
1	Di, 18.02.20	Programmierübung 0	Sum It - Submission Toppling Dominoes - Submission
3	Do, 05.03.20	Programmierübung 1	Important Stops - Submission Password - Submission

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
Theoretische Übung 4

Minitests:

Fragensammlung (Stand 25. Februar 2020) zu Kapitel 1 zur Vorbereitung der Minitests

Minitests finden jede zweite Woche am Donnerstag zu Beginn der Übungstunde statt, beginnend in der zweiten Woche. Diese bestehen aus ungefähr 10-15 Wahr/Falsch Fragen oder Lückentextartigen Fragen. Die Dauer ist ungefähr 10 Minuten. Der Test kann Fragen zum Gesamten Material des Kurses bis und einschliesslich des Dienstages der selben Woche beinhalten, wobei der Fokus auf dem Material der letzten zwei Wochen liegen wird.

Minitest 1

Lösung Minitest 1

Einschreibung in die Übungsstunden

Sie können sich ab der ersten Vorlesungswoche selbstständig für eine Übungsstunde in myStudies anmelden. Ein späterer Wechsel ist in der Regel nicht möglich.

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

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.

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 17. Februar 2020)

Voraussetzungen: Grundbegriffe, Bäume, Pfade (Kapitel 1.1-1.3)
Vorlesung 1 (18.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 (20.02.): - Hamiltonkreise, Eulertouren - Effizientes entscheiden, ob ein Graph eulersch ist. - Gray codes	Slides: lang kurz
Vorlesung 3 (25.02.): - Satz von Dirac - Suchen von Hamiltonkreise, Dynamische Programmierung	Slides (Mainly on blackboard)
Vorlesung 4 (27.02.): - P und NP - 2-Approximation des Problems des Handlungsreisenden (TSP) - Matchings - inklusions-maximal und kardinalitäts-maximal	Slides: lang kurz
Vorlesung 5 (03.03.): - Greedy-Algorithmus und Satz 1.44 - 3/2-Approximation für metrisches TSP - Satz von Hall	Slides
Vorlesung 6 (05.03.): - Satz 1.48 (Frobenius) - Satz 1.49 - Färbungen, chromatische Zahl - Greedy-Algorithmus zur Graphfärbung - Satz von Brooks	Slides
Vorlesung 7 (10.03.): - Einfürung in die Wahrscheinlichkeitstheorie - Definition Wahrscheinlichkeitsraum / Laplace-Raum - Prinzip der Inklusion/Exklusion	Slides
Vorlesung 8 (14.03): - Prinzip der Inklusion/Exklusion - Bedingte Wahrscheinlickeit - Satz der totalen Wahrscheinlickeit - Geburtstagsparadox / Balls into Bins	Slides: Slides

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 Charlotte Knierim organisiert. For questions about organization or theory exercises, please contact Anders Martinsson. For questions regarding CodeExpert or programming exercises please contact Asier Mujika or Miloš Trujić. Alle Anfragen falls möglich bitte auf Englisch.