\documentclass[10pt]{article}

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

\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}}}

\thispagestyle{empty}

\begin{center}
  {\Large Übungsblatt 5} \\
  Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
  Andreas Steinel (Matrikelnummer 2029984) \\
  Manuel Gorius (Matrikelnummer 2030845) \\
  Robert Vollmann (Matrikelnummer 2030097) \\
  Übungsgruppe Di, 9-11 Uhr \\
  Andreas Augustin \\
\end{center}

\newpage
\section*{Aufgabe 1}
Sei $m$ die Anzahl von Operationen. Lege $2^n+1$ Werte per \verb!pushBack! auf das Array, mit $2^n+1\approx\frac{m}{2}$. Die interne Größe des Arrays ist dann gleich $2^n+1$. Entfernt man nun wechselweise mit \verb!popBack! ein Element und legt mit \verb!pushBack! wieder eines auf das Array, so wird das Array bei jeder Operation auf die Hälfte verkleinert bzw. vergrößert, sodass jedesmal $2^n$ Elemente kopiert werden müssen. Die Laufzeit ist ungefähr $\frac{1}{4}4^{log_2m}$. Mit $4^x=2^x\cdot2^x$ gilt:
$$\frac{1}{4}4^{log_2m} = \frac{1}{4}\cdot2^{log_2m}\cdot2^{log_2m} = \frac{1}{4}\cdot m\cdot m = \frac{1}{4}\cdot m^2 \in \theta(m^2)$$
\hfill $\Box$

\section*{Aufgabe 2}
\subsubsection*{(a)}
worst-case-Laufzeit = $\lceil log_2m \rceil$

\subsubsection*{(b)}
\begin{itemize}
\item betrachte $m=2^k-1, \; \; \; k\in\SetN$, sodass $k$ Binärziffern benötigt werden
\item sei $c=\sum_{i=0}^{k-1}d_i\cdot2^i$
\item ist $d_0=0$, so muss für das Inkrement nur 1 Bit verändert werden; dies stellt die Hälfte aller Fälle dar
\item ist $d_0=1$ und $d_1=0$, so müssen zwei Bits verändert werden; dies stellt ein Viertel aller Fälle dar
\item ...
\item für $m=2^k-1$ Inkrementopertionen sind also
$$\sum_{i=1}^k \frac{2^k}{2^i} = 2^k-1$$
Bit-Änderungen notwendig; berechne die durchschnittliche Anzahl von Bit-Änderungen pro Inkrement-Operation
$$\frac{\sum_{i=1}^k\frac{2^k}{2^i}}{m} = \frac{2^k-1}{2^k-1} = 1 \in \mathcal{O}(1)$$
\item ist $m$ nicht von der Form $2^k-1$, so erhöht sich die durchschnittliche Anzahl von Bit-Änderungen pro Inkrement-Operation, sie bleibt aber dennoch $\in\mathcal{O}(1)$. \hfill $\Box$
\end{itemize}

\subsubsection*{(c)}
Betrachte $m=2^k, \; \; \; k\in\SetN$, sodass $k$ Binärziffern benötigt werden. Führe $\frac{m}{2}$ Inkrementoperationen durch. Anschließend ist $c=\frac{m}{2}=2^{k-1}$; die amortisierte Laufzeit beträgt $\frac{m}{2}$. Führe nun wechselweise je $2^{k-2}$ Dekrement- und Inkrementoperationen durch, beginnend mit einer Dekrementoperation. Da dann jeweils $log_2m=k$ Bit-Änderungen vorgenommen werden müssen, beträgt die Laufzeit $\frac{m}{2}\cdot log_2m$. In der Summe erhalten wir nun für diese $m$ Operationen eine Laufzeit von $\frac{m}{2}(1+log_2m) \in \theta(m\cdot log_2m)$. \hfill $\Box$

\section*{Aufgabe 3}
\lstset{language=C++,basicstyle=\sffamily}
\textsf{\lstinputlisting{fifo.cpp}}


\end{document}