==== Seminar "Hallo Welt fuer Fortgeschrittene" ====

Prüfer: Tobias Werth, Daniel Brinkers

Haupthema war Suchen&Sortieren 1, Nebenthemen Graphen1 und FSB1

===  Suchen & Sortieren 1: ===
  - 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?

===  Graphalgorithmen 1: ===
  - 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?

=== Fluesse, Schnitte und bipartite Graphen: ===

  - 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?