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

\newcommand{\ZETTELNUMMER}{3}
\newcommand{\ABGABEDATUM}{am 10. 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{O-Notation}{10 Punkte}
\begin{enumerate}
  \item  
  Sortieren Sie die folgenden Laufzeiten aufsteigend. (Wenn
  $f(n) \in O(g(n))$, aber nicht $g(n) \in O(f(n))$, dann soll $f(n)$ vor
  $g(n)$ stehen.) Erkl\"aren Sie Ihre Antwort.
\[
\text{(1) }
n^3
\text{\quad(2) }
\log_2 n
\text{\quad(3) }
1{,}8^n
\text{\quad(4) }
n
\text{\quad(5) }
3^n
\text{\quad(6) }
\sqrt n
\text{\quad(7) }
n(\log_2 n)^2
\text{\quad(8) }
n^2
\]
\item  
Angenommen, ein Programm hat Laufzeit $f(n)$, wobei $f(n)$ eine
von Ihnen gew\"ahlte Funktion aus Teil (a) ist. Nehmen Sie weiter an, 
dass in 
zehn Jahren die Rechner 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{Simultanes Minimum und Maximum}{10 Punkte}

\begin{enumerate}
  \item Sei $A$ eine Folge von $n$ paarweise vergleichbaren Elementen.
    Geben Sie einen einfachen, m\"oglichst effizienten Algorithmus zum 
    Finden des Minimums und des Maximums von $A$. 
    Bestimmen Sie die erforderliche Anzahl von Vergleichen im schlimmsten
    Fall 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 im
    schlimmsten Fall 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 den folgenden Entwurf f\"ur ein Interface f\"ur einen 
  Stapel.
  \begin{verbatim}
    public interface Stack<E> {
      void push(E element);
      E pop();
      E top();
      int size();
      boolean isEmpty();
    }
  \end{verbatim}
  Vervollst\"andigen Sie das Interface mit sinnvollen Ausnahmen.
  Schreiben Sie eine Klasse  
  \texttt{ListStack}\textless\texttt{E}\textgreater{} und
  eine Klasse
  \texttt{DynamicArrayStack}\textless\texttt{E}\textgreater. 
  Die zwei Klassen sollen \texttt{Stack} implementieren,
  jeweils mit einer verketteten Liste und
  mit einem dynamisch wachsenden Feld. Achten Sie auf eine geeignete
  Fehlerbehandlung und Ausnahmen 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}.

\item \emph{(freiwillig, 5 Zusatzpunkte)}
Informieren Sie sich \"uber das Konzept des \emph{Modultests} (unit 
testing) und insbesondere \"uber das \emph{JUnit}-Framework.
Laden Sie das JUnit-Framework herunter und implementieren Sie
jeweils 5 Testcases f\"ur Ihre beiden Stapelimplementierungen aus (a) und
2 Testcases f\"ur Ihr Programm aus (b).
\end{enumerate}

\end{description}

\end{document}
