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

\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}}
\newcommand{\N}{\mathbb{N}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}

\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
Probeklausur zur Vorlesung

\smallskip
\noindent
\large
\textbf{Informatik B} \hfill SoSe 2016\\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule
\smallskip
\noindent
Bearbeitungszeit: mindestens 90 Minuten 

\vskip 0.5cm

\begin{description}

%\newpage
\AUFGABE{Insertion Sort}{6+4 Punkte}

\begin{enumerate}
%  \item Richtig oder falsch: Insertion Sort ben\"otigt nie
%    mehr Vergleiche als Merge Sort. Begr\"unden Sie Ihre Antwort.
  \item F\"uhren Sie den Insertion Sort Algorithmus auf der folgenden
    Liste aus. Zeigen Sie die einzelnen Schritte.
    \begin{verbatim}
        5, 1, 4, 2, 7
    \end{verbatim}
  \item Der Insertion Sort Algorithmus f\"ugt in jeder Iteration
    das n\"achste Element in das bereits sortierte Anfangsst\"uck der Liste
    ein. Der Algorithmus bestimmt die Einf\"ugeposition, indem er
    das sortierte Anfangsst\"uck von hinten nach vorne durchgeht.
    Betrachten Sie eine alternative Implementierung, die
    \emph{bin\"are Suche} verwendet, um die Einf\"ugeposition zu finden.

    Wie viele \emph{Vergleiche} ben\"otigt der alternative Algorithmus (in 
    der $O$-Notation)? Was k\"onnen Sie \"uber die \emph{Laufzeit} sagen?
\end{enumerate}

\AUFGABE{Programmieren}{3+5+2 Punkte}

Die Fibonacci-Zahlen $F_n$, $n \in \N$, sind definiert durch
\[
  F_1 = 1; \quad F_2 = 1; \quad F_n = F_{n - 1} + F_{n - 2}, \,
    \text{f\"ur } n \geq 2.
\]
Betrachten Sie die folgende Python-Funktion zur Berechnung
der Fibonacci-Zahlen.

\begin{verbatim}
def fib(n):
   if n <= 0:
       raise Exception
   elif n == 1:
       return 1
   elif n == 2:
       return 1
   else:
       return fib(n - 1) + fib(n - 2)
\end{verbatim}

\begin{enumerate}
  \item Beschreiben Sie die einzelnen Schritte, die bei der 
     Berechnung von \texttt{fib(5)} durchgef\"uhrt werden.
  \item Geben Sie eine Python-Funktion \texttt{fib2(n)}, welche
     die Fibonacci-Zahlen iterativ mit Hilfe einer 
     Z\"ahlschleife berechnet.
     Beschreiben Sie die einzelnen Schritte, die bei der 
     Berechnung von \texttt{fib2(5)} durchgef\"uhrt werden.
%  \item Beweisen Sie durch Induktion, dass 
%    zur Berechnung von $F_n$ mit Hilfe von 
%    \texttt{fib(n)} mindestens $(3/2)^{n-2}$ 
%    Aufrufe von \texttt{fib} durchgef\"uhrt werden m\"ussen
%    (inklusive des ersten Aufrufs \texttt{fib(n)}).
  \item Wie viele Schritte ben\"otigt
    \texttt{fib2(n)} zur Berechnung von $F_n$? Geben Sie Ihre
    Antwort in der $O$-Notation und begr\"unden Sie sie kurz.
\end{enumerate}
\AUFGABE{Vermischtes}{3+2+2+3 Punkte}

\begin{enumerate}
  \item Zeigen Sie anhand der Definitionen, dass
    $n^2 + 2n - 10 = O(n^2)$ gilt. Welche Aussage
    m\"usste man zus\"atzlich beweisen, um 
   $n^2 + 2n - 10 = \Omega(n^2)$ zu zeigen?
  \item Richtig oder falsch: Gleitkommazahlen verhalten
    sich wie rationale Zahlen. Begr\"unden Sie Ihre Antwort.
  \item Richtig oder falsch: Quicksort ben\"otigt nie
    mehr als $O(n \log n)$ Vergleiche. Begr\"unden Sie
    Ihre Antwort.
  \item Beschreiben Sie den Unterschied zwischen dem
    statischen und dem dynamischen Datentyp einer Variable in Java
    und illustrieren Sie ihn an einem Beispiel.
\end{enumerate}


\AUFGABE{Bin\"are Heaps}{4+3+3 Punkte}

\begin{enumerate}
\item F\"uhren Sie die folgenden Operationen auf einem anfangs
  leeren bin\"aren Max-Heap aus. Zeigen Sie die einzelnen Schritte
  in der Baumdarstellung.
  
  \begin{verbatim}
    insert(2), insert(5), insert(6), extractMax, 
    insert(9), insert(1), extractMax, extractMax
  \end{verbatim}
\item Gegeben seien $k \geq 2$ \emph{sortierte} Listen
  \texttt{l1}, \texttt{l2}, $\dots$, \texttt{lk} mit
  insgesamt $n$ Elementen.
  Beschreiben Sie einen Algorithmus, der mit Hilfe eines
  bin\"aren Heaps diese Listen in $O(n\log k)$ Schritten in 
  eine einzige sortierte Liste zusammenf\"ugt. Begr\"unden Sie die
  Laufzeit Ihres Algorithmus.
\item Sei \texttt{a} eine Liste, die einen bin\"aren Max-Heap 
  mit $n$ Element enth\"alt. 
  Die Operation \texttt{increaseKey(i, x)} erh\"alt
  einen Index \texttt{i} in \texttt{a} und einen Wert $x$. Sie soll
  den Schl\"ussel in \texttt{a[i]} auf den Wert \texttt{x}
  erh\"ohen und danach die Heap-Eigenschaft wieder herstellen. 

  Beschreiben Sie eine Implementierung von \texttt{increaseKey}
  mit Hilfe der Operation \texttt{bubbleUp},
  die $O(\log n)$ Schritte ben\"otigt.
  Begr\"unden Sie die
  Laufzeit Ihres Algorithmus. 
\end{enumerate}



\end{description}
\end{document}
