%  Zwischenklausur ALP3 WS 2003/2004
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,5cm
\textheight=25cm
\hoffset = -17mm
\voffset = -35mm

\begin{document}

\def\blatt#1#2#3#4
{
\count0=7
\begin{centering}
{\large
\openup 0,5ex
 \bf Algorithmen und Programmieren 3,
%\hfill Matrikelnummer: \vrule width 3cm height -2.5pt depth 3pt
%
 WS 2003/2004.

zweite Nachklausur zur ersten Teilklausur

Dienstag, 6. April
 2004.
%\hfill FAMILIENNAME: \vrule width 4cm height -2.5pt depth 3pt

%\hfill Vorname: \vrule width 4cm height -2.5pt depth 3pt
\par}
%\bigskip
\par \bigskip
\end{centering}
\hrule
\medskip

\noindent \emph{Anleitung}:
Streichen Sie \emph{eine} Aufgabe deutlich auf dem Angabeblatt.
Diese Aufgabe wird nicht in die Bewertung einbezogen.
Wenn Sie selbst keine Aufgabe streichen, wird die erste
Aufgabe nicht in die Bewertung einbezogen.
Bearbeiten Sie die "ubrigen drei Aufgaben.\medskip

\emph{Bearbeiten Sie jede Aufgabe auf einem getrennten Blatt.}
Jede Aufgabe hat 10 Punkte. Bearbeitungszeit: 90 Minuten
\medskip
\hrule


\begin{enumerate}
\parskip=0,5\parskip
%\itemsep=0pt
\item \aufgabe #1
\item \aufgabe #2
\item \aufgabe #3
\item \aufgabe #4
\end{enumerate}
%\eject
}

\long\def\aufgabe #1{\ifcase #1\or
 Fügen Sie nacheinander die Werte 5, 3, 9, 2, 7, 10, 11, 4, 1 in einen
  anfangs leeren 2-3-Baum ein.  Entfernen Sie dann die Element 5 und 7.
  Zeichnen Sie den 2-3-Baum nach jeder Operation auf.

\or
\emph{Rot-Schwarz-B"aume} sind bin"are B"aume mit folgenden
Eigenschaften:%
\footnote{Diese Definition stimmt mit der Definition auf dem
6. "Ubungsblatt "uberein.}
\begin{enumerate}
\item Jeder innere Knoten hat zwei Kinder.
\item Jeder Knoten ist entweder als \emph{rot} oder als
\emph{schwarz} gekennzeichnet.
\item Die Wurzel und alle Bl"atter sind schwarz.
\item Die Kinder eines roten Knotens sind schwarz.
\item Ein schwarzer Knoten kann h"ochstens ein rotes Kind haben.
\item Alle Wege von der Wurzel zu den Bl"attern enthalten
die gleiche Anzahl von schwarzen Knoten.
\end{enumerate}
Die \emph{schwarze H"ohe} ist die um eins verminderte Anzahl
der schwarzen Knoten auf jedem Weg von der Wurzel zu einem Blatt.
\begin{enumerate}
\item
Welche H"ohe kann ein Baum mit schwarzer H"ohe $h'$
mindestens und h"ochstens haben?
\item
Wie viele rote Knoten kann ein Baum mit schwarzer H"ohe $h'$
mindestens und h"ochstens haben?
\item
Wie viele schwarze Knoten kann ein Baum mit schwarzer H"ohe $h'$
mindestens und h"ochstens haben?
\end{enumerate}
Begr"unden Sie Ihre Antworten.

\or % \item

F\"ur eine gegebene Folge von $n$ verschiedenen Zahlen
$x_1,x_2,\ldots,x_n$ soll die Anzahl der \emph{Inversionen} (Fehlst"ande)
bestimmt werden, das sind die Paare $(x_i,x_j)$ mit $1\le i<j\le n$ und $x_i>x_j$.
Zum Beispiel hat die Folge $(3,5,10,1,6)$ vier
Inversionen, n"amlich die Paare $(3,1)$, $(5,1)$, $(10,1)$ und $(10,6)$.

Zeigen Sie, wie man den Algorithmus \emph{Sortieren durch Verschmelzen}
so erweitern kann, dass er in $O(n\log n)$ Zeit 
die Anzahl der Inversionen berechnet.
Geben Sie insbesondere genau an, was man beim Verschmelzen machen muss.

Wahlweise d"urfen Sie auch einen anderen Algorithmus angeben, der das Problem
in $O(n\log n)$ Zeit l"ost.

\or % \item %(10 Punkte)
Schreiben Sie ein Programm in Java oder Haskell, das eine sortierte Liste von
$n$ ganzen Zahlen in einen bin"aren Suchbaum der kleinstm"oglichen H"ohe
$h=\lceil \log_2 (n+1) \rceil-1$ umwandelt.

(Ihr Programm muss \emph{nicht} vollständig in dem Sinn sein, dass Sie zum
Beispiel das Suchen und alle notwendigen und nützlichen Methoden für eine
Klasse \texttt{Baum} programmieren müssen. Beschränken Sie sich auf die
gestellte Aufgabe.)

\fi
}

\def\alleperm
{
\blatt 1234
\blatt 2341
\blatt 3412
\blatt 4123

\blatt 1243
\blatt 2431
\blatt 4312
\blatt 3124

\blatt 1432
\blatt 4321
\blatt 3214
\blatt 2143

\blatt 1423
\blatt 4231
\blatt 2314
\blatt 3142

\blatt 1342
\blatt 3421
\blatt 4213
\blatt 2134

\blatt 1324
\blatt 3241
\blatt 2413
\blatt 4132
}

\blatt 2134
\end{document}


\item ?? Iterator mit Vorgängerzeigern

Nehmen wir an, dass jeder Knoten eines binären Baumes auch einen
Vorgängerzeiger zur Mutter hat:
$$\vcenter{\begin{tabbing}
\qquad\=\+
\texttt{class Baum2 extends Baum}\\
{\texttt{\char`\{} } \={\tt Baum2 predecessor;}\\
\>$\cdots$
\end{tabbing}
}
$$
Implementieren Sie f"ur solche bin"aren Suchb"aume eine Methode,
die einen \emph{Iterator} mit den Methoden
\texttt{next()} und
\texttt{hasNext()} erzeugt.
Der Iterator darf nur konstant viel
zus"atzlichen Speicher ben"otigen.

\end{enumerate}

\end{document}

\alleperm

%\blatt 1234

