Datum: 2021

Prüfungsform: Mündliche Prüfung (online)

Benötigte Lernzeit als Empfehlung: 
Unbedingt alle Vorlesung besuchen. Für die Prüfung selbst mindestens zwei Wochen lernen. Um Sachen zu verstehen, kann man auf andere Quellen zugreifen (z.B. Wikipedia). Aber wenn es um Definitionen/detaillierte Erklärungen geht, dann will der Prüfer nur seine eigenen hören.

"Atmosphäre" der Prüfung / Verhalten der Beisitzer:
Prof. Kratsch war sehr unfreundlich (von Anfang bis Ende), hat manchmal gehetzt bzw. unterbrochen und wenn man was nicht wusste, wurde kaum nachgeholfen.
Beisitzer dagegen schien nett.

Prüfungsfragen:
(Achtung: Nicht alle Fragen wurden direkt so gestellt. Bei vielen Fragen wurde noch zusätzlich nach Details gefragt und man sollte es ggf. an einem Beispiel aus der Vorlesung erklären. Wenn unten in den Fragen etwas steht wie "Was ist ein.." oder "Erklären", dann nehmt das bitte nicht auf die leichte Schulter! Manchmal wollte er 1:1 Definitionen hören genau wie sie in seinen Vorlesungsfolien stehen.)

1)
-Was ist ein Fibonacci-Heap?
-Etwas zu den Knoten, Kanten, Höhe/n sagen
-Sehr genaue Details zu Operationen nennen: Extract-Min, Decrease Key, Union
-Laufzeit von diesen Operationen nennen (amortisiert und nicht-amortisiert) -> wieso ist Decrease Key amortisiert O(1)? -> Was steckt hinter der Potentialmethode? Welche Potentialfunktion verwenden wir für Fibonacci-Heaps und wieso?
-Noch mehr zu Operationen / amortisierter Laufzeit: Wie wird markiert / unmarkiert.. wozu?
-Was ist der Unterschied zwischen normaler Laufzeitanalyse und amortisierter Analyse?

2)
-Was ist ein Binomial-Baum?
-Was ist ein Binomial-Heap?
-Details zu Knoten, Kinder, Kanten, Höhe von Binomial-Bäumen
-Kurz was zu Laufzeiten von Operationen sagen

3)
-Was ist ein Flussnetzwerk?
-Was ist ein Fluss?
-Was ist der Wert eines Flusses?
-Was ist ein Schnitt?
-Wie bestimmt man die kleinste Kapazität eines Schnitts?
-Wie bestimmt man einen maximalen Fluss (er lenkt auf den Ford-Fulkerson-Algorithmus)
-Ford-Fulkerson-Algorithmus erklären -> Dynamisch oder Greedy? -> Wieso terminiert der Algorithus bzw. terminiert er überhaupt?
-Was ist das Max-Flow-Min-Cut-Theorem?

4)
-Was ist dynamische Programmierung?
-Was ist ein Teilproblem, was ist eine Teillösung?
-Wie baut man ein dynamisches Programm?
-Wie beweist man optimale Teilstruktur-Eigenschaft?
-Anwendung/Erklärung all dieser Aspekte auf ein von ihm gegebenes Beispiel

5)
-Was ist ein Matroid?
-Zusammenhang Greedy & Matroid


Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...):
Sehr schlechte Prüfung mit einem äußerst paranoiden und unfreundlichen Professor, der die ganze Zeit mieß gelaunt in die Kamera schaut und in einem auffällig unhöflichen bzw. genervten Ton mit einem spricht. Man fühlt sich überhaupt nicht willkommen in der Prüfung - das war extrem unangenehm und ich wünsche das keiner Person weiter. Vielleicht ist das aber auch nur ein tragischer Einzelfall - wer weiß.......!

= Datum der Prüfung
August 2021, mündliche Onlineprüfung

= Benötigte Lernzeit als Empfehlung
2 Wochen intensive Lernzeit. Vorlesungen und Übungen regelmäßig besuchen.
Prof. Kratsch hat in den Vorlesungen sehr deutlich gemacht was in der Prüfung verlangt wird und was nicht. Es gab keine bösen Überraschungen oder unfaire Fragen, sondern genau das was er hat durchblicken lassen. 

= Verwendete Materialien (Bücher, Skripte etc...)
Überwiegend Vorlesungsfolien, aber teilweise auch die empfohlene und zur Verfügung gestellte Literatur. Außerdem Notizen aus den Übungen (viele hilfreiche Bilder und Beispiele, die helfen alles besser zu verinnerlichen und beschreiben zu können)

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sowohl Prof. Kratsch als auch der Beisitzer waren sehr lieb und geduldig und haben eine sehr angenehme Atmosphäre geschaffen. Das andere Prüfungsprotokoll vom August 2021 kann ich überhaupt nicht nachvollziehen. Alle mit denen ich mich über diese Prüfung ausgetauscht habe, waren sehr zufrieden und fanden Prof. Kratsch gut gelaunt, hilreich und sehr sehr nett! Wenn ich hing oder zu nervös wurde, dann hat mir Prof. Kratsch auf die Sprünge geholfen und seine Frage auch immer noch einmal anders formuliert. 

= Prüfungsfragen
Es gab insgesamt 10 große Themen. Zu wie vielen davon man gefragt wird, hängt wohl davon ab wie gut und schnell man Fragen beantwortet. Ich habe von manchen gehört, dass sie zu allen gefragt wurden. Ich hing etwas öfter mal und wurde zu insgesamt 7 Themen befragt. Es sind alle Themen prüfungsrelevant. Wenn Unterthemen nicht abgefragt werden, dann hat Prof. Kratsch das in der Vorlesung gesagt.
Man muss frei zu Themen sprechen können, Definitionen geben und Beweise führen können (vor allem für sehr gute Noten geht es nicht ohne Beweise). 
Meine Fragen waren(es gab immer noch kleinere Folgefragen, die ich aber nicht mehr so genau weiß):

-Definition von Maximum Matching
-Hopcroft Karp Algorithmus erklären, Laufzeit angeben, erklären wieso Wurzel n bei den Phasen
-Definition augmentierender Pfad

-Definition binomialer Heap, etwas ausführlichere Beschreibung was das soll und kann  

-Definition Fibonacci heap und Amortisierte Analyse
-Potentialmethode bei Fibonacci
-Decreasekey erklären
 
-Maximaler Fluss, Flussnetzwerk und Fluss erklären
-Definition Residualnetzwerk
-Ford Fulkerson Algorithmus erklären, Beweis
-Defintion Schnitt
-Max Flow Min Cut Theorem erklären, Beweis

-Dynamische Programmierung
-Beispiel aus der Vorlesung war gefragt und optimale Teilstruktur Eigenschaft sollte daran erklärt werden
-erklären wie die rekursive Formulierung bewiesen wird

-Greedy Algorithmen erklären
-Wie beweist man, dass es greedy möglich ist
-Definition Matroide und wie hängt das mit Greedy zusammen

= Note (Optional)
Lief gut
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Die Benotung war sehr sehr fair, eher etwas freundlicher bewertet würde ich sagen. Man muss nicht alles beantworten können, um zu bestehen und das hat Prof. Kratsch auch zu beginn der Prüfung klar gesagt. Man wird mehr gefragt, damit man genug Möglichkeiten hat Punkte zu holen und manche Fragen sind einfach dafür da vielleicht die Note noch etwas zu verbessern.
Insgesamt kann ich mir keine freundlichere Prüfung vorstellen. Sowohl Prof. Kratsch als auch der Beisitzer haben von Anfang bis Ende sichergestellt, dass ich mich wohl fühle, alles verstehe (oder wenn ich was gar nicht wusste eben ein neues Thema gewählt) und dass die Benotung nachvollziehbar ist. Man merkt, dass Prof. Kratsch etwas daran liegt, dass man die Prüfung gut schafft und er möchte die Studierenden sicher nicht scheitern sehen und baut somit auch nichts unfaires oder überraschendes in die Prüfung ein. 
Es ist sehr viel Stoff und es ist ein anspruchsvolles Modul, aber wer in der Vorlesung nicht nur schläft und auch mal an den Übungen teilnimmt und lernt, kann das absolut schaffen. 

Mündliche Prüfung, Online über zoom, Oktober 2021 ​

Herr Prof. Kratsch war während der Prüfung sehr nett und hat mir auf jeden Fall weitergeholfen, wenn ich nicht weiter wusste. Die Bewertung ("nicht bestanden") kann ich leider überhaupt nicht nachvollziehen, weil ich definitiv zumindest die Hälfte der Fragen richtig beantwortet habe. Aber da meine Meinung sowieso nichts wert ist hinsichtlich der Bewertung und ich in diesem Moment geschockt und enttäuscht war (und es immer noch bin), habe ich auch nichts dazu gesagt. Alles in allem ist das ein sehr umfangreiches Modul und es wird zu streng bewertet (meine Meinung).

### Matrixkettenmultiplikation ###
-> Wieso hat das die optimale Teilstruktur Eigenschaft?
-> Beweise (nur grob), dass diese Eigenschaft gilt

### Fibonacci-Heap ###
-> Was hat es mit den Operationen auf sich, die nur O(1) kosten?
-> Was ist amortisierte Analyse, wozu macht man das?
-> Kurz den Unterschied erläutern zwischen amortisierter Analyse und Laufzeitanalyse
-> Potentialmethode des Fibonacci-Heaps erklären
-> DecreaseKey warum hat das die Laufzeit O(1)? , amortisierte Analyse dazu machen

### Maximaler Fluss ###
-> Definition Fluss
-> Was ist der Wert eines Flusses?
-> Definition Flussnetzwerk
-> Wie haben wir (intuitiv) einen maximalen Fluss in einem Flussnetzwerk bestimmt?
-> Ford-Fulkerson, Algorithmus erklären
-> Was ist ein Residualnetzwerk, wozu braucht man das genau?
-> Schnitt, was ist das?
-> Max Flow Min Cut Theorem erklären, inklusive Beweisidee

### Maximum Matching ###
-> Definition Matching
-> Unterschied "Maximum" , "Maximal"
-> Definition augmentierender Pfad
-> Und was ist ein alternierender Pfad?
-> Wozu augmentierende Pfade, wie kann man mithilfe von diesen Pfaden ein Maximum Matching finden (-> Satz von Berge, Beweisidee)
-> Was tut der Hopcroft-Karp-Algorithmus? Wie funktioniert er?
-> SAP-Packing, was ist das? Wozu?

Das zu schreiben hat sehr weh getan. Aber ich hoffe es hilft euch weiter, machts gut.

= Datum der Prüfung: 25.07.2022
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Herr Kratsch war sehr entspannt, hat immer versucht die Stimmung aufzulockern und wenn man sich unsicher was gefragt war hat er immer geholfen.
= Prüfungsfragen
###Matching
-Definition Matching
-Unterschied Maximal & Maximum
-Was sind augmentierende Pfade
-Funktionsweise Hopcroft-Karp
-Beweis warum Pfadlängen bei SAP-Packings strikt steigen
-Beweis warum  O(√n) Phasen
-Wie findet man SAP-Packings in bipartiten Graphen(ohne Beweis)

###Fibonacci-Heaps
-Amortisierte Analyse decrease Key
-Kosten andere Operationen
-Amortisierte Analyse extractmin
-zwischendruch immer ein bisschen allgemein zu Amortisierter Analyse, wie z.b unterschied zur normalen Analyse, warum es eine obere Schranke für eine Folge an Operationen ist usw.

= Note (Optional)
1,0
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr gute Prüfung, aber deutlich mehr Beweise als ich dachte (und vor allem sehr ausführlich!). Dafür sehr wenige Themen (nur 2)

= Datum der Prüfung
SoSe 2022
= Benötigte Lernzeit als Empfehlung
3 Tage
= Verwendete Materialien (Bücher, Skripte etc...)
Skript + Wikipedia
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Sehr freundliche Prüfer. Leider über Zoom.
= Prüfungsfragen
Es wurden direkt Fragen gestellt und keine Themenübersicht vom Studenten verlangt.

Kürzeste Wege:
-Eigenschaften kürzester Pfade und der Relaxation nennen und Intuition geben
-Bellman-Ford-Algorithmus: Algorithmus, Laufzeit und Intuition warum dieser funktioniert
-Johnson’s Algorithmus: Algorithmus, Laufzeit und Intuition warum dieser funktioniert

Matching
-Definition vom Matching
-Kernidee hinter Matching-Algorithmen nennen (augmentierende Pfade)
[Ich habe hier selbst die Überleitung zu den Hopcroft-Karp-Algorithmus gemacht]
-Hopcroft-Karp-Algorithmus: Algorithmus, Laufzeit (warum sqrt(n)) und warum werden die SAPs im Packing mit jeder Iteration länger

Binomial-Heap
-Definition Binomial-Heap und wofür brauch man ihn (Union in O(logn))
-Alle Operationen und Laufzeiten nennen
-Union und DecreaseKey: Funktionsweise und Laufzeit erklären

Fibonacci-Heap
-Definition Fibonacci-Heap und Motivation
-Alle Operationen und (amortisierte) Laufzeiten nennen
-Was sind amortisierte Kosten bzw. wofür sind sie gut
-Potenzialfunktion nennen und oberflächlich motivieren
-Warum liefert die Potentialmethode korrekte amortisierte Kosten (Teleskopsumme)
-ExtractMin und DecreaseKey: Funktionsweise genau erläutern, Worstcase-Kosten ermitteln und zeigen inwiefern die Potentialfunktion diese amortisiert
= Note (Optional)
bestanden
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Gute Prüfung, am Anfang haben wir kurz aneinander vorbeigeredet. Danach lief alles relativ glatt. Wenn man mal eine Frage nicht beantworten kann ist das auch kein Problem. Gute Prüfung mit einer fairen Bewertung.

= Datum der Prüfung
SoSe 2022
= Benötigte Lernzeit als Empfehlung
2 Wochen
= Verwendete Materialien (Bücher, Skripte etc...)
Alle Folien durchlesen, Definition merken (mathematische Sauberkeit findet der Prof gut), Beweise verstehen und erklären können.
Buch lesen hilft, ist aber nicht nötig.
= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
War entspannt und über Zoom. Es wurden nur verbal Fragen gestellt.  
= Prüfungsfragen

## Binomial Heaps
- Was ist ein Binomial Heap?, Was ist ein Binomial Baum?, Was sind Eigenschaften des Binomial Baums (Höhenschranke, Kinderknoten,...)? (Wie beweist man diese?)
- Wie ist extract_min für den Binomial Heap implementiert?
- Warum ist die Worstcase-Laufzeit O(log n) (von extract_min)?
- Wie ist decrease_key implementiert? Laufzeit?

## Fib Heap
- knüfte an vorheriges an...
- Was sind die Kernideen beim "schnelleren" Fib-Heap?
- Unbeschränkte Wurzellänge wichtig, Funktionsweise von decrease_key 
- Übergang zur Potentialmethode: Wie funktioniert decrease_key genau (bezug auf Markierungen), Was ist die Worstcase-Laufzeit? Wieso ist die amortisierte Laufzeit O(1)?
- Was heisst amortisierte Laufzeit? Wieso liefert die Potentialmethode korrekte amortisierte Laufzeiten (Teleskopsumme)?
- Wie ist exract-min für Fib-Heap implementiert? Worstcase-Laufzeit? Amortisierte Laufzeit mit Potential erklären.
- Gradschranke für Fib-Heap beweisen (die Induktion erklären)! (Wenn ich es nicht gekonnt hätte wären wir wahrscheinlich zu einem anderem Thema weiter gegangen.)


## Max Flow
- Definition Flussnetzwerk? Definition Fluss? Definition Wert eines Flusses?
- Wie kann man den Fluss maximalen Wertes bestimmen?
- Ford-Fulkerson: Wie funktioniert der Algorithmus?
- Definition Residualnetzwerk
- Wann hält der Algorithmus garantiert (Ganzzahligkeit)
- Warum hält der Ford-Fulkerson? (Iterationen <= Max Flow)
- Beweisen das der Algo. den korrekten Max Flow berechnet (falls er hält).
- Dabei sollte man den Max-Flow-Min-Cut-Satz gleich mitbeweisen!

Insgesamt reichen (anscheinend) zwei saubere Beweise für eine gute Note!

= Note (Optional)
Sehr gut.
= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Der Professor versucht eher die Tiefe des Wissens einzuschätzen; viele hier wurden zu sehr vielen Themen befragt, weil sie (wahrscheinlich) keine Beweise o.Ä. angeben konnten bzw. nicht erklären konnten. Mathematisch sauber die Struktur von Beweisen erklären und sich auf die Lemmas in der VL zu beziehen ist nötig für die 1.0 (also jetzt grösser mit grössergleich vertauschen oder so oder eine konstante vertauschen ist egal). Viel Glück.,