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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 7. November 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{Simultanes Minimum und Maximum}{10 Punkte}

\begin{enumerate}
  \item Sei $A$ eine Folge von $n$ vergleichbaren Elementen.
    Geben Sie einen einfachen Algorithmus zum 
    Finden des Minimums und des Maximums von $A$. 
    Bestimmen Sie die erforderliche Anzahl von Vergleichen 
    als Funktion von $n$
    exakt.
  \item L\"osen Sie das gleiche Problem mit dem Teile-und-Herrsche
    Prinzip, indem Sie $A$  in zwei H\"alften zerlegen, falls $n \geq 2$ ist. 
    Bestimmen Sie die ben\"otigte Anzahl der Vergleiche exakt. 
    Sie d\"urfen dabei annehmen, dass $n$ eine Zweierpotenz ist.
\end{enumerate}

\AUFGABE{Einfache Datenstrukturen in Java}{10 Punkte}

\begin{enumerate}
\item
  Betrachten Sie das folgende Interface f\"ur einen Stapel.
  \begin{verbatim}
    public interface Stack<E> {
      void push(E element) throws StackFullException;
      E pop() throws StackEmptyException;
      E top() throws StackEmptyException;
      int size();
      boolean isEmpty();
    }
  \end{verbatim}
  Schreiben Sie eine Klasse \texttt{ArrayStack}\textless\texttt{E}\textgreater, 
  eine Klasse \texttt{ListStack}\textless\texttt{E}\textgreater{} und
  eine Klasse
  \texttt{DynamicArrayStack}\textless\texttt{E}\textgreater. 
  Die drei Klassen sollen \texttt{Stack} implementieren,
  jeweils mit einem Feld fester L\"ange, mit einer verketteten Liste und
  mit einem dynamisch wachsenden Feld. Achten Sie auf eine geeignete
  Fehlerbehandlung und testen Sie Ihre Implementierung mit
  verschiedenen Eingaben.
\item
 Schreiben Sie ein Programm, welches f\"ur
 beliebige Zeichenketten, die verschiedene
 Klammern enthalten, \"uberpr\"uft, ob sie 
 korrekt geklammert sind. Erlaubte Klammertypen sind (), [], 
 \textless\textgreater 
 und \{\}. 
 Verwenden Sie eine geeignete Datenstruktur.
 Zum Beispiel ist ``(A)\{L[P]3\}'' korrekt geklammert,
 nicht aber ``(A)\{L[P\}3]'' und ``(A)\{L[P3''.

 \emph{Hinweis}: Einzelne Zeichen eines Strings bekommt man in Java mit 
   \texttt{charAt}.

\end{enumerate}

\newpage
\AUFGABE{Amortisierte Analyse}{10 Punkte}

Gegeben sei ein elektrisches Bin\"arz\"ahlwerk mit beliebig vielen
Ziffern aus der Menge $\{0,1\}$. Das Umschalten einer Ziffer kostet
eine Stromeinheit. Wie viele Stromeinheiten kostet es insgesamt,
wenn das Z\"ahlwerk von $0$ bis $n$ aufsteigend z\"ahlt?

\begin{enumerate}
  \item Verwenden Sie die Buchhaltermethode, um zu zeigen,
      dass die Gesamtkosten $O(n)$ sind.
  \item Berechnen Sie die Stromkosten exakt unter der Annahme,
      dass $n$ eine Zweierpotenz ist.
\end{enumerate}

\end{description}
\end{document}
