% 2. Uebungsblatt ALP3 WS 1999/2000
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\textwidth=16,1cm
\textheight=25cm
\hoffset = -17mm
\voffset = -20mm

\setcounter{page}{2}
\begin{document}

\begin{centering}
{\large \bf Algorithmen
und Programmieren 3, WS 1999/2000 ---
 2.~\"Ubungsblatt\par
}
\bigskip
Abgabe bis Dienstag, 9. November 1999
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{6}

\item (3 Punkte)
Was passiert bei 
\emph{Sortieren durch Einf"ugen}, wenn
die gegebene Folge bereits (a) aufsteigend oder (b) absteigend
sortiert ist?
Ist es m"oglich, dass man blo"s $O(n)$ Zeit ben"otigt?

\item (2 Punkte)
Beantworten Sie die vorige Frage f"ur
\emph{Sortieren durch Auswahl}.

\item (0 Punkte)
Nehmen wir an, dass die Eingabefolge \emph{fast sortiert} ist.
Das hei"st, dass jedes Element in der Ausgangsreihenfolge
h"ochstens $k$ Stellen von der endg"ultigen Position in
der sortierten Reihenfolge entfernt ist.
Geben Sie eine Schranke f"ur die Laufzeit von
\emph{Sortieren durch Einf"ugen} in Abh"angigkeit von $n$ und $k$ an.

\item (0 Punkte)
Wie kann man
\emph{Sortieren durch Einf"ugen} so anpassen, dass es f"ur
Folgen, die absteigend oder fast absteigend sortiert sind,
m"oglichst schnell l"auft?

\item (2 Punkte)
Geben Sie alle m"oglichen topologischen Sortierungen f"ur
folgende Eingabe an:
$n=6$ und $\{(6,1), (3,5), (1,4), (3,1), (2,4), (2,6), (5,1), (3,6)\}$.
% Wieviele sind es?

\item (2 Punkte)
Was passiert beim in der Vorlesung angegebenen Algorithmus f"ur
\emph {Topologisches Sortieren}, wenn ein Paar
$(i,j)$  in der Eingabe mehrfach auftritt?
Was passiert, wenn ein Paar $(i,i)$ auftritt?

\item (0 Punkte)
Untersuchen Sie verschiedene M"oglichkeiten, wie man
die Liste der freien Elemente beim topologischen
Sortieren verwalten kann, im Hinblick auf ihre Effizienz.
Kann man auf diese Liste auch g"anzlich verzichten?

Welche Variablen oder Felder im Programm aus der Vorlesung
k"onnte man ohne Nachteil einsparen?

\item (8 Punkte)
Erweitern Sie das Java-Programm zum topologischen Sortieren,
sodass bei der Existenz eines Kreises nicht einfach mit
einer Meldung abgebrochen wird, sondern auch ein
Kreis (als "`Beweis"') ausgegeben wird.

Ihr Programm sollte nicht mehr als $O(m+n)$ zus"atzliche
Zeit und nicht mehr als $O(n)$ zus"atzlichen Speicher brauchen.

\item (8 Punkte)
Es gibt eine Variante von \emph{Sortieren durch Verschmelzen} (mergesort),
die von unten nach oben (\emph{bottom-up}) arbeitet:
Zun"achst werden je zwei aufeinanderfolgende Elemente zu einem
Paar zusammengefasst und gegebenenfalls vertauscht, sodass eine
Folge von sortierten Zweierbl"ocken entsteht.
Dann werden je zwei benachbarte Zweierbl"ocke zu einem
sortierten Viererblock verschmolzen, diese werden wiederum
paarweise zu Achterbl"ocken verschmolzen, usw.

\begin{enumerate}
\item (4 Punkte)
Schreiben Sie ein Programm f"ur dieses Sortierverfahren in
Haskell oder Java\footnote{oder in C oder C++ oder Pascal. 
Weitere Programmiersprachen
auf Anfrage}.
\item (4 Punkte)
Analysieren Sie die Laufzeit dieses Algorithmus.
\item (0 Punkte)
Falls Sie f"ur Aufgabe (a) nicht Haskell gew"ahlt haben,
analysieren Sie auch den \emph{zus"atzlichen} Speicherbedarf
(zus"atzlich zu dem Feld, in dem die zu sortierenden Elemente
am Anfang stehen).
Falls Sie f"ur Aufgabe (a) Haskell gew"ahlt haben,
erkl"aren Sie, warum Sie die obige Frage nicht
beantworten m"ussen.
\end{enumerate}

\item (0 Punkte)
Entwerfen Sie eine bottom-up-Variante von Quicksort.
\end{enumerate}
\end{document}
