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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{29. May 2017, in class}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\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{\R}{\mathbb{R}}



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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem Set for 

\smallskip
\noindent
\large
\textbf{Advanced Algorithms II}\hfill Spring 2017 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost 

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{KKT-Algorithm}{10 Points}

In this problem, we will see an alternative proof
of the KKT-sampling lemma. We consider the variant
of the algorithm where the sample $R \subseteq E$
is obtained through \emph{Bernoulli-sampling}:
each edge $e \in E_1$ is added to $R$ independently
with probability $1/2$.

\begin{enumerate}
 \item 
   Argue that the following algorithm gives the same distribution
   on edge sets $F_2$ as the algorithm that first chooses
   $R$ and then computes $\text{MSF}(V_1, R)$. 

     Set $A = \emptyset$. 
     Sort the edges in $E_1$ according to their weight.
     For each edge $e \in E_1$, from lightest to heaviest,
     do the following: flip a fair coin. If the coin flip
     yields tails, then discard $e$. If it yields heads,
     then add $e$ to $A$ if and only if it does not create
     a cycle in $(V_1, A)$.
     Finally, set $F_2 = A$.
  \item Let $e_i \in E_1$ be the $i$th edge in the
   sorted order of edges from $E_1$.
   Argue that after the $(i-1)$th coin flip, it is determined
   whether $e_i$ will be $F_2$-light or not.
  \item Divide the random experiment from (a) into 
  \emph{phases}. The $k$th phase begins as soon as the 
  $k$th edge is inserted in to $A$.
    Let 
    $X_k$ be the number of $F_2$-light edges that are created during phase
    $k$. Give an upper bound for the expected value of $X_k$.
  \item Show that the expected number of $F_2$-light edges is at most
    $2|V_1|$. 
\end{enumerate}

\AUFGABE{MST for planar graphs} {10 Points}

Let $G = (V, E)$ be a simple connected planar planar graph
with $n$ vertices. Suppose that the edges of $G$ are weighted
and that all weights are pairwise distinct. 
Show that $\text{MST}(G)$ can be computed in $O(n)$ time.

\emph{Hint}: Show that if we contract
an edge in a planar graph, the resulting graph is
again planar. 

\AUFGABE{Cuckoo-Hashing} {10 Points}

Prove the theorem from class that a set 
$S \subset U$ can be inserted successfully for the
hash functions 
$h_1, h_2: S \rightarrow \{0, \dots, m-1\}$ if and only if
the corresponding cuckoo graph $G_{h_1, h_2}(S)$ is valid.

\end{description}
\end{document}
