\documentclass[11pt, a4paper]{article}

\usepackage{ngerman}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage[latin1]{inputenc}
\usepackage{graphicx}
\usepackage[pdftex,             
            pdfpagelabels,
            colorlinks=true,           % Links nicht farbig umrahmen, sondern als farbigen Text
            urlcolor=colorBlue,        % Farbe für externe Verweise, \href{...}{...}
            filecolor=colorGreen,      % Farbe für lokale Verweise, \href{...}{...}
            linkcolor=colorRed,        % Farbe für interne Verweise, \ref{...} und \pageref{...}
            pdftitle={},
            pdfauthor={Jan Hendrik Dithmar},
            pdfsubject={},
            pdfkeywords={},
            pdfpagemode=None,          % Navigationsleiste beim Start ausblenden 
            % pdfpagemode=UseThumbs,     % Thumbnails beim Start anzeigen
            % pdfpagemode=UseOutlines,   % Lesezeichen beim Start anzeigen
            % pdfpagemode=FullScreen,    % im Vollbildmodus starten
            % pdfstartpage=2,            % spezielle Startseite festlegen
            bookmarks,
            % bookmarksopen,             % alle Lesezeichen aufklappen
            % bookmarksopenlevel=2,      % Tiefe, bis zu welcher die Lesezeichen aufgeklappt werden sollen
            bookmarksnumbered,         % Lesezeichen nummerieren
            pdfstartview=FitH,         % Seite auf voller Breite anzeigen
            pagebackref
           ]{hyperref}

\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{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\thispagestyle{empty}

\title{Programmierung II - Übungsblatt 10 \\
	Übungsgruppe Do 14-16 \\	
	Andreas Augustin}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941) \\
	Andreas Glitsch (Matrikelnummer 2026130)}
\date{}

\maketitle

\newpage

\section*{Aufgabe 1}
\subsubsection*{(i)}
$$T(n) = 3T(\lfloor \displaystyle \frac{n}{2} \rfloor) + n^2$$
nach der Substitutionsmethode schätzen wir die Lösung:
$\OnotO(n^2 log(n))$\\
Zu zeigen: $T(n) = cn^2 log(n)$ für ein geeignetes $c > 0$ und hinreichend großes $n \geq n_0$\\
\\
Beweis:\\
Wir nehmen an es gelte $T(\lfloor \displaystyle \frac{n}{2} \rfloor) \leq c(\lfloor \displaystyle \frac{n}{2}
\rfloor)^2 + \log(\lfloor \displaystyle \frac{n}{2} \rfloor)$\\
Induktionsanfang:\\
Wir wählen $n_0 = 2$ als Induktionsstart.
$$\Rightarrow T(2) = c_2 > c \cdot 4 \log(4) \approx 2,408 > 2$$
Induktionsschluss:
\begin{eqnarray*}
T(n) & \leq & 3(c(\lfloor \frac{n}{2} \rfloor)^2 \log(\lfloor \frac{n}{2} \rfloor)) + n^2 \\
& \leq & c(\lfloor \displaystyle \frac{n}{2} \rfloor)^2 \log(\lfloor \frac{n}{2}\rfloor) + n^2 \\
& \leq & cn^2 \log(\displaystyle \frac{n}{2}) +  n^2 \\
& \leq & cn^2 \log(n) - cn^2 \log(2) + n^2 \\
& \leq & cn^2 \log(n) - cn^2 + n^2 \\
& \leq & cn^2 \log(n) \text{ falls } c > 1
\end{eqnarray*} \QED

\subsubsection*{(ii)}
$$T(n) = 3T(\lfloor \frac{n}{8} \rfloor) + T(\lfloor \displaystyle \frac{n}{4} \rfloor) + 1$$
Wir schätzen, dass $T(n) \in \OnotO(n)$\\
Dies zeigen wir mit Hilfe der Annahme: $T(n) \leq cn - b$ für ein $b > 0$\\
Beweis:\\
IA: $n=1: T(1) = 1 \leq c - b$ für $c \geq b + 1$\\
IS:
\begin{eqnarray*}
T(n) & = & 3T(\lfloor \displaystyle \frac{n}{8} \rfloor) + T(\lfloor \displaystyle \frac{n}{4} \rfloor) + 1 \\
& \leq & 3c \frac{1}{8}n - 3b + c \frac{1}{4}n - b + 1 \\
& = & cn - 4b + 1 \\
& \leq & cn - b \text{ für } b = \frac{1}{3}
\end{eqnarray*}
\QED


\section*{Aufgabe 2}
\subsubsection*{(i)}
$$T(n) = 49 \sqrt{7}T\left(\frac{n}{7}\right) + 7 \cdot \sqrt{n^5} + 49 \sqrt{7}$$
Hier gilt $f(n):=7\sqrt{n^5} + 49 \sqrt{7} = 7 n^{\frac{5}{2}} + 49\sqrt{7}$ und $n^{\log_7(49\sqrt{7})} = n^{\log_7(\sqrt{7^5})} = n^{\log_7(7^\frac{5}{2})} = n^{\frac{5}{2}}$.
Offenbar gilt $f(n) \in \Theta (n^\frac{5}{2})$ und damit nach Fall 2 des Mastertheorems:
$$T(n) \in \Theta(n^\frac{5}{2} \log_7(n))$$

\subsubsection*{(ii)}
$$T(n) = 27 T\left(\frac{n}{3}\right) + \frac{n^3}{\log_9^3(n)}$$
Es gilt $f(n) := \frac{n^3}{\log_9^3(n)}$ und $n^{\log_3(27)} = n^3$. Offenbar gilt $f(n) \in \OnotO(n^3)$. Es müsste ein $\varepsilon > 0$ existieren, sodass $f(n) \in \OnotO(n^{3-\varepsilon})$ ist.
Der Logarithmus wächst aber langsamer als jede Potenz $n^\varepsilon$: \\
Es gilt:
	$$\log_9(n) = \frac{\ln(n)}{\ln(9)}$$
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{\log_9^3(n)}{n^\varepsilon} & \stackrel{\text{L'Hôpital}}{=} & \lim_{n \to \infty} \frac{3 \cdot \log_9^2(n) \cdot \frac{1}{n \ln(9)}}{\varepsilon \cdot n^{\varepsilon-1}} \\
	& = & \lim_{n \to \infty} \frac{3 \log_9^2(n)}{\varepsilon \cdot n^\varepsilon \cdot \ln(9)} \\
	& \stackrel{\text{L'Hôpital}}{=} & \lim_{n \to \infty} \frac{6 \log_9(n)}{\varepsilon^2 \cdot n^\varepsilon \cdot \ln^2(9)} \\
	& \stackrel{\text{L'Hôpital}}{=} & \lim_{n \to \infty} \frac{6}{\varepsilon^3 \cdot n^\varepsilon \cdot \ln^3(9)} \\
	& = & 0
\end{eqnarray*}
Daher können wir kein $\varepsilon > 0$ finden mit $\frac{n^3}{\log_9^3(n)} \in \OnotO(\frac{n^3}{n^\varepsilon})$. Damit mach das Mastertheorem keine Aussage.

\subsubsection*{(iii)}
$$T(n) = 9 T \left(\frac{n}{3}\right) + 3 \log(n) n^2$$
Hier gilt $f(n):=3 \log(n)n^2$ und $n^{\log_3(9)} = n^2$. Damit gilt $f(n) \in \Omega(n^2)$. Wir können jedoch kein $\varepsilon > 0$ finden, sodass $f(n) \in \Omega(n^{2+\varepsilon})$ ist,
da der Logarithmus langsamer als jede Potenz wächst:
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{\log(n) n^2}{n^2 n^\varepsilon} & = & \lim_{n \to \infty} \frac{\log(n)}{n^\varepsilon} \\
	& = & \lim_{n \to \infty} \frac{\frac{\ln(n)}{\ln(2)}}{n^\varepsilon} \\
	& \stackrel{\text{L'Hôpital}}{=} & \lim_{n \to \infty} \frac{\frac{1}{n \cdot \ln(2)}}{\varepsilon \cdot n^{\varepsilon-1}} \\
	& = & \lim_{n \to \infty} \frac{1}{\varepsilon \cdot \ln(2) \cdot n^\varepsilon} = 0
\end{eqnarray*}
Damit ist das Mastertheorem nicht anwendbar.

\subsubsection*{(iv)}
$$T(n) = 15625 T\left(\frac{n}{5}\right) + \frac{1}{37}n^7$$
Es gilt $f(n) := \frac{1}{37} n^7$ und $n^{\log_5(15625)} = n^6$. Offenbar gilt $f(n) \in \Omega(n^6)$. Da $n^7$ schneller wächst als $n^6$ können wir ein bel. $\varepsilon>0$
wählen, sodass $f(n) \in \Omega(n^{6+\varepsilon})$. \\
Für Fall 3 des Mastertheorems muss man noch zeigen. dass für irgendein $c<1$ und genügend großes $n$ $15625 \cdot f(\frac{n}{5}) \le c \cdot f(n)$ gilt.
\begin{eqnarray*}
	15625 \cdot f\left(\frac{n}{5}\right) & \le & c \cdot f(n) \\
	15625 \cdot \frac{1}{37} \cdot \left(\frac{n}{5}\right)^7 & \le & c \cdot \frac{1}{37} n^7 \\
	15625 \cdot \left(\frac{n}{5}\right)^7 & \le & c \cdot n^7 \\
	15625 \cdot \frac{\left(\frac{n}{5}\right)^7}{n^7} & \le & c \quad \quad n \text{ genügend groß} \\
	15625 \cdot \left(\frac{\frac{n}{5}}{n}\right)^7 & \le & c \\
	15625 \cdot \left(\frac{n}{5n}\right)^7 & \le & c \\
	15625 \cdot \left(\frac{1}{5}\right)^7 & \le & c \\
	\frac{15625}{78125} & \le & c \\
	0.2 & \le & c \\
	c & \ge & 0.2
\end{eqnarray*}
Wähle z.B. $c=0.3$. Somit ist die Behauptung gezeigt und es gilt nach Fall 3 des Mastertheorems:
$$T(n) \in \Theta(n^7)$$

\subsubsection*{(v)}
$$T(n) = 1296 T \left(\frac{n}{6}\right) + n^3 \sqrt{n} \log(n)$$
Hier gilt: $f(n) := n^3 \sqrt{n} \cdot \log(n)$ und $n^{\log_6(1296)} = n^4$. Offenbar gilt $f(n) \in \Omega(n^3)$. Mann kann jedoch kein $\varepsilon > 0$ finden, sodass
$f(n) \in \Omega(n^{3+\varepsilon})$, denn der Logarithmus und die Wurzelfunktion wachsen langsamer als jede Potenz:
\begin{eqnarray*}
	\lim_{n \to \infty} \frac{n^3 \sqrt{n} \log(n)}{n^3 \cdot n^\varepsilon} & = & \lim_{n \to \infty} \frac{\sqrt{n}\log(n)}{n^\varepsilon} \\
	& = & \lim_{n \to \infty} \frac{n^{\frac{1}{2}} \cdot \log(n)}{n^\varepsilon} \\
	& = & \lim_{n \to \infty} \frac{\log(n)}{n^{\varepsilon - \frac{1}{2}}} \\
	& \stackrel{\varepsilon' := \varepsilon - \frac{1}{2}}{=} & \lim_{n \to \infty} \frac{\log(n)}{n^{\varepsilon'}} \\
	& \stackrel{\text{L'Hôpital}}{=} & \lim_{n \to \infty} \frac{\frac{1}{n \cdot \ln(2)}}{\varepsilon' \cdot n^{\varepsilon' -1}} \\
	& = & \lim_{n \to \infty} \frac{1}{\varepsilon' \cdot n^{\varepsilon'} \cdot \ln(2)} = 0
\end{eqnarray*}
Damit kann das Mastertheorem hier nicht angewendet werden.

\newpage
\section*{Aufgabe 3}
\subsubsection*{(a)}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-a1.jpg}\\[0.2cm]
	\end{center}
\end{figure}

\subsubsection*{(b)}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-b1.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-b2.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-b3.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=8cm]{a3-b4.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=5cm]{a3-b5.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=3cm]{a3-b6.jpg}\\[0.2cm]
	\end{center}
\end{figure}

\newpage
\subsubsection*{(c)}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-c1.jpg}\\[0.2cm]
	\end{center}
\end{figure}
\begin{figure}[htbp]
	\begin{center}
		\includegraphics*[width=10cm]{a3-c2.jpg}\\[0.2cm]
	\end{center}
\end{figure}

\newpage
\section*{Aufgabe 4}
\begin{enumerate}
\item
Durch die Implementierung wird eine lineare Kette erzeugt, ein unbalancierter Baum, bei dem jeweils an den
untersten Knoten angehängt wird. Daher muss vor jedem insert die bisherige Kette noch einmal angelaufen
werden. Daraus ergibt sich für die $i$-te insert-Operation eine Laufzeit $\OnotO(i)$\\
$\Rightarrow$ Gesamtkosten für die Sequenz: $\displaystyle{\sum^n_{i=1}ci = \frac{1}{2}n(n+1) \in \OnotO(n^2)}$\\

\item
Hier wird nun ein balancierter Binärbaum erzeugt, der dann im $i$-ten Aufruf von insert maximal die Höhe
$log_2(i)$ besitzen kann\\
$\Rightarrow$ Gesamtkosten für die Sequenz:
$\displaystyle{\sum^n_{i=1}log_2(i)=log_2(\prod^n_{i=1}i)=log_2(n!)}$\\

\item
Hier erhalten wir einen Baum mit genau einem Knoten. Man kann z.B. vorne an die Liste in $\OnotO(1)$ anhängen;
daraus ergibt sich eine Gesamtlaufzeit von $\OnotO(n)$.\\

\item
Die worst-case-Laufzeit entspricht genau dem Verhalten des Algorithmus in der Volesung, d.h. die lineare Kette
wird in $\OnotO(n^2)$ erzeugt. Über die durchschnittliche Laufzeit kann man ganz informell sagen, dass der Baum
auf beiden Seiten gleich schnell wächst und daher ein balancierter Binärbaum zu erwarten ist. Daher ist
die Laufzeit entsprechend dem Punkt 2 $\in \OnotO(n log_2(n))$.\\
\end{enumerate}


\end{document}
