\documentclass[12pt, oneside]{article}

\usepackage{a4, latexsym}
\usepackage{fullpage}
\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 6}
\end{center}

\vspace{1cm}


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Implementierung von HeapSort (8 P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Implementieren Sie den {\sf HeapSort} Algorithmus.
Benutzen Sie dazu bitte die Datei\\
{\tt http://www-ab.informatik.uni-tuebingen.de/teaching/ws07/algo/HeapSort.java}.

Schreiben Sie dazu eine Methode {\sf sort}, wie vorgegeben, die mittels den Funktionen {\sf leftChild}, {\sf rightChild}, {\sf swap},
{\sf buildMaxHeap} und {\sf maxHeapify} operiert.

Ein- und Ausgabe sind in der {\sf main} Methode bereits implementiert. Achtung, das Array {\sf A} hat bei $n$ Eingaben
die L"ange ${\sf A.length}=n+1$, da in {\sf A[0]} kein Wert eingetragen wird; es werden die Zellen {\sf A[1..n]} gef"ullt. (Das bitte nicht "andern.)


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, Empirische Laufzeit von HeapSort (2 P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Bestimmen Sie empirisch die Laufzeit Ihres Programmes f"ur Probleme verschiedener Gr"o"se und 
zeichnen Sie eine Graphik, die die Laufzeit sinnvoll darstellt.


\bigskip
\bigskip
\noindent
Bitte die L"osungen per Email an Daniel Huson mit Subject: {\tt Aufgabenblatt 6}.
\end{document}