Wow. Hat er auch nach Steiner-Distanz und Konsensus-Fehler gefragt?
Ich sollte die abstrakte Distanzfunktion nicht-rekursiv und rekursiv angeben und sagen, warum die rekursive vorteilhaft ist, bzw letztendlich sollte ich sagen, warum Wagner-Fischer funktioniert.
Dort sollte ich dann auch die Matrix für globale, semiglobale und lokale Ausrichtungssuche angeben und den Aufbau erklären und sagen, wo man das Ergebnis findet.
Danach ging es direkt zu Kapitel 6, wo allerdings auch nichts ausgelassen wurde.
Laufzeit war bei Wagner-Fischer, beim Erstellen des Sterngraphen und für das Matrixerstellen für multiple Ausrichtungen gefragt.
Meine Prüfung verlief in etwa wie die von ProNoob.
k-Differenzenproblem - Sellers, 2 Leute und Ukkonen, Diagonalenverfahren und Wu-Manber (jeweils mit Zeit und manchmal Speicherkomplexität).
Die Formeln durfte ich mir selbst basteln, aber gefordert war das zumindest bei Wu-Manber nicht. Voranging ging es darum dass er sieht, dass man die Verfahren und Probleme wirklich verstanden hat.
Wenn man bei einer Kleinigkeit ( O(d) statt O(k) oder ein index falsch) etwas unsicher ist, dann ist das nicht fatal.