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


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

\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
Practice Exam for

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

\medskip\hrule

\smallskip
\noindent
Time: at least 90 minutes

\vskip 0.5cm

\begin{description}
\AUFGABE{Implementations of an ADT}{3+3+4}

Consider the following specification of an abstract
data type:
let $\mathcal{U}$ be a totally ordered universe. We would like
to store subsets $S \subseteq U$, so that the following operations
are possible:
\begin{itemize}
  \item \texttt{insert}(x): Pre: None. Effect:
                  $S \mapsto S \cup \{x\}$.
  \item \texttt{deleteMin}(): Pre: $S$ is not empty. Effect:
                  $S \mapsto S \setminus \{\min S\}$.
  \item \texttt{deleteMax}(): Pre: $S$ is not empty. Effect:
                  $S \mapsto S \setminus \{\max S\}$.
\end{itemize}
You may assume that two elements from $\mathcal{U}$
can be compared in constant time. For each of the
following data structures, describe briefly how
to implement the operations
\texttt{deleteMin} and \texttt{deleteMax} efficiently, and
give good asymptotic upper bounds on the running times.
If necessary, explain what additional assumptions need
to be made.

\begin{enumerate}
  \item Sorted doubly linked list with pointers to the first and last
     element;
  \item AVL-tree; and
  \item binary min-heap.
\end{enumerate}

\AUFGABE{Hashing}{2+4+4}

\begin{enumerate}
  \item 
    Hashing with chaining gives \emph{expected} running
    time $O(1)$ per operation. What does this mean?
    What can we say about the \emph{worst-case} performance?
  \item
    Let $T$ be a hash table with chaining that has $m$ slots
    and stores a set $S$ with $2m$ entries. Prove the following:
    assuming that the hash function $h$ behaves randomly,
    the expected time to find a random element $x$ in the
    hash table is $O(1)$. You may assume that $h(x)$ can
    be computed in $O(1)$ time.
  \item 
    Let $T$ be a hash table with $n$ slots in which we
    store a set $S$ with $n$ entries. Let $h$ be 
    a hash function.

    What is a \emph{collision} under $h$? Compute the
    \emph{total} expected number of collisions in $T$,
    assuming that $h$ behaves randomly.

    \emph{Hint}: Consider all possible pairs of entries
      in $S$, and use linearity of expectation.
\end{enumerate}


\newpage
\AUFGABE{Miscellaneous}{3+2+2+3}

\begin{enumerate}
  \item  What is a cryptographic hash function? Describe 
  two properties and one application.
  \item What is the difference between the static and the dynamic
      data type of a variable?  Give a short example.
  \item Under which circumstances is a data structure with
     $O(\log n)$ \emph{amortized} time per operation preferable
     to a data structure with 
     $O(\log n)$ \emph{worst-case}
     time per operation?
  \item What is an \emph{Abstract Data Type}?
    Give two examples from class and explain the general
    principle that forms the basis of the notion of
    an abstract data type.
\end{enumerate}

\AUFGABE{Skip Lists}{4+3+3}

\begin{enumerate}
  \item Show that the expected size of a randomly constructed skip list
      with $n$ elements is $O(n)$.
  \item
      Let $L_1$ and $L_2$ be two randomly constructed 
      skip lists, with element sets
      $K_1$ and $K_2$, respectively. Give an
      efficient algorithm to obtain a skip list for
      the element set $K_1 \cup K_2$ from $L_1$ and $L_2$. 
      Analyze the expected running time of your algorithm.
      (You may use the result from (a) without proof.)
  \item Suppose that in (b) we also know that for all $k_1 \in K_1$,
      $k_2 \in K_2$ we have $k_1 < k_2$. This means that every element in
      $L_1$ comes before every element in $K_2$. Describe an
      algorithm that merges $L_1$ and $L_2$ in expected time 
      $O(\max\{\log |K_1|, \log |K_2|\})$. Prove the guarantee on
      the running time.

      \emph{Hint:} For $x \in (0,1)$, we have
        $\sum_{i=1}^{\infty} ix^i = x/(1-x)^2$.

\end{enumerate}
\end{description}


\end{document}
