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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{am 28. Juni 2016 bis 12 Uhr in die
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})}
\renewcommand{\labelenumii}{(\roman{enumii})}


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

\smallskip
\noindent
\large
\textbf{Informatik B}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Stapel mit Arrays}{10 Punkte}

\begin{enumerate}
  \item Geben Sie eine alternative Implementierung f\"ur das
    Interface \texttt{Stack<A>}, welche auf einem 
    Array basiert. Ihr Stapel darf eine begrenzte Kapazit\"at haben.

    Was sind die Laufzeiten der einzelnen Operationen?

  \item \"Andern Sie Ihre Implementierung aus (a) so, dass
    der Stapel beliebig viele Elemente enthalten kann.
    Benutzen Sie dazu ein \emph{dynamisches Array}: 
    Wenn das aktuelle Array an die Grenzen seiner Kapazit\"at
    gelangt, wir ein neues Array mit doppelter Gr\"o\ss{}e angelegt
    und die Elemente kopiert. Wenn zu wenige Elemente im aktuellen
    Array gespeichert sind, wird ein neues Array mit halber Gr\"o\ss{}e
    angelegt.

    \emph{Zusatzfrage (5 Zusatzpunkte)}: Was k\"onnen Sie jetzt \"uber die Laufzeiten der Operationen sagen?
\end{enumerate}

\AUFGABE{Priorit\"atswarteschlangen}{10 Punkte}

Betrachten Sie das folgende Java-Interface f\"ur
\emph{Priorit\"atswarteschlangen}:
\begin{verbatim}
    public interface PriorityQueue<A> {
        boolean isEmpty();
        void enqueue(A x, int prio);
       	A dequeue();
    }
\end{verbatim}
Priorit\"atswarteschlangen arbeiten \"ahnlich wie
Warteschlangen, aber beim Einf\"ugen wird jedem
Element eine Priorit\"at \texttt{prio} zugewiesen.
Die Operation \texttt{dequeue} liefert ein
Element aus der aktuellen Warteschlange, das die 
gr\"o\ss{}te Priorit\"at \texttt{prio} hat.

Implementieren Sie Priorit\"atswarteschlangen mit Hilfe
von bin\"aren Heaps. Die Priorit\"atswarteschlange
darf eine begrenzte Kapazit\"at haben.

Was sind die Laufzeiten der einzelnen Operationen?

\AUFGABE{Bin\"are Suchb\"aume}{10 Punkte}

Rufen Sie sich aus Informatik A die Funktionsweise
von bin\"aren Suchb\"aumen ins Ged\"achtnis. Implementieren
Sie dann bin\"are Suchb\"aume zusammen mit den Algorithmen
zum Einf\"ugen und L\"oschen in Java.

\emph{Hinweis:} Der Haskell-Quelltext f\"ur bin\"are
  Suchb\"aume ist auf der Veranstaltungs-Website verlinkt.
\end{description}
\end{document}
