Die Vorlesung fällt am 14.5. und 16.5. aus. Die Tutorien finden regulär statt und die Übungsblätter 4 und 5 kommen wie üblich Montags im Laufe des Tags raus.
Für die Gruppen 1, 2, 7, 8, 11 und 15 haben sich die Räume der Tutorien geändert.
Die Videos sind jetzt verfügbar. Links im Logbuch.
Sollten Sie bisher keinen Link für die Abgabe der Übungsaufgaben bekommen haben, melden Sie sich rechtzeitig bei uns.
Sollten Sie die Anmeldung verpasst haben, melden Sie sich bitte zeitnah bei uns (algo124@ae.cs.uni-frankfurt.de) und teilen Sie uns Ihren Namen, Matrikelnummer sowie drei Optionen für Übungsgruppen mit (außer die Gruppen 4, 5, 10, und 11, diese sind voll).
Die Zugangsdaten für die Materialien auf dieser Webseite sowie die Zugangsdaten zum Online-Tutorium (Gruppe 10) finden Sie im Moodle.
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
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.
Gruppe | Tag | Uhrzeit | Raum |
---|---|---|---|
Gruppe 1 | Mo | 10-12 | H 6 |
Gruppe 2 | Mo | 14-16 | H 13 |
Gruppe 3 | Mo | 16-18 | NM 114 |
Gruppe 4 | Di | 10-12 | H 13 |
Gruppe 5 | Di | 14-16 | NM 113 |
Gruppe 6 | Di | 16-18 | NM 112 |
Gruppe 7 | Mi | 08-10 | H 5 |
Gruppe 8 | Mi | 10-12 | H 9 |
Gruppe 9 | Mi | 14-16 | H 13 |
Gruppe 10 | Mi | 16-18 | online |
Gruppe 11 | Do | 12-14 | H 9 |
Gruppe 12 | Do | 14-16 | NM 113 |
Gruppe 13 | Do | 16-18 | NM 113 |
Gruppe 14 | Fr | 10-12 | NM 120 |
Gruppe 15 | Fr | 12-14 | H 11 |
Gruppe 16 | Fr | 16-18 | H 13 |
Zur Onlineabgabe:
Plagiate und Betrugsversuche:
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.
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.
Hauptklausur: Montag, 29.07.2024
Nachklausur: Mittwoch, 25.09.2024
Kapitel 1 | ohne Clicker | mit Clicker |
Kapitel 2 | ohne Clicker |
Wir arbeiten daran.
Altklausuren finden Sie hier.
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.
Download | Ausgabe | Abgabe |
---|---|---|
Übung 0 | 16.04.24 | keine |
Übung 1 (Stand 23.4. 13:00) | 23.04.24 | 29.04.24 23:55 |
Übung 2 | 29.04.24 | 06.05.24 23:55 |
Übung 3 | 06.05.24 | 13.05.24 23:55 |
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-Notation | Aufgaben | Lösung |
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.
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: