\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{bis zum 02. November 2016, 12 Uhr, in den
Briefkasten neben Raum 111}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\eps}{\varepsilon}
\newcommand{\E}{\mathbf{E}}
\renewcommand{\Pr}{\mathbf{Pr}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Randomisierte Algorithmen}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Paul Seiferth, Max Willert

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Details zur Implementierung des engste Paares}{10 Punkte}

\begin{enumerate}
\item
Gegeben sei ein Feld \texttt{A} mit $n$ paarweise verschiedenen
Elementen. Beschreiben Sie einen Algorithmus, der 
eine zuf\"allig gleichverteilte Permutation von \texttt{A} liefert.
Jede Permutation soll mit Wahrscheinlichkeit $1/n!$ gew\"ahlt werden.

Ihr Algorithmus soll die Funktion \texttt{random(n)} benutzen,
welche eine zuf\"allig gleichverteilte Zahl aus der Menge
$\{1, \dots, n\}$ liefert.
Die Laufzeit soll $O(n)$ betragen.
\item
Ein Gitterw\"orterbuch ist ein abstrakter Datentyp, der
zwei Operationen unterst\"utzt: (i) \texttt{insert(i, p)} f\"ugt
den Punkt $p \in \R^2$ in das $i$-te Standardgitter ein und (ii)
\texttt{lookup(i, (a,b))} liefert die Menge aller Punkte, die
in der Zelle $(a,b)$ des $i$-ten Standardgitters gespeichert sind.
Dabei werden die Punktmengen in den verschiedenen Standardgittern
unabh\"angig voneinander verwaltet.

Beschreiben Sie eine Implementierung des Gitterw\"orterbuchs,
die $O(\log n)$ Zeit pro Operation ben\"otigt.
\end{enumerate}

\AUFGABE{Ein alternativer Algorithmus f\"ur das engste Paar}{15 Punkte}

Sei $P$ eine Menge von $n$ Punkten in der Ebene, so
dass alle $\binom{n}{2}$ Abst\"ande paarweise verschieden sind
und so dass alle Koordinaten positiv sind.
Sei $k = \lfloor \log n \rfloor - 1$.
Wir berechnen zuf\"allig Punktmengen 
$P = P_0 \supset P_1 \supset P_2 \supset \dots \supset P_k$,
indem wir f\"ur $i = 1, \dots, k$ die Menge  $P_i$ als 
zuf\"allige Teilmenge von $P_{i-1}$ mit genau 
$\lfloor n/2^i \rfloor$ Elementen w\"ahlen.

Der Algorithums legt f\"ur $i = k, \dots, 0$ ein
Gitterw\"orterbuch $G_i$ f\"ur $P_i$ an, so dass jede Zelle
in $G_i$ h\"ochstens einen Punkt enth\"alt und
so dass die Zellen f\"ur das engste Paar Abstand $O(1)$
besitzen. Der Algorithmus geht in Runden vor. Die Runden sind nummeriert
von $k$ bis $1$. In Runde
$i$ wird das Gitterw\"orterbuch $G_{i-1}$ berechnet,
unter der Annahme, dass das Gitterw\"orterbuch  $G_i$
verf\"ugbar ist. Das geht so:
(i) f\"uge alle Punkte aus $P_{i-1}$ in $G_i$ ein;
(ii) bestimme mit einem brute-force Verfahren f\"ur die Punkte in jeder 
Gitterzelle eine optimale neue Gitterbreite;  (iii) berechne daraus
die Gitterbreite f\"ur $G_{i-1}$; und (iv) f\"uge alle Punkte
aus $P_{i-1}$ in $G_{i-1}$ ein.

\begin{enumerate}
  \item Beschreiben Sie den Algorithmus in allen Details.
    Gehen Sie insbesondere darauf ein, wie man am Schluss das
    engste Paar findet.
    Die Anzahl der Operationen auf dem Gitterw\"orterbuch soll
    $O(n)$ im worst-case betragen. Die Zeit pro Gitterzelle kann
    quadratisch in der Anzahl der enthaltenen Punkte sein.
  \item Sei $Z_i$ die Anzahl der Schritte, die der Algorithmus
    in Runde $i$ ben\"otigt. Zeigen Sie: Falls 
    $\E[Z_i] = O(|P_{i-1}|)$ ist, dann ben\"otigt
    der Algorithmus im Erwartungswert $O(n)$ Operationen.
  \item Sei $Q \subseteq P$ mit $|Q| = \lfloor n/2^{i-1} \rfloor$
    fixiert. 
    Zeigen Sie: 
    \[ 
      \E[Z_i \mid P_{i-1} = Q] \leq \sum_{p \in Q} \E[X_p \mid P_{i-1} = Q],
    \]
    wobei $X_p$ die Anzahl der Punkte aus $P_{i-1}$ ist,
    die in der Zelle von $G_{i}$ liegen, die $p$ enth\"alt.
  \item Zeigen Sie $\E[X_p \mid P_{i-1} = Q] = O(1)$.
    
    \emph{Hinweis}: Sch\"atzen Sie zun\"achst die
      Wahrscheinlichkeit $\Pr[X_p \geq r \mid P_{i-1} = Q]$ ab. 
      Wenn $X_p \geq r$ ist, dann muss die Zelle
      in $G_i$, welche $p$ enth\"alt, mindestens $r$ Punkte aus 
      $P_{i-1}$ enthalten. Verstehen sie genau, wie
      das passieren kann, und sch\"atzen Sie die Wahrscheinlichkeit
      f\"ur dieses Ereignis ab.
  \item Folgern Sie $\E[Z_i] = O(|P_{i-1}|)$ und schlie\ss{}en
    Sie die Laufzeitanalyse ab.
\end{enumerate}

\AUFGABE{MinCuts}{5 Punkte}

\begin{enumerate}
\item Benutzen Sie die Analyse des Algorithmus 
  \textsc{MinCut1}, um zu zeigen, dass ein Graph
  mit $n$ Knoten h\"ochstens $\binom{n}{2}$ minimale
  Schnitte besitzt.
\item Geben sie f\"ur jedes $n \geq 3$ einen Graphen
  an, der $\binom{n}{2}$ minimale Schnitte besitzt.
\end{enumerate}
\end{description}

\end{document}
