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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{on 23. 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}}



\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{Specification and Implementation of an ADT}{10 Points}

Give a meaningful verbal specification for the abstract
data type ``double ended queue'' that allows insertion and
deletion of elements on both ends of a queue.
Try to be as exact as possible.

Write down a corresponding interface in Java,
and implement the abstract data type in two different
ways. Name respective 
advantages and disadvantages of your implementations
(e.g., wrt running time, ease of implementation, 
flexibility, etc.).

\emph{(voluntary, 5 extra points)} 
Proceed as in Problem 3.3(c) and 
create at least five JUnit-testcases for your 
implementation.

\AUFGABE{Lower Bounds for Priority Queues}{5 Points}

\begin{enumerate}

\item
Show how to use a priority queue in order to sort
a sequence of $n$ pairwise comparable elements.
\item
In \emph{AlP2}, you learned that
every comparison-based sorting algorithm 
requires $\Omega(n \log n)$ comparisons.
Conclude that in every comparison-based 
implementation of a priority queue,
there is at least one operation
with $\Omega(\log n)$ amortized running
time.
\end{enumerate}

\AUFGABE{Binary Heaps}{15 Points}
\begin{enumerate}
  \item  
    What is the minimum number of elements a binary heap with
    height $h$ can have?
    What about the maximum number?
    Conclude that a binary heap with $n$ elements 
    must have height
    $\Theta(\log n)$. 
    
    \emph{Attention:} We count the levels from $0$.
  \item 
    Where in a binary heap can the second smallest
    element be located? What about the third
    smallest element?
    Provide a general formula for the levels
    that may contain the $k$-smallest element in 
    a binary heap with $n$ elements.
    (You may assume that all levels are filled completely).
  \item 
    Illustrate the 
    bottom-up heap construction for 
    \texttt{[7, 6, 5, 3, 1, 4, 2, 8]}. 
    
    \item
    Suppose we insert $n$ elements successively into
    a binary heap that is initially empty.
    Show that this takes
     $\Omega(n \log n)$ time in the worst case.

    \emph{Attention}: Initially, an insertion takes much
      less than $\log n$ steps.
\end{enumerate}



\end{description}

\end{document}
