Prüfer: Tobias Werth, Daniel Brinkers

Haupthema war Suchen&Sortieren 1, Nebenthemen Graphen1 und FSB1

1. Was hat dir am besten Gefallen? (Habe RMQ/LCA geantwortet, es wurden dann nur noch Fragen dazu gefragt)
2. Was ist das RMQ-Problem?
3. Was ist die triviale Loesung? Welche Laufzeit besitzt sie? (n^3 Aufbau)
4. Wie kann man dieses triviale DP beim Aufbau noch verbessern? Welche Laufzeit ergibt sich?
5. Wie funktioniert der Sparse-Table-Ansatz? Welche Laufzeit besitzt er?
6. Warum funktioniert das?
7. Was ist das LCA-Problem?
8. Was ist die triviale Loesung?
9. Was hat das mit RMQ zu tun?
10. Wie ist der Reduktionsansatz von LCA zu RMQ?
11. Warum funktioniert er?

1. Was sind implizite Graphen und was unterscheidet sie von expliziten?
2. Was bedeutet das fuer die Programmierung von z.B. Dijkstra?
3. Was sind Zusammenhangskomponenten?
4. Wie findet man Zusammenhangskomponenten? Warum funktioniert der Algorithmus?
5. Was sind Bruecken?
6. Wie findet man Bruecken?
7. Warum funktioniert der Algorithmus?
8. Warum ist der Startpunkt ein Spezialfall?
9. Wie funktioniert der Algorithmus von Kosaraju und warum?

1. Was benoetigt man zum Finden eines Flusses?
2. Wodurch genau ist die Flusskapazitaet begrenzt?
3. Wie funktioniert das Finden der Fluesse theoretisch und algorithmisch?
4. Was ist die Laufzeit fuer das Finden eines Flusses mittels Tiefensuche?
5. Zeichne einen Graphen, der diesen Worst-Case erreichen kann
6. Wie kann man die Laufzeit verbessern, welche Laufzeit erreicht man dadurch?
7. Was sind Reduktionen und wo wendet man sie an?
8. Was sind Matchings und wie kann man ein maximales Matching finden?