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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 24. November~2017 bis 10 Uhr in die 
  jeweiligen Tutorenf\"acher}

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



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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}
\AUFGABE{Spezifizieren und Implementieren eines ADT}{10 Punkte}

Spezifizieren Sie sinnvoll
den abstrakten Datentyp
``double ended queue'', der das Einf\"ugen und L\"oschen von Objekten
an beiden Enden unterst\"utzt, und zwar auf zwei verschiedene Arten:
einmal verbal (versuchen Sie, m\"oglichst genau zu sein) und einmal
anhand eines mathematischen Modells.

Formulieren Sie ein entsprechendes Interface in Java, und
implementieren Sie den Datentyp auf zwei verschiedene Arten. 
Vergleichen Sie die Vor- und Nachteile Ihrer beiden
Implementierungen (bez\"uglich Laufzeit, Implementierungsaufwand, 
Flexibilit\"at, usw.).

\emph{Freiwillig, 5 Zusatzpunkte:} Verfahren Sie wie in Aufgabe 
3.3(c) und erstellen Sie mindestens f\"unf JUnit-Testcases f\"ur
Ihre Implementierung.

\AUFGABE{Untere Schranken f\"ur Priorit\"atswarteschlangen}{5 Punkte}

\begin{enumerate}

\item
Zeigen Sie, wie man eine Priorit\"atswarteschlange verwenden kann,
um eine Folge von $n$ vergleichbaren Elementen zu sortieren. 
\item
Aus \emph{Konzepte der imperativen und objektorientierten
Programmierung} wissen Sie, dass jeder vergleichsbasierte 
Sortieralgorithmus
mindestens $\Omega(n \log n)$ Operationen ben\"otigt. 
Folgern Sie, dass in jeder vergleichsbasierte Implementierung 
der Priorit\"atswarteschlange
mindestens eine Operation $\Omega(\log n)$ amortisierte Laufzeit haben
muss.
\end{enumerate}

\AUFGABE{Bin\"are Heaps}{15 Punkte}
\begin{enumerate}
  \item  
    Wie viele Elemente enth\"alt ein bin\"arer Heap der H\"ohe $h$
    mindestens? Wie viele sind es h\"ochstens?
    Beweisen Sie, dass ein bin\"arer Heap mit $n$ Elementen
    H\"ohe $\Theta(\log n)$ hat. (\emph{Achtung:}
    Wir z\"ahlen die H\"ohe und die Ebenen ab $0$.)
  \item 
    Wo kann in einem bin\"aren Heap das zweitkleinste
    Element stehen? Wie ist es mit dem drittkleinsten
    Element? Geben Sie allgemein an, auf welchen Ebenen eines
    bin\"aren Heaps mit $n$ Elementen sich das $k$.~kleinste Element 
    befinden kann
    (Sie d\"urfen annehmen, dass alle Ebenen voll besetzt sind).
  \item 
    Veranschaulichen Sie die bottom-up Heapkonstruktion mit dem Array
    \texttt{[7, 6, 5, 3, 1, 4, 2, 8]}. 
    
    \item
    Angenommen, wir f\"ugen $n$ Elemente nacheinander in einen
    anfangs leeren Heap ein. Zeigen Sie, dass dies im
    worst-case $\Omega(n \log n)$ Zeit ben\"otigt.

    \emph{Achtung}: Anfangs braucht das Einf\"ugen wesentlich
      weniger als $\log n$ Schritte.
\end{enumerate}


\end{description}

\end{document}
