So, auch grad Prüfung gehabt.
Exponentielle Laufzeit: Kurze augmenting paths wählen, oder? *kopfkratz
Genau, entweder einen kürzesten (Edmonds-Karp) oder mehrere kürzeste bzw. einen "blockierenden Fluss" (Dinic). Ansonsten stand in den Folien noch, dass man immer nur einen Pfad mit einer bestimmten sinnvollen Mindestkapazität wählen könnte, ohne spezifisch zu sagen, was das Minimum sein sollte. Tiefer gehende Details oder Beispiele musste ich aber nicht wissen.
Pseudocode musste ich zum Glück gar nicht aufschreiben, da es Arne gereicht hat, dass ich die Arbeitsweise der Algorithmen erklären konnte. Prinzipiell ging es am Anfang einmal durch alle Graphenalgorithmen: BFS, DJP, BF, FW, FF: was machen die, wieso braucht man sie, welche Laufzeit haben sie und wie kommt die zustande? Ein Beispiel sollte ich für ein anderes Problem konstruieren: wieso kann man bei negativen Gewichten nicht einfach auf alle Kanten eine Konstante addieren und dann DJP anwenden? Zur Färbbarkeit kam nur die Frage nach dem Satz von Kuratowski und Wagner und was ein Minor ist.
Parallele Algorithmen kamen bei mir etwas kurz, vermutlich weil ich vorher etwas getrödelt habe. Da kamen hauptsächlich grundlegende Fragen: Was ist eine PRAM, was unterscheidet die Typen, wie regelt man Schreibzugriffe bei CRCW-PRAMS? Was sind Kosten und wann ist etwas optimal? An Algorithmen kamen nur die binären Bäume am Beispiel der Summierung von n Zahlen, die Laufzeit und Optimalität, und wie man es besser machen könnte, und wieso es dann optimal ist. Dann noch die Laufzeit und Optimalität von compCC, und dann war die Prüfung auch schon vorbei.
Das was nano zur Bewertung gesagt hat kann ich im Prinzip bestätigen. Ich hatte am Anfang auch das Gefühl, ziemlich versagt zu haben, weil ich die Laufzeiten des BFS-Algorithmus für verschiedene Datenstrukturen erst hingekriegt habe, nachdem Arne mich gebeten hat, den Algorithmus nochmal zu erklären. Auch bei anderen Laufzeiten hab ich sehr stockend geantwortet, das Beispiel zu konstruieren hat ziemlich lange gedauert und beim Beheben der exponentiellen Laufzeit hab ich zu Anfang mit Mindestkapazität und -fluss verhaspelt. Aber offenbar gab es dafür am Ende keine Abzüge.