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

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


\begin{enumerate}
\setcounter{enumi}{0}

\item
  \begin{enumerate}
  \item [(i)] (4 Punkte)
 Sortieren Sie die folgenden Laufzeiten aufsteigend. (Wenn
  $f(n)=O(g(n))$ ist, aber nicht $g(n)=O(f(n))$, dann soll $f(n)$ vor
  $g(n)$ kommen.)
$$
\textrm{(a) }
n^3
\textrm{\quad(b) }
\log_2 n
\textrm{\quad(c) }
1{,}8^n
\textrm{\quad(d) }
n
\textrm{\quad(e) }
3^n
\textrm{\quad(f) }
\sqrt n
\textrm{\quad(g) }
n(\log_2 n)^2
\textrm{\quad(h) }
n^2
%\textrm{\quad(a) }
%n\log_2 n
$$
  \item [(ii)] (4 Punkte)
Wenn ein Programm die Laufzeit $f(n)$ aus Aufgabe (i) hat und die
Computer in zehn Jahren um den Faktor 1000 schneller werden, dann kann
man Probleme \emph{welcher Größe} in derselben Zeit lösen, in der man
heute Probleme der Größe (1)~$n=20$, (2)~$n=1000$ lösen kann?
  \end{enumerate}

\item (2 Punkte)
Die Computer werden immer schneller, die Speicherelemente immer billiger.
Wird der Entwurf von effizienten Algorithmen angesichts dieser Entwicklung in
Zukunft an Bedeutung verlieren?
Bei welchen Computeranwendungen werden Effizienzfragen eine
gr"o"sere/kleinere Rolle spielen?

Diskutieren Sie diese Fragen. (mindestens  5--10 Zeilen)

\item (0 Punkte) \label{insert}
Das folgende Programmstück ist ein Versuch,
Sortieren durch Einf"ugen zu implementieren.
\def\st{$^\dag$}
{\tt
\begin{tabbing} \qquad\=\+
void insertionSort(int[] a)\\
\char`\{\ \=\+int x;\\
for (int i = 0; i\char`< a.length; i++)\\
\char`\{\ \=\+\st\ x = a[i];\\
{\rm // Sortiere {\tt x} zwischen {\tt a[0..i-1]} ein}\\
{\rm // Bestimme zun"achst die richtige Position {\tt j}:}\\
\llap{$({*})$ \qquad }int j=i-1;
    \st\ while (j\char`>=0 \&\& a[j-1]\char`> x) j-- \st\ ;\\
{\rm // Nun verschiebe einen Teil des Feldes und
f"uge {\tt x} an dieser Stelle ein:}\\
\llap{\st\ }for (int k = i-1; k\char`>=j; k--) a[k+1]=a[k];\\
a[j]=x; \st \-\\
\char`\}\-\\
\char`\}
\end{tabbing}
}
Stellen Sie dieses Programm richtig und f"ugen Sie an den
durch \st\ bezeichneten Stellen in Ihrem Programm Schleifeninvarianten
in der Form vom Zusicherungen (assertions)
ein, aus denen die Korrektheit des Programmes hervorgeht.
(Ein formaler Beweis ist nicht erforderlich, aber die Zusicherungen
m"ussen aussagekr"aftig sein und vor allem zutreffen.)

\item (0 Punkte)
Kann man Sortieren durch Einf"ugen schneller machen, indem man
die Einf"ugestelle {\tt j} schneller findet als oben in Zeile ($*$), zum Beispiel
durch bin"ares Suchen?
Wie ist es im besten und im schlechtesten Fall?

\item (0 Punkte) Zeigen Sie:
\begin{enumerate}
\item Wenn $f(n)=a_d n^d + a_{d-1} n^{d-1} + \cdots + a_1 n + a_0$
ein Polynom vom Grad $d$ mit positivem Leitkoeffizienten ($a_d>0$) ist,
dann ist $$f(n) = \Theta(n^d).$$
\item $\log_a n = \Theta(\log_b n)$ f"ur $a,b>1$.
\item Unter welchen Bedingungen folgt $g(n)=\Omega(f(n))$ aus $f(n)=O(g(n))$?
\end{enumerate}

\item (0 Punkte)
 Welche der beiden folgenden Laufzeiten $f(n)$ und $g(n)$ ist für
  große Werte von $n$ schneller, und welche für kleine $n$?
Bei welchem Wert von $n$ ändert sich die Antwort?
\begin{enumerate}
\item $f(n)= 10n (\log_2 n)^2$, $g(n)=2n^{3/2}$
\item $f(n)=5\cdot 2^n$, $g(n)=100n^2\log_2 n$
\end{enumerate}


\item (0 Punkte)
\begin{enumerate}
\item  Beweisen Sie: Wenn $f(n)=O(g(n))$ ist, dann ist $f(n)+g(n)=O(g(n))$.
\item  Beweisen Sie: $\max\{f(n), g(n)\} = \Theta(f(n)+g(n))$ f"ur $f(n),g(n)>0$.
\item
Welche der folgenden Aussagen sind richtig (Begr"unden Sie Ihre Antworten):\\
$n\sqrt n = O(n (\log n)^2)$; \
$n (\log n)^2 = O(n\sqrt n )$; \
$n \log n \cdot (\log\log n) = O(n^2)$; \\
$n^2 = O(n \log n \cdot (\log\log n))$; \
$n^2 \cdot 2^n = O(2^{n+2})$; \
$n^2 \cdot 2^n = O(3^n)$; \
$3^n = O(n^2 \cdot 2^n)$; \
\end{enumerate}

\item (4 Punkte)
Finden Sie m"oglichst einfache Ausdr"ucke der Form $\Theta(\cdot)$ f"ur
folgende Funktionen:\\
(a) $3n^2 - 4n + 32 + 27\,n \cdot\lceil \log_2 n \rceil/2$; \quad
(b) $\max\{n\lceil \log_2 n\rceil, (\lceil \log_2 n\rceil)^4 \}$; \quad
(c) $2^{2n + \lceil \log_2 n\rceil}$

\item (6 Punkte) 
Formulieren Sie \emph{Sortieren durch Auswahl} in
Java (als Methode wie in Aufgabe~\ref{insert}) oder in Haskell (als
lauf"|fähige Funktion).

\end{enumerate}
\end{document}
