====== Randomisierte Algorithmen, 2017 ======

  - Wir hatten uns am Anfang zwei Beispiele zum warm Werden angeschaut, eins davon war der Randomisierte Quicksort. Erklären, was daran randomisiert ist und wie wir den analysiert hatten
    * Allgemein erstmal Quicksort erklären (verschiedene Strategien zur Pivot-Wahl, Eingabe).
    * Laufzeit in Anzahl Schlüsselvergleiche (was ist ein Schlüssel? Index ist Position im sortierten Array) -> Worst Case n^2, aber sehr unwahrscheinlich
    * Randomisierte Quicksort: Pivot-Element wird zufällig gewählt. 
    * warum reicht es den Bereich i bis j zu betrachten?
    * Analyse mit der Indikatorvariable im Detail erklären. (Man sollte das Endergebnis und die Rechnung über die Doppelsumme mit H(n) auswendig können, 2*n*ln(n))
  - SAT-Algorithmus erklären
    * Eingabe, Anzahl Iterationen, Ausgabe (wichtig: ggf. auch falsch, Monte-Carlo-Algorithmus)
    * Analyse erklären (wichtig: Eingabe __muss__ erfüllbar sein, sonst gibt es kein //S//)
    * Wahrscheinlichkeiten erklären, für Markov-Modell Ungleichung auflösen -> höchstens schlechter
    * Markov-Modell zeichnen, Gleichungssystem aufstellen, Lösung des Gleichungssystem als EW = n^2 + i^2 (Lösen geht, da n Gleichungen für n Unbekannte, nicht abhängig, h für hitting)
    * Abschätzung des EW mit Markov-Ungleichung und Wahrscheinlichkeitsverstärkung c
  - Was ändert sich bei 3SAT im Markov-Modell/Gleichungssystem?
    * Algo tendiert zu 0, zufällige Startbelegung binomialverteilt, was bringt das?
    * Erwartungswert jetzt schlechter als 2^n
    * Was macht Schöning? Neustart nach 3n Iterationen (Rechnung war nicht wichtig)
    * Schönings Algo läuft in O(4/3^n)
  - Wo hatten wir noch Markov-Ketten? -> Cover-Time und als UG für MCMC
    * Anzahl der Schritte h_i,i = 1/pi = ...
    * Anzahl der Schritte h_i,j < 2*|E|, Abschätzung über Summe erklären (wichtig: i und j sind Nachbarn)
    * Wie haben wir dann Cover-Time abgeschätzt? -> Spannbaum und Euler-Tour 4*|V|*|E|
    * Wo haben wir das benutzt: s-t-Connectivity (wichtig: langsamer als Tiefensuche aber deutlich weniger Speicher)
    * Wie viele Iterationen macht Algorithmus? -> Cover-Time über vollständigen Graphen abschätzen, insgesamt |V|^3