Algorithmen und Datenstrukturen 1

SoSe-2023

Modulkürzel: B-ALGO-1→ALGO1
Externe Links:
QIS Moodle algo-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]. (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).

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.

Aktuelle Infos zur Zweitklausur am 02. Oktober

Die Klausur wird bilingual angeboten, das heißt, alle Aufgabentexte sind auf Deutsch und auf Englisch abgedruckt. Sie können in jeder der beiden Sprachen antworten.
Die Klausur wird in zwei Hörsälen geschrieben. Die Aufteilung der Studierenden auf die Hörsäle erfolgt nach der Endziffer Ihrer Matrikelnummer. Die Aufteilung ist wie folgt:
- Studierende, deren Matrikelnummer auf einer Ziffer zwischen 0-4 endet, müssen um 8:45 in Hörsaal HV sein.
- Studierende, deren Matrikelnummer auf einer Ziffer zwischen 5-9 endet, müssen um 8:45 in Hörsaal HVI sein.
- Studierende ohne Matrikelnummer (z.B. Erasmus und Doktoranden) müssen um 8:45 in Hörsaal HV sein.
Bringen Sie unbedingt Ihren Studierendenausweis sowie Ihren Personalausweis oder Reisepass mit. Ohne diese Dokumente können Sie nicht an der Klausur teilnehmen.

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