% 4. Uebungsblatt ALP3 WS 2003/04
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
\usepackage {ngerman}
\textwidth=16,1cm
\textheight=25cm
\hoffset = -17mm
\voffset = -30mm

\setcounter{page}{5}
\begin{document}

\begin{centering}
{\large \bf Algorithmen und Programmierung 3, WS 2003/2004 ---
 4.~\"Ubungsblatt\par}
\bigskip
Abgabe bis Donnerstag, 20. November 2003
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{22}

\item (15 Punkte)\label{hash}
Eine hash-Funktion zum Speichern ungeordneter Paare.\\
Finden Sie $n$ ganze Zahlen $t_1,\ldots,t_n$, sodass alle Summen
$t_i+t_j$ für $1\le i<j\le n$ verschieden sind und in einem möglichst
kleinen Intervall $\{a,a+1,\ldots,b\}$ enthalten sind,
für $n=5,6,7,8,9,10$. 

\item (3 Punkte)
 Speichern ungeordneter Paare in einem Array.
 \begin{enumerate}
 \item (0 Punkte)
Wie kann man die Lösung der vorigen Aufgabe dazu verwenden,
für eine feste Liste von $n$ Objekten
die Paare, die man aus je zwei dieser Objekte bilden kann,
möglichst kompakt zu verwalten und zu speichern
(wie in einer Hash-Tabelle), sodass man in
konstanter Zeit auf jedes Paar $\{u,v\}$ zugreifen kann, wenn man $u$
und $v$ kennt?
\item (3 Punkte)
Wie kann man dieses Problem auf andere Art mit einem Array der (optimalen) Länge $n(n+1)/2$ lösen?
 \end{enumerate}
\item (0 Punkte) Bestimmen des doppelten Elementes.\\
In einem Array $a_0,a_1,\ldots,a_n$ sind ganzzahlige Werte
zwischen 1 und $n$ gespeichert, und zwar kommt jede Zahl mindestens
einmal vor.
Daraus folgt, dass es genau eine Zahl geben muss, die doppelt vorkommt.
Schreiben Sie ein Programm, das diese Zahl bestimmt.
Das Programm soll lineare Laufzeit haben, auf das Array $a$ nur \emph{lesend}
zugreifen, und nur konstanten zusätzlichen Speicher benötigen.%
%
\footnote{Diese Aufgabe dient nur zur Unterhaltung und hat mit dem
  Stoff der Vorlesung nichts zu tun. Wenn Sie das Rätsel aus einer
  anderen Quelle bereits kennen, dann würde mich sehr interessieren,
  woher.}


 \item (0 Punkte) \label{hash2}
Lösen Sie Aufgabe~\ref{hash}
für \emph{geordnete} Paare:
Finden Sie $2n$ ganze Zahlen $s_1,\ldots,s_n$ und
$t_1,\ldots,t_n$ 
sodass alle Summen
$s_i+t_j$ für $1\le i,j\le n$ verschieden sind und in einem möglichst
kleinen Intervall $\{a,a+1,\ldots,b\}$ enthalten sind.

 \item Zusatzaufgabe (3 Zusatzpunkte).
Finden Sie eine Formel für $t_i$ in Aufgabe~\ref{hash},
die das Problem für allgemeines $n$ löst (nicht unbedingt optimal
in dem Sinn, dass das enthaltende Intervall kleinstmöglich ist).
Analysieren Sie die Länge des enthaltenden Intervalls bei Ihrer
Methode.
(Für die beste abgegebene Formel gibt es bis zu 10 weitere Zusatzpunkte.)
%
% \item (0 Punkte) 
%Lösen Sie die vorige Aufgabe auch für das Problem
% aus Aufgabe~\ref{hash2}.
(Die gleiche Frage kann man natürlich auch für die geordneten Paare %das Problem
 aus Aufgabe~\ref{hash2} stellen.)

\item (5 Punkte)
Entfernen Sie die Endrekursion aus der Methode \texttt{zugroß} im
Programm zur Verwaltung einer Halde.\footnote{Siehe Aufgabe 21
und das Heapsort-Programm aus der Vorlesung:\\
  \texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/heapsort.java}}
\begin{quote}
  \begin{verbatim}
void zugroß(int i)
// a[i] ist möglicherweise größer als seine Nachfolger.
{   int kleinsterNachfolger;
    if (2*i+1 <= n) {
        if (a[2*i]<a[2*i+1]) kleinsterNachfolger = 2*i;
        else                 kleinsterNachfolger = 2*i+1;
    }
    else if (2*i <= n) kleinsterNachfolger = 2*i;
    else return;
    if (a[i] > a[kleinsterNachfolger]) {
        vertausche(i, kleinsterNachfolger);
        zugroß(kleinsterNachfolger);
    }
}
\end{verbatim}
\end{quote}


\end{enumerate}
\end{document}
