\documentclass[11pt, oneside]{article}

\usepackage{a4, latexsym}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{german}
\usepackage{nopageno}

\date{}

\begin{document}
\noindent
\textsl{Vorlesung Algorithmen, D.~Huson und R.~Rupp, Universit\"at T\"ubingen, WS07/08}

\vspace{1cm}

\begin{center}
\LARGE{Aufgabenblatt 4}
\end{center}

\vspace{1cm}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Lineare Suche (4P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Betrachte das {\bf Suchproblem}:\\
{\bf Eingabe}: Eine Sequenz von $n$ Zahlen $A=\langle a_1,a_2,\dots, a_n\rangle$ und ein Wert $v$.\\
{\bf Ausgabe:} Ein Index $i$, so dass $v=A[i]$ gilt, oder NIL, falls $v$ in $A$ nicht vorkommt.

\vspace{2mm}

\noindent
a) Scheiben Sie bitte in Pseudocode einen Algorithmus {\bf lineare Suche},
der die Sequenz linear durchsucht,
um ein Vorkommen von $v$ zu finden. (2P)

\vspace{2mm}

\noindent
b) Formulieren Sie eine Schleifeninvariante, die man benutzen k"onnte,
um die Korrektheit des Algorithmus zu zeigen.  (1P)

\vspace{2mm}

\noindent
c) Welche drei Aussagen m"usste man f"ur die Schleifeninvariante beweisen? (1P)


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, Master Theorem (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Benutzen Sie das Master Theorem, um asymptotische Grenzen f"ur die folgenden Rekurrenzen zu finden:

\begin{displaymath}
T(n) = 4 T(\frac{n}{2}) + n
\end{displaymath}

\begin{displaymath}
T(n) = 4 T(\frac{n}{2}) + n^2
\end{displaymath}

\begin{displaymath}
T(n) = 4 T(\frac{n}{2}) + n^3
\end{displaymath}


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, Master Theorem (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Kann das Master Theorem bei der Rekurrenz
\begin{displaymath}
T(n) = 4 T(\frac{n}{2}) + n^2 \log_2(n)
\end{displaymath}
angewendet werden?
Begr"unden Sie ihre Aussage.


\end{document}