====== Randomisierte Algorithmen, 2014 ======

  * Was ist denn ein randomisierter Algorithmus? -> Algorithmus, der mit Zufall(szahlen) arbeitet
  *  Wir hatten uns am Anfang zwei Beispiele zum warm Werden angeschaut, eins davon war der Randomisierte Quicksort. Erklären Sie mal, was daran randomisiert ist und wie wir den analysiert hatten -> Allgemein erstmal Quicksort erklären (verschiedene Strategien zur Pivot-Wahl). Randomisierte Quicksort: Pivot-Element wird zufällig gewählt. Dann die Analyse mit der Indikatorvariable im Detail erklären. (Man sollte das Endergebnis auswendig können, 2 * n * ln(n))
  * Was ist die Probabilistische Methode? -> Man möchte wissen, ob es ein Objekt mit Eigenschaft E gibt. Also würfelt man ein zufälliges Objekt A und zeigt, dass die Wahrscheinlichkeit, dass A diese Eigenschaft E besitzt < 1 ist => es gibt ein solches Objekt.
  *  Wir haben uns dazu Max-Cut und Independet Set angesehen. Was ist denn ein Independet Set? -> Definition
  *  Und was haben wir da mit der probabilistischen Methode gemacht? -> Algorithmus erklären und vorrechnen.
  *  Wie kann ich denn jetzt sicherstellen, dass ich auf jeden Fall ein richtiges Ergebnis bekomme, bisher haben wir ja nur den Erwartungswert. -> Las Vegas-Algorithmus
  *  Was ist ein Monte Carlo-Algorithmus? -> Stichprobe auf Universum übertragen, Uniformer Generator, Beantworter, Zähl-Probleme
  *  Was besagt denn das Estimator Theorem? -> Erklären und ihm war sehr wichtig, dass T von der Expansion abhängt.
  *  Wie hatten wir denn beim #DNF-Problem das clevere Universum gewählt? -> Algorithmus samt Wahrscheinlichkeiten erklären
  *  Und dann hatten wir ja noch das #COL_k -Problem... -> Den kompletten Algorithmus erklären und zeigen, was davon Monte-Carlo ist und was Markov. Wichtig: Markov arbeitet hier als UG, weil der Färbungsgraph, den Markov erstellt, regulär ist!