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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 12.\@ Mai 2015 vor der Vorlesung in die
Mitarbeiterschachteln}

\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{\half}[1]{\frac{#1}{2}}
\newcommand{\eps}{\varepsilon}


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


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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik II}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Lena Schlipf, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{KKT-Algorithmus}{10 Punkte}

In dieser Aufgabe sollen Sie einen alternativen Beweis f\"ur das
KKT-Sampling Lemma kennen lernen. F\"ur diese Variante bestimmen
wir das Kantensample $R$ mit Hilfe von Bernoulli-Sampling:
Wir f\"ugen jede Kante $e$ von $G_1$ mit Wahrscheinlichkeit $1/2$
zu $R$ hinzu.

\begin{enumerate}
 \item Begr\"unden Sie, dass der folgende Algorithmus die gleiche Verteilung
     auf den Kantenmengen $F_2$ liefert wie der Algorithmus, der erst
     $R$ w\"ahlt und dann $\text{MSF}(V_1, R)$ bestimmt.
     Setze $A = \emptyset$. 
     Sortiere die Kanten in $E_1$ nach Gewicht. F\"ur jede Kante $e$, von der 
     leichtesten zur schwersten, tue folgendes: wirf eine faire M\"unze.
     Wenn Zahl, tue nichts.  Wenn Kopf, f\"uge $e$  genau dann in $A$ ein,
     wenn dadurch kein Kreis in $(V_1, A)$ entsteht.
     Setze am Ende $F_2 = A$.
  \item Sei $e_i$ die $i$-te Kante in der sortierten Reihenfolge.
    Begr\"unden Sie, dass nach dem $(i-1)$-ten M\"unzwurf fest steht, ob $e_i$ $F_2$-leicht 
    ist oder nicht. 
  \item Unterteilen Sie das Zufallsexperiment aus (a) in \emph{Phasen}, wobei die $k$-te
    Phase beginnt,  sobald die $k$-te Kante in $A$ eingef\"ugt wird. Sei
    $X_k$ die Anzahl der $F_2$-leichten Kanten, die in der $k$-ten Phase entstehen.
    Berechnen Sie eine obere Schranke f\"ur den Erwartungswert von $X_k$.
  \item Zeigen Sie, dass die erwartete Anzahl der $F_2$-leichten Kanten h\"ochstens
    $2|V_1|$ ist. 
\end{enumerate}

\AUFGABE{Kuckucks-Hashing} {10 Punkte}

Beweisen Sie den Satz aus der Vorlesung, dass sich eine
Menge $S \subset U$ bez\"uglich zweier Hashfunktionen
$h_1, h_2: S \rightarrow \{0, \dots, m-1\}$ genau dann
erfolgreich einf\"ugen l\"asst, falls der entsprechende
Kuckucksgraph $G_{h_1, h_2}(S)$ g\"ultig ist.

\AUFGABE{Kodierungsargument}{10 Punkte}

Angenommen, wir haben eine Hashtabelle mit $n$ Pl\"atzen, die
eine Menge $S \subset U$ der Gr\"o\ss{}e $n$ speichert. Konflikte
werden mit Hilfe von Verkettung gel\"ost. Wir nehmen an, dass
die Hashfunktion zuf\"allige aus der Menge der Funktionen
$h : S \rightarrow \{0, \dots, n-1\}$ gew\"ahlt wird.

F\"ur einen Platz $i$ in der Hashtabelle, bezeichne mit $Q_i$
die \emph{Anzahl} der Schl\"ussel, die auf $i$ gehasht werden.
Zeigen Sie mit Hilfe eines Kodierungsarguments, dass
$\textbf{E}\bigl[\max_{i=0}^{n-1} Q_i\bigr] = O(\log n/\log\log n)$ ist.

\emph{Hinweis}:
  Es ist $\binom{n}{k} \leq (ne/k)^k$.
  Zeigen Sie, dass man bei einer Hashfunktion,
  die $k$ Elemente auf denselben Platz abbildet, $k \log (k/e) - \log n$
  Bits sparen kann.


\end{description}
\end{document}
