Algorithmen und Datenstrukturen 1 (Sommer 2022)

Aktuelles

Zum Logbuch.

Hinweis für Lehramtsstudierende: Die Freiversuchsregelung aufgrund der Corona-Sonderregelungen ist nicht mehr in Kraft und nicht bestandene Prüfungen in den Lehramtsstudiengängen müssen wieder zum nächstmöglichen Termin wiederholt werden (nähere Infos hier).

Organisatorisches

Dozent: Prof. Dr. Martin Hoefer
Übungsbetrieb: Tim Koglin, Marco Schmalhofer
Kontakt: algo122[AT]cs.uni-frankfurt.de

Vorlesung: Dienstag und Donnerstag, 08:15 - 09:45 Uhr, Hörsaalgebäude - H V
Eintrag im LSF

Die Veranstaltung ist in Algo-1a (5 CP) und Algo-1b (3 CP) unterteilt.
Algo-1a endet nach der Diskussion der Breitensuche. Algo-1b startet mit Dijkstra's Algorithmus.
Der Übergang war in der 14. Vorlesung am 07.06.22.

Hauptklausur: Montag, 08.08.2022, 09:00 - 12:00 Uhr.
Zweitklausur: Freitag, 14.10.2022, 09:00 - 12:00 Uhr.
Als erlaubtes Hilfsmittel für die Klausuren wird ein beidseitig handbeschriebenes DIN-A4-Blatt zugelassen.

Material

Videos

Die Vorlesung wird von studiumdigitale im Hörsaal aufgezeichnet und auf der Mediasite beim HRZ veröffentlicht.

Die Videos finden Sie hier (Zugriff mit HRZ-Account).

Vorlesungsfolien

Kapitel			Stand	Vorlesungen
Grundlagen	Folien	Handout	21.04.2022	01-04
Datenstrukturen	Folien	Handout	03.05.2022	04-07
Wörterbücher	Folien	Handout	19.05.2022	07-11
Graphalgorithmen	Folien	Handout	21.06.2022	11-16
Entwurfsmethoden	Folien	Handout	07.07.2022	16-21

Wiederholungsfragen

Set 1 (Asymptotische Notation, Rekursionsgleichungen, 21.04.)
Set 2 (Asymptotische Notation, Rekursionsgleichungen, 26.04.)
Set 3 (Rekursionsgleichungen, Deques, Höhe/Tiefe, 28.04.)
Set 4 (Asymptotische Notation, Heaps im Array, Heap-Ordnung, Tiefe des Heaps, 03.05.)
Set 5 (Binäre Suchbäume, AVL-Bäume, 17.05.)
Set 6 (Binäre Suchbäume, AVL-Bäume, (a,b)-Bäume, Hashing, 24.05.)
Set 7 (Baumtraversierung, Kreise, Topologische Sortierung, 31.05.)
Set 8 (Asymptotische Notation, Tiefensuche, Heaps, 07.06.)
Set 9 (Laufzeitanalyse, Breitensuche, Algorithmus von Dijkstra, 09.06.)
Set 10 (Laufzeitanalyse, Tiefensuche, Minimale Spannbäume, Algorithmus von Kruskal, 21.06.)
Set 11 (Laufzeitanalyse, Verzögerungsminimierung, 23.06.)
Set 12 (Rekursionsgleichungen, Breitensuche, Huffman-Codes, 28.06.)

Set 13 (Laufzeitanalyse, dynamische Programmierung Fibonacci, gewichtetes Intervall-Scheduling, 05.07.)
Set 14 (APSP, paarweises Alignment, 07.07.)

Skripte

Skript [DS] zu einer Veranstaltung ''Datenstrukturen'' von Georg Schnitger. Enthält Material zum ersten Teil der Vorlesung (Grundlagen, Datenstrukturen, Wörterbücher).

Skript [TI1] zu einer Veranstaltung ''Theoretische Informatik 1'' von Georg Schnitger. Enthält Material zum zweiten Teil der Vorlesung (Graphalgorithmen, Entwurfsmethoden).

Übungsblätter

Blatt 0, Besprechung 25.04. - 29.04.2022
Blatt 1, Ausgabe: 19.04.2022. Abgabe bis 26.04.2022, 08:00 Uhr.
Blatt 2, Ausgabe: 26.04.2022. Abgabe bis 03.05.2022, 08:00 Uhr.
Blatt 3, Ausgabe: 03.05.2022. Abgabe bis 10.05.2022, 08:00 Uhr.
Blatt 4, Ausgabe: 10.05.2022. Abgabe bis 17.05.2022, 08:00 Uhr.
Blatt 5, Ausgabe: 17.05.2022. Abgabe bis 24.05.2022, 08:00 Uhr.
Blatt 6, Ausgabe: 24.05.2022. Abgabe bis 31.05.2022, 08:00 Uhr.
Blatt 7, Ausgabe: 31.05.2022. Abgabe bis 07.06.2022, 08:00 Uhr.
Blatt 8, Ausgabe: 07.06.2022. Abgabe bis 14.06.2022, 08:00 Uhr. (Letztes Blatt Algo-1a)
Blatt 9, Ausgabe: 14.06.2022. Abgabe bis 21.06.2022, 08:00 Uhr. (Erstes Blatt Algo-1b)
Blatt 10, Ausgabe: 21.06.2022. Abgabe bis 28.06.2022, 08:00 Uhr.
Blatt 11, Ausgabe: 28.06.2022. Abgabe bis 05.07.2022, 08:00 Uhr.

Klausurvorbereitung

Nutzen Sie das Logbuch, um sich einen Überblick über die Themen zu verschaffen. Wiederholen Sie die Inhalte mithilfe der Folien, der Übungsblätter, den Videos und der Skripte.
Fertigen Sie ein beidseitig handbeschriebenes DIN A4 Blatt als Hilfsmittel für die Klausur an.

Tutorien

Es werden 16 Tutorien angeboten. Die Tutorien montags bis donnerstags finden in Präsenz statt, die Tutorien freitags online. Wenn Sie einem Online-Tutorium zugeteilt wurden, bekommen Sie die Zugangsdaten rechtzeitig per E-Mail an Ihre HRZ-Mailadresse (...@stud.uni-frankfurt.de) zugesandt.

Übungen

Die Übungen dienen der Wiederholung, Vertiefung sowie Erweiterung des Lernstoffes. Das Lösen von Übungsaufgaben sowie die Teilnahme an Ihrem Tutorium sind daher sehr zu empfehlen, jedoch freiwillig. Es besteht die Möglichkeit, durch erfolgreiche Bearbeitung der Übungsaufgaben bis zu 10% Klausurbonus zu sammeln.

Lösungen müssen stets begründet werden, es sei denn, die Aufgabenstellung erlaubt explizit, dass eine Begründung nicht nötig ist. Notationen, die nicht aus der Vorlesung, den Folien oder dem Skript bekannt sind, sollten vermieden oder zumindest einheitlich verwendet werden.

Der Übungsbetrieb folgt einem wöchentlichen Rhythmus. Blatt 0 ist ein Präsenzblatt und wird in den ersten Tutorien in Woche 3 besprochen, eine Abgabe entfällt. Blatt 1 wird in Woche 2 ausgegeben, in Woche 3 abgegeben und in Woche 4 in den Tutorien besprochen. Die weiteren Blätter folgen ebenfalls diesem Rhythmus (Blatt i: Ausgabe in Woche i+1, Abgabe in Woche i+2, Besprechung in Woche i+3).
Abgabeschluss ist jeweils Dienstag, 8:00 Uhr. Verspätete Abgaben werden nicht angenommen!
Die Abgabe erfolgt elektronisch über das SAP in Form einer einzigen PDF-Datei. Nutzen Sie dafür den Abgabe-Link, den Sie erhalten haben, nachdem Sie einer Übungsgruppe zugewiesen wurden. Dieser Link ist das gesamte Semester lang gültig. Sie können Ihre Abgabe gerne in LaTeX setzen oder handschriftlich ausführen und einscannen (Scan-Apps wie z.B. Open Note Scanner helfen Ihnen dabei). Schwer lesbare Abgaben werden nicht korrigiert! Wichtig: Laden Sie Ihre Abgabe nicht in letzter Minute hoch! Ein reibungsloser Ablauf kann nicht garantiert werden, wenn alle in den letzten fünf Minuten hochladen!

Es wird empfohlen, in Gruppen über die Aufgaben zu diskutieren und zusammen Lösungswege zu erarbeiten. Bitte schreiben Sie die Lösung trotzdem eigenständig auf und machen Sie erkennbar, dass Sie den Lösungsweg verstanden haben. Im Zweifelsfall kann der Tutor bzw. die Tutorin verlangen, dass Sie eine Lösung vorrechnen, um dies zu überprüfen. Wenn Sie in diesem Fall im Tutorium nicht anwesend sind, können die auf dieses Übungsblatt erhaltenen Punkte aberkannt werden.
Wenn festgestellt wird, dass die Lösung einer Aufgabe abgeschrieben wurde, dann...
- ... gibt es beim ersten Mal in jedem Fall für alle Beteiligten 0 Punkte auf die gesamte Abgabe.
- ... wird beim zweiten Mal allen Beteiligten die Bonifikation für Erst- und die Zweitklausur aberkannt.
Die Inhalte der Vorlesung, der Folien, der Übungsblätter und des Skripts reichen für die Bearbeitung der Aufgaben stets aus. Sollte Ihre Lösung dennoch Inhalte von externen Quellen enthalten, beachten Sie bitte die Hinweise zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Machen Sie beim Zitieren insbesondere erkennbar, was Ihre eigene Leistung ist, denn nur diese wird bewertet.

Ihr Bonus für die Klausur berechnet sich wie folgt: Bonus = 16 * min { 1, Summe aller erreichten Punkte / Summe aller Punkte ohne Extrapunkte } (kaufmännisch gerundet auf eine ganze Zahl).
Beachten Sie, dass Ihnen Ihr Bonus erst angerechnet wird, wenn Sie bis zur Klausur im Tutorium mindestens einmal vorgerechnet und die Klausur bestanden haben!

Empfohlene Literatur

[CLRS] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. (Eng) MIT Press, 2002.
Deutsche Version als E-Book hier abrufbar.
[GTM] Goodrich, Tamassia, Mount. Data Structures and Algorithms in C++. (Eng) Wiley & Sons, 2004.
[DMS] Dietzfelbinger, Mehlhorn, Sanders. Algorithmen und Datenstrukturen: Die Grundwerkzeuge. Springer Vieweg, 2014.
[KT] Kleinberg, Tardos. Algorithm Design. (Eng) Pearson, 2006.
[S] Sedgewick. Algorithmen in C++. Pearson Studium, 2002.