====== Algorithmen 1 ======

**Dozent:** [[people:thomasblaesius|]]

**Übungsleitung:** [[people:maximiliankatzmann|]], [[people:marcuswilhelm|]], [[people:wendyyi|]]
\\
\\

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 [[teaching:hochschulgruppenwerbung:start|hier]].
\\
== Umfrage zum Studienstart ==
Mit einer **[[https://onlineumfrage.kit.edu/evasys/online.php?p=XYZ2U|5-minütigen, anonymen Umfrage]]** könnt ihr dazu beitragen den Studienstart am KIT zu verbessern! (Bitte nur 1x ausfüllen.)

===== Nachklausur =====

  * 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 {{ :teaching:2023ss:algo1:participants.pdf |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.

== Ergebnisse == 
  * Die vorläufigen Noten (//mit// Bonus) wurden im Campus-System eingetragen.  
  * Die Klausur vom Wintersemester 23/24 findet ihr {{ :teaching:2023ss:algo1:exam2.pdf |hier}}, eine Version mit Lösungen {{ :teaching:2023ss:algo1:exam-sol2.pdf |hier}}. 
  * {{ :teaching:2023ss:algo1:notenskala2.pdf |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. 

===== Hauptklausur =====

  * 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 [[https://www.fsmi.uni-karlsruhe.de/odie/web/#documentselection/l28|hier]] verfügbar. Die Hauptklausur vom Sommersemester 2022 findet ihr {{ :teaching:2022ss:algo1:klausur1.pdf |hier}}, eine Version mit Lösungen {{ :teaching:2022ss:algo1:klausur1_loesung.pdf |hier}}, die Nachklausur vom Wintersemester 22/23 {{ :teaching:2022ss:algo1:klausur2.pdf |hier}} und eine Version mit Lösungen {{ :teaching:2022ss:algo1:klausur2_loesung.pdf |hier}}.

== Ergebnisse == 
  * Die vorläufigen Noten (//mit// Bonus) wurden im Campus-System eingetragen.  
  * Die Klausur vom Sommersemester 2023 findet ihr {{ :teaching:2023ss:algo1:exam1.pdf |hier}}, eine Version mit Lösungen {{ :teaching:2023ss:algo1:exam-sol1.pdf |hier}}. 
  * {{ :teaching:2023ss:algo1:notenskala.pdf |Hier}} findet ihr die Notenskala und die Notenverteilung. 
  * Die Einsicht wird voraussichtlich Ende September stattfinden, der genaue Termin wird rechtzeitig bekannt gegeben. 

======  ======

{{section>:teaching:2023ss:algo1:zusatztut:&nofooter&noeditbtn&firstseconly}}

===== Ablauf =====


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

^ Woche ^ Montag                ^ Mittwoch (Aus- und Abgabe von Übungsblättern)  ^
| 1     | 2023-04-17: Vorlesung 1      | 2023-04-19: Vorlesung 2      |
| 2     | 2023-04-24: Übung 1   | 2023-04-26: Vorlesung 3      |
| 3     | 2023-05-01: Feiertag  | 2023-05-03: Vorlesung 4      |
| 4     | 2023-05-08: Vorlesung 5      | 2023-05-10: Übung 2   |
| 5     | 2023-05-15: Vorlesung 6      | 2023-05-17: Vorlesung 7      |
| 6     | 2023-05-22: Vorlesung 8      | 2023-05-24: Übung 3   |
| 7     | 2023-05-29: Pfingsten | 2023-05-31: Pfingsten |
| 8     | 2023-06-05: Vorlesung 9      | 2023-06-07: Vorlesung 10     |
| 9     | 2023-06-12: Vorlesung 11     | 2023-06-14: Übung 4   |
| 10    | 2023-06-19: Vorlesung 12     | 2023-06-21: Vorlesung 13     |
| 11    | 2023-06-26: Vorlesung 14     | 2023-06-28: Übung 5   |
| 12    | 2023-07-03: Vorlesung 15     | 2023-07-05: Vorlesung 16     |
| 13    | 2023-07-10: Vorlesung 17     | 2023-07-12: Übung 6   |
| 14    | 2023-07-17: Vorlesung 18     | 2023-07-19: Vorlesung 19     |
| 15    | 2023-07-24: Vorlesung 20     | 2023-07-26: Übung 7   |

===== Vorlesung =====

  - Einführung - Multiplikation und O-Notation: {{ :teaching:2023ss:algo1:01-o-notation.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:01-o-notation-print.pdf |ohne Klicks}}
  - Teile und Herrsche: {{ :teaching:2023ss:algo1:02-multiplikation.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:02-multiplikation-print.pdf |ohne Klicks}}
  - Dynamische Arrays, amortisierte Analyse: {{ :teaching:2023ss:algo1:03-dyn-array.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:03-dyn-array-print.pdf |ohne Klicks}}
  - Listen und binäre Suche: {{ :teaching:2023ss:algo1:04-listen-und-suchen.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:04-listen-und-suchen-print.pdf |ohne Klicks}}
  - Sortieren - Mergesort, Quicksort, untere Schranke: {{ :teaching:2023ss:algo1:05-sortieren.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:05-sortieren-print.pdf |ohne Klicks}}
  - Sortieren - Bucketsort, Radixsort, Word-RAM: {{ :teaching:2023ss:algo1:06-sortieren2.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:06-sortieren2-print.pdf |ohne Klicks}}
  - Hashing: {{ :teaching:2023ss:algo1:07-hashing.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:07-hashing-print.pdf |ohne Klicks}}
  - Graphen und Breitensuche: {{ :teaching:2023ss:algo1:08-graphen-bfs.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:08-graphen-bfs-print.pdf |ohne Klicks}}
  - Kürzeste Wege - Dijkstras Algorithmus: {{ :teaching:2023ss:algo1:09-dijkstra.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:09-dijkstra-print.pdf |ohne Klicks}}
  - Kürzeste Wege - negative Kanten und APSP: {{ :teaching:2023ss:algo1:10-kuerzeste-wege-2.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:10-kuerzeste-wege-2-print.pdf |ohne Klicks}}
  - Binärer Heap: {{ :teaching:2023ss:algo1:11-heap.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:11-heap-print.pdf |ohne Klicks}}
  - Sortierte Folgen und Suchbäume: {{ :teaching:2023ss:algo1:12-ab-trees.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:12-ab-trees-print.pdf |ohne Klicks}}
  - (2, 3)-Bäume - Implementierung: {{ :teaching:2023ss:algo1:13-23-tree-implementation.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:13-23-tree-implementation-print.pdf |ohne Klicks}}
  - Tiefensuche - Brücken finden: {{ :teaching:2023ss:algo1:14-dfs-bridges.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:14-dfs-bridges-print.pdf |ohne Klicks}}
  - Tiefensuche auf gerichteten Graphen: {{ :teaching:2023ss:algo1:15-dfs-directed.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:15-dfs-directed-print.pdf |ohne Klicks}}
  - Minimale Spannbäume: {{ :teaching:2023ss:algo1:16-mst.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:16-mst-print.pdf |ohne Klicks}}
  - Union-Find: {{ :teaching:2023ss:algo1:17-union-find.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:17-union-find-print.pdf |ohne Klicks}}
  - Dynamische Programme: {{ :teaching:2023ss:algo1:18-dp.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:18-dp-print.pdf |ohne Klicks}}
  - Generische Optimierungsmethoden: {{ :teaching:2023ss:algo1:19-generische-optimierung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:19-generische-optimierung-print.pdf |ohne Klicks}}
  - Average-Case Analyse, Zusammenfassung, Ausblick: {{ :teaching:2023ss:algo1:20-zusammenfassung-ausblick.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:20-zusammenfassung-ausblick-print.pdf |ohne Klicks}}
==== Lernziele, Literaturhinweise und Glossar ====

Zusätzliche Notizen mit den Lernzielen, Literaturhinweisen zu den einzelnen Vorlesungen und eine Glossar mit den wichtigsten Begriffen findet ihr {{ :teaching:2023ss:algo1:algo1.pdf |hier}}. Hier auch nochmal das selbe Dokument aber mit Links zu den Folien {{ :teaching:2023ss:algo1:algo1-print.pdf |ohne Klicks}}.
===== Übung =====

  - Asymptotik, Pseudocode und Master-Theorem: {{ :teaching:2023ss:algo1:01-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:01-uebung-print.pdf |ohne Klicks}} (Update 24.04. 15:00)
  - Algorithmenentwurf, amortisierte Analyse: {{ :teaching:2023ss:algo1:02-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:02-uebung-print.pdf |ohne Klicks}}
  - Sortieren, Hashing: {{ :teaching:2023ss:algo1:03-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:03-uebung-print.pdf |ohne Klicks}} (Update 24.05. 9:45)
  - Graphen: {{ :teaching:2023ss:algo1:04-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:04-uebung-print.pdf |ohne Klicks}}
  - Suchbäume & Suche in Graphen: {{ :teaching:2023ss:algo1:05-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:05-uebung-print.pdf |ohne Klicks}}
  - Starker Zusammenhang mit DFS, strukturelle Induktion: {{ :teaching:2023ss:algo1:06-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:06-uebung-print.pdf |ohne Klicks}}
  - DP, amortisierte Analyse  {{ :teaching:2023ss:algo1:07-uebung.pdf |mit Klicks}}, {{ :teaching:2023ss:algo1:07-uebung-print.pdf |ohne Klicks}}
===== Übungsblätter =====

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.

  * {{ :teaching:2023ss:algo1:blatt01.pdf |Übungsblatt 01}}
  * {{ :teaching:2023ss:algo1:blatt02.pdf |Übungsblatt 02}}
  * {{ :teaching:2023ss:algo1:blatt03.pdf |Übungsblatt 03}}
  * {{ :teaching:2023ss:algo1:blatt04.pdf |Übungsblatt 04}}
  * {{ :teaching:2023ss:algo1:blatt_05.pdf |Übungsblatt 05}}
  * {{ :teaching:2023ss:algo1:blatt_06.pdf |Übungsblatt 06}}
  * {{ :teaching:2023ss:algo1:blatt_07.pdf |Übungsblatt 07}}
  * {{ :teaching:2023ss:algo1:blatt_08.pdf |Übungsblatt 08}}
  * {{ :teaching:2023ss:algo1:blatt_09.pdf |Übungsblatt 09}}
  * {{ :teaching:2023ss:algo1:blatt_10.pdf |Übungsblatt 10}}
  * {{ :teaching:2023ss:algo1:blatt_11.pdf |Übungsblatt 11}}
  * {{ :teaching:2023ss:algo1:blatt_12.pdf |Übungsblatt 12}}
  * {{ :teaching:2023ss:algo1:blatt_13.pdf |Übungsblatt 13}}
  * {{ :teaching:2023ss:algo1:blatt_14.pdf |Übungsblatt 14}}

===== Pseudocode =====

Wir bieten die folgenden Richtlinien für das Schreiben von Pseudocode an, die zur Orientierung helfen können: {{ :teaching:2023ss:algo1:guidelines.pdf |Pseudocode Richtlinien}}

===== Tutorien =====

Über die Woche verteilt gibt es 31 Tutorien ([[teaching:2023ss:algo1: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/]].

======  ======

{{section>:teaching:2023ss:algo1:twitch:&nofooter&noeditbtn&firstseconly}}