Algorithmen und Datenstrukturen 1 (SS 2020)

Vorlesung

Prof. Dr. Ulrich Meyer

Dienstag 08:00 - 10:00 Hörsaal H VI (Jügelhaus/Hörsaalgebäude)
Donnerstag 08:00 - 10:00 Hörsaal H V (Jügelhaus/Hörsaalgebäude)

Sprechstunde: Nach Vereinbarung

Übungsbetrieb

Alex Schickedanz

E-Mail: algo120@ae.cs.uni-frankfurt.de
Sprechstunde: Nach Vereinbarung

Das Lösen von Übungsaufgaben geschieht auf freiwilliger Basis. Dennoch ist die Teilnahme am Übungsbetrieb unbedingt zu empfehlen. Es werden weiterführende Inhalte vermittelt und es gibt die Möglichkeit Bonuspunkte zu sammeln. Eine Beobachtung unsererseits ist: Je höher die Bonuspunkte, desto höher die Wahrscheinlichkeit, eine gute Note zu erhalten. Weiterhin gilt aber, dass leider in der Vergangenheit immer wieder Betrugsversuche bei Übungsabgaben vorkamen. Deshalb bitten wir Sie darum, von solchen Täuschungsversuchen Abstand zu nehmen. Es lohnt sich nicht! Eine Zuwiderhandlung kann dazu führen, dass wir Ihnen alle Bonuspunkte aberkennen (genaue Regelung: siehe “Hinweise zu den Übungsabgaben”).

Es gibt wöchentlich Übungsblätter. Die Abgabe des Blattes erfolgt normalerweise eine Wochen später vor Beginn der Vorlesung. Die genaue Abgabefrist steht auf der Webseite und dem Übungsblatt. Außerdem besteht dieses Semester die Möglichkeit die Lösungen online als PDF abzugeben. Den genauen Ablauf erfahren Sie rechtzeitig hier auf der Webseite.

Sie können durch die Teilnahme an den Übungen bis zu 10 Bonuspunkte erhalten. Diese werden auf die Note einer bestanden Klausur angerechnet.

Termine der Übungsgruppen

Die Übungen finden vorerst nur online statt. Die hier angegebenen Räume sind nur für den Fall, dass Präsenzveranstaltungen wieder möglich werden.

Hinweise zu den Übungsabgaben

• Die Abgabe der Übungen hat stets bis zu Beginn der Vorlesung zu erfolgen.
• Wie immer gilt: Was unsere Tutoren nicht lesen können, müssen sie auch nicht korrigieren und gibt dementsprechend auch keine Punkte.
• Da es eine online Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.
• Wir stellen eine LaTeX Vorlage zur Verfügung.

Zu Onlineabgabe:

• Die Abgabe wird Ihnen automatisch zugeordnet. Es schadet jedoch nicht Matrikelnummer und Namen darauf zu vermerken.
• Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
• Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
  • Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
  • Zur Not können Sie Scans oder Bilder zu einer PDF zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.

Zu Abgaben in Papierform (vorerst nicht vorgesehen):

• Jedes(!) Blatt ist mit dem vollständigen Namen, Matrikelnummer und Gruppennummer zu versehen.
• Bei Abgabe im Briefkasten muss auch die Veranstaltung auf das Blatt geschrieben werden.
• Abgaben ohne vollständigen Namen, Matrikelnummer und Gruppennummer werden nicht korrigiert.
• Wer eine falsche Gruppennummer auf dem Blatt angibt und deshalb nicht bei seinem Tutor landet, bekommt auf die Abgabe keine Punkte.
• Mehrseitige Übungsabgaben sind zu tackern.

Plagiate und Betrugsversuche:

• Wenn festgestellt wird, dass eine Aufgabe abgeschrieben wurde, dann…
  • … gibt es beim ersten Mal für alle Beteiligten 0 Punkte auf das Blatt.
  • … wird beim zweiten Mal allen Beteiligten die Bonifikation sowohl für die Erst- als auch die Zweitklausur aberkannt. Außerdem werden keine weiteren Abgaben der Beteiligten mehr korrigiert.
• Wichtig: Wer bereits in einer unseren anderen Veranstaltung erwischt wurde, bekommt keine Verwarnung. In dem Fall wird die Bonifikation sofort aberkannt. Leider sehen wir uns zu diesem Schritt gezwungen nachdem die Zahlen der abgeschriebenen Lösungen in den letzten Semestern massiv angestiegen sind.
• Sie dürfen in Gruppen über die Aufgaben diskutieren und zusammen Lösungswege erarbeiten (es ist sogar empfohlen). Jedoch muss jeder Student in der Abgabe die Lösung selbst schreiben und somit erkennbar machen, dass der Lösungsweg verstanden wurde. Im Zweifelsfall kann der Tutor verlangen, dass Sie eine Lösung vorrechnen. Sind Sie im Tutorium gar nicht anwesend, so kann der Tutor die Punkte vom Übungsblatt aberkennen.

Prüfungsvarianten (Algo1a und Algo1b)

Die Inhalte von Datenstrukturen (DS) und Theoretische Informatik 1 (GL1) wurden in der neuen Prüfungsordnung neu aufgeteilt. Algo1 besteht jetzt aus den Inhalten von DS (jetzt Algo1a) und einem Teil der Inhalte aus GL1 (Algo1b).

Die Äquivalenzregelung des Prüfungsamts Informatik finden Sie hier.

Die Prüfung wird als ganzes oder in Teilen für sowohl Algo1a als auch Algo1b angeboten. Wenn Sie sich nur in einem Teil prüfen lassen, werden auch auch nur die Bonuspunkte aus dem entsprechenden Teil der Übungsaufgaben angerechnet. Die Übungsaufgaben und Vorlesungsvideos für Algo1b werden entsprechend markiert. Alles andere gehört zu Algo1a. Es wird auch auf der Webseite geschrieben, wenn Algo1b Inhalte auf den Übungsblättern oder in den Videos vorkommen, aber es wird keine Vorankündigung geben. Schauen Sie bitte regelmäßig auf die Webseite.

Hinweis: Manche Inhalte zählen explizit zu Algo1b. Allerdings heißt das nicht, dass in der Prüfung die anderen Inhalte nicht Teil der Aufgaben sein können. Bspw. braucht man für die Graphalgorithmen aus Algo1b Datenstrukturen die evtl. Teil von Algo1a sind. Das wäre auch bei einer regulären GL1 Prüfung nicht anders gewesen. Kurz: Alle Inhalte von Algo1a sind relevant für Algo1b. Beides sind Grundlagen.

GL1 als Auflage
Masterstudenten, die GL1 als Auflage bekommen haben, müssen nur Algo2 hören. Es ist keine Prüfung in Algo1b nötig.

GL1 im Nebenfach
Bitte klären Sie mit Ihrem Prüfungsamt, ob sie Algo1b hören müssen oder ob Algo2 genügt.

Inhalt

Die Vorlesung behandelt die Laufzeitanalyse, fundamentale Datenstrukturen und allgemeine Methoden für den Entwurf und die Analyse von Algorithmen und Datenstrukturen. Die Analyse im Hinblick auf Laufzeit und Speicherplatzbedarf wird motiviert. Die asymptotische Notation wird eingeführt, und Methoden zur Lösung von Rekursionsgleichungen werden besprochen.

Elementare Datenstrukturen wie Listen, Keller und Warteschlangen werden beschrieben und analysiert. Der Begriff des abstrakten Datentyps wird eingeführt und motiviert, und effiziente Realisierungen der Datentypen des Wörterbuchs und der Prioritätswarteschlange unter Benutzung von Bäumen und Hashing werden besprochen. Außerdem werden effiziente Datenstrukturen für das Union-Find-Problem behandelt.

Die Darstellung von Bäumen und allgemeinen Graphen im Rechner und Algorithmen zur systematischen Durchmusterung von Graphen diskutiert. Weiterführende Algorithmen für Graphenprobleme wie minimale Spannbäume und kürzeste Wege werden besprochen, und der Einsatz von Datenstrukturen in diesen Verfahren wird exemplarisch vorgestellt.

Lernergebnisse / Kompetenzziele

Wissen und Verstehen: Die Studierenden sollen grundlegende Algorithmen und Datenstrukturen mit deren Eigenschaften und Leistungsparametern kennen und diese Parameter in asymptotischer Notation verstehen und vergleichen können

Können: Die Studierenden lernen, Datenstrukturen fur neue Problemstellungen eigenständig zu entwerfen und deren Leistungsparameter zu analysieren (instrumentale Kompetenz). Dadurch sollen sie im Beruf z.B. in der Lage sein, bestehende Software durch geeignetere Datenstrukturen zu beschleunigen (systemische Kompetenz).

Kommunikative Kompetenzen werden durch Arbeiten in Gruppenübungen und die dortige Vorstellung und Diskussion von Übungsaufgaben erworben.

Literatur

• [CLRS] Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms. (Eng) MIT Press, 2002.
• [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.

Klausurtermine

Bestätigte Termine

Hauptklausur: 27.07.2020 14:00 s.t. WESTEND-Campus
Nachklausur: 05.10.2020 9:00 s.t. WESTEND-Campus Weitere Informationen insb. zur Raumzuteilung werden zu rechtzeitig bekannt gegeben.

Materialien

Folien

• Infoslides (Fassung vom 23.04.2020)
• Fragestunde vom 28.04. (mit Notizen)
• Fragestunde vom 07.05. (mit Notizen)
• Fragestunde vom 14.05. (mit Notizen)
• Fragestunde vom 19.05. (mit Notizen)
• Fragestunde vom 28.05. (mit Notizen)
• Fragestunde vom 04.06. (mit Notizen)
• Fragestunde vom 18.06. (mit Notizen)
• Fragestunde vom 25.06. (mit Notizen)
• Fragestunde vom 02.07. (mit Notizen)
• Fragestunde vom 09.07. (mit Notizen)
• Fragestunde vom 16.07. (mit Notizen)

Videoaufzeichnungen

Videos zur Vorlesung stehen hier zur Verfügung.

Es handelt sich dabei um Aufzeichnungen der Vorlesungen Datenstrukturen und Theoretische Informatik 1 aus den vergangen Semestern. Teilweise werden die Videos neu geschnitten oder durch neue Videos ergänzt um den Inhalt der aktuellen Vorlesung gerecht zu werden.

Es stehen auch die Videos zu Datenstrukturen vom Sommersemester 2018 (werden neu geschnitten und für diese Vorlesung hochgeladen) und Sommersemester 2019 (Prof. Hoefer) zur Verfügung.

Hinweis: Die Videos werden von studiumdigitale gehostet.

Folien zu den Videos

Video V01: Wiederholung mathematischer Grundlangen
Video V02: Laufzeitmessung und asymptotische Notation
Video V03: Mastertheorem und Analyse von Pseudocode
Video V04: Stacks, Queues, Listen und Bäume
Video V05: Binärbäume und Traversierung
Video V06: Topologisches Sortieren, Graphimplementierung und Tiefensuche
Video V07: Tiefensuche
Video V08: Breitensuche und Heaps / Prioritätswarteschlangen
Video V09.1: Heaps und Heapsort
Video V09.2: Binäre Suchbäume
Video V10: AVL-Bäume und (a,b)-Bäume
Video V11: (a,b)-Bäume und Hashing
Video V12: Hashing
Video V13: Tiefen- und Breitensuche (WH) und Dijkstras Algorithmus
Video V14: Dijkstras Algorithmus und minimale Spannbäume
Video V15: Algorithmen von Prim und Kruskal
Video V16: Greedy-Algorithmen, Scheduling, Huffman-Code und -Bäume
Video V17: Divide & Conquer, Schnelle Multiplikation, Dynamische Programmierung, TSP und gewichtete Intervall-Scheduling
Video V18: Gewichtete Intervall Scheduling, All-Pairs-Shortest-Path, Paarweises Alignment
Video V19: Das paarweise globale Alignment Problem und RNA-Sekundärstruktur
Video V20: Lineare Programmierung

Die Folien zu den Videos von Prof. Hoefer finden Sie auf der zugehörigen Vorlesungswebseite.

Altklausuren

Altklausuren finden Sie hier.

Übungsblätter

Die Bearbeitung der Übungsblätter in Gruppen ist erlaubt, jedoch müssen Sie Ihre Lösungen eigenständig aufschreiben.

Die Übungsblätter werden so entworfen, dass ihre Bearbeitung mit den Kenntnissen aus der Vorlesung und aus vorangegangenen Übungsblättern möglich ist. Sollten Sie in Ihrer Lösung dennoch andere Quellen (Bücher, Skripte, Internetforen, soziale Netzwerke, Lösungen anderer Studenten, etc.) verwenden, so müssen Sie die entsprechenden Stellen als direkte oder indirekte Zitate kennzeichnen. Orientieren Sie sich hierfür einfach an den Hinweisen zum Zitieren in schriftlichen Arbeiten am Institut für Informatik. Darüber hinaus muss Ihre persönliche Leistung stets deutlich erkennbar sein. Bei direkten Zitaten oder fast unverändert übernommenen Passagen liegt keine persönliche Leistung vor.

Beachten Sie auch die Hinweise zu Plagiaten und Betrugsversuchen.

Update: In der Aufgabe 6.2a war zuvor das Element 34 zwei Mal aufgeführt. Das erste sollte eine 35 sein.
Update: Der Lösungsvorschlag zu Aufgabe 5.4a wurde verbessert.
Update: In Aufgabe 8.1 stand “Hashtabelle der Größe 8”. Das muss natürlich 11 statt 8 sein, da 11 Elemente eingefügt werden sollen. In Aufgabe 8.2 hat eine Klammer in der Hashfunktion gefehlt. Ohne Klammer macht die Hashnunktion an der Stelle auch keinen Sinn.
Update Die Lösung zu Aufgabe 9.2 hatte einen Tippfehler bei der Laufzeit.
Update: Aufgabe 10.1 war unvollständig. Irgendwie war die zweite Satzhälfte verloren gegangen…

Selbsttests

Selbststest sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können. Die PDF Dateien gibt es mit und ohne JavaScript Validierung. Um diese nutzen zu können, benötigen Sie einen entsprechenden Reader der das unterstützt, z.B. der Reader von Adobe. Die Version ohne JS sollte mit allen Readern funktionieren.

Hinweis: In der PDF mit den Lösungen sind die richtigen Antworten angekreuzt. Leider sieht das aufgrund der Formatierung aus als wäre die Antwort durchgestrichen. Wir arbeiten daran, dass das besser wird.

Hinweis: Ab Selbsttest 12 bieten wir keine JavaScript-Variante mehr an. Der Grund ist, dass es nur sehr eingeschränkt unterstützt wird und JavaScript in PDFs normalerweise aus Sicherheistsgründen ausgeschaltet ist. Außerdem haben wir die Lösungen mit in die Datei mit den Aufgaben gepackt. In der Mitte des Dokuments ist eine Seite die darauf hinweist, dass die Lösungen beginnen.

Skript

Es stehen Skripte von Herrn Prof. Dr. G. Schnitger zu Datenstrukturen und Theoretische Infromatik 1 zur Verfügung.

Hinweis: Mit der Zeit sollen die beiden Skripte neu aufgeteilt werden in Skripte für Algo1 und Algo2. Bis dahin sind hier noch die Skripte zu DS und GL1.