\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{8mm}

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

\vspace{8mm}

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

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

Gegeben sei eine Hash-Funktion $h(k,i) = (h'(k) + c_1 i + c_2 i^2) ~mod ~m$.
Welche der folgenden Werte von $c_1$, $c_2$ und $m$ geeignet und warum:\\
a) $c_1 = 6$, $c_2 = 9$, $m = 16$ \hfill
b) $c_1 = c_2 = \frac{1}{2}$, $m = 2^p$ mit $p \in \N$


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2,  Bin\"are Suchb\"aume  (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Schreiben Sie eine  \textsf{TREE-PREDECESSOR} Methode in Pseudocode. 


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3,  Minimum und Maximum (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Schreiben Sie rekursive Versionen von \textsf{TREE-MINIMUM} und \textsf{TREE-MAXIMUM} in Pseudocode.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 4, Eigenschaften von Knoten  (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Zeigen Sie, wenn ein Knoten $x$ zwei Kinder hat, dass dann
der Knoten  \textsf{TREE-SUCCESSOR}($x$) kein linkes Kind,
und der Knoten  \textsf{TREE-PREDECESSOR}($x$) kein rechtes Kind hat.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 5, Suche in bin\"aren Suchb\"aumen  (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

In einem bin\"aren Suchbaum seinen Zahlen zwischen 0 und 1000, gesucht wird nach der Zahl 363. Welche der folgenden Sequenzen k\"onnen die untersuchten Knoten sein? (In der gegebenen Reihenfolge)\\
a) 2, 252, 401, 398, 330, 344, 397, 363\\
b) 924, 220, 911, 244, 898, 258, 362, 363\\
c) 925, 202, 911, 240, 912, 245, 363\\
d) 2, 399, 387, 219, 266, 382, 381, 278, 363\\
%e) 935, 278, 347, 621, 299, 392, 358, 363\\


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 6, Reihenfolge der Eingabe  (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

In einen bin\"are Suchbaum werden die Zahlen von 1 bis 12 eingegeben.
F\"ur welche Permutationen der Eingabe wird der Baum gut, f\"ur welche nicht? Geben Sie je ein Beispiel.

\end{document}