\documentclass[11pt, oneside]{article}

\usepackage{a4, latexsym}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{german}
\usepackage{nopageno}

\date{}

\begin{document}
\noindent
\textsl{Vorlesung Algorithmen, D.~Huson und R.~Rupp, Universit\"at T\"ubingen, WS07/08}

\vspace{1cm}

\begin{center}
\LARGE{Aufgabenblatt 5}
\end{center}

\vspace{1cm}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Heapsort (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Was ist die Laufzeit von \textsf{HEAPSORT} auf einem Array $A$ der L\"ange $n$,
wenn die Elemente von $A$ in aufsteigener Reihenfolge vorsortiert sind? (1P)

\noindent
Und wie sieht die Laufzeit aus,
wenn die Elemente von $A$ in absteigender Reihenfolge sortiert sind? (1P)


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2,  Heap-Extract-Max (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Stellen Sie die Funktionsweise von \textsf{HEAP-EXTRACT-MAX} bildlich dar.
Benutzen Sie als Beispiel den Heap
$A = \langle 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1 \rangle$.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, Warteschlangen (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Schreiben sie in Pseudocode einen Algorithmus, der einen Stack implementiert und dazu eine  Priorit\"atswarteschlange benutzt. (1P)

\noindent
\"Andern Sie ihren Algorithmus, so dass aus dem Stack eine first-in-first-out Warteschlange wird. (1P)


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 4, Heap-Increase-Key (5P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei der folgende Algorithmus:
\vspace{4mm}

\noindent
\textsf{
HEAP-INCREASE-KEY($A,i,key$)\\
1 \hspace*{5mm} {\bf if} $i < A[i]$ \\
2 \hspace*{10mm} {\bf then error} ``new key is smaller than current key'' \\
3 \hspace*{5mm} $A[i] \leftarrow key$ \\
4 \hspace*{5mm} {\bf while} $i > 1$ and $A[\textsf{PARENT}(i)] < A[i]$ \\
5 \hspace*{15mm} {\bf do} exchange $A[i] \leftrightarrow A[\textsf{PARENT}(i)]$ \\
6 \hspace*{21mm} $ i \leftarrow \textsf{PARENT}(i)$ \\
}
\vspace{4mm}

\noindent
Beweisen Sie die Korrektheit des Algorithmus.






\end{document}