Algorithmen 1

Dozent: Thomas Bläsius

Übungsleitung: Maximilian Katzmann, Marcus Wilhelm, Wendy Yi

In dieser Vorlesung werden grundlegende Kenntnisse im Bereich Algorithmen und Datenstrukturen vermittelt. Ziel ist es, Fähigkeiten zu Verständnis und Lösung algorithmischer Probleme, sowie insbesondere deren Formalisierung, Kommunikation und Analyse zu erlernen.

Austausch findet vorrangig über Discord statt. Der Zugang ist verlinkt im ILIAS-Kurs: https://ilias.studium.kit.edu/goto.php?target=crs%5F2086671&client_id=produktiv

Eine Liste von Hochschulgruppen, die gerade aktiv neue Mitglieder suchen findet ihr hier.

Mit einer 5-minütigen, anonymen Umfrage könnt ihr dazu beitragen den Studienstart am KIT zu verbessern! (Bitte nur 1x ausfüllen.)

• Die Nachklausur findet am 01. März statt. Klausurbeginn ist um 8:00 Uhr; seid also am besten um 7:40 Uhr vor Ort.
• Eine Zuteilung, wer in welchem Hörsaal schreibt, findet ihr in dieser Liste.
• Die Bearbeitungszeit beträgt 2 Stunden.

• Als Hilfsmittel ist ein Spickzettel erlaubt. Ein Spickzettel besteht aus einem A4 Blatt, auf dem die Vor- und Rückseite beliebigen Inhalt enthalten darf.

• Die vorläufigen Noten (mit Bonus) wurden im Campus-System eingetragen.
• Die Klausur vom Wintersemester 23/24 findet ihr hier, eine Version mit Lösungen hier.
• Hier findet ihr die Notenskala und die Notenverteilung.
• Die Einsicht findet am 13.03.24 von 13 bis 14 Uhr im Raum 301 im Informatik-Gebäude statt.

• Die Hauptklausur fand am 31. August statt. Klausurbeginn ist um 8:00 Uhr; seid also am besten um 7:40 Uhr vor Ort.
• Die Bearbeitungszeit beträgt 2 Stunden.

• Als Hilfsmittel ist ein Spickzettel erlaubt. Ein Spickzettel besteht aus einem A4 Blatt auf dem die Vor- und Rückseite beliebigen Inhalt enthalten darf.

• Altklausuren sind hier verfügbar. Die Hauptklausur vom Sommersemester 2022 findet ihr hier, eine Version mit Lösungen hier, die Nachklausur vom Wintersemester 22/23 hier und eine Version mit Lösungen hier.

• Die vorläufigen Noten (mit Bonus) wurden im Campus-System eingetragen.
• Die Klausur vom Sommersemester 2023 findet ihr hier, eine Version mit Lösungen hier.
• Hier findet ihr die Notenskala und die Notenverteilung.
• Die Einsicht wird voraussichtlich Ende September stattfinden, der genaue Termin wird rechtzeitig bekannt gegeben.

Es gibt zwei Wöchentliche Termine für Vorlesung und Übung: Montags 15:45 und Mittwoch 14:00.

Zusätzlich gibt es Tutorien (genaue Liste folgt).

1. Einführung - Multiplikation und O-Notation: mit Klicks, ohne Klicks
2. Teile und Herrsche: mit Klicks, ohne Klicks
3. Dynamische Arrays, amortisierte Analyse: mit Klicks, ohne Klicks
4. Listen und binäre Suche: mit Klicks, ohne Klicks
5. Sortieren - Mergesort, Quicksort, untere Schranke: mit Klicks, ohne Klicks
6. Sortieren - Bucketsort, Radixsort, Word-RAM: mit Klicks, ohne Klicks
7. Hashing: mit Klicks, ohne Klicks
8. Graphen und Breitensuche: mit Klicks, ohne Klicks
9. Kürzeste Wege - Dijkstras Algorithmus: mit Klicks, ohne Klicks
10. Kürzeste Wege - negative Kanten und APSP: mit Klicks, ohne Klicks
11. Binärer Heap: mit Klicks, ohne Klicks
12. Sortierte Folgen und Suchbäume: mit Klicks, ohne Klicks
13. (2, 3)-Bäume - Implementierung: mit Klicks, ohne Klicks
14. Tiefensuche - Brücken finden: mit Klicks, ohne Klicks
15. Tiefensuche auf gerichteten Graphen: mit Klicks, ohne Klicks
16. Minimale Spannbäume: mit Klicks, ohne Klicks
17. Union-Find: mit Klicks, ohne Klicks
18. Dynamische Programme: mit Klicks, ohne Klicks
19. Generische Optimierungsmethoden: mit Klicks, ohne Klicks
20. Average-Case Analyse, Zusammenfassung, Ausblick: mit Klicks, ohne Klicks

Zusätzliche Notizen mit den Lernzielen, Literaturhinweisen zu den einzelnen Vorlesungen und eine Glossar mit den wichtigsten Begriffen findet ihr hier. Hier auch nochmal das selbe Dokument aber mit Links zu den Folien ohne Klicks.

1. Asymptotik, Pseudocode und Master-Theorem: mit Klicks, ohne Klicks (Update 24.04. 15:00)
2. Algorithmenentwurf, amortisierte Analyse: mit Klicks, ohne Klicks
3. Sortieren, Hashing: mit Klicks, ohne Klicks (Update 24.05. 9:45)
4. Graphen: mit Klicks, ohne Klicks
5. Suchbäume & Suche in Graphen: mit Klicks, ohne Klicks
6. Starker Zusammenhang mit DFS, strukturelle Induktion: mit Klicks, ohne Klicks
7. DP, amortisierte Analyse mit Klicks, ohne Klicks

Die Übungsblätter werden mittwochs ab 14:00 Uhr hier verfügbar sein. Die Lösungen können dann bis Freitag 18:00 Uhr in der darauffolgenden Woche in Form eines PDFs online eingereicht werden. Dies erfolgt über ILIAS unter 'Tutoriumsgruppen' in der Gruppe des jeweiligen Tutors.

• Es wird genau eine Abgabe pro Student erwartet.
• Die Lösungen müssen mit gut sichtbar mit Namen und Matrikelnummer beschriftet sein.
• Bei handschriftlichen Abgaben muss auf Lesbarkeit und ausreichend Platz für Korrekturanmerkungen gesorgt werden.
• Achte darauf, effiziente Algorithmen zu formulieren, also solche mit möglichst geringer asymptotischer Laufzeit!
• Wenn du die Korrekheit deines Algorithmus begründen oder dessen Laufzeit analysieren sollst, tue dies getrennt von der Beschreibung deines Algorithmus.
• Gib Algorithmen nur in Pseudocode an anstatt sie in Worten zu beschreiben, falls dies explizit gefordert ist!
• Falls nicht anders spezifiziert, bezeichnen wir mit „Graph“ einen einfachen, ungerichteten und ungewichteten Graphen.

Wer mindestens 50% aller Punkte erreicht, die auf den Übungsblättern vergeben werden, erhält einen Bonus von 0.3 Notenpunkten in der Abschlussklausur.

• Übungsblatt 01
• Übungsblatt 02
• Übungsblatt 03
• Übungsblatt 04
• Übungsblatt 05
• Übungsblatt 06
• Übungsblatt 07
• Übungsblatt 08
• Übungsblatt 09
• Übungsblatt 10
• Übungsblatt 11
• Übungsblatt 12
• Übungsblatt 13
• Übungsblatt 14

Wir bieten die folgenden Richtlinien für das Schreiben von Pseudocode an, die zur Orientierung helfen können: Pseudocode Richtlinien

Über die Woche verteilt gibt es 31 Tutorien (siehe Liste). Diese dienen dem interaktiven Austausch über die Übungsblätter sowie aktuelle Themen aus Vorlesung und Übung. In den Tutorien werden außerdem die Übungsblätter abgegeben, korrigiert und besprochen.

Die Anmeldung zu den Tutorien erfolgt von Dienstag, den 18.04.2023, 18:00 Uhr bis Donnerstag, den 20.04.2023, 18:00 Uhr unter https://www.informatik.kit.edu/tutorieneinteilung/.