\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 2}
\end{center}

\vspace{1cm}

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

%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 1, Vollst\"andige Induktion (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Zeigen Sie mittels Induktion, dass f\"ur alle Zweierpotenzen $n = 2^k$ und
\begin{displaymath}
T(n) = \left\{ \begin{array}{ll}
	2 & \textrm{f\"ur } n = 2\\
	2T(\frac{n}{2}) + n & \textrm{f\"ur } n = 2^k, k > 1
	\end{array} \right.
\end{displaymath}
gilt:
$T(n) = n \cdot \log_2(n)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 2, Binary search (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei eine geordnete Sequenz $A$, und eine Zahl $v$.

\noindent
Schreiben Sie in Pseudocode einen Algorithmus, der bestimmt, ob $v$ in $A$ vorkommt. Beweisen Sie, dass die Laufzeit des Algorithmus h\"ochstens von der Gr\"ossenordnung $\Theta(\log_2(n))$ ist.


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 3, Laufzeit verbessern (2P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Beim insertion sort Algorithmus aus der Vorlesung werden in der while-Schleife alle Elemente von der Position $j-1$ an r\"uckw\"arts mit dem aktuellen Element verglichen.
Kann der binary search algorithmus aus der vorhergehenden Aufgabe dazu verwendet werden, die Laufzeit des insertion sort auf die Gr\"ossenordnung $\Theta(n \cdot \log_2(n))$ zu verbessern?


%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Aufgabe 4, Algorithmus (3P)}
%%%%%%%%%%%%%%%%%%%%%%%%%%

Gegeben sei eine Menge $S$ von nat\"urlichen Zahlen,
und eine weitere nat\"urliche Zahl $x$.
Schreiben Sie einen Algorithmus (in Pseudocode), der in $\Theta(n \cdot \lg(n))$ Zeit bestimmt, ob es zwei Zahlen $a,b \in S$ gibt so dass $a + b = x$ gilt.


\end{document}