Algorithmen und Datenstrukturen 1

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

Ü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 zu den Übungsgruppen: Auf dem Anmeldesystem AUGE
• Anmeldung in Moodle: In diesem Moodle-Kurs.
• 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:30 in Hörsaal V, mit allen Studierenden und Professor oder Dozent:in): 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 mit Tutor:in): Diskussionen, Präsenzübungen, Lösungsspaziergänge und individuelle Betreuung. (Einzelne Tutorien oder Helpdesks werden möglicherweise 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 (deutsch) · Full text as E-Book (english)]. (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:

• 0 Vorbereitung
  Übungen zur eigenständigen Vorbereitung auf ALGO1 · Organisationsfolien
• 10. April – 14. April1 Einführung: Pseudocode, Hügelalgorithmen
  CLRS Kapitel 1 in Teil I · Übungsblatt · 📽️ · Folien
• 17. April – 21. April2 Entwurfsmethoden I: Suchen und Sortieren, Divide-and-Conquer
  CLRS Kapitel 2 · Übungsblatt · 📽️1 · 📽️2 · Folien · Plenum
• 24. April – 28. April3 Analyse von Algorithmen: Asymptotische Notation, Rekursionsgleichungen, Mastertheorem
  CLRS Kapitel 3, 4.3-4.5 · Übungsblatt · 📽️ · Folien
• 1. Mai – 5. Mai4 Datenstrukturen I: Stapel, Warteschlangen, Verkettete Listen, Bäume
  CLRS Einleitung von Teil III, Kapitel 10, Kapitel 17.4 bis Mitte von 17.4.1 · Übungsblatt · 📽️ · Folien
• 8. Mai – 12. Mai5 Graphalgorithmen I: Darstellung, Breitensuche, Tiefensuche
  CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · Folien
• 15. Mai – 19. Mai6 Graphalgorithmen II: Gerichtete Graphen, Suche, Topologisches Sortieren, Starke Zusammenhangskomponenten
  CLRS Einleitung von Teil VI + Kapitel 22.1-22.4 + Appendix B.4-B.5 · Übungsblatt · 📽️1 · 📽️2 · Folien
• 22. Mai – 26. Mai7 Datenstrukturen II: Prioritätswarteschlangen, Heaps
  CLRS Kapitel 6 + Appendix B.5 · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · Folien
• 29. Mai – 2. Juni8 Datenstrukturen III: Disjunkte Mengen, Union-Find
  CLRS Kapitel 21 ohne 21.4 (oder Algorithms 4ed. Kapitel 1.5) · Übungsblatt · 📽️1 · 📽️2 · Folien
• 5. Juni – 9. Juni9 Graphalgorithmen III: Minimale Spannbäume: Jarník–Prims Algorithmus, Kruskals Algorithmus
  E Kapitel 7 (oder CLRS Kapitel 23) · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · Folien
• 12. Juni – 16. Juni10 Graphalgorithmen IV: Dijkstras Algorithmus, kürzeste Wege
  E Kapitel 8 ohne 8.7 (oder CLRS Kapitel 24 außer 24.1 und 24.4) · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · Folien
• 19. Juni – 23. Juni11 Datenstrukturen IV: Wörterbücher, Hashing
  CLRS Kapitel 11 ohne 11.5 · Übungsblatt · 📽️1 · 📽️2 · Folien · cuckoo hashing
• 26. Juni – 30. Juni12 Datenstrukturen V: Traversierung, binäre Suchbäume, AVL-Bäume
  CLRS Kapitel 12 ohne 12.4 · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · Folien
• 3. Juli – 7. Juli13 Entwurfsmethoden II: Dynamische Programmierung, Fibonacci, längste gemeinsame DNA-Teilsequenz, Teilmengensumme, DP auf Bäumen
  E Kapitel 3 ohne 3.6 und 3.9 · Übungsblatt · 📽️1 · 📽️2 · 📽️3 · 📽️4 · 📽️5 · Folien
• 10. Juli – 14. Juli14 Entwurfsmethoden III: Greedy-Algorithmen, Scheduling, Huffman-Codierungen
  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! Eine Anmeldung über das ALGO1-Team ist nicht möglich. Weitere Informationen zu den Informatikstudiengängen finden Sie auf der entsprechenden Seite des Prüfungsamts Informatik.

Reklamationen zur Bewertung der Zweitklausur

• Sie sollten bereits eine E-Mail mit Ihrer Note für die Zweitklausur und einem Scan der Klausur erhalten haben.
• Fehler in unserer Bewertung können Sie bis zum 17. Oktober 2023 reklamieren.
• Offensichtliche Fehler (falsch addierte Punkte oder falsche Bewertungen in den Aufgaben 1, 2 oder 3) können Sie bis zum 17. Oktober 2023 um 13:00 direkt per Antwort auf die entsprechende Mail reklamieren.
• Reklamationen in den Aufgaben 4-5 können Sie am 17.10.2023 im persönlichen Gespräch online in Zoom anbringen.
• Ihren Zeitslot bestimmen Sie, indem Sie die Quersumme Ihrer Matrikelnummer bilden und modulo 6 rechnen. Beispielsweise müsste jemand mit Matrikelnummer 1234567 in Zeitslot 4 = (1+2+3+4+5+6+7)%6 erscheinen.
• Zeitslot 0: 13:00 - 13:30
• Zeitslot 1: 13:30 - 14:00
• Zeitslot 2: 14:00 - 14:30
• Zeitslot 3: 14:30 - 15:00
• Zeitslot 4: 15:00 - 15:30
• Zeitslot 5: 15:30 - 16:00
• Die Einsicht findet in folgendem Zoom-Raum statt: Zoom-Link

Allgemeine Infos

• Repetitorium: 17.-21. Juli 2023
• Erstklausur: 24. Juli 2023
• Klausureinsicht zur Erstklausur: Die bewertete Klausur wurde Ihnen am 27. Juli 2023 auf Ihrer HRZ-E-Mail-Adresse zugestellt, wodurch die Klausureinsicht in virtueller Form erfolgt ist. Falls Sie sicher sind, dass die Bewertung fehlerhaft ist, können Sie uns darüber bis spätestens 8. August 2023, 8:00 informieren, indem Sie direkt auf diese E-Mail antworten (reply). (Bitte beachten Sie also, dass die E-Mail-Adresse algo1-2023@uni-frankfurt.de genutzt wird und die Klausurnummer angegeben ist.) Bitte halten Sie sich kurz und beziehen Sie sich ausschließlich auf den fachlichen Inhalt Ihrer Klausur. Erklären Sie uns mit Hilfe von Screenshots und genauen Anmerkungen, welche Aufgabe Ihrer Meinung nach falsch bewertet wurde und warum. Wir werden Ihre Argumente berücksichtigen und die Klausuraufgabe anhand des von uns festgelegten Bewertungsschemas neu bewerten. Bitte beachten Sie, dass eine Neubewertung auch dazu führen kann, dass sich die Punktzahl verringert.
• Repetitorium: 20.-22. September 2023
• Zweitklausur: 2. Oktober 2023
• Organisatorische Fragen:
  • “Welche Hilfstmittel sind erlaubt?” 1 handbeschriebenes DIN-A4-Blatt darf mitgebracht werden.
  • “Wie melde ich mich an?” Nur über Ihr Prüfungsamt. Lehramt über Lehramt-Prüfungsamt, Informatik über Informatik-Prüfungsamt, etc.
  • “I am an Erasmus student or a doctoral student…” The written exam will be provided bilingually by default. Please register at algo1-2023@uni-frankfurt.de in case you want to take the exam.
  • Bei sonstigen Anliegen wenden Sie sich an das ALGO1-Team unter algo1-2023@uni-frankfurt.de (nicht: dell@ oder moodle).

Wenn Sie eine Klausur verpassen oder nicht bestehen, müssen Sie bis zur nächsten Klausur warten. Eine mündliche Prüfung ist nicht möglich.

Weitere Hinweise

• Altklausuren. Dieses Verzeichnis enthält alle ALGO1-Klausuren samt Lösungsvorschlägen seitdem das Modul B-ALGO-1 in der aktuellen Form existiert.
• 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“.