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

\newcommand{\ZETTELNUMMER}{4}
\newcommand{\ABGABEDATUM}{am 14. 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{Java-Drill}{15 Punkte}

\begin{enumerate}
  \item  
    Geben Sie jeweils zwei Schluesselw\"orter in Java, welche die 
    Konzepte \emph{Kapselung} und
    \emph{Vererbung} umsetzen.
  \item 
    Nennen Sie drei Arten von \emph{Polymorphie}, die in Java vorkommen,
    und geben Sie jeweils ein kurzes Beispiel. 
  \item
    Beschreiben Sie in zwei S\"atzen, was \emph{Annotationen} in Java sind.
    Was tut die \texttt{@Override} Annotation? Warum w\"urde man sie
    einsetzen?
  \item
    Was ist der Unterschied zwischen dem dynamischen und dem statischen
    Typ einer (Referenz-)Variable?
  \item
  Gegeben seien die folgende Schnittstelle und Klassen.

\begin{verbatim}
interface I {
  void a();
}
class A implements I {
  public void a() { System.out.println("A"); }
}
class B implements I {
  public void a() { System.out.println("B"); }
  public void b() { System.out.println("C"); }
}
\end{verbatim}

Kommentieren Sie f\"ur jede einzelne Zeile der folgenden \texttt{main}-Methode 
genau, ob diese erlaubt ist bzw. warum nicht. Streichen Sie fehlerhafte 
Zeilen, und geben Sie die Ausgabe des verbleibenden Programms an.
Geben Sie auch f\"ur jede Variable den statischen und die (evtl. wechselnden)
dynamischen Datentypen an.  Versuchen Sie, die Aufgabe ohne Rechner zu l\"osen.

\begin{verbatim}
public static void main(String[] args) {
  A a = new A();
  a.a();
  a.b();
  B b = new B();
  b.a();
  b.b();
  I i;
  i = new I();
  i = a;
  i.a();
  i.b();
  i = b;
  i.a();
  i.b();
  b = i;
  b = (B)i;
  a = (A)i;
}
\end{verbatim}

\item
Verfahren Sie wie bei (e) mit dem folgenden
Codefragment.
\begin{verbatim}
public static void main(String[] args) {
  List<?> x = new ArrayList<String>();
  List<Object> y = new ArrayList<Integer>();
  List<? extends Number> y2 = new ArrayList<Integer>();
  Object[] z = new Integer[3];
  z[2] = "ALP3"; 
}
\end{verbatim}
\
\end{enumerate}

\AUFGABE{Spezifizieren und Implementieren eines ADT}{10 Punkte}

Spezifizieren Sie sinnvoll
den abstrakten Datentyp
``double ended queue'', der das Einf\"ugen und L\"oschen von Objekten
an beiden Enden unterst\"utzt, und zwar auf zwei verschiedene Arten:
einmal verbal (versuchen Sie, m\"oglichst genau zu sein) und einmal
modellierend (mathematisch oder in Haskell).

Formulieren Sie ein entsprechendes Interface in Java, und
implementieren Sie den Datentyp auf zwei verschiedene Arten. 
Vergleichen Sie die Vor- und Nachteile Ihrer beiden
Implementierungen (bez\"uglich Laufzeit, Implementierungsaufwand, 
Flexibilit\"at, usw.).


\AUFGABE{Untere Schranken f\"ur Priorit\"atswarteschlangen}{5 Punkte}

\begin{enumerate}

\item
Zeigen Sie, wie man eine Priorit\"atswarteschlange verwenden kann,
um eine Folge von $n$ vergleichbaren Elementen zu sortieren. 
\item
Aus ALP2 wissen Sie, dass jeder vergleichsbasierte Sortieralgorithmus
mindestens $\Omega(n \log n)$ Operationen ben\"otigt. 
Folgern Sie, dass in jeder vergleichsbasierte Implementierung 
der Priorit\"atswarteschlange
mindestens eine Operation $\Omega(\log n)$ amortisierte Laufzeit haben
muss.
\end{enumerate}

\end{description}
\end{document}
