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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{on 07. December~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{Hashing: Implementation}{10 points}

\begin{enumerate}
\item 
Read the documentation of \texttt{hashCode()} in
\texttt{java.lang.Object}. 
Which properties need to be satisfied?
Why should you overwrite the method in your own classes?
\item
Implement hashing with chaining, as described in class.
Use \texttt{hashCode()}.
For the linked lists, you may use the Java-library.
The hash-table should grow dynamically as soon as a
certain load factor is reached.

Perform experiments with your implementation.
How do the access times depend on the load factor?
Compare two different hash functions (these may
be hard-coded for a fixed table size).
\end{enumerate}

\AUFGABE{Analysis of Skip Lists}{10 points}

Let $L$ be a skip list with $n$ entries.
Show the following:
\begin{enumerate}
  \item The expected number of nodes in  $L$ 
     is $O(n)$.
  \item With probability at most 
    $n/2^{j-1}$, the list  $L$ has at least
    $j$ horizontal lists.

       \emph{Hint}: For events  $A_1, \dots, A_\ell$,
   we have $\Pr[A_1 \cup \dots \cup A_\ell]
   \leq \sum_{i=1}^{\ell} \Pr[A_i]$ (this is called the
   \emph{union bound}).
\end{enumerate}


\AUFGABE{Implementation of an Ordered Dictionary}{10 points}

\begin{enumerate}
\item 
Write a Java-interface for the abstract data type
\texttt{OrderedDictionary} from class.
Provide comments to specify the operations.
Implement the interface using a skip list.

\emph{Hint:} You can find pseudocde for the skip list
operations on the website.

\item 
Read the specification of 
\texttt{java.util.Iterator}.
Write methods
\texttt{iterator()} and \texttt{reverseIterator()}
that create an
\texttt{Iterator}-Object.
\texttt{iterator()} should process the
entries in sorted order, 
\texttt{reverseIterator()} should process 
the entries in reverse order.

Make sure your implementation follows the
specification 
laid out in
the Java-API-documentation.
You do not need to implement the \texttt{remove()}-method.

\item
(\emph{voluntary, 5 additional points})

What happens if the skip list is changed while an
\texttt{Iterator}-object is active? Describe a
possible problem.

One solution uses \emph{fail-fast} iterators: as soon as
the skip list is changed through \texttt{put} or \texttt{remove},
\emph{all} active  \texttt{Iterator}-objects become invalid.
Later method calls result in a 
\texttt{ConcurrentModificationException}. Iterators that
were created after the modification should still work.
How can this behavior be implemented?
Read about the 
\emph{observer pattern}, and describe how to use it for
the problem at hand.

You do not need to write any code.
\end{enumerate}

\AUFGABE{Cryptographic Hash Functions}{voluntary, 10 additional points}

\begin{enumerate}
    \item What is a crytopgraphic hash function? Name three heuristic
        candidates.
     \item Which cryptographic hash functions are available in
     Java? How can they be used?
     \item Adapt your hash table from Problem 1(b), so that
      it uses cryptographic hash functions. Perform  appropriate
      experiments.

      Give an advantage and a disadvantage of this implementation.
\end{enumerate}

\end{description}


\end{document}
