Prüfer: Tobias Werth, Daniel Brinkers

Haupthema war Suchen&Sortieren 1, Nebenthemen Graphen1 und FSB1

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

• Was sind implizite Graphen und was unterscheidet sie von expliziten?
• Was bedeutet das fuer die Programmierung von z.B. Dijkstra?
• Was sind Zusammenhangskomponenten?
• Wie findet man Zusammenhangskomponenten? Warum funktioniert der Algorithmus?
• Was sind Bruecken?
• Wie findet man Bruecken?
• Warum funktioniert der Algorithmus?
• Warum ist der Startpunkt ein Spezialfall?
• Wie funktioniert der Algorithmus von Kosaraju und warum?

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