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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{am 7. 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{Heap-Sort}{10 Punkte}

Die folgende Variante von Heapsort kommt nur mit
\texttt{bubbleDown} aus.
\begin{verbatim}
def heapSort2(a):
    # Erstelle Heap in der Eingabeliste
    for i in range(len(a) - 1, -1, -1):
        bubbleDown(a, len(a), i)
    # Entferne wiederholt das Maximum
    for i in range(len(a) - 1, 0, -1):
        # Tausche Wurzel an die richtige Stelle
        swapElements(a, 0, i)
        # Benutze bubbledown, um die Max-Heap-Eigenschaft 
        # herzustellen  der Heap befindet sich in den ersten 
        # i Plaetzen der Eingabeliste
        bubbleDown(a, i)
\end{verbatim}

\begin{enumerate}
  \item Demonstrieren Sie den modifizierten Algorithmus f\"ur die folgende Eingabeliste: 
   \[
     2; 5; 16; 4; 10; 23; 29; 18; 26; 15.
   \]
  \item Begr\"unden Sie \emph{kurz}, warum der modifizierte Algorithmus funktioniert. 
    Argumentieren Sie dazu mit Hilfe von bin\"aren Heaps.

   \emph{Vorschlag}: Es ist hifreich, sich \emph{mehrere Heaps} vorzustellen, die in
     der Eingabeliste angelegt werden. Durch die \texttt{bubbleDown}-Aufrufe werden
     Heaps zusammengef\"uhrt.
   
  \item  Beweisen Sie, dass die folgende Schleife nur $O(n)$ Vergleiche der Eingabeelemente durchf\"uhrt:
   \begin{verbatim}
    for i in range(len(a) - 1, -1, -1):
        bubbleDown(a, len(a), i)
    \end{verbatim}

   \emph{Hinweis}: Wie viele Vergleiche ben\"otigt \texttt{bubbleDown} maximal bei einem
     Heap mit $i$ Ebenen? Au\ss{}erdem gilt f\"ur alle $n \in \mathbb{N}$: 
     $\sum_{i = 1}^{\log (n+1)} \frac{n+1}{2^i} \cdot 3(i-1) = O(n)$.
\end{enumerate}

\AUFGABE{O-Notation}{10 Punkte}

\begin{enumerate}
\item Algorithmus A hat Laufzeit $10n \log^2 n$, Algorithmus B hat Laufzeit
   $n \sqrt{n}$ und Algorithmus C hat Laufzeit $n^2$. Bestimmen Sie die Eingabegr\"o\ss{}e $n_0$, 
   ab der A effizienter ist als B, und die Eingabegr\"o\ss{}e $n_1$, ab der A effizienter ist als C.
\item Zeigen Sie anhand der Definition, dass $n \log_8 n \in \Theta(n \log_2 n^2)$ ist.
\item
Sortieren Sie die folgenden Funktionen aufsteigend bez\"uglich ihres asymptotischen
Wachstums und markieren Sie die Funktionen mit gleichem asymptotischen Verhalten:
\[
n^3;\, 4n \log n + 2n;\, 2^{10};\, 2^{\log_4 n};\, 3n + 100 \log n;\,
4n;\, 2^n;\, n^2 + 10n;\, \sum_{i = 0}^{n-1} i^2.
\]
\end{enumerate}

\AUFGABE{Algorithmik }{10 Punkte}

\begin{enumerate}
  \item
Geben Sie ein Verfahren mit Laufzeit $O(n+k \log n)$ zur Bestimmung des $k.$-kleinsten Elementes
unter $n$ Zahlen an. Begr\"unden Sie die Laufzeit.
Implementieren Sie Ihren Algorithmus in Python.

\emph{Hinweis}: Beachten Sie Aufgabe 1c.
  \item
Gegeben sei eine $n \times n$ Matrix mit ganzzahligen Eintr\"agen. Dabei seien jeweils jede Zeile
und jede Spalte aufsteigend sortiert. Geben Sie einen Algorithmus mit
Laufzeit $O(n)$ an, der entscheidet, ob eine Anfragezahl $x$ in der Matrix vertreten ist
oder nicht. Begr\"unden Sie die Laufzeit.
Implementieren Sie Ihren Algorithmus in Python.
\end{enumerate}

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