Algorithmen und Datenstrukturen 1
- SoSe-2023
- Modulkürzel: B-ALGO-1→ALGO1
- Externe Links: qis
Übersicht
Organisatorisches
- Erste Veranstaltung: Dienstag, 11.04.2023, 8-10 Uhr, H V (Hörsaaltrakt Bockenheim). Wichtig: Bearbeiten Sie vorher eigenständig die Übungen zur Vorbereitung auf ALGO1
- Anmeldung in Moodle: Kommt bald
- Organisatorische und inhaltliche Fragen: Die meisten Fragen sind vielleicht weiter unten bereits beantwortet? Ansonsten gerne eine E-Mail an algo1-2023@uni-frankfurt.de (nicht: dell@ oder moodle)
Vorlesungskonzept
Der Kurs findet als Flipped Classroom statt, das heißt:
- Eigenständige Vorbereitung: Video der Woche, Buchkapitel und erste Übungen durcharbeiten.
- „Plenum“ (Dienstag und Donnerstag, 8:15–9:45 in Hörsaal V, mit allen Studierenden): Fragen & Antworten, Quizze, Kurzpräsentationen, Präsenzübungen und Lösungsspaziergänge. Diese Präsenzzeit findet ausschließlich im Hörsaal statt und wird nicht hybrid übertragen.
- „Tutorium“ (in kleinen Gruppen): Diskussionen, Präsenzübungen und individuelle Betreuung. Einzelne Tutorien und Helpdesks werden online stattfinden.
Vorlesungsteam
- Holger Dell (Professor)
- Claudia Gressler (Sekretärin)
- Leo Krull (Dozentin)
- Anselm Haak (Dozent)
- Tutor:innen
Literatur
- CLRS: Algorithmen – Eine Einführung (4. Auflage) von Cormen, Leiserson, Rivest, Stein. [Volltext als E-Book]. (Das Standardwerk.)
- E: Algorithms von Jeff Erickson. [pdf · web]. (Ein wunderschönes Buch, das die ersten Themen von ALGO1 aber nur überfliegt.)
Wochenplan
Die Veranstaltung dauert 14 Wochen:
Einführung und Peaks · a
CLRS Kapitel 1 · Übungsblatt · ⭐ · 📽️ · Folien · OrganisationsfolienSuchen und Sortieren · a
CLRS Kapitel 2 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · FolienAnalyse von Algorithmen, Asymptotische Notation, Rekursionsgleichungen, Mastertheorem · a
CLRS Kapitel 3, 4.3-4.5 · Übungsblatt · ⭐ · 📽️ · Folien · experiment.py · LagebesprechungElementare Datenstrukturen: Stapel, Warteschlangen, Verkettete Listen, Bäume · a
CLRS Einleitung von Teil III und Kapitel 10, Kapitel 17.4 bis Mitte von 17.4.1 · Übungsblatt · ⭐ · 📽️ · FolienDarstellung von Graphen, Breitensuche, Tiefensuche · b
CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · FolienGerichtete Graphen, Suche, Topologisches Sortieren, Starke Zusammenhangskomponenten · b
CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · FolienPrioritätswarteschlangen, Heaps · a
CLRS Kapitel 6 + Appendix B.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · FolienDisjunkte Mengen, Union-Find · a
CLRS Kapitel 21 ohne 21.4 (oder Algorithms 4ed. Kapitel 1.5) · Übungsblatt · ⭐ · 📽️1 · 📽️2 · FolienMinimale Spannbäume: Jarník–Prims Algorithmus, Kruskals Algorithmus · b
E Kapitel 7 (oder CLRS Kapitel 23) · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · FolienDijkstras Algorithmus, kürzeste Wege · b
E Kapitel 8 ohne 8.7 (oder CLRS Kapitel 24 außer 24.1 und 24.4) · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · FolienWörterbücher, Hashing · a
CLRS Kapitel 11 ohne 11.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · Folien · cuckoo hashingTraversierung, binäre Suchbäume, AVL-Bäume · a
CLRS Kapitel 12 ohne 12.4 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · FolienDynamische Programmierung, Fibonacci, längste gemeinsame DNA-Teilsequenz, Teilmengensumme, DP auf Bäumen · b
E Kapitel 3 ohne 3.6 und 3.9 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · FolienGreedy-Algorithmen, Scheduling, Huffman-Codierungen · b
E Kapitel 4 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
Lernziele
Nach der Veranstaltung können die Studierenden:
- Grundlegende Algorithmen und Datenstrukturen in Pseudocode und natürlicher Sprache beschreiben, an kleinen Beispielen anwenden, und implementieren,
- sie an neue Problemstellungen anpassen,
- Eigenschaften wie etwa die Laufzeit, den Platzbedarf oder die Korrektheit dieser und ähnlicher Algorithmen ermitteln, vergleichen und mathematisch beweisen,
- sich über fachbezogene Inhalte mündlich und schriftlich austauschen,
- neue Algorithmen und Datenstrukturen mit Hilfe grundlegender Entwurfsmethoden entwickeln.
Inhalte
- Analyse von sequentiellen Algorithmen (Laufzeit, Platzbedarf, asymptotische Notation)
- Rekursionsgleichungen (Rekursionsbäume)
- Grundlegende Algorithmen (zum Beispiel binäre Suche, Mergesort, Editierdistanz, Scheduling, Huffman-Codierung, oder andere)
- Grundlegende abstrakte und konkrete Datenstrukturen (Stacks, Queues, Verkettete Listen, Heaps, Union-Find, Hash-Tabellen, Suchbäume)
- Grundlegende Entwurfsmethoden (Divide and Conquer, Dynamische Programmierung, Gierige Algorithmen)
- Graphalgorithmen (Tiefensuche, Breitensuche, Kruskal, Prim, Dijkstra) für verschiedene Arten von Graphen (ungewichtet, gewichtet, ungerichtet, gerichtet).
Verwandte Vorlesungen
- ALGO1 an der Goethe Universität:
- SoSe-2022 (Prof. Hoefer) mit Vorlesungsmitschnitten
- SoSe-2021 (Prof. Dell) mit Videos
- SoSe-2020 (Prof. Meyer) mit Vorlesungsmitschnitten
- Vorbild für diese Vorlesung war eine Lockdown-Vorlesung von Philip Bille und Inge Li Gørtz an der DTU Kopenhagen. Mange tak Philip og Inge!
- Weitere exzellente Videoaufzeichnungen zu denselben Themen finden Sie auf MIT Open Courseware.
- Vorsemesterkurs Informatik (Einführung in Python) im WiSe-2021.
Zusätzliche Literatur
- DMS: Algorithmen und Datenstrukturen von Martin Dietzfelbinger, Kurt Mehlhorn und Peter Sanders [UB] (kompakter, besser organisiert, und formaler als CLRS, gut zum Nachschlagen von Detailfragen.)
- Sa: Skript „Datenstrukturen“ von Georg Schnitger [pdf] (ähnliche Auswahl von Themen; wurde in den vergangenen Jahren an der Goethe-Uni benutzt.)
- Sb: Skript „Theoretische Informatik 1“ von Georg Schnitger [pdf] (für ALGO1 ist nur das Kapitel „Effiziente Algorithmen“ relevant.)
- KT: Kleinberg, Tardos. Algorithm Design. [UB] (Ein modernes Buch, das die verschiedenen Entwurfsmethoden in den Mittelpunkt stellt, anstatt einzelner Probleme.)
- SWa: Sedgewick, Wayne, Algorithms, Fourth Edition, 2011. (konkreter und leichter zugänglich als CLRS und DMS, denn hier werden alle besprochenen Datenstrukturen und Algorithmen penibel implementiert, in Java oder Python.)
- SWb: Sedgewick, Wayne. Introduction to Programming in Java, 2017. [pdf] (Nützlich, falls Sie die Grundlagen der Programmierung auffrischen möchten.)
- GL: Gogol-Döring, Letschert. Algorithmen und Datenstrukturen für Dummies. [E-Book] (Ähnliche Themen wie ALGO1, benutzt möglichst wenig Mathematik.)
Klausur
Um an der Klausur teilzunehmen, müssen Sie sich mindestens zwei Wochen vorher über das QIS-System oder über das Prüfungsamt Ihres Studiengangs anmelden!
- Klausur: 24. Juli 2023
- Nachklausur: 2. Oktober 2023
- Organisatorische Fragen: E-Mail an algo1-2023@uni-frankfurt.de (nicht: dell@ oder moodle).
Wenn Sie eine Klausur verpassen, müssen Sie bis zur nächsten Klausur warten. Eine mündliche Prüfung ist nicht möglich.
Altklausuren
- SoSe 2021: 9. August 2021 · Klausuraufgaben · Musterlösung
- WiSe 2021/22: 6. Oktober 2021 · Klausuraufgaben · Musterlösung
- Weitere Altklausuren: Es gibt noch weitere Altklausuren. (Algorithmen und Datenstrukturen 1 war früher aufgeteilt in „Datenstrukturen“ und „Theoretische Informatik 1“.)
Weitere Hinweise
- Kattis. Um die Lerninhalte durch Programmieraufgaben zu vertiefen, eignen sich diese Kattis-Probleme.
- Algo1a/Algo1b. Die Prüfungsvarianten Algo1a und Algo1b stehen nicht mehr zur Verfügung. Studierende aus alten Studienordnungen müssen die volle ALGO1 Prüfung bestehen.
- Bonuspunkte. Im Sommersemester 2023 gibt es keine „Bonuspunkte“.