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
03.03.2022

= Benötigte Lernzeit als Empfehlung
2 Wochen, wenn man die Hausaufgaben alle relativ problemfrei lösen konnte

= Verwendete Materialien (Bücher, Skripte etc...)
nichts erlaubt

= "Atmosphäre" der Prüfung / Verhalten der Beisitzer
Erstaunlich entspannt für eine Präsenzprüfung

= Prüfungsfragen
1. DFA war gegeben, diesen sollten wir minimieren (mittels Unterscheidertabelle)

2. Einige Fragen über das Pumping-Lemma für REG

3. Umwandeln einer Typ-3 Grammatik in eine CNF-Grammatik; Die einzelnen Schritte und die Reihenfolge dieser waren gegeben, nur die Umsetzung war selbst zu machen

4. Es waren einige Sprachen gegeben, und diese waren (ohne begründung) in die Chompsky-Hirarchie (Typ-0, 1, 2, 3) einzuordnen. 

5. Es war eine NTM gegeben. Zu dieser sollten wir 4 Fragen beantworten
a) ist diese eine DTM und warum (warum nicht)? 
b) Werden die 3 gegebenen Wörter Akzeptiert?
c) Was für eine Sprache erkennt diese?
d) Welchen Zweck erfüllt eine Spezifische Regel?

6. Diverse Aufgaben (7) zur Graphentheorie, u.a.
- von den 4 gegebenen Graphen, wer hat welche Cliquenzahl und warum?
- zwischen Welchen dieser 4 Graphen besteht ein Isomorphismus? falls es welche gibt, geben sie diese an; falls nicht, begründen sie warum es keine geben kann.

7. Es waren 2 Probleme gegeben, und dessen Komplexitätsklasse sollte eingeordnet werden in P oder in NP-hart. 
a) eins davon war QuarterHamPath; also: Ist es möglich, zu einem gegebenen Graphen einen Pfad zu finden, der ein Viertel der Knoten besucht (und dabei den anderen Regeln eines Hamiltonpfades entspricht)? Um dieses Problem zu lösen konnte man zB. HamPath darauf reduzieren, indem man 3 mal so viele Knoten hinzufügt wie in dem Originalgraphen war. Dadurch Überträgt sich die Komplexitätsklasse von HamPath auf QuarterHamPath.

8. es wurden 3 Sprachen? gegeben, und gefragt, ob diese in REC\RE, RE oder sogar ausserhalb von RE liegen. (Ganz ehrlich, keine Ahnung wie man das Problem angehen sollte.)


= Note (Optional)
2.3, mehr wäre definitiv möglich gewesen

= Fazit (Gute/schlechte Prüfung , angemessene Benotung etc...)
Sehr Zeitbeschränkt in der Prüfung, ansonsten finde ich die Prüfung sehr angemessen. Sie erwartet kein einprägen von kompolexen Algorithmen, sondern eher ein Verständnis und eine Intuition für Automaten und Grammatiken. 

= 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.

27.7.2022

=== Benötigte Lernzeit als Empfehlung ===
Hab ungefähr eine Woche 2-4 Stunden pro Tag gelernt. Im Nachhinein hätte ich vermutlich ein paar Tage früher angefangen.
Hab die Vorlesungen und Übungen immer besucht, und mich ab und zu mal mit Kommilitonen über bestimmte Fragen ausgetauscht.

=== Verwendete Materialien (Bücher, Skripte etc...) ===
Folien der Vorlesung.

=== "Atmosphäre" der Prüfung / Verhalten der Beisitzer ===
Normal für eine mündliche Prüfung. War während der Prüfung weniger gestresst als kurz davor. Prof. Kratsch war sehr freundlich.

=== Prüfungsfragen ===
(Nur ungefähr, und kann sein, dass ich was vergessen/verdrängt habe)

1. Allgemeines über das Thema
- Was sind FPT Algorithmen?
- Warum funktionieren FPT Algorithmen nicht für alle Paramter (z.B. Vertex Cover mit Parameter der den minimalen Grad beschreibt)?

2. Kernelization
- Zusammenhang zwischen Kernelization und FPT?
- Wie kann man aus FPT eine Kernelization machen?
- Was ist eine Crown Decomposition?
- Wie kann man Crown Decomposition benutzen, um Kernelization hinzubekommen?

3. Bounded Search Trees
- Wie funktioniert Branching mit Vertex Cover? Welche Lauzeit?

4. Iterative Compression
- Was ist Iterative Compression (also Foo Deletion Problem, Foo Compression, Foo Disjoint)?
- Warum gilt der Trick, dass wenn Disjoint Foo Laufzeit a^k hat, dass dann Compression Foo Laufzeit (a+1)^k hat?
- Wie funktioniert Iterative Compression für Feedback Vertex Set? Laufzeit?

5. Randomized Methods
- Wie kann man Feedback Vertex Set noch schneller hinbekommen? (Antwort: Randomized Methods)
- Wie funktioniert das?
- Wie kann man Long Path derandomisieren?

6. Tree Width
- Was ist Baumweite?
- Was ist eine Tree Decomposition?
- Wie benutzt man das, um Maximum Independent Set zu lösen?
- Was ist eine Nice Tree Decomposition?
- Was ist eine Join Node?
- Wie funktioniert die Rekurrenz von Forget Node (für Maximum Independent Set)?

=== Note ==
2.7

- Wie man von FPT zu Kernelization kommt, wusste ich nicht richtig.
- Ich hab Crown Decomposition nicht wirklich gelernt (nur das für Maximum Satisfiability, was aber nicht dran kam :P).
- Wie man derandomisiert wusste ich auch nicht wirklich, nur halt irgendwas von wegen Färbungsfamilien mit bestimmten Eigenschaften
- Beim ganzen Treewidth Kapitel hatte ich Schwierigkeiten mich auszudrücken, hätte da bei den Fragen auch mehr Zeit gebraucht, um mich da nochmal einzuarbeiten. Hab deswegen auch bei der Frage über die Rekurrenz von Forget Node das glaube ich mit Introduce Node verwechselt.
- Ansonsten, bis auf die oben genannten Punkte hatte ich zumindest das Gefühl, dass ich die Fragen gut beantworten konnte, also vom Verständnis her. Das Erklären hat dann doch nicht so gut funktioniert:
Insgesamt legt er sehr viel Wert darauf, dass man sich klar und präzise ausdrückt, also sodass "Kommilitone das verstehen könnten". Das hab ich wohl eher nicht so gut hinbekommen. Fairerweise hat Prof. Kratsch mehrfach in den Vorlesungen gesagt, dass man üben sollte, die Konzepte und Algorithmen anderen Leuten zu erklären.

=== Fazit (Gute/schlechte Prüfung, angemessene Benotung etc...) ===
Benotung finde ich größtenteils angemessen. Finde aber insgesamt, dass die Prüfung zu kurz ist, als dass man genug Zeit haben könnte, jede Frage schön, ordentlich, und präzise zu beantworten, ohne dass man das vorher zu jedem Thema auswendig gelernt hat. Kann aber auch an mir liegen, bin eher ein bisschen langsam im Denken.

= 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.,