Algorithmen und Datenstrukturen 1 (SS 2024)

• Übungsblätter
• Logbuch

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

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
Nachklausur: Mittwoch, 25.09.2024

Materialien

Folien

• Kapitel 1

Videoaufzeichnungen

Folien zu den Videos

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.

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.

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.

Logbuch

V04 (25.04.2024) Rekursionsgleichungen, Master-Theorem, 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:

• Skript: Kapitel 3.3 und 3.4
• Folien: Kapitel 1 (Seiten 58-73)
• Video: kommt noch

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.

Materialien und weitere Lektüre:

• Skript: Kapitel 3.2
• Folien: Kapitel 1 (Seiten 47-58)
• Video: kommt noch

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

Vollstänidige Induktion am Beispiel der Anzahl k-elementiger Teilmengen, Binärsuche (Aglorithmus, Korrektheit, Luafzeit), Laufzeitmesung und Pseudocode am Beispiel des Teilfolgenproblems.

Eingestreute mathematische Grundlagen: Binomialkoeffizienten, Logarithmen.

Materialien und weitere Lektüre:

• Skript: Kapitel 3 bis einschließlich 3.3.2
• Folien: Kapitel 1 (Seiten 27-47)
• Video: kommt noch

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:

• Skript: Kapitel 2.3
• Folien: Kapitel 1 (Seiten 1-27)
• Video: kommt noch