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

\newcommand{\ZETTELNUMMER}{6}
\newcommand{\ABGABEDATUM}{bis zum 2. Dezember 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{Caching} {10 Punkte}

\begin{enumerate}
\item
In der Vorlesung wurde behauptet, dass man jede Ersetzungsstrategie
f\"ur das Offline-Caching-Problem in eine \emph{reduzierte} 
Ersetzungsstragie umwandeln kann, die Anzahl der Hauptspeicherzugriffe
zu erh\"ohen. Dabei bedeutet reduziert, dass ein Datum erst dann 
aus dem Hauptspeicher in den Cache geladen wird, wenn es auch wirklich 
angefragt wird. 

Geben
Sie einen detaillierten Beweis f\"ur diese Behauptung.
\item
Normalerweise findet Caching in einem Online-Setting statt, bei dem
die Zugriffsfolge nicht im Voraus bekannt ist.
Eine beliebte Heuristik ist die LRU-Regel (Least-Recently-Used).  LRU 
entfernt immer das Datum aus dem Cache, dessen letzter Zugriff am 
weitesten zur\"uck liegt.
Zeigen Sie, dass es beliebig lange Zugriffsfolgen gibt, bei denen LRU $k$ 
mal so viele
Cache-Misses verursacht wie die Furthest-in-the-Future-Regel aus der
Vorlesung, welche die gesamte Zugriffsfolge kennt. 
Hierbei bezeichnet $k$ die Cachegr\"o\ss{}e.

Sie k\"onnen annehmen, dass der Cache anfangs die Elemente
mit Adressen $1, 2, \dots, k$ enth\"alt, und dass die ersten
Speicherzugriffe der Folge an die Adressen $1, 2, \dots, k$ gehen.
\end{enumerate}

\AUFGABE{Union-Find} {10 Punkte}

Betrachten Sie eine Folge von \textbf{Union} und \textbf{Find} Operationen
der L\"ange $m$. Nehmen Sie an, dass wir mit
der Partition $\{\{1\}, \{2\}, \ldots, \{n\}\}$ beginnen und dass wir
den Algorithmus aus der Vorlesung mit Union-By-Rank und Pfadkompression
verwenden.
Zeigen Sie:
\begin{enumerate}
\item
Werden alle \textbf{Union}-Operationen  vor allen \textbf{Find}-Operationen 
durchgef\"uhrt, so ist die Gesamtlaufzeit $O(n+m)$. 

\emph{Hinweis}: Ordnen Sie die Kosten jeder bei einem 
\textbf{Find} durchlaufenen Kante, bis auf die letzte, einer 
\textbf{Union}-Operation zu.
\item
Wenn alle \textbf{Find}-Operationen auf Mengen mit mindestens 
$\log n$ Elementen durchgef\"uhrt werden, so ist die Gesamtlaufzeit
$O(n + m)$.
\end{enumerate}

\AUFGABE{Bitmaps} {10 Punkte}

Sei $n$ eine nat\"urliche Zahl. Ein \emph{$n \times n$ Bitmap} ist
ein Array $B[1\ldots n, 1 \ldots n]$ vom Typ \texttt{Boolean}, welches
ein Schwarz-Wei\ss{}-Bild darstellt. Der Eintrag \texttt{true}
bedeutet, dass das Pixel an der entsprechenden Stelle schwarz ist,
der Eintrag \texttt{false} bedeutet, dass das entsprechende Pixel wei\ss{} ist.
Zwei Pixel sind \emph{benachbart}, wenn sie horizontal oder
vertikal nebeneinander liegen.
\begin{enumerate}
\item Entwerfen und analysieren Sie einen effizienten Algorithmus, der
  eine gr\"o\ss{}te Zusammenhangskomponente von  schwarzen
  Pixeln in $B$ bestimmt.
\item Beschreiben und analysieren Sie eine Datenstruktur,
welche die folgende Funktion unterst\"utzt: 
  \texttt{schw\"arze}$(i,j)$ f\"arbt das Pixel an der
  Stelle $B[i,j]$ schwarz und gibt die Gr\"o\ss{}e
  einer gr\"o\ss{}ten Zusammenhangskomponente von schwarzen
  Pixeln zur\"uck. Zu Beginn sind alle
  Pixel wei\ss{}. 
  
  Die Gesamtlaufzeit f\"ur jede Folge von
  $m$ Aufrufen von \texttt{schw\"arze} sollte so gering wie m\"oglich sein.
\item Was ist die worst-case Laufzeit f\"ur einen Aufruf Ihrer Funktion
  \texttt{schw\"arze} aus (b)?
\end{enumerate}

%\hskip12cm \emph{Bitte wenden}
%
%\newpage

\AUFGABE {Matroide}{freiwillig, 10 Zusatzpunkte}

Sei $S$ eine endliche, nichtleere Menge, und sei
$\mathcal{I} \subseteq 2^S$ eine nichtleere Menge von Teilmengen von $S$.
Das Paar $M = (S, \mathcal{I})$ hei\ss{}t \emph{Matroid}, wenn gilt:
(i) \textbf{Vererbung}: Wenn $A \in \mathcal{I}$ und $B \subseteq A$,
so ist $B \in \mathcal{I}$. Insbesondere ist $\emptyset \in \mathcal{I}$.
(ii) \textbf{Austausch}: Wenn $A, B \in \mathcal{I}$ und $|A| < |B|$ ist,
dann existiert ein $x \in B \setminus A$, so dass 
$A \cup \{x\} \in \mathcal{I}$ ist.
Die Elemente von $\mathcal{I}$ hei\ss{}en die \emph{unabh\"angigen Mengen}
von $M$.

\begin{enumerate}
  \item Eine inklusionsmaximale unabh\"angige Menge hei\ss{}t \emph{Basis} von $M$.
     Zeigen Sie, dass alle Basen von $M$ die gleiche Anzahl von Elementen
     haben.
  \item Sei $w: S \rightarrow \mathbb{R}^+$ eine Gewichtsfunktion, die 
  jedem Element
     aus $S$ ein positives Gewicht zuordnet. Wir m\"ochten eine Basis 
     von $M$
     mit maximalem Gewicht finden, wobei das Gewicht einer Teilmenge als die
     Summe der Einzelgewichte definiert ist. Dies geht mit einem gierigen
     Algorithmus: Sortiere die Elemente aus $S$ absteigend nach ihrem
     Gewicht. Setze $B := \emptyset$. Gehe $S$ in der Reihenfolge durch 
     und f\"uge das n\"achste Element zu $B$ hinzu, wenn $B$ dadurch
     unabh\"angig bleibt. Gib die resultierende Menge $B$ zur\"uck.

     Zeigen Sie, dass der gierige Algorithmus eine Basis von maximalem
     Gewicht bestimmt. Was k\"onnen Sie zur Laufzeit sagen?

     \emph{Hinweis}: Verwenden Sie ein Austauschargument, um zu zeigen,
       dass sich jede optimale Basis in die gierige Basis
       \"uberf\"uhren l\"asst, ohne dass sich dabei das Gewicht verringert.

\end{enumerate}

\end{description}
\end{document}
