\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{amstext}
\usepackage{ngerman}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 31. Oktober 2013 vor der Vorlesung in 
                          die jeweiligen Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe \arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen und Programmierung III} \\[0.5ex]
\normalsize
Wolfgang Mulzer \hfill WiSe 2013/14

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{O-Notation}{10 Punkte}
\begin{enumerate}
  \item  
  Sortieren Sie die folgenden Laufzeiten aufsteigend. (Wenn
  $f(n) = O(g(n))$, aber nicht $g(n)=O(f(n))$, dann soll $f(n)$ vor
  $g(n)$ stehen.)
\[
\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
\]
\item  
Angenommen, ein Programm hat Laufzeit $f(n)$, wobei $f(n)$ eine
der Funktionen aus Teil (a) ist.
Nehmen Sie weiter an, dass in zehn Jahren die Computer 1000 mal schneller
sind als heute.
Probleme \emph{welcher Gr\"o\ss{}e} kann man dann in derselben Zeit l\"osen, die man
heute f\"ur Probleme der Gr\"o\ss{}e $n=20$ braucht?

\end{enumerate}


\AUFGABE{Experimentelles Sortieren}{10 Punkte}

Aus ALP2 kennen Sie diverse Sortierverfahren.
Suchen Sie sich drei davon aus,
und implementieren Sie diese in Java oder Python.
Dabei soll  ein Algorithmus mit
Laufzeit $\Theta(n^2)$  und ein Algorithmus mit
Laufzeit $\Theta(n \log n)$ vorkommen.
Testen Sie Ihre Implementierung mit zuf\"alligen Eingaben,
und geben Sie au\ss{}erdem f\"ur jeden Algorithmus eine
Klasse von Eingaben an, die einen ``Grenzfall'' darstellt.

Messen Sie die Millisekunden, die  Ihre Algorithmen 
f\"ur zuf\"allige Eingaben verschiedener Gr\"o\ss{}en ben\"otigen, und 
stellen Sie die Ergebnisse graphisch dar.

Diskutieren Sie Ihre Erkenntnisse. Was sind die jeweiligen Vorteile 
der Algorithmen, was die Nachteile? Welchen
Algorithmus w\"urden Sie unter welchen Umst\"anden verwenden?
Was sagen die Ergebnisse \"uber die O-Notation?

\AUFGABE{Die T\"urme von Hollywood}{10 Punkte}

Wahrscheinlich kennen Sie die Legende der T\"urme von 
Hanoi.

\noindent
\textit{
Im gro\ss{}en Tempel von Benares steht eine Blechplatte, auf der
drei vertikale Stangen aus Diamanten befestigt sind.
An diesen Stangen sind $n$ Scheiben aus massivem Gold angebracht,
mit $n$ verschiedenen Gr\"o\ss{}en. Am Anfang der Zeit hat der 
Gott Brahma alle Scheiben auf einer Stange abgelegt,
der Gr\"o\ss{}e nach sortiert, mit der gr\"o\ss{}ten Scheibe
ganz unten. Die Brahmanen im Tempel arbeiten unerm\"udlich
und transportieren die Scheiben von Stange zu Stange, wobei sie
jeweils nur eine Scheibe auf einmal verschieben und niemals eine gr\"o\ss{}ere
Scheibe auf eine kleinere Scheibe legen d\"urfen. Wenn alle 
Scheiben auf der letzten Stange angekommen sind, beginnt der 
Weltuntergang.
}

\begin{enumerate}
\item
Beschreiben Sie einen rekursiven Algorithmus, mit dessen
Hilfe die Brahmanen den Weltuntergang m\"oglichst schnell
herbeif\"uhren k\"onnen. 
Bestimmen Sie die ben\"otigte Anzahl der Verschiebeoperationen
genau. Wie viele Jahre m\"ussen wir auf den Weltuntergang warten,
wenn Brahma anfangs 100 Scheiben abgelegt hat und es einen Tag
dauert, um eine Scheibe zu verschieben?

\item
K\"urzlich wurde der Tempel nach Kalifornien verlegt, wo die
Brahmanen wesentlich l\"assiger zur Sache gehen.
Mittlerweile sind die Scheiben nur noch aus vergoldetem
Sperrholz, und die Stangen sind aus Plexiglas.
Vor allem aber wurde die Anforderung an die Reihenfolge
der Scheiben gelockert: die gr\"o\ss{}te Scheibe an einer Stange
muss immer noch ganz unten liegen, aber die Scheiben dar\"uber
k\"onnen in beliebiger Reihenfolge kommen. Zum Schluss m\"ussen
die Scheiben aber nat\"urlich wieder in der richtigen Ordnung
auf der letzten Stange angekommen sein.

Beschreiben Sie einen effizienten Algorithmus f\"ur das gelockerte
Problem.
Wie viele Verschiebeoperationen braucht Ihr Algorithmus
genau?
Wie viele Jahre m\"ussen wir jetzt auf den Weltuntergang warten,
wenn wir mit 100 Scheiben anfangen und es einen Tag
dauert, eine Scheibe zu verschieben?
\end{enumerate}

Credits: Diese Aufgabe habe ich bei Jeff Erickson gefunden.\\
\texttt{http://www.cs.uiuc.edu/\~{}jeffe/teaching/algorithms/hwex/s09/hw0.pdf}
\end{description}
\end{document}
