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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{on 11. January~2019, 10:00, in the
respective TA's mailbox}

\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})}


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

\smallskip
\noindent
\large
\textbf{Algorithms, Data Structures and Data 
Abstraction}\hfill WS 18/19 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm 
\noindent
All the problems on this exercise sheet are voluntary. 
We wish all the participants of AlP3 a good holiday season
and a happy new year!

\begin{description}

\AUFGABE{Huffman-Implementation --- Design}{10 Points}

Implement the Huffman-compression algorithm.
More precisely: write two Java-programs
\texttt{HuffmanEncode}
and \texttt{HuffmanDecode}. Then, 
\texttt{java HuffmanEncode foo} should read the file \texttt{foo}
and compress it with the Huffman-algorithm (at byte-level).
The result (together with the coding table)
should be written to the file \texttt{foo.hc}.
The command  \texttt{java HuffmanDecode foo.hc} should
read the compressed file  \texttt{foo.hc}  and decompress 
it into the file  \texttt{foo.uc}.

Come up with a design for the implementation.
Which subproblems do you need to solve?
Which abstract data types are required?
How should the subproblems be mapped into a
class structure? How should the classes interact with
each other?
Give a brief description of your design and visualize
it with appropriate diagrams.

\AUFGABE{Huffman-Implementation --- Programming}{15 Points}

Write actual code that implements your design from the
previous problem. Perform appropriate tests.

\AUFGABE{Cuckoo Hashing}{10 Points}

Look at the Bachelor thesis about cuckoo hashing
and answer the following questions:
\begin{enumerate}
  \item What is the cuckoo graph?
  \item What does the cuckoo graph have to do
     with the success of the insertion procedure?
  \item What is an encoding?
  \item How are encodings used in order to show that a
      certain event must have small probability?
  \item Which variant of cuckoo hashing seems to
     be most efficient in practice?
\end{enumerate}

\newpage
\AUFGABE{Hashing: Worst-case-Analysis}{10 Points}

Let $A$ be a hash table with $N$ slots, and $n \in \N$ 
be given. 
Show the following:
For every set $K$ of keys with $|K| \ge (n-1)N + 1$ and for every
hash function $h: K \to \{0, \dots,N-1\}$, there is a set 
$S \subseteq K$ with
$|S|=n$, so that all elements from $S$ are mapped by $h$ 
to the same position in $A$.
What does this mean for the worst-case running time of hashing 
with chaining?
Does this result contradict our analysis from class?

\AUFGABE{Hashing: Open Addressing}{15 Points}

We insert a set $S$ with $n$ entries into 
a hash table $T$ with $m = 6n$ slots. 
The collisions are resolved with open addressing 
using linear probing. We assume that the hash function
$h$ behaves randomly. The indices in $T$ are taken
modulo $m$, i.e., $T[-1] = T[m-1]$ and $T[m] = T[0]$. 

\begin{enumerate}
  \item Let $k \in \N, k < m$. A \emph{cluster of size $k$} in $T$ 
    is a sequence $i, i + 1, \dots, i + k - 1$ of 
    consecutive indices such that 
    $T[i], T[i+1], \dots, T[i+k-1]$ are all occupied, but 
    $T[i - 1]$ and $T[i + k]$ are free.

    Show the following: The probability, that after the 
    insertion of $S$, the table $T$ contains a cluster 
    of size $k$ that starts at $i$ is at most
    \[
    p_{i,k} := \binom{n}{k}
           \left(\frac{k}{m}\right)^k\left(\frac{m-k}{m}\right)^{n-k}.
    \]

\emph{Hint}: If there is a cluster of size $k$ that starts 
at $i$, then there is a subset 
 $S' \subseteq S$ of $k$ entries that are
mapped by $h$ to $i, i+1, \dots, i+k-1$. 
The remaining hash values must be outside this set.

 \item Use  $m = 6n$ and the bound
    $\binom{n}{k} \leq (\frac{ne}{k})^k$, 
    in order to show that
    \[
    p_{i,k} \leq 2^{-k}.
    \]
    Here,  $e \approx 2.71\dots$ denotes Euler's number.
\item Give a good bound for the event that $T$ contains a 
  cluster of size 
  $2\log n$.
 
\item Let $x \notin S$ be a fixed entry. 
Argue that the expected running time for a 
lookup of $x$ in $T$ is at most 
  proportional to
  \[
    1 + \sum_{k = 0}^{n} k 
    \Pr[\text{$h(x)$ is in a cluster of length $k$]}.
    \tag{*}
  \]
  Show that (*) can be bounded as
  \[
    1 + \sum_{k = 0}^{n} k^2 
    \Pr[\text{a cluster of length $k$ starts at $h(x)$]}
    \tag{*}
  \]
  and conclude that the expected time to look up $x$ is $O(1)$.
\end{enumerate}




\end{description}


\end{document}
