\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{german}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage[utf8x]{inputenc}

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 10. Juni 2014 vor der Vorlesung} 

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}



\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung \hfill SoSe 2014

\smallskip
\noindent
\large
\textbf{Ausgewählte Themen der Algorithmik: Datenstrukturen}\\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann, Yannik Stein
\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Batchers Algorithmus}{15 Punkte}

Analysieren Sie Batchers Sortieralgorithmus. Sei $h$ eine
Zweierpotenz.
Eine Folge $x_0, \dots, x_{h-1}$ hei\ss{}t \emph{bitonisch}, 
falls sie erst monoton w\"achst und dann monoton f\"allt,
oder falls sie durch eine zyklische Permutation aus einer solchen
Folge hervorgegangen ist. 

Batchers Algorithmus sortiert $x_0, \dots, x_{h-1}$ rekursiv
wie folgt: Setzte $t = h/2$
und f\"ur $i = 0, \dots, t-1$, setze $m_i = \min\{x_i, x_{i+t}\}$,
$M_i = \max\{x_i, x_{i+t}\}$. Sortiere rekursiv die Folgen
$m_0, \dots, m_{t-1}$ und $M_0, \dots, M_{t-1}$. Konkateniere
dann die sortierte $m_i$-Folge mit der sortierten $M_i$-Folge.

\begin{enumerate}
  \item Analysieren Sie die Laufzeit von Batchers Algorithmus.
  \item Zeigen Sie: Falls $x_0, \dots, x_{h-1}$ bitonisch
  ist, dann sind auch $m_0, \dots, m_{t-1}$ und
  $M_0, \dots, M_{t-1}$ bitonisch.
  \item Zeigen Sie: Es ist $\max \{m_0, \dots, m_{t-1}\} \leq \min \{M_0, \dots, M_{t-1}\}$.
  \item Folgern Sie, dass Batchers Algorithmus korrekt ist.
\end{enumerate}

\AUFGABE{Bit-Tricks}{15 Punkte}

Beweisen Sie die Behauptung aus der Vorlesung.
Wir interpretieren Wort $w$ als eine Folge
von $k$ Eintr\"agen mit $\ell$ Bits, wobei das
oberste Bit \emph{Testbit} genannt wird.

\begin{enumerate}
  \item In $O(1)$ Operation kann man eine Operation
    \texttt{copyTestBit}$(w)$ implementieren, welche
    jedes Feld von $w$ mit $\ell-1$ Kopien des entsprechenden
    Testbits f\"ullt und danach alle Testbits l\"oscht.
  \item In $O(\log k)$ Zeit kann man ein Wort $A$ berechnen,
    das in jedem Feld die Zahl $1$ speichert.
  \item
     In $O(\log k)$ Zeit kann man ein Wort $B$ berechnen,
      das in Feld $i$ die Zahl $i$ speichert.
  \item
     In $O(\log k)$ Zeit kann man $\log k$ W\"orter
      $C_0, \dots, C_{\log k}$ berechnen, so dass
      das Testbit des $i$-ten Eintrags von
      $C_j$ das $j$-te Bit der Bin\"ardarstellung von
      $i$ enth\"alt.
  \item Sei $X$ ein Wort, das die Folge $x_0, x_1, \dots, x_{k-1}$
    darstellt. Dann kann man in $O(\log k)$ Zeit ein Wort $Y$
    berechnen, das die Folge $x_{k-1}, x_{k-2}, \dots, x_0$ darstellt.
\end{enumerate}
\end{description}
\end{document}
