The Kurs behandelt die Grundlagen des Entwurfs und der Analyse von Algorithmen und Datenstrukturen. Diese werden anhand von klassischen algorithmischen Problemen einschliesslich Graphenproblemen studiert. Die dazu nötige Einführung in die Graphentheorie ist ebenfalls Teil dieses Kurses.
Lernziel
Verständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen. Verständnis der Grundlagen der Graphentheorie und einiger ihrere grundlegenden Algorithmen,
Inhalt
Der Kurs ist eine Einführung in die Grundlagen des Designs and der Analyse von Algorithmen. Dazu gehören zum einen klassische Entwurfsmuster für Algorithmen wie Induktion, Divide-and-Conquer und dynamische Programmierung. Diese werden anhand von klassischen Problemen wie zum Beispiel Suchen und Sortieren studiert. Zum anderen geht es um das Zusammenspiel von Algorithmen und Datenstrukturen wie verkettete Listen, Suchbäumen, Heaps und Union-Find Strukturen. Ein besondere Fokus sind Graphenalgorithmen für Probleme wie kürzeste Wege und minimale Spannbäume. Die dazu notwendige erste Einführung in die Graphentheorie ist ebenfalls Teil der Vorlesung.
Skript
Ein vollständiges Skript in Deutsch ist in der Entwicklung und bereits als vollständiger Entwurf auf der Vorlesungswebseite verfügbar.
Literatur
Abgesehen vom Skript und Vorlesungsunterlagen empfehlen wir die folgenden Bücher als zusätzliches Nachschlagewerk.
Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: An Introduction to Algorithms, 3rd edition, MIT Press, 2009
Leistungskontrolle
Information zur Leistungskontrolle (gültig bis die Lerneinheit neu gelesen wird)
Die Leistungskontrolle wird in jeder Session angeboten. Die Repetition ist ohne erneute Belegung der Lerneinheit möglich.
Prüfungsmodus
schriftlich 120 Minuten und 180 Minuten
Zusatzinformation zum Prüfungsmodus
Während des Semesters können durch aktive Mitarbeit Bonuspunkte erarbeitet werden. Die Veranstaltung bietet als "Leistungselement" (im Sinne der WEISUNG: Anwendung von Leistungselementen in der Lehre vom 22.12.2017) zwei Arten von Lernelementen an. Die einen Lernelemente sind Bonusaufgaben und klar markierter Teil der wöchentlichen Aufgabensammlung. In maximal 13 Wochen wird es Bonusaufgaben geben. Das andere Lernelement ist Peer Feedback, d.h., die Korrektur der Bonusaufgaben von Kommilitonen in den wöchentlichen Übungen. Die durch die Lernelemente erworbenen Punkte verbessern das Ergebnis der schriftlichen Prüfung um maximal 0.25 Notenpunkte, wobei für dieses Maximum nicht die Maximalpunktzahl erforderlich ist.
Unehrliches Verhalten bei der Bearbeitung der Lernelemente (z.B., Kopieren der Lösungen von Kommilitonen oder anderen Quellen, zur Verfügung stellen der eigenen Lösungen zum Kopieren) haben ernste Konsequenzen inklusive der Aberkennung aller Bonuspunkte dieser Veranstaltung.
Die Prüfung wird an zwei verschiedenen Daten stattfinden: 1) Schriftliche Prüfung auf Papier: 120 Min. und 2) Computerbasierte Online-Prüfung: 180 Min.
Hilfsmittel schriftlich
keine
Digitale Prüfung
Die Prüfung findet auf Geräten statt, die von der ETH Zürich zur Verfügung gestellt werden.
Fernprüfung
Das Ablegen als Fernprüfung ist nicht möglich.
Falls die Lerneinheit innerhalb eines Prüfungsblockes geprüft wird, werden die Kreditpunkte für den gesamten bestandenen Block erteilt. Diese Angaben können noch zu Semesterbeginn aktualisiert werden; verbindlich sind die Angaben auf dem Prüfungsplan.
Leistungskontrolle als Semesterkurs