%%\RequirePackage{fix-cm}
\documentclass[a4paper,fleqn,ngerman]{scrartcl}
\usepackage{cmap}
\usepackage[T1]{fontenc}
\usepackage{textcomp}
\usepackage[ngerman]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
%%\usepackage[nointegrals]{wasysym}
\usepackage{dsfont}
%%\input{fonts}
\usepackage{booktabs}
\usepackage{color}
\usepackage{units}
\usepackage{eule}
\usepackage[activate]{pdfcprot} % optischer Randausgleich mit pdfLaTeX
\usepackage{graphicx}
\usepackage{calc}
\usepackage[bookmarksnumbered,bookmarksopen]{hyperref}
\hypersetup{
 pdftitle={\"Ubungsblatt 10},
 pdfsubject={Programmierung II, Lenhof},
 pdfauthor={Andreas Glitsch, Jan Hendrik Dithmar, Dirk Heine},
 pdfkeywords={Programmierung II, Lenhof},
 pdfstartview={FitH \hypercalcbp{\paperheight-\topmargin-1in-\headheight-\headsep}}
}
\usepackage{listings}
\lstloadlanguages{Pascal,C++}
\lstset{tabsize=4,language=Pascal,basicstyle=\ttfamily}
\lstset{morekeywords={process,par_begin,par_end,monitor,public,from},
morecomment=[l]{//},
morecomment=[s]{/*}{*/}}
\input{macros}
\setcounter{secnumdepth}{0}
%%\renewcommand*{\sectfont}{\bfseries}
\listfiles
\begin{document}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\titlehead{
  \newlength{\calclengthA}
  \newlength{\calclengthB}
  \settowidth{\calclengthA}{\EULE}
  \setlength{\calclengthB}{\linewidth}
  \addtolength{\calclengthB}{-\calclengthA}
  \addtolength{\calclengthB}{-1em}
  \parbox{\calclengthB}{
    \raggedright
    \scshape{
    Universit\"at des Saarlandes\\
    Fachrichtung 6.2 - Informatik\\
    Sommersemester~2004\\
    Gruppe~Andreas~Augustin ~Do~14-16
    }
  }
  \hfill
  \parbox[b]{\calclengthA}{\EULE}
}
\subject{Programmierung II}
\title{Übungsblatt 10}
\author{Andreas Glitsch 2026130 \and Jan Hendrik Dithmar 2031259 \and Dirk Heine 2030941}
\date{\today}

\maketitle

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
1 & 2 & 3 & 4 & $\sum$\\
\hline
& & & & \\
\hline
\end{tabular}
\end{center}
\section{Aufgabe 1 - Rekurrenz, Substitutionsmethode}
\subsection{i)}
$T(n) = 3T(\lfloor \displaystyle \frac{n}{2} \rfloor) + n^2$\\
nach der Substitutionsmethode sch\"atzen wir die L\"osung:
$O(n^2 log(n))$\\
Zu zeigen: $T(n) = cn^2 log(n)$ f\"ur ein geeignetes $c > 0$ und hinreichend gro"ses $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\"ahlen $n_0 = 2$ als Induktionsstart.\\

$\Rightarrow T(2) = c_2 > c \cdot 4log(4) \approx 2,408 > 2$\\

Induktionsschluss:\\
$T(n) \leq 3(c(\lfloor \displaystyle \frac{n}{2} \rfloor)^2 log(\lfloor \displaystyle \frac{n}{2} \rfloor)) + %%@
n^2$\\
$\phantom{T(n)} \leq c(\lfloor \displaystyle \frac{n}{2} \rfloor)^2 log(\lfloor \displaystyle \frac{n}{2} %%@
\rfloor) + n^2$\\
$\phantom{T(n)} \leq cn^2 log(\displaystyle \frac{n}{2}) +  n^2$\\
$\phantom{T(n)} \leq cn^2 log(n) - cn^2 log(2) + n^2$\\
$\phantom{T(n)} \leq cn^2 log(n) - cn^2 + n^2$\\
$\phantom{T(n)} \leq cn^2 log(n)$ falls $c > 1$\\
\QED

\subsection{ii)}
$T(n) = 3T(\lfloor \displaystyle \frac{n}{8} \rfloor) + T(\lfloor \displaystyle \frac{n}{4} \rfloor) + 1$\\
Wir sch\"atzen, dass $T(n) \in O(n)$\\
Dies zeigen wir mit Hilfe der Annahme: $T(n) \leq cn - b$ f\"ur ein $b > 0$\\
Beweis:\\
IA: $n=1: T(1) = 1 \leq c - b$ f\"ur $c \geq b + 1$\\
IS: $T(n) = 3T(\lfloor \displaystyle \frac{n}{8} \rfloor) + T(\lfloor \displaystyle \frac{n}{4} \rfloor) + %%@
1$\\
$\phantom{IS:T(n)} \leq 3c \frac{1}{8}n - 3b + c \frac{1}{4}n - b + 1$\\
$\phantom{IS:T(n)} = cn - 4b + 1$\\
$\phantom{IS:T(n)} \leq cn - b$ f\"ur $b = 3$\\
\QED

\subsection{iii)}

\section{Aufgabe 2 - Rekurrenz, Mastertheorem}
\subsection{i)}
\subsection{ii)}
\subsection{iii)}
\subsection{iv)}
\subsection{v)}

\section{Aufgabe 3 - Rot-Schwarz-Baum}
\subsection{i)}
\subsection{ii)}
\subsection{iii)}

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

\item
Hier wird nun ein balancierter Bin\"arbaum erzeugt, der dann im i-ten Aufruf von insert maximal die H\"ohe %%@
$log_2(i)$ besitzen kann\\
$\Rightarrow$ Geaamtkosten f\"ur 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 $O(1)$ anh\"angen; %%@
daraus ergibt sich eine Gesamtlaufzeit von $O(n)$.\\

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

\end{document}
