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

\newcommand{\ZETTELNUMMER}{5}
\newcommand{\ABGABEDATUM}{bis zum 25. 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{Intervallauswahl und Intervallunterteilung}{10 Punkte}

Beschreiben Sie, wie sich die Strategien aus der
Vorlesung zur Intervallauswahl und zur Intervallunterteilung
mit Laufzeit $O(n \log n)$ implementieren lassen. 
Begr\"unden Sie Ihre Antwort.

\AUFGABE{Intervallauswahl}{10 Punkte}
 
In der Vorlesung haben Sie einen Algorithmus zur 
Intervallauswahl gesehen. 
Gegeben sind $n$ Intervalle $[s_1, t_1], 
\dots, [s_n, t_n]$. Gesucht ist eine 
gr{\"o}{\ss}tm{\"o}gliche Menge $A$ von 
paarweise disjunkten Intervallen.  Wir 
haben eine einfache Greedy-Strategie verwendet: 
Sortiere die Intervalle nach einem bestimmten Kriterium 
und betrachte die Intervalle in dieser 
Reihenfolge. Ein Intervall wird genau dann zu $A$ 
hinzugef{\"u}gt, wenn es zu den bisherigen 
Intervallen in $A$ disjunkt ist. 

Entscheiden Sie f{\"u}r jedes der folgenden Kriterien, 
ob es eine Menge $A$ maximaler Gr{\"o}{\ss}e liefert. 
Falls ja, so geben Sie Pseudocode f\"ur eine effiziente
Implementierung an und begr\"unden Sie Korrektheit und 
Laufzeit. Falls nein, geben Sie ein Beispiel an,
f{\"u}r welches der Algorithmus keine optimale L{\"o}sung 
liefert. 
\begin{enumerate}
\item Sortiere aufsteigend nach den Anfangszeiten.
\item Sortiere absteigend nach den Anfangszeiten.
\item Sortiere absteigend nach den Endzeiten.
\item Sortiere aufsteigend nach der L{\"a}nge.
\item Sortiere absteigend nach der L{\"a}nge.
\end{enumerate}

\AUFGABE{Autobahnfahrt}{10 Punkte}

Hannelore und Werner wollen mit dem Auto von 
Berlin nach Dortmund fahren. Wenn der Tank 
des Autos voll ist, so k\"onnen sie $n$ 
Kilometer zur\"ucklegen. Die Stra\ss{}enkarte 
gibt ihnen die Abst\"ande zwischen den einzelnen
Tankstellen entlang der Autobahn. Werner und Hannelore 
wollen so wenig Tankstopps wie m\"oglich einlegen. 
Geben Sie einen effizienten Algorithmus an,
mit dem Hannelore und Werner eine kleinstm\"ogliche Menge von 
Tankstellen finden k\"onnen, an denen sie anhalten sollen.

Beweisen Sie die Korrektheit Ihres Algorithmus und analysieren 
Sie die Laufzeit.

\end{description}
\end{document}
