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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{on 30. November~2018, 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}}



\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

\begin{description}

\AUFGABE{Further Heap-Operations}{10 Points}

\begin{enumerate}
\item
Write code for a binary heap with $n$ elements, stored as an
array. Also, implement the following two
operations, with worst-case running time $O(\log n)$.

\begin{itemize}
\item {\texttt{decreaseKey$(i,k)$}}:  Set the key 
 at position $i$ to $k$ and restore the heap property 
(Precondition:
  $k$ is less than or equal to the old key at $i$).
\item {\texttt{delete$(i)$}}:  Remove the element at
position $i$ and restore the heap property.
\end{itemize}

Both \texttt{decreaseKey} and
\texttt{delete} may use \texttt{bubble-up}
and \texttt{bubble-down}.
Briefly justify correctness and running time
of your implementation.

\item
We would like to extend the interface \texttt{PriorityQueue} 
with the additional operations from (a). Explain briefly
why an efficient implementation 
needs a  ``pointer'' into the data structure
(i.e., why is it not enough to pass only the
old and the new key to \texttt{decreaseKey}, even if
the old key appears only once?).

How would you implement this without violating the
information hiding principle?
Define a new interface \texttt{Position} that
represents a pointer into the priority queue.
Explain briefly how to modify 
\texttt{PriorityQueue} in order to use \texttt{Position}.
What problems does this create?
Sketch a possible solution.
(You do not need to write any code.)
\end{enumerate}

\AUFGABE{Elementary Probability Theory}{10 Points}

We have  $N$ bins, and we throw 
$n$ balls into them such that each throw is independent
of the others and such that each bin is hit with the same 
probability $1/N$.

\begin{enumerate}
\item Compute the probability that bin 
$i$ remains empty, for $i = 1, \dots, N$.
Furthermore, let $Y_i$ be the indicator random variable 
that is $1$, if bin $i$ remains empty, and $0$, 
otherwise.
Compute the expected value $E[Y_i]$ of $Y_i$.

\item Let $X$ be the random variable that indicates
the number of bins that remain empty. 
Compute the expected value of  $X$ using the expected
values $E[Y_i]$, for $i = 1, \dots, N$.

\item 
Determine a good bound $f(N)$ so that
the following holds: suppose we throw $n$
balls into $N$ bins, independently and uniformly at random.
If  $n \geq f(N)$, then with probability at least $1/2$ 
there is at least one bin with at least two balls.

\emph{Hint}:
Imagine that the $n$ balls are thrown 
successively. 
What is the probability that the next ball
ends up in an empty bin, provided that all the
previous balls have ended up in an empty bin?
You might find the bound 
$1+x \leq e^x$ useful. It holds for all $x \in \R$.
\end{enumerate}

\AUFGABE{Hashing}{10 Points}

\begin{enumerate}
  \item  
    Successively insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10
    into a  hash table with 9 positions. Use the hash function
    $h(k) = k \bmod 9$, and resolve conflicts with chaining.
  \item 
    Successively insert the keys 10, 22, 31, 4, 15, 28, 17, 88, 59
    into a hash table with 11 positions. Use the hash function
    $h(k) = k \bmod 11$, and resolve conflicts using open addressing
    with linear probing.
  \item 
    Successively insert the keys 10, 22, 31, 4, 15, 29, 17, 88, 59
    into a hash table with 11 positions. Resolve conflicts
    with cuckoo hashing, using $h_1(k) = k \bmod 11$ and
    $h_2(k) = (k \bmod 13) \bmod 11$.
\end{enumerate}

Show the individual steps.

\emph{Hint}: Pseudo-code for the hashing operations
   is available on the course website.
\end{description}


\end{document}
