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

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

\begin{enumerate}
  \item  
    Geben Sie jeweils zwei Schl\"usselw\"orter in Java an, 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{O-Notation}{5 Punkte}

Entscheiden Sie f\"ur die folgenden Aussagen,
ob Sie jeweils wahr oder falsch sind. Geben Sie jeweils einen
Beweis oder ein Gegenbeispiel.

\begin{enumerate}
\item Es gilt $\log n \in O(2^{\log\log^2 n})$.
\item Es ist $f(n) \in O(g(n))$ genau dann, wenn
  $g(n) \in \Omega(f(n))$ ist.
\item Wenn $f(n) \in O(g(n))$ ist, dann ist auch
 $2^{f(n)} \in O(2^{g(n)})$.
\end{enumerate}

\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}
