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


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

**Übungsleitung:** [[people:vonderheydt]], [[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.
\\
\\

Regen Austausch zur Vorlesung gibt es auf Discord. Der Zugang ist im [[https://ilias.studium.kit.edu/ilias.php?baseClass=ilrepositorygui&ref_id=2367543|Ilias]] verlinkt.

\\
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/online.php?p=FMP6J|5-minütigen, anonymen Umfrage]]** könnt ihr dazu beitragen den Studienstart am KIT zu verbessern! (Bitte nur 1x ausfüllen.)

==== Hauptklausur ====
  * Die Hauptklausur findet am Freitag den 30. August statt. Klausurbeginn ist um 8:00 Uhr; seid also am besten um 7:40 Uhr vor Ort.
  * **Die Zuteilung wer in welchem Hörsaal schreibt (und weitere Hinweise)**, findet ihr in dieser {{ :teaching:2024ss:algo1:participants.pdf |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 (d.h. insbesondere sind sowohl handbeschriebene wie auch gedruckte Spickzettel zulässig).

  * Altklausuren findet ihr hier:
    * Wintersemester 23/24: {{ :teaching:2023ss:algo1:exam2.pdf |ohne Lösungen}}, {{ :teaching:2023ss:algo1:exam-sol2.pdf |mit Lösungen}}
    * Sommersemester 2023: {{ :teaching:2023ss:algo1:exam1.pdf |ohne Lösungen}}, {{ :teaching:2023ss:algo1:exam-sol1.pdf|mit Lösungen}}
    * Wintersemester 22/23 {{ :teaching:2022ss:algo1:klausur2.pdf |ohne Lösungen}}, {{ :teaching:2022ss:algo1:klausur2_loesung.pdf |mit Lösungen}}
    * Sommersemester 2022 {{ :teaching:2022ss:algo1:klausur1.pdf |ohne Lösungen}}, {{ :teaching:2022ss:algo1:klausur1_loesung.pdf |mit Lösungen}}
    * Außerdem sammelt die Fachschaft [[https://www.fsmi.uni-karlsruhe.de/odie/web/#documentselection/l28|hier]] Altklausuren

== Ergebnisse == 
  * Die vorläufigen Noten (//mit// Bonus) wurden im Campus-System eingetragen.  
  * {{ :teaching:2024ss:algo1:notenskala.pdf |Hier}} findet ihr die Notenskala und die Notenverteilung. 
  * {{ :teaching:2024ss:algo1:exam1-sol.pdf |Hier}} findet ihr eine Musterlösung zur Klausur 

== Einsicht ==

  * Die Einsicht findet am Donnerstag, den 12.9, im Raum -101 statt.
  * Über folgenden Link könnt ihr euch für einen Zeitslot eintragen: [[https://plus.campus.kit.edu/signmeup/go/KVj1tjqyM]]
  * Falls ihr selbst nicht zur Einsicht erscheinen könnt, könnt ihr einer anderen Person eine Vollmacht ausstellen, damit diese Person eure Klausur einsehen darf. 


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

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

===== Ablauf =====

Es gibt wöchentlich zwei Termine für Vorlesung und Übung: Montag 15:45 und Mittwoch 14:00. 

Zusätzlich gibt es Tutorien.

^ Woche  ^ Montag               ^ Mittwoch             ^
| 1      | 15.04. Vorlesung 1   | 17.04. Vorlesung 2   |
| 2      | 22.04. Vorlesung 3   | 24.04. Übung 1       |
| 3      | 29.04. Vorlesung 4   | 01.05. Maifeiertag   |
| 4      | 06.05. Vorlesung 5   | 08.05. Übung 2       |
| 5      | 13.05. Vorlesung 6   | 15.05. Vorlesung 7   |
| 6      | 20.05. Pfingsten     | 22.05. Pfingsten     |
| 7      | 27.05. Vorlesung 8   | 29.05. Übung 3       |
| 8      | 03.06. Vorlesung 9   | 05.06. Vorlesung 10  |
| 9      | 10.06. Vorlesung 11  | 12.06. Übung 4       |
| 10     | 17.06. Vorlesung 12  | 19.06. Vorlesung 13  |
| 11     | 24.06. Vorlesung 14  | 26.06. Übung 5       |
| 12     | 01.07. Vorlesung 15  | 03.07. Vorlesung 16  |
| 13     | 08.07. Vorlesung 17  | 10.07. Übung 6       |
| 14     | 15.07. Vorlesung 18  | 17.07. Vorlesung 19  |
| 15     | 22.07. Übung 7       | 24.07. Vorlesung 20  |
===== Vorlesung =====

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

Unter https://algo-code.iti.kit.edu findet ihr ein Tool, mit dem ihr die Fähigkeit trainieren könnt, eine algorithmische Idee tatsächlich umzusetzen. Das ist eine Fähigkeit, die man nicht //lernen//, sondern nur //trainieren// kann (im Sinne von: es hilft nicht viel, sich anzuschauen bzw erklären zu lassen, wie das geht; das muss man oft genug selber machen).

Die Seite wird zwar gerade noch entwickelt, es gibt noch viele Bugs und nicht so viele Levels, aber nützlich für das Training sollte sie trotzdem schon sein. Im Laufe des Semesters kommt sicher auch das eine oder andere Level dazu.

===== Übung =====
   - Asymptotik, Pseudocode, amortisierte Analyse: {{ :teaching:2024ss:algo1:01-uebung.pdf | mit Klicks}},  {{ :teaching:2024ss:algo1:01-uebung-print.pdf | ohne Klicks}}
   - Datenstrukturen / Amortisierte Analyse, Sortieren und Quicksort: {{ :teaching:2024ss:algo1:02-uebung.pdf |mit Klicks}},  {{ :teaching:2024ss:algo1:02-uebung-print.pdf | ohne Klicks}}
   - Hashing und Graphen: {{ :teaching:2024ss:algo1:03-uebung.pdf |mit Klicks}}, {{ :teaching:2024ss:algo1:03-uebung-print.pdf |ohne Klicks}}
   - Kürzeste Wege: {{ :teaching:2024ss:algo1:04-uebung.pdf |mit Klicks}}, {{ :teaching:2024ss:algo1:04-uebung-print.pdf |ohne Klicks}}
   - Sortierte Folgen: {{ :teaching:2024ss:algo1:05-uebung.pdf |mit Klicks}}, {{ :teaching:2024ss:algo1:05-uebung-print.pdf |ohne Klicks}}
   - Starker Zusammenhang mit DFS, strukturelle Induktion: {{ :teaching:2024ss:algo1:06-uebung.pdf |mit Klicks}} {{ :teaching:2024ss:algo1:06-uebung-print.pdf |ohne Klicks}}
   - Dynamische Programme und Amortisierte Analyse: {{ :teaching:2024ss:algo1:07-uebung.pdf |mit Klicks}} {{ :teaching:2024ss:algo1:07-uebung-print.pdf |ohne Klicks}}




===== Übungsblätter =====
 Die Übungsblätter werden mittwochs ab 15:30 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.
Bitte beachtet die Hinweise auf den Übungsblättern!

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:2024ss:algo1:blatt_01.pdf |Übungsblatt 01}} {{ :teaching:2024ss:algo1:blatt_01_loesung.pdf | Lösung}} 
  * {{ :teaching:2024ss:algo1:blatt_02.pdf |Übungsblatt 02}} {{ :teaching:2024ss:algo1:blatt_02_loesung.pdf | Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_03.pdf |Übungsblatt 03}} {{ :teaching:2024ss:algo1:blatt_03_loesung.pdf | Lösung}}
  * {{:teaching:2024ss:algo1:blatt_04.pdf |Übungsblatt 04}} (Update am 10.05. um 15:38: Klarstellung zur Bedeutung von k bei Aufgabe 3, 16.05: Aufgabe 2a), Hinweis merge aus VL nicht verwenden) {{ :teaching:2024ss:algo1:blatt_04_loesung.pdf | Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_05.pdf |Übungsblatt 05}} {{ :teaching:2024ss:algo1:blatt_05_loesung.pdf | Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_06.pdf |Übungsblatt 06}} {{ :teaching:2024ss:algo1:blatt_06_loesung.pdf | Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_07.pdf |Übungsblatt 07}} {{ :teaching:2024ss:algo1:blatt_07_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_08.pdf |Übungsblatt 08}} {{ :teaching:2024ss:algo1:blatt_08_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_09.pdf |Übungsblatt 09}} (Update 25.06: Unterschrift der Grafik angepasst) {{ :teaching:2024ss:algo1:blatt_09_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_10.pdf |Übungsblatt 10}} (Update 28.06: Aufgabe 3 wurde durch eine neue Aufgabe 4 ersetzt. Update 03.07.: Typo in neuer Aufgabe 4, grüne Zusammenhangskomponente statt brückenloser Zusammenhangskomponente) {{ :teaching:2024ss:algo1:blatt_10_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_11.pdf |Übungsblatt 11}} {{ :teaching:2024ss:algo1:blatt_11_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_12.pdf |Übungsblatt 12}} {{ :teaching:2024ss:algo1:blatt_12_loesung.pdf |Lösung}}
  * {{ :teaching:2024ss:algo1:blatt_13.pdf |Übungsblatt 13}} {{ :teaching:2024ss:algo1:blatt_13_loesung.pdf |Lösung}}

===== Pseudocode =====

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


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

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