% 2. 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}{3}
\begin{document}

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


\begin{enumerate}
\setcounter{enumi}{9}

\item (4 Punkte)
Was passiert bei 
\emph{Sortieren durch Einf"ugen}, wenn
die gegebene Folge bereits (a) aufsteigend oder (b) absteigend
sortiert ist? (c) Was passiert, wenn alle Elemente gleich sind?
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)
Nehmen wir an, wir haben ein Liste mit $n$ sortierten Elementen,
gefolgt von $k$ Elementen in beliebiger Reihenfolge.
Welchens Sortierverfahren empfehlen Sie zum Sortieren der Gesamtliste für
\begin{enumerate}
\item $k=\Theta(1)$,
\item $k=\Theta(\log n)$,
\item $k=\Theta(\sqrt n)$?
\end{enumerate}

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

\item (0 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\footnotemark\
k"onnte man ohne Nachteil einsparen?
\setcounter{footnote}{0}

\item (5 Punkte)
Erweitern Sie den Algorithmus  zum topologischen Sortieren aus der
Vorlesung,
sodass bei der Existenz eines Kreises nicht einfach mit
einer Meldung abgebrochen wird, sondern auch ein
Kreis (als "`Beweis"') ausgegeben wird.

Beschreiben Sie Ihren erweiterten Algorithmus auf der Ebene von Pseudo-Code.
(Zum Beispiel können Sie eine Schleife ``für alle Elemente $x$ \dots''
schreiben.)

Erklären Sie Ihren Algorithmus \emph{in Worten}, ohne
notwendigerweise auf Details der Implementierung einzugehen.
(Sie müssen nur das erklären, was gegenüber dem ursprünglichen
Algorithms neu ist. Ein Korrektheitsbeweis ist nicht verlangt.)

\item (6 Punkte)
Schreiben Sie ein Java-Programm für die vorige Aufgabe.
Sie können das Programm aus der Vorlesung%
\footnote{%siehe die Programme aus der Vorlesung,
\texttt{http://www.inf.fu-berlin.de/\char`\~rote/Lere/2003-04-WS/Algorithmen+Programmierung3/TopoSort.java}}
erweitern.

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

\end{enumerate}
\end{document}
