## Klausuraufbau
### Klausurrelevant:

- Fragen (~9 Punkte)
- 4x Handaufgaben (4x 8-10 Punkte, $\sum$ 36 Punkte)
- Quicksort (selten: Mergesort, Heapsort)
- Dijstra oder Floyd-Warshall
- Binäre Suchbäume, B-Baum (selten: AVL)
- KMP (selten: Pi-Feld) oder Boyer-Moore (selten: Last Feld, Bad Character)
- B-Bäume, Dijkstra Floyd-Warshall, Boyer-Moore-Sunday, Quicksort, Mergesort, Heapsort
- _Vermutlich nicht in Klausur: Knuth-Morris-Pratt_

- Theorieaufgabe / Theoretische Informatik (9 Punkte + 5 Bonus-Punkte)
- Theorieaufgabe wird es eine Teilaufgabe geben, mit der man Zusatzpunkte erwirtschaften kann. Die Teilaufgabe selbst wird eine Wahlaufgabe sein; d.h. aus zweien muss man nur eine beantworten.
- Zeichnen Sie einen Automaten
- Minimieren Sie einen Automaten
- Wahlaufgabe: Induktive/Rekursive Definitionen **vs.** Mächtigkeit von Sprachen/Abzählende Kombinatorik

- ~~Code analysieren (~14 Punkte)~~

- Programmieren (15 Punkte)
- Binärer Baum, Linked List, etc.

## Wahlaufgaben
- Programmieren / Theoretische Informatik (15 Punkte)
- Erzeugende Funktion, Polynom 2. Gerades (sicher!)

- Programmieren / Algorithmus entwerfen (15 Punkte)
- Transferaufgabe, Richtung~ DEA designen, minimieren, überlegen was passen könnte
- Beispiel: Nicht-gewichteter Graph -> gewichteter Graph -> Dijkstra

| Aufgabe | Punkte |
| ------------------------ |:---------------- |
| Fragen | 10 P |
| 4x Handaufgaben | 36 P |
| Theoretische Informatik | 9 P (+5 P Bonus) |
| Programmierung | 15 P |
| Wahlaufgabe: Prog./TI | 15 P |
| Wahlaufgabe Prog./Algor. | 15 P |
| **Insgesamt:** | **100P + 5P** |

Klausurrelevant:

- Floyd-Warshall oder Dijkstra
- Quicksort (selten: Mergesort, Heapsort)
- Binäre Suchbäume, B-Baum (selten: AVL)
- Insertion Sort oder Selection Sort
- KMP (selten: Pi-Feld) oder Boyer-Moore (selten: Last Feld, Bad Character)
- Erzeugendenfunktion, ~~Master Theorem~~
- Endliche Automaten, Minimieren von Automaten, Regulärer Ausdruck -> Automat
- Induktive Definition einer Funktion
- Diskrete Kombinatorik
- Breitensuche, Tiefensuche für Graph + Baum, ~~Topologisches Sortieren~~

# Themen aus den Aufgaben
## Übungen
- Binary Search
- ArrayList
- Stack (umgekehrte polnische Notation)
- Doppelt verkettete Liste
- Deque
- AVL-Bäume, AVL-Index
- HashMap benutzt Hashtabelle, LinkedHashMap gleicht einen Nachteil von HashMap - aus (Recherchieren), TreeMap benutzt Rot-Schwarz-Baum
- ArrayList/TreeList O-Klassen
- Binary Search Tree (isValid, aus preorderList erstellen)
- Breitensuche
- Gerichtete Graphen
- Algorithmus zur Lösung von einem Problem designen
- Beziehungen als Modell in einem Graph darstellen, Bipartitheit prüfen
- Entfernungen in einem Graphen modellieren und kürzesten Weg finden
- Permutationen
- Dijkstra
- Algorithmen mit maximaler Laufzeitkomplexität entwerfen

## Hausaufgaben
- Parsen mit ArrayDeque Stack
- Hashtabelle mit Teillisten
- LinkedList
- Binary Search Tree (Implementieren, Durchlaufen, Pre-/In-/Post-Order, Level-Order)
- vollständigkeit (alle Ebenen besetzt)
- AVL-Bedingung
- Heap (Feld-Einbettung, upheap, downheap)
- Minimaler Spannbaum (Prim Algorithmus)
- Adjazenzmatrix, Adjazenzliste, Kantenliste
- Backtracking-Algorithmus
- Dijkstra
- Textsuche Regex
- NEA

## Themen für Fragen
- Prioritätswarteschlange
- Laufzeitkomplexität
- Voraussetzungen und Anwendungsfälle für Algorithmen
- Pre-/In-/Post-Order
- PCRE Regex analysiren (~~Graph~~)
- DEA / NDA
- Datenstruktur / Abstrakter Datentyp (ADT)
- B-Bäume (vollständig balanciert, Ordnung, Höhe)
- Hashing (Kollisionsbehandlung durch Teillisten, Lineares Sondieren, Quadratisches Sondieren, Doppeltes Hashing)
- AVL-Bäume (AVL-Index/-Eigenschaft)
- Sortieralgorithmen (Eigenschaften, stabil, Laufzeitkomplexität avg./best - case, Quick-Sort)
- Dynamische Programmierung, Entwurfsprinzipien
- AVL-Index berechnen (~~Rotati~~)
- Binäre Suchbäume (Knoten Löschen), Rot-Schwarz Bäume
- Kantenliste, Knotenliste, Adjazenzmatrix
- Merge Sort, Hashtabllen, Prim, Baum- Graphdurchlauf

# Handaufgaben
- Dijkstra (Tabelle, nicht Baum)
- Floyd-Warshall Kürzester Weg
- B-Bäume (vollständig balancierter Baum) (Elemente Entfernen, Einfügen, Balancieren) (Ordnung, Höhe)
- Heap-Sort (Prioritätswarteschlange) (Einfügen, Löschen, Feld-Einbettung, Einbettung mit Hashtabelle, Heap-Sort)
- Quick-Sort
- Boyer-Moore-Sunday mit Last-Tabelle
- kein zeichnen von Rot-Schwarz Bäumen, kein händisches Durchführen von Merge Sort, keine Rotation von AVL-Bäumen

# Aufgaben
lineare Rekursionsgleichung mit Hilfe von Erzeugenden Funktionen lösen

## Prof. Pflug wichitg
- Dynamische Programmierung nur wissen, welche Algorithmen das betrifft