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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{am 3. November~2017 bis 10 Uhr 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, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{D\"unn besetzte Polynome}{10 Punkte}

In der Vorlesung haben wir zwei M\"oglichkeiten gesehen,
um Polynome von Grad $n$ darzustellen.
Die Koeffizientendarstellung wird ineffizient, wenn viele
Koeffizienten des Polynoms $0$ sind (so genannte 
\emph{d\"unn besetzte Polynome}). Entwickeln Sie eine 
effiziente Darstellung f\"ur solche Polynome und beschreiben 
Sie Algorithmen zum Addieren, Multiplizieren und Auswerten in 
Ihrer Darstellung.
Analysieren Sie die Effizienz Ihrer Algorithmen in Abh\"angigkeit 
von dem Grad $n$ des Polynoms und von der Anzahl $k$ der 
Koeffizienten, die nicht Null sind.

\emph{Zusatzaufgabe (5 Punkte)}: Implementieren Sie Ihre Datenstruktur 
  in Java oder Python.



\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 worst-case
Laufzeit $\Theta(n^2)$  und ein Algorithmus mit worst-case
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 jeweils mindestens zehn verschiedene zuf\"allige Eingaben 
f\"ur mindestens hundert verschiedene Eingabegr\"o\ss{}en ben\"otigen. 
Bereiten Sie die Ergebnisse graphisch auf.

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}
