Algorithmen und Datenstrukturen 1

• Modulkürzel: B-ALGO-1→ALGO1
• Externe Links:
  QISMoodle

Übersicht

Allgemeine Informationen

Der Kurs findet nur synchron und vollständig online statt, und ist didaktisch so konzipiert, dass Student:innen in kleinen Gruppen gemeinsam Übungsaufgaben diskutieren und währenddessen individuell von einem freundlichen und kompetenten Team betreut werden.

Ort und Zeit

• Dienstag und Donnerstag 8:00–10:00. Lagebesprechung, Gruppenarbeit, Helpdesks, Lösungsvorschläge.
• Freitag 14:15–15:45. Besprechung der ⭐-Aufgabe und Helpdesks.
• Discordserver des Lernzentrums.

Anmeldung

Bitte melden Sie sich in Moodle an.

Dozent

• Holger Dell

Tutor:innen

• Niklas Fleischer
• Marius Hagemann
• Alexander Hengstmann
• Lars Huth
• Melvin Kallmayer
• Dayana Khadush
• Aura Sofia Lohr
• Patrick Masny
• Patrick Raphael Melnic
• Julian Mende
• Anton Micke
• Jonas Strauch
• Tolga Tel
• Marc Viel

Voraussetzungen

Sie brauchen für den Kurs Basisfähigkeiten im Programmieren sowie grundlegende mathematische Fähigkeiten. Mit diesem Selbsttest können Sie vorab Ihre Fähigkeiten prüfen und auffrischen.

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 · Plan · ⭐ · 📽️ · Folien · Organisationsfolien
   

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

3. Analyse von Algorithmen, Asymptotische Notation, Rekursionsgleichungen, Mastertheorem · a
   CLRS Kapitel 3, 4.3-4.5 · Plan · ⭐ · 📽️ · 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 · Plan · ⭐ · 📽️ · Folien
   

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

6. Gerichtete Graphen, Suche, Topologisches Sortieren, Starke Zusammenhangskomponenten · b
   CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Plan · ⭐ · 📽️1 · 📽️2 · Folien
   

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

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

9. Minimale Spannbäume: Jarník–Prims Algorithmus, Kruskals Algorithmus · b
   E Kapitel 7 (oder CLRS Kapitel 23) · Plan · ⭐ · 📽️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) · Plan · ⭐ · 📽️1 · 📽️2 · 📽️3 · Folien
    

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

12. Traversierung, binäre Suchbäume, AVL-Bäume · a
    CLRS Kapitel 12 ohne 12.4 · Plan · ⭐ · 📽️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 · Plan · ⭐ · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
    

14. Greedy-Algorithmen, Scheduling, Huffman-Codierungen · b
    E Kapitel 4 · Plan · ⭐ · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
    

Lernziele

Nach der Veranstaltung können die Studierenden:

• Algorithmen aus dem Grundkanon beschreiben und anwenden,
• Pseudocode interpretieren und von natürlicher Sprache sowie Programmiersprachen abgrenzen,
• sich über fachbezogene Inhalte mündlich und schriftlich austauschen,
• die Funktionsweise und Eigenschaften von gegebenen Algorithmen und Datenstrukturen an kleinen Beispielen demonstrieren,
• die Laufzeit und den Platzbedarf von gegebenen Algorithmen ermitteln, vergleichen und bewerten,
• praxisnahe Fragestellungen als algorithmische Probleme formulieren und einschätzen, welcher Algorithmus / welche Datenstruktur zu deren Lösung geeignet ist,
• gegebene Algorithmen und Datenstrukturen an neue Problemstellungen anpassen,
• die Korrektheit und Komplexität von gegebenen Algorithmen und Datenstrukturen mathematisch begründen,
• neue Algorithmen und Datenstrukturen mit Hilfe grundlegender Entwurfsmethoden entwickeln,
• als Pseudocode gegebene Algorithmen und Datenstrukturen in einer Programmiersprache korrekt implementieren und testen.

Übungen

Alleine ein Buch lesen oder Videos anschauen können Sie auch ohne diesen Kurs. Mit 1–2 anderen Student:innen zusammen Übungsaufgaben bearbeiten, und dabei unsere Unterstützung und unser Feedback erfahren, das sind die Qualitäten, die Sie ohne diesen Kurs nicht haben. Daher sind Übungen und die Möglichkeit zum direkten mündlichen Gespräch mit Tutor:innen oder dem Dozenten das zentrale Angebot dieses Kurses.

⭐

Manche Übungsaufgaben sind besonders, denn sie sind mit ⭐ markiert. Diese Aufgaben lösen Sie außerhalb des Synchronbetriebs und geben sie als PDF-Datei ab; fotografieren Sie hierzu Ihre lesbare Handschrift mit einer Scanner-App oder benutzen Sie unser .tex-Template. Sie erhalten nützliches Feedback von den Tutor:innen auf Ihre Lösung, und Ihre Lösung wird anhand objektiver Kriterien entweder akzeptiert oder nicht akzeptiert. Wenn Ihre Lösung akzeptiert wird, erhalten Sie einen Stern ⭐, der möglicherweise Ihre Klausurnote verbessert. ⭐-Aufgaben verfolgen zwei Ziele: 1) Sie lernen, im sozialen Rahmen einer kleinen Gruppe Algorithmen für Ihnen vorher unbekannte algorithmische Probleme selbst zu entwickeln und zu analysieren. 2) Indem Sie die Lösung aufschreiben, verfassen Sie dadurch einen kurzen, wissenschaftlichen Text, und lernen dabei, die wissenschaftliche Sprache der Algorithmenforschung korrekt zu benutzen. Beide Aspekte sind wichtig und ergänzen sich gegenseitig, Sie sollten daher für Beides genügend Zeit einplanen. Folgende Regeln sind verpflichtend zu beachten:

• Sie dürfen in einer Gruppe von bis zu drei Student:innen zusammen abgeben. Aber: Bevor Sie anfangen, eine ⭐-Aufgabe zu bearbeiten, legen Sie sich verbindlich auf diese Gruppe fest.
• Außerhalb Ihrer Lerngruppe dürfen Sie über Lösungen, Ideen, Ansätze, oder sonstige Hinweise zu ⭐-Aufgaben nicht sprechen oder diese anderweitig kommunizieren.
• Tutor:innen und Dozent:innen und Freunde und Fremde dürfen Ihrer Lerngruppe bei der Bearbeitung von ⭐-Aufgaben in keiner Weise helfen.
• Sie dürfen auch keine Lösungsansätze zu ähnlichen Aufgaben aus vergangenen Jahren oder aus ähnlichen Kursen oder aus dem Internet oder von irgendwoher sonst anschauen.
• Sie dürfen die Lösung einer ⭐-Aufgabe weder weitergeben noch von sich abschreiben lassen noch irgendwo für Andere sichtbar hochladen noch liegen lassen.
• Wenn Sie gegen diese Regeln verstoßen, werden beim ersten Vergehen alle Mitglieder der betroffenen Lerngruppen von allen ⭐-Programmen dieser Professur ausgeschlossen. Wenn Sie von sich abschreiben lassen oder selbst abschreiben, schaden Sie also immer mindestens zwei ganzen Lerngruppen.
• Falls Sie die Klausur bestehen, erhöhen gesammelte ⭐ Ihr Klausurergebnis um bis zu 10 %. Das heißt, eine mit 50 % der Punkte gerade so bestandene Klausur kann im besten Fall als 60 % gewertet werden, aber eine mit 49 % nicht bestandene Klausur bleibt nicht bestanden. Der Bonus berechnet sich als 10 % * #(von Ihnen gesammelte ⭐) / #(insgesamt verfügbare ⭐).

Verwandte Vorlesungen

• Vorbild für diese Vorlesung ist eine Lockdown-Vorlesung von Philip Bille und Inge Li Gørtz an der DTU Kopenhagen. Mange tak Philip og Inge!
• Eine vorherige Iteration von ALGO1 wurde im SoSe-2020 (Prof. Meyer) angeboten, wofür Videos aus Präcoronazeiten zusammengeschnitten wurden. Videos sind auch verfügbar aus dem SoSe-2019 und WiSe-2019/20 (Prof. Hoefer).
• 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

• Klausur: 9. August 2021 · Klausuraufgaben · Musterlösung
• Nachklausur: 6. Oktober 2021 · Klausuraufgaben · Musterlösung
• Organisatorische Fragen: E-Mail an algo121@uni-frankfurt.de (nicht: dell@ oder moodle).

Weitere Hinweise

• Um die Lerninhalte durch Programmieraufgaben zu vertiefen, eignen sich diese Kattis-Probleme.
• Die Prüfungsvarianten Algo1a und Algo1b stehen für Student:innen aus der alten Studienordnung zur Verfügung. Siehe hierzu die Äquivalenzregelung des Prüfungsamts. In diesem Fall zählen nur die ⭐, die für die jeweilige Unterprüfung relevant sind. Sie sehen in der Wochenübersicht 14 Wochen, jede Woche ist in Grau mit a oder b markiert. Beachten Sie, dass diese Einteilung vorläufig ist, und dass Algo1b auf Algo1a aufbaut, weshalb für viele Themen in Algo1b immer auch die Grundlagen aus Algo1a wichtig sind.
• Nur der Suchen-Teil von Suchen und Sortieren ist klausurrelevant für ALGO1, denn Sortieren ist Teil der ALGO2 Prüfung.
• Ein Übertrag von „Bonuspunkten“ aus den Vorjahren wird aus technischen und didaktischen Gründen nicht stattfinden. Dieser ist aber auch nicht nötig, da die Klausur nicht zulassungsbeschränkt ist. Sie können also einfach mitschreiben, wenn Sie sich rechtzeitig anmelden.
• Altklausuren. Dieses Verzeichnis enthält alle ALGO1-Klausuren samt Lösungsvorschlägen seitdem das Modul B-ALGO-1 in der aktuellen Form existiert.