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

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


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

\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)
Das folgende Programm 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 (6 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)=\Theta(f(n))$ aus $f(n)=O(g(n))$?
\end{enumerate}

\item (7 Punkte) Beweisen Sie:
\begin{enumerate}
\item Wenn $f(n)=O(g(n))$ ist, dann ist $f(n)+g(n)=O(g(n))$.
\item $\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)$; \
\item
Finden Sie m"oglichst einfache Ausdr"ucke der Form $O(\cdot)$ f"ur
folgende Funktionen:\\
$3n^2 - 4n + 32 + 27\,n \cdot\lceil \log_2 n \rceil/2$; \quad
$\max\{n\lceil \log_2 n\rceil, (\lceil \log_2 n\rceil)^4 \}$; \quad
$2^{2n + \lceil \log_2 n\rceil}$
\end{enumerate}

\item (5 Punkte) 
Formulieren Sie \emph{Sortieren durch Auswahl} in
einer Programmiersprache Ihrer
Wahl.

\end{enumerate}
\end{document}

