%  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=1
\begin{centering}
{\large \bf Algorithmen und Programmieren 3
\hfill Matrikelnummer: \vrule width 3cm height -2.5pt depth 3pt

 WS 2003/2004, Zwischenklausur
\hfill NAME: \vrule width 5cm height -2.5pt depth 3pt
\par}
\bigskip
Abgabe bis Dienstag, 16. Dezember 2003
\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{Schreiben Sie jede Aufgabe auf ein getrenntes Blatt.}
Jede Aufgabe hat 10 Punkte.
\hrule
\medskip


\begin{enumerate}
\item \aufgabe #1
\item \aufgabe #2
\item \aufgabe #3
\item \aufgabe #4
\end{enumerate}
\eject
}

\newbox\prog
\setbox\prog=\vbox{
\begin{verbatim}
int [ ] pos = new int[n];
for (int i=0; i<n; i++) { // Zähle Elemente kleiner als a[i]:
    pos[i] = 0;
    for (int j=0; j<n; j++)
        if (a[j]<a[i]) pos[i]++;
    // pos[i] ist die Position von a[i] in der sortierten Reihenfolge.
}
// In die richtige Reihenfolge umordnen:
for (int i=0; i<n; i++) a[pos[i]] = a[i];
\end{verbatim}}

\long\def\aufgabe #1{\ifcase #1\or
%\item %(10 Punkte)
Ein binärer Suchbaum soll Einträge speichern, die außer dem Schlüssel $x_i$
noch ein "`Gewicht"' $w_i$ enthalten.
 Die Algorithmen zum Suchen, Einf"ugen und
L"oschen in bin"aren Suchb"aumen sollen so erweitert werden,
dass man jederzeit zu
% zwei Werten $a$ und $b$
 einem Wert $a$
das Gesamtgewicht aller Einträge finden kann,
 deren Schlüssel
% $x$
% im Intervall $a< x\le b$ liegt.
 $x\fergl a$ ist.

Die %benötigte
 Laufzeit für alle Operationen soll höchstens proportional zur
H"ohe des Baumes sein.

Beschreiben Sie die Felder, die in den Knoten enthalten sind
(zusammen mit einer Erklärung der Bedeutung, sofern sie nicht offensichtlich ist),
und ein
Programmstück (eine oder mehrere Methoden in Java oder Funktionen in Haskell), das die Intervallabfrage durchführt.
(Einfügen und Löschen müssen Sie \emph{nicht} programmieren.)

\or % \item %(10 Punkte)
Programmieren Sie eine \emph{stabile} Variante von Sortieren durch
Verschmelzen (\emph{mergesort}) in Java oder Haskell.
Erläutern Sie die Stellen im Programm, die für die Stabilität wichtig sind.

\or % \item
Sortieren durch Zählen:\\
Das folgende Programmstück soll $n$ verschiedene \texttt{double}-Zahlen sortieren, die in einem Array
\texttt{a[0]}, \dots, \texttt{a[n-1]} gespeichert sind,
mit  Hilfe eines Arrays \texttt{pos[i]}, das die
Anzahl der Elemente zählt, die kleiner als \texttt{a[i]} sind.

\noindent\copy\prog
\begin{enumerate}
\item Was ist der Speicherbedarf und die asymptotische Laufzeit dieses
  Programmes?
\item Warum funktioniert dieses Programm nicht richtig?
Geben Sie ein Beispiel an, bei dem
das Array \texttt{a[0]}, \dots, \texttt{a[n-1]} am Ende
\emph{nicht aufsteigend sortiert} ist.
\item Stellen Sie das Programm richtig,
sodass am Ende die sortierten Zahlen in \texttt{a[0]}, \dots, \texttt{a[n-1]} stehen,
 ohne dass die
 die asymptotische Laufzeitschranke in Aufgabe~(a) überschritten wird.
\item Was passiert, wenn die Eingabe gleiche Werte enthält?\\
Erstellen Sie eine Variante des Programms, die auch solche Eingaben sortiert.
%stabil sortiert, ...
\end{enumerate}
%}

\or % \item %(10 Punkte)
Beweisen Sie:
Ein bin"arer Baum mit $n$ Bl"attern hat mindestens $n-1$ innere Knoten.
(Innere Knoten haben 1 oder 2 Kinder, und Blätter haben keine Kinder.)
Sie dürfen nicht einfach die Aussage von Übung 31 über volle binäre Bäume
verwenden, aber Sie dürfen die Lösung (den Beweis) dieser Aufgabe anpassen.

% \item (10 Punkte)
% Schreiben Sie ein Programm in Java oder Haskell oder C oder C++,
% das f"ur einen gegebenen bin"aren Suchbaum die \emph{mittlere innere Wegl"ange}
% berechnet; sie ist um 1 kleiner als die erwartete Anzahl
% von Vergleichen, die zum Finden eines zuf"allig ausgew"ahlten
% Knotens in dem Baum im Durchschnitt erforderlich sind.
% (Jeder Knoten wird mit gleicher Wahrscheinlichkeit gesucht.)
\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
}

\def\fergl{<}\blatt 1234
\end{document}

\def\fergl{<}
\alleperm
\def\fergl{>}
\alleperm
\def\fergl{\ge}
\alleperm
\def\fergl{\leq}
\alleperm

%\blatt 1234
\end{document}

