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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{am 19. Dezember 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{$(2,3)$-B\"aume}{10 Punkte}

\begin{enumerate}
\item F\"ugen Sie die Schl\"ussel A, L, P, D, R, E, I, X, Y, Z
  in dieser Reihenfolge in einen anfangs leeren $(2,3)$-Baum ein.
  Zeigen Sie die einzelnen Schritte. L\"oschen Sie sodann die 
  Schl\"ussel A, L, X.
\item Beschreiben Sie schematisch einen $(2,3)$-Baum mit $n$ Schl\"usseln, so
  dass eine L\"oschoperation $\Omega(\log n)$ Rebalancierungsoperationen
  ben\"otigt.
\end{enumerate}


\AUFGABE{$(a,b)$-B\"aume}{10 Punkte}
\begin{enumerate}
\item Beschreiben Sie, wie man in einem $(a,b)$-Baum mit $n$ Schl\"usseln die
  Operation \texttt{findRange}($k_1 , k_2$) implementieren kann, die alle Schl\"ussel $k$ liefert, 
  f\"ur die $k_1 \leq k \leq k_2$ ist. Die Laufzeit soll $O(b\log_a n + s)$ betragen.
  Dabei ist $s$ die Anzahl der gelieferten Schl\"ussel.
\item Seien $T_1$ und $T_2$ zwei $(a,b)$-B\"aume, und sei $S_1$ die Schl\"usselmenge von
  $T_1$ und $S_2$ die Schl\"usselmenge von $T_2$. Alle Schl\"ussel in $S_1$ sind kleiner
  als alle Schl\"ussel in $S_2$.
  Beschreiben Sie eine Operation \texttt{join},
  die aus $T_1$ und $T_2$ einen $(a,b)$-Baum f\"ur die Schl\"usselmenge
  $S_1 \cup S_2$ erzeugt. Die Laufzeit sollte $O(b \log_a \max \{|S_1|, |S_2|\})$ betragen.

  \emph{Hinweis}: Betrachten Sie zun\"achst den Fall, dass $T_1$ und $T_2$ die
    gleiche H\"ohe haben. Achten Sie darauf, dass hinterher die $(a,b)$-Baum-Eigenschaften
    wieder hergestellt werden.
\end{enumerate}
\
\AUFGABE{Gieriges M\"unzwechseln}{10 Punkte}
 
Betrachten Sie das Problem des M\"unzwechselns an der
Supermarktkasse. Es soll ein Betrag von $n$ Cents herausgegeben
werden, wobei die minimale Anzahl an M\"unzen verwendet werden soll.
Zur Erinnerung: es gibt Euro-M\"unzen f\"ur
1, 2, 5, 10, 20, 50, 100 und 200 Cent.

\begin{enumerate}
\item Beschreiben Sie einen gierigen Algorithmus f\"ur das Problem,
  und implementieren Sie ihn in Java. Was ist die Laufzeit des Algorithmus?
\item
  Beweisen Sie, dass Ihr Algorithmus aus (a) eine optimale L\"osung liefert.

  \emph{Hinweis:} Machen Sie sich Gedanken \"uber die Struktur einer optimalen
    L\"osung: Wie viele 1-Cent M\"unzen kann eine optimale L\"osung 
    h\"ochstens enthalten? Wie viele 2-Cent M\"unzen? usw?

\item Geben Sie ein Beispiel von M\"unzwerten, so dass der gierige
  Algorithmus nicht optimal ist. Dabei sollte es eine 1-Cent M\"unze
  geben, so dass sich jeder Betrag auch wechseln l\"asst.

%\item Seien $c > 1$ und
%  $k \geq 1$ nat\"urliche Zahlen, und nehmen Sie an, Sie haben M\"unzen
%  mit Werten $1, c, c^2, \ldots, c^k$. Beweisen Sie, dass der gierige 
%  Algorithmus auch in diesem Fall die minimale Anzahl von M\"unzen verwendet.
%
%  \emph{Hinweis:} Zeigen Sie zun\"achst, dass in einer optimalen L\"osung 
%    kein M\"unzwert, au\ss{}er eventuell $c^k$, \"ofters als $c-1$ mal 
%    vorkommt. Nehmen Sie nun an, dass der gierige Algorithmus nicht optimal
%    ist, und betrachten Sie den gr\"o\ss{}ten M\"unzwert $c^i$, bei dem sich 
%    die gierige und die optimale L\"osung unterscheiden. Argumentieren Sie,
%    dass dann die gierige L\"osung mehr M\"unzen vom Wert $c^i$ nimmt als
%    die optimale L\"osung. Beachten Sie nun, dass 
%    $(c-1)\sum_{j=0}^{i-1}c^j = c^i -1$ ist.
\end{enumerate}


\end{description}
\end{document}
