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

\newcommand{\ZETTELNUMMER}{10}
\newcommand{\ABGABEDATUM}{bis zum 13. Januar 2017, 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{Page-Rank I}{10 Punkte}

In der Vorlesung haben Sie gesehen,
dass Page-Rank einen
D\"ampfungsfaktor verwendet.  In dieser
Aufgabe sollen Sie untersuchen, was passiert,
wenn dieser D\"ampfungsfaktor weggelassen wird.
\begin{enumerate}
  \item Geben Sie ein Beispiel, bei dem 
    Page-Rank ohne D\"ampfungsfaktor
    \emph{nicht} konvergiert.
  \item Geben Sie ein Beispiel, bei dem 
    Page-Rank ohne D\"amfpungsfaktor
    zwar konvergiert, aber jedem Knoten die
    Page-Rank-Bewertung $0$ zuweist.
\end{enumerate}

\AUFGABE{Page-Rank II}{10 Punkte}

Betrachten Sie den folgenden Graphen $G$.

\begin{center}
\includegraphics{u10graph}
\end{center}

\begin{enumerate}
\item Geben Sie die modifizierte Adjazenzmatrix f\"ur 
      $G$ an.
\item Bestimmen Sie die Page-Rank-Bewertung f\"ur 
jeden Knoten algebraisch durch L\"osen des 
entsprechenden
Gleichungssystems (verwenden Sie den D\"ampfungsfaktor 
$0.25$).
\item F\"uhren Sie den iterativen Page-Rank-Algorithmus 
auf $G$ durch (wieder mit D\"ampfungsfaktor $0.25$). 
Wie viele Iterationen sind notwendig, bis der absolute 
Fehler kleiner als $0.001$ ist?

\emph{Hinweis}: Sie k\"onnen bei dieser 
Teilaufgabe gerne Octave oder Maple benutzen 
oder auch den Algorithmus selbst implementieren.
\end{enumerate}

\newpage
\AUFGABE{Priorit\"atswarteschlangen}{10 Punkte}
\begin{enumerate}
\item Nennen Sie zwei Ihnen bekannte Implementierungen 
des abstrakten Datentyps \emph{Priorit\"atswarteschlange},
und geben Sie die zugeh\"origen Laufzeiten an.
\item
Zeigen Sie, wie man mit Hilfe einer 
Priorit\"atswarteschlange eine Folge 
von $n$ Elementen aus einem total 
geordneten Universum sortieren kann.
\item
Wie Sie wissen, ben\"otigt jeder vergleichsbasierte 
Sortieralgorithmus mindestens $\Omega(n \log n)$ 
Operationen. In Anbetracht von (b), was besagt 
dies \"uber die Laufzeit jeder vergleichsbasierten 
Implementierung einer Priorit\"atswarteschlange?
Kann amortisierte Analyse hier helfen?
\end{enumerate}

\end{description}
\end{document}
