\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 7}
\end{center}

\vspace{1cm}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Sortieren von Objekten unterschiedlicher L\"angen (4P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei ein Array von Zahlen, die unterschiedliche Anzahlen von Dezimalstellen haben k\"onnen. Die Summe aller Anzahlen von Dezimalstellen ist $n$.
(Beispiel: F\"ur $A = \langle 123, 45678, 90, 1, 23, 45 \rangle$ ist $n = 15$)
Zeigen Sie, wie der Array mit Zeitaufwand $O(n)$ sortiert werden kann.

\vspace{3mm}
\noindent
Gegeben sei ein Array von Buchstabenfolgen (W\"ortern) unterschiedlicher L\"angen.
Die Anzahl aller Buchstaben im Array sei $n$. Zeigen Sie, wie der Array mit Zeitaufwand $O(n)$ alphabetisch sortiert werden kann.\\
(Beispiel: F\"ur $A = \langle a, b, ab \rangle$ ist $n = 4$ und die gew\"unschte Ordnung ist $a < ab < b$.)




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

Wie k"onnen $n$ Zahlen, alle aus dem Bereich von $0$ bis $n^2-1$, mit Zeitaufwand $O(n)$ sortiert werden?


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

Eine Hash-Funktion sei gegeben durch $h(k) = k ~mod ~9$.
Machen Sie eine Hash-Tabelle f\"ur die keys 5, 28, 19, 15, 20, 33, 12, 17 und 10. L\"osen Sie das Problem von Kollisionen durch chaining. 

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 4, Hashing (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei eine Hash-Tabelle der Gr\"osse $m = 1000$ mit Hash-Funktion
$h(k) = \lfloor m ( k \cdot a ~mod ~1) \rfloor$ mit $a = \frac{\sqrt 5 - 1}{2}$.
Berechnen Sie die Hash-Werte der nat\"urlichen Zahlen von 60 bis 65.

\end{document}