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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{am 31. Mai 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{Anwendungen von Sortieralgorithmen}{10 Punkte}

\begin{enumerate}
  \item
    Sei \texttt{l} eine Liste, die aus $n$ Zahlen besteht.
    Beschreiben Sie einen m\"oglichst schnellen Algorithmus, der bestimmt, 
    ob \texttt{l} zwei verschiedene Zahlen $x$, $y$ enth\"alt,
    so  dass $|x - y| \leq 10$ ist. Implementieren Sie Ihren Algorithmus 
    in Python.

\emph{Bemerkung}. ``M\"oglichst schnell'' bedeutet: Der 
Algorithmus sollte nicht alle Paare von Zahlen vergleichen.
  \item
    Seien \texttt{l1}, \texttt{l2}, \texttt{l3} drei Listen, die aus
    jeweils $n$ Zahlen bestehen.
    Beschreiben Sie einen m\"oglichst schnellen Algorithmus, der bestimmt, 
    ob es Zahlen $x \in \texttt{l1}$, $y \in \texttt{l2}$, 
    $z \in \texttt{l3}$ gibt,
    so dass $x + y + z = 0$ ist.
    Implementieren Sie Ihren Algorithmus in Python.

\emph{Bemerkung}. ``M\"oglichst schnell'' bedeutet: Der Algorithmus 
sollte nicht alle Tripel von Zahlen vergleichen.

\end{enumerate}
Machen Sie geeignete Testl\"aufe,
und achten Sie auf eine angemessene Fehlerbehandlung und Dokumentation
Ihres Programms.

\AUFGABE{Bin\"are Heaps}{10 Punkte}

\begin{enumerate}
  \item 
    F\"ugen Sie die Elemente I, N, F, O, B, X, Y in einen 
    anfangs leeren bin\"aren Heap ein und f\"uhren Sie dann zwei
    \emph{extract-max} Operationen durch. Zeigen Sie die einzelnen 
    Schritte.
  \item  
    Wie viele Elemente muss ein bin\"arer Heap der H\"ohe $h$
    mindestens enthalten? Wie viele sind es h\"ochstens?
    Beweisen Sie, dass ein bin\"arer Heap mit $n$ Elementen
    H\"ohe $\Theta(\log n)$ haben muss. (\emph{Achtung:}
    Wir z\"ahlen die H\"ohe und die Ebenen ab $0$.)
  \item 
    An welchen Stellen in einem bin\"aren Heap kann das zweitgr\"o\ss{}te
    Element gespeichert werden? Wie sieht es mit dem drittgr\"o\ss{}ten
    Element aus? Geben Sie allgemein an, auf welchen Ebenen eines
    bin\"aren Heaps mit $n$ Elementen sich das $k$.~gr\"o\ss{}te Element 
    befinden kann
    (Sie d\"urfen annehmen, dass alle Ebenen voll besetzt sind).
\end{enumerate}

\newpage

\AUFGABE{Stabiles Sortieren}{10 Punkte}

Das \emph{stabile Sortierproblem} ist folgenderma\ss{}en gegeben:

\textbf{Eingabe}: Eine Liste $x_1, x_2, \dots, x_n$ mit
  $n$ Elementen aus einem total geordneten Universum.

\textbf{Ausgabe}: Eine Permutation
  $\sigma: \{1, \dots, n\} \rightarrow \{1, \dots, n\}$, so dass gilt:
    (i) $x_{\sigma(1)} \leq x_{\sigma(2)} \leq \dots \leq x_{\sigma(n)}$
    und (ii) f\"ur alle $1 \leq i <  n$:
      wenn $x_{\sigma(i)} = x_{\sigma(i+1)}$ ist, dann ist
      $\sigma(i) < \sigma(i+1)$.
\end{description}

Ein Sortierverfahren hei\ss{}t \emph{stabil}, falls
es das stabile Sortierproblem l\"ost.

\begin{enumerate}
  \item  Beschreiben Sie in zwei S\"atzen, was es hei\ss{}t, dass ein
    Sortierverfahren stabil ist, und geben Sie zwei Beispiele.
  \item
    Bestimmen Sie f\"ur die folgenden Sortierverfahren aus der
    Vorlesung, ob sie stabil sind oder nicht:
      Insertion Sort, Quick Sort, Heap Sort und Merge Sort.
    
    Geben Sie jeweils eine kurze Begr\"undung.
  \item Beschreiben Sie einen einfachen Weg,
    wie sich \emph{jedes} vergleichsbasierte Sortierverfahren
    zu einem stabilen Sortierverfahren \"uberf\"uhren l\"asst.
\end{enumerate}
\end{document}
