\documentclass[10pt]{article}

\usepackage{ngerman,a4,amssymb,amsmath}
\usepackage[latin1]{inputenc}
\usepackage{listings}
\usepackage{enumerate}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\Inv}[1]{\ensuremath{\frac{1}{#1}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}

\pagestyle{myheadings}
\markright{Jan Hendrik Dithmar (Matrikelnummer 2031259) - Andreas Augustin}

\title{Programmierung 2 - Übungsblatt 10 \\
	Di, 9-11 Uhr \\
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 2}
\lstset{language=C++,basicstyle=\small}
\lstinputlisting{a2.cpp}

\newpage

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
	\item Aus der Vorlesung ist bekannt das die asymptotische Klassifizierung von Summen durch den \glqq größten\grqq\ Summanden gegeben ist. 
		Da alle gegebenen Funktionen $g_j$ mit $j \neq i$ maximal in der selben Laufzeitklasse wie $g_i$ sind kann maximal gelten: $f(n) \in \Theta(k \cdot g_i(n))$.
		Somit gilt aber auch $f(n) \in \Theta(g_i(n))$ da $k$ ein konstanter Faktor. Wenn aber gilt $g_j(n) = 0 \forall j \neq i$ also die Summe minimal ist,
		dann gilt trivialerweise $f(n) \in \Theta(g_i(n))$. \QED
	\item Anordnung: $$\log_2 \log_2 (n)$$ $$(log_2 (n))^2$$ $$(\sqrt{2})^{log_2 (n)} = \sqrt{n}$$ $$n$$ $$(\frac{3}{2})^n$$
\end{enumerate}

\newpage

\section*{Aufgabe 4}
\paragraph{Geraten:} $$T(n) \in cn^2 + \Theta(n^{\log_5(3)}) \in \Theta(n^2)$$
\paragraph{Beweis:}
\subsubsection*{Induktionsanfang:}
$$T(1) = 3T(\frac{1}{5}) + c \cdot 1^2 = 3T(\frac{1}{5}) + 1 \in 1 + \Theta(1) \in \Theta(1)$$
\subsubsection*{Induktionsschritt: $n \leadsto 5n$}
$$T(5n) = 3T(n) + 25cn^2 \stackrel{IV}{\in} 25cn^2 + \Theta(n^2) \in \Theta(n^2)$$ 
\QED

\newpage

\section*{Aufgabe 8}
\begin{eqnarray*}
	E(X) & = & \sum_{i=0}^\infty i\cdot (1-p)^{i-1}p \\
	& =&  p\sum_{i=1}^\infty i \cdot (1-p)^{i-1} \\
	& = & p \cdot \frac{1}{p^2} \\
	& = & 1/p \\ \\
	V(X) & = & E(X - E(X)) \\
	& = & E(X^2) - (E(X))^2 \\
	& = & \sum_{i=0}^\infty i\cdot ((1-p)^{i-1}p)^2 \\
	& = & \frac{1}{(p - 2)^2}
\end{eqnarray*}


\end{document}