Die Zugangsdaten für die Materialien auf dieser Webseite sowie die Zugangsdaten zum Online-Tutorium (Gruppe 10) finden Sie im Moodle.

Algorithmen und Datenstrukturen 1 (SS 2024)

Vorlesung

Prof. Dr. Ulrich Meyer

LSF

Dienstag 08:00 - 10:00 Hörsaal H V (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
Daniel Allendorf

E-Mail: algo124@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 online. Der genaue Ablauf wird rechtzeitig bekannt gegeben.

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

Termine der Übungsgruppen

GruppeTagUhrzeitRaum
Gruppe 1Mo10-12H 6
Gruppe 2Mo14-16H 13
Gruppe 3Mo16-18NM 114
Gruppe 4Di10-12H 13
Gruppe 5Di14-16NM 113
Gruppe 6Di16-18NM 112
Gruppe 7Mi08-10H 5
Gruppe 8Mi10-12H 9
Gruppe 9Mi14-16H 13
Gruppe 10Mi16-18online
Gruppe 11Do12-14H 9
Gruppe 12Do14-16NM 113
Gruppe 13Do16-18NM 113
Gruppe 14Fr10-12NM 120
Gruppe 15Fr12-14H 11
Gruppe 16Fr16-18H 13

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.

Zur 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.

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.

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

Hauptklausur: Montag, 29.07.2024 9:00
Nachklausur: Mittwoch, 25.09.2024 9:00

Materialien

Folien

Kapitel 1ohne Clickermit Clicker
Kapitel 2ohne Clickermit Clicker
Kapitel 3ohne Clickermit Clicker
Kapitel 4ohne Clickermit Clicker
Kapitel 5ohne Clickermit Clicker

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.

DownloadAusgabeAbgabe
Übung 016.04.24keine
Übung 1 (Stand 23.4. 13:00)23.04.2429.04.24 23:55
Übung 229.04.2406.05.24 23:55
Übung 306.05.2413.05.24 23:55
Übung 413.05.2420.05.24 23:55
Übung 520.05.2427.05.24 23:55
Übung 627.05.2403.06.24 23:55
Übung 703.06.2410.06.24 23:55
Übung 810.06.2417.06.24 23:55
Übung 917.06.2424.06.24 23:55
Übung 1024.06.2401.07.24 23:55
Übung 1101.07.2408.07.24 23:55
Übung 1208.07.2415.07.24 23:55

Selbsttests

Selbststests sind ein zusätzliches Übungsangebot. Hier finden Sie Aufgaben und Lösungen mit denen Sie Ihren Wissensstand selbst überprüfen können.

Dieses Jahr neu haben wir interaktive Selbsttests.
Das ganze ist noch ein Prototyp, hat aber bereits einige Aufgaben zu Oh-Notation, zu finden unter Asymptotik/Asymptotics.
Feedback Aller art gerne an alex@ae.cs.uni-frankfurt.de oder auf GitHub.

Als alternative zu den Online Selbsttests haben wir auch noch die PDF Versionen.

Selbsttest 1: O-NotationAufgabenLösung

Skript

Es stehen Skripte von Herrn Prof. Dr. G. Schnitger zu Datenstrukturen und Theoretische Informatik 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.

Logbuch

V21 (16.07.2024) Lineare Programmierung

Dies war die letzte Vorlesung für dieses Semester.

Materialien und weitere Lektüre:

V20 (11.07.2024) Dynamische Programmierung

Dynamische Programmierung, Floyd Algorithmus, paarweises (globales) Alignment

Materialien und weitere Lektüre:

V19 (09.07.2024) Dynamische Programmierung

Dynamische Programmierung, gewichtetes Intervall Scheduling (Greedy-Algorithmus), All-Pairs-Shortest-Path Problem (Bellman-Ford-Algorithmus).
Hinweis: Auf den Folien (Seite 71) und im Skript (Seite 69) wurde ein Fehler korrigiert der die Rekursion im Bellman-Ford-Algorithmus betrifft.

Materialien und weitere Lektüre:

V18 (04.07.2024) Stabiles Matching, Divide & Conquer, Dynamische Programmierung

Letztes Beispiel für Greedy-Algorithmen (Stabiles Matching), Divide & Conquer Algorithmen (schnelle Multiplikation, Matrixmultiplikation), Dynamische Programmierung (Traveling Salesman Problem)

Materialien und weitere Lektüre:

V17 (02.07.2024) Intervall Scheduling, Huffman Codes

Übersicht über Entwurfsmethoden, Beispiele Für Greedy-Algorithmen, Intervall Scheduling, Scheduling mit minimaler Verspätung, Huffman Codes

Materialien und weitere Lektüre:

V16 (20.06.2024) Minimale Spannbäume, Algorithmen von Prim und Kruskal

Minimale Spannbäume, Algorithmen von Prim und Kruskal, Union-Find Datenstruktur

Materialien und weitere Lektüre:

V15 (18.06.2024) Dijkstras Algorithmus

Dijkstras Algorithmus zur Bestimmung kürzester Wege

Materialien und weitere Lektüre:

V14 (13.06.2024) Tiefensuche auf gerichteten Graphen, Breitensuche

Tiefensuche auf gerichteten Graphen (Baum-, Vorwärts, Rückwärts- und Querkanten), Anwendung von Tiefensuche, Breitensuche

Materialien und weitere Lektüre:

V13 (11.06.2024) Tiefensuche auf ungerichteten Graphen

Tiefensuche, Baum- und Rückwärtskanten, Wald der Tiefensuche, Zusammenhangskomponenten, Laufzeit

Materialien und weitere Lektüre:

V12 (06.06.2024) Graphen, topologisches Sortieren, Graph-Implementierung

Graphen (Motivation, wichtige Begriffe), topologisches Sortieren, Graph-Implementierung (Adjazenzlisten, Adjazenzmatrix)

Materialien und weitere Lektüre:

V11 (04.06.2024) Hashing

Hashing mit Verkettung, Hashing mit offener Adressierung, Lookup, Insert und Remove, Hashfunktionen, universelles Hashing

Materialien und weitere Lektüre:

V10 (28.05.2024) (a,b)-Bäume, Hashing

(a,b)-Bäume (Eigenschaften, lookup, insert, remove), Hashing (Motivation), Übersicht zu Hashing mit Verkettung.

Materialien und weitere Lektüre:

V09 (23.05.2024) AVL-Bäume, (a,b)-Bäume

AVL-Bäume Suchbäume Operationen (lookup, insert, remove) und Rotationen, (a-b)-Bäume (Eigenschaften)

Materialien und weitere Lektüre:

V08 (21.05.2024) Heaps und binäre Suchbäume

Heapfunktionen repair_down, change_priority und remove, Anwendung in Heapsort, binäre Suchbäume (lookup, insert, remove)

Materialien und weitere Lektüre:

V07 (07.05.2024) Implementierung von Binärbäumen, Traversierung, Prioritätswarteschlangen und Heaps

Implementierung von (Binär-)Bäumen (Elternarray, Kind-Geschwister Darstellung), Traversierung (Pre-, Post, Inorder), Heaps und Operationen auf Heaps

Materialien und weitere Lektüre:

V06 (02.05.2024) Listen, Stacks, Queues, Deques, Bäume

Grundlegende Datenstukturen (Einfach verkettete Listen, Stacks, Queues, Deques) und Operationen auf ihnen so wie ihre Implementierung. Gewurzelte Bäume, zentrale Begriffe und Operationen auf Bäumen.

Materialien und weitere Lektüre:

V05 (30.04.2024) Rekursionsgleichungen, Mastertheorem, Wachstumsverhalten in der Laufzeitanalyse

Das Mastertheorem zur Lösung von bestimmten Rekursionsgleichung, Zählen von Programmanweisungen zur Bestimmung des Wachstumsverhalten in der Laufzeitanalyse.

Materialien und weitere Lektüre:

V04 (25.04.2024) Rechnen mit Grenzwerten, Wachstumshierarchie, Rekursionsgleichungen

Rechnen mit Grenzwerten bei unbeschrankt wachsenden Funktionen, Integralkriterium, eine Wachstumshierarchie, Rekursionsgleichungen.

Materialien und weitere Lektüre:

V03 (23.04.2024) Laufzeitanalyse, Oh-Notation

Asymptotische Notation (auch Landau-Notation oder Oh-Notation) zur Beschreibung von asymptotischen Verhalten von Funktionen. Grenzwertkriterien und rechnen mit Grenzwerten (L’Hospital).

Materialien und weitere Lektüre:

V02 (18.04.2024) Vollständige Induktion, Binärsuche, Laufzeitmessung

Vollständige Induktion am Beispiel der Anzahl k-elementiger Teilmengen, Binärsuche (Algorithmus, Korrektheit, Laufzeit), Laufzeitmessung und Pseudocode am Beispiel des Teilfolgenproblems.

Eingestreute mathematische Grundlagen: Binomialkoeffizienten, Logarithmen.

Materialien und weitere Lektüre:

V01 (16.04.2024) Einführung

Bitte unbedingt an den Übungen teilnehmen. Der Übungsbetrieb beginnt nächste Woche Donnerstag den 25.4. mit der Besprechung von Blatt 0. Vorlesungsinhalt: Organisatorisches und vollständige Induktion gezeigt an verschiedenen Beispielen.

Materialien und weitere Lektüre: