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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{6. June 2017, in the exercise session.}

\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}}
\newcommand{\N}{\mathbb{N}}



\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{Cuckoo Hashing}{10 Points}

\begin{enumerate}
\item
Let $k \in \{3, \dots, 2n\}$, and suppose
we have a cuckoo hashing data structure that
stores a set $S \subseteq \mathcal{U}$ and that
was built using hash functions 
$h_0, h_1: \mathcal{U} \rightarrow \{0, \dots, m-1\}$.

Let $x \in \mathcal{U} \setminus S$. Show that if 
$T(x) = k$, then
$G_{h_0, h_1}(S \cup \{x\})$ contains an edge-simple 
path that starts with $x$ and has at 
least $\lfloor k/3 \rfloor$ edges.
\item
Let $G = (V, E)$ be a connected graph with 
at least two cycles such that each connected
component of every proper subgraph of $G$ contains at
most one cycle.  Show that
either (i) there are $u \neq v \in V$ 
such that $G$ consists of three distinct paths with
endpoints $u$ and $v$ that share no other vertices; 
or (ii)
there are $u, v \in V$ such that
$G$ consists of a cycle $C_1$ that contains $u$,
a cycle $C_2$ that contains $v$, and a (possibly empty) path
$\pi$ from $u$ to $v$. The path $\pi$ contains no
vertices from $C_1$ or $C_2$ except for $u$ and $v$. 
The cycles $C_1$ and $C_2$ share
no vertices except possibly $u =v$, in case that
$\pi$ is empty.
\end{enumerate}

\AUFGABE{Encoding Arguments I}{10 Points}

Let $n \in \N$ and $x \in \{0, 1\}^n$ a 
binary string of length $n$. A \emph{run
of length} $k$ in $x$ ist a contiguous
substring of $k$ ones in $x$, for $k \in \N$.

Using the uniform encoding lemma, derive
a good upper bound for the probability
that a random binary string of length $n$
contains a run of length
$\lceil \log n \rceil + s + 1$,  
for $s \in \N$.
 
\AUFGABE{Encoding Arguments II}{10 Points}

Suppose we have a hash table $T$ with $n$ slots in which
we would like to store a set $S \subset U$ with $n$
elements. Conflicts are resolved using chaining.
Furthermore, we assume that the hash function is chosen
uniformly at random from the set of all functions
$h : S \rightarrow \{0, \dots, n-1\}$.

For a slot $i$ of $T$, we let $Q_i$
denote the \emph{number} of elements from $S$ that
are mapped to slot $i$ by the hash function.

\begin{enumerate}
  \item What is the number $H$ of possible hash functions
    $h : S \rightarrow \{0, \dots, n-1\}$?
    Argue that there is a canonical code that encodes
    all such hash functions with $\log H$ bits.
  \item Let $h$ be a hash function that maps 
    $k$ elements from $S$ into the same slot $i$.
    Show that $h$ can be encoded using
    $\log H - k \log(k/e) + \log n$ bits.

\emph{Hint}:
   $\binom{n}{k} \leq (ne/k)^k$.

  \item Show that for any $s \geq 1$, the probability that there is a slot
    with at least $3 \log n / \log \log n + s$
    elements is at most $2^{-s/2}$.
  \item
    Show that
\[\textbf{E}\left[\max_{i=0}^{n-1} Q_i\right] = O(\log n/\log\log n).\]
\end{enumerate}
\end{description}
\end{document}
