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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{bis zum 04. November 2016, 12 Uhr, in den
Briefkasten neben Raum 111}

\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

\smallskip
\noindent
\large
\textbf{H\"ohere Algorithmik}\hfill WiSe 2016/17 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Boris Klemz

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm

\begin{description}

\AUFGABE{Gewichteter Median}{10 Punkte}

Sei $S = \{s_1, s_2, \ldots, s_n\}$ eine Menge
von $n$ paarweise verschiedenen Elementen aus einem
total geordneten Universum. Seien $w_1$, $w_2$, $\ldots$,
$w_n$ positive Gewichte, so dass das Element $s_i$ Gewicht
$w_i$ hat. Es gelte $\sum_{i=1}^{n}w_i = 1$.
Der \emph{gewichtete Median} von $S$ ist das Element $s_k \in S$,
so dass gilt:
\[
\sum_{i:s_i < s_k} w_i \leq 1/2
\]
und
\[
\sum_{i: s_i > s_k} w_i < 1/2.
\]

\begin{enumerate}
\item
Angenommen, Sie haben eine Funktion, welche den gewichteten Median in
Zeit $T(n)$ bestimmt. Zeigen
Sie, wie man den (normalen) Median in Zeit $O(n) + T(n)$ 
berechnen kann.

\emph{Hinweis}: Finden Sie eine geschickte Wahl der Gewichte.

\item
Zeigen Sie, wie man den gewichteten Median in $O(n \log n)$ Zeit berechnen kann.

\emph{Hinweis}: Verwenden Sie einen geeigneten Sortieralgorithmus.

\item
Zeigen Sie, wie man den gewichteten Median in $O(n)$ Zeit finden kann, wenn
ein ein Linearzeitalgorithmus zum Finden des normalen Medians zur Verf\"ugung
steht.

\emph{Hinweis}: Passen Sie den generischen SELECT-Algorithmus
  geeignet an.
\end{enumerate}

\AUFGABE {Analyse des BFPRT-Algorithmus} {10 Punkte}

In der Vorlesung wurde der BFPRT-Algorithmus vorgestellt,  der in linearer Zeit das 
Auswahlproblem l\"ost. Dazu wird die Eingabe in 5-er Bl\"ocke aufgeteilt.
Bleibt die Laufzeit linear, wenn man die Eingabe in 7-er 
Bl\"ocke unterteilt? 
Welche Laufzeit erh\"alt man, wenn man 3-er Bl\"ocke verwendet
(in der $\Theta$-Notation)? 
Begr\"unden Sie jeweils Ihre Antwort.

(\emph{freiwillig, 5 Zusatzpunkte}) 
Man k\"onnte die Eingabe auch f\"ur festes ungerades $k$ in $k$-er 
Bl\"ocke aufteilen. Wie verh\"alt sich die Laufzeit in Abh\"angigkeit von $k$?
 
\hskip12cm \emph{Bitte wenden}

 \newpage

\AUFGABE {Schmutzige Tricks mit dem Einheitskostenma\ss{}}{10 Punkte}

Wenn die Zahlen in den Registern der RAM zu gro\ss{} werden, 
wird das Einheitskostenma\ss{} unrealistisch. Wir wollen nun
ein Beispiel sehen, wie man dadurch in Algorithmen schummeln
kann.

\begin{enumerate}
\item 
F\"ur zwei ganzzahlige Vektoren 
$x = (x_1; x_2; \ldots ; x_n)$ und $y = (y_1; y_2; \ldots ; y_n)$ mit
$0 \leq x_i, y_i \leq M$ und einen Wert $u > M$ betrachten wir die Zahlen 
\[
a = x_1 u^n + x_2 u^{n-1} + \cdots + x_nu^1 
\]
und
\[
b = y_1u^n + y_2u^{n-1} + \cdots + y_nu^1.
\]

Zeigen Sie: $a = b$ genau dann, wenn $x = y$ ist; $a < b$ genau dann, 
wenn $x$ lexikographisch kleiner als $y$ ist.

(Man kann also den Vergleich beliebig langer Vektoren durch den Vergleich 
einzelner Zahlen ersetzen.) 

\item 
Anwendung: Entwerfen Sie einen Algorithmus, der f\"ur zwei gegebene Folgen 
nichtnegativer ganzer Zahlen $x = (x_1; x_2; \ldots ; x_m)$ und 
$y = (y_1; y_2; \ldots ; y_n)$ in ``linearer'' Zeit entscheidet,
ob $x$ als Teilfolge $(y_{i+1}; y_{i+2}; \ldots ; y_{i+m})$ in 
$y$ vorkommt $(0 \leq i \leq n - m)$. Was ist die Laufzeit Ihres
Algorithmus im EKM und im  LKM?

\emph{Bemerkung}: Mit Hilfe von Hashing kann man aus dieser Idee
 einen ``seri\"osen'' Algorithmus zum Finden von Teilfolgen entwickeln.
 Dies ist der Algorithmus von Karp-Rabin.
\end{enumerate}

\end{description}
\end{document}
