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:

1. Einführung und Peaks · a
   CLRS Kapitel 1 · Übungsblatt · ⭐ · 📽️ · Folien · Organisationsfolien
   

2. Suchen und Sortieren · a
   CLRS Kapitel 2 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · Folien
   

3. Analyse von Algorithmen, Asymptotische Notation, Rekursionsgleichungen, Mastertheorem · a
   CLRS Kapitel 3, 4.3-4.5 · Übungsblatt · ⭐ · 📽️ · Folien · experiment.py · Lagebesprechung
   

4. Elementare 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 · ⭐ · 📽️ · Folien
   

5. Darstellung von Graphen, Breitensuche, Tiefensuche · b
   CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · Folien
   

6. Gerichtete 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 · Folien
   

7. Prioritätswarteschlangen, Heaps · a
   CLRS Kapitel 6 + Appendix B.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · Folien
   

8. Disjunkte Mengen, Union-Find · a
   CLRS Kapitel 21 ohne 21.4 (oder Algorithms 4ed. Kapitel 1.5) · Übungsblatt · ⭐ · 📽️1 · 📽️2 · Folien
   

9. Minimale Spannbäume: Jarník–Prims Algorithmus, Kruskals Algorithmus · b
   E Kapitel 7 (oder CLRS Kapitel 23) · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · Folien
   

10. Dijkstras 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 · Folien
    

11. Wörterbücher, Hashing · a
    CLRS Kapitel 11 ohne 11.5 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · Folien · cuckoo hashing
    

12. Traversierung, binäre Suchbäume, AVL-Bäume · a
    CLRS Kapitel 12 ohne 12.4 · Übungsblatt · ⭐ · 📽️1 · 📽️2 · 📽️3 · Folien
    

13. Dynamische 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 · Folien
    

14. Greedy-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“.