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

\newcommand{\ZETTELNUMMER}{7}
\newcommand{\ABGABEDATUM}{am 3. 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{Kodierungsargument}{15 Punkte}

In der ersten Aufgabe des ersten \"Ubungsblattes haben
Sie gezeigt, dass bei Hashing mit Verkettung die
erwartete maximale Anzahl von Elementen auf demselben
Platz $O(\log n/\log\log n)$ ist.

Beweisen Sie nun diese Tatsache mit einem Kodierungsargument,
analog zur Analyse von Cuckoo-Hashing aus der Vorlesung.

\AUFGABE{Bereichsreduktion}{15 Punkte}

Beweisen Sie das Bereichsreduktionslemma von
Kirkpatrick und Reisch:
Angenommen, uns steht eine Wortl\"ange von $w$ Bits
zur Verf\"ugung und 
wir wissen, dass man $n$ Zahlen mit jeweils $w/4\log n$ Bits 
in $O(n \log\log n)$ Zeit sortieren kann.
Dann kann man auch $n$ Zahlen mit jeweils $w$ Bits in
$O(n \log\log n)$ Zeit sortieren.

\emph{Hinweis}:
  Nehmen Sie einen van-Emde-Boas-Baum und schneiden Sie ihn
  nach $\log\log n +2$ Ebenen ab.

%\AUFGABE{Korrektheit von Batchers Algorithmus}{10 Punkte}
%
%Ein Folge $S$ von Zahlen hei\ss{}t \emph{bitonisch},



\end{description}
\end{document}
