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

 WS 2003/2004, Zwischenklausur
\hfill FAMILIENNAME: \vrule width 4cm height -2.5pt depth 3pt

Dienstag, 20. Januar 2004.
\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
\hrule
\medskip


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

\newbox\prog
\setbox\prog=\vbox{
\begin{verbatim}
int [ ] count = new int[m+1];
for (int j=1; j<=m; j++) count[j]=0;
for (int i=0; i<n;  i++) count[a[i]]++;
int i=0;
for (int j=1; j<=m; j++)
     for (int k=0; k<count[j]; k++)  {a[i]=j; i++;}
\end{verbatim}}

\newbox\progg
\setbox\progg=\vbox{
\begin{verbatim}
int anz(int[ ] a, int[ ] b, int n) { return anz2(a,b,n,0); }
int anz2(int[ ] a, int[ ] b, int n, int s)
{ if(n==0) return s;
  if(a[n-1]==b[n-1]) return anz2(a,b,n-1,s+1);
  return anz2(a,b,n-1,s);
}
\end{verbatim}}

\long\def\aufgabe #1{\ifcase #1\or
%\item %(10 Punkte)

Eliminieren Sie die Endrekursion aus dem folgenden Programmstück,
das die Anzahl der übereinstimmenden Elemente in zwei Vektoren
\texttt{a[0]}, \dots, \texttt{a[n-1]} und
\texttt{b[0]}, \dots, \texttt{b[n-1]} zählt.
Gehen Sie dabei systematisch Schritt für Schritt vor.
Schreiben Sie eine einzige Methode als Ersatz für \texttt{anz}.
\\
\noindent\copy\progg


\or % \item %(10 Punkte)

Man möchte einen binären Baum wie bei einer Halde als
\emph{array} speichern: Die Kinder des Knotens $\texttt{a[i]}$ stehen
an den Stellen $\texttt{a[2*i]}$ und $\texttt{a[2*i+1]}$.
Nehmen Sie an, dass die Bäume (im Gegensatz zu einer Halde) nicht
ausgeglichen sein müssen.
Bestimmen Sie die notwendige Größe des Arrays zum Speichern von
$n$ Elementen in Abhängigkeit von $n$,
\begin{enumerate}
\itemsep=0pt
\item wenn der Baum die Höhe $2\lceil \log n \rceil$ hat,
\item im schlimmsten Fall,
\item wenn die Höhe des Baumes nur um 2 größer als die kleinstmögliche Höhe ist.
\end{enumerate}
Geben Sie außerdem an, in welchem dieser Fälle man mit $O(n)$ Speicher auskommt.
\or % \item
Sortieren:
Das folgende Programmstück soll $n$ verschiedene \texttt{int}-Zahlen
zwischen 1 und $m$ sortieren, die in einem Array
\texttt{a[0]}, \dots, \texttt{a[n-1]} gespeichert sind.
\\
\noindent\copy\prog\\[-9mm]
\begin{enumerate}
\itemsep=0pt
\item Bestimmen Sie die asymptotische Laufzeit dieses Programms.
\item Warum muss man in der letzten Zeile in der Anweisung
\texttt{a[i]=j} keinen Überlauf des Indexes $i$ über die
Feldgrenzen von \texttt{a} befürchten?
Geben Sie eine ausführliche Begründung.
\item Funktioniert dieses Verfahren auch, wenn die Zahlen nicht
verschieden sind? Was muss man gegebenenfalls ändern, damit es
für diesen Fall funktioniert?
\end{enumerate}

\or % \item %(10 Punkte)

Schreiben Sie ein Programm in Java oder Haskell,
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
}

\blatt 2134
\end{document}

\alleperm

%\blatt 1234
\end{document}

