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

\vspace{8mm}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Red-Black Trees (1P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Zeichnen Sie den Red-Black-Tree der entsteht, wenn man die Schl"ussel 41, 38, 31, 12, 19 und 8 nacheinander in einen zu Beginn leeren Red-Black-Tree einf"ugt.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2,  Red-Black Trees  (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

$T$ sei ein Red-Black-Tree in den mit dem in der Vorlesung behandelten {\sf{INSERT}} Algorithmus nacheinander $n$ Schl"ussel eingef"ugt wurden. Zeigen Sie, dass $T$ mindestens einen roten Knoten hat, wenn $n > 1$ gilt.

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3,  Transponierter Graph (4P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

F"ur einen Graph $G = (V,E)$ definieren wir den transponierten Graph von $G$ als
$G^T = (V, E^T)$ mit $E^T = \{ (v,u) \mid (u,v) \in E \}$.
Beschreiben Sie zwei Algorithmen, die Graphen transponieren.
Der eine Algorithmus soll als Eingabe eine Adjazenzliste, der andere eine Adjazenzmatrix benutzen. Analysieren Sie die Laufzeiten ihrer Algorithmen.


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

Was ist die Laufzeit von {\sf BFS} wenn der Algorithmus so abge"andert ist, dass die Eingabe als Adjazenzmatrix repr"asentiert wird?

\end{document}