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

\newcommand{\ZETTELNUMMER}{9}
\newcommand{\ABGABEDATUM}{bis zum 6. 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
\noindent
Dieser Zettel enth\"alt nur Zusatzaufgaben. Das HA-Team
w\"unscht frohe Weihnachten und ein gutes neues Jahr.

\begin{description}
\AUFGABE {Verst\"andnisfragen}{10 Zusatzpunkte}

\begin{enumerate}
\item Definieren Sie die folgenden Begriffe:
  worst-case Laufzeit, average-case Laufzeit, amortisierte Laufzeit,
  erwartete Laufzeit. Finden Sie Gemeinsamkeiten und Unterschiede.
\item Nennen Sie Gemeinsamkeiten und Unterschiede zwischen 
Divide-and-Conquer und dynamischem Programmieren.
\item  Angenommen, wir haben einen ungerichteten Graphen 
$G = (V,E)$ mit Knotenmenge
$V= \{a, b, c, d, e, f, g, h, i, j, k\}$ gegeben. 
Wir m\"ochten die Zusammenhangskomponenten
von $G$ bestimmen. Dazu verwenden wir die Union-Find 
basierte Strategie aus der
Vorlesung. Nehmen Sie an, dass die Kanten aus $E$ in folgender Reihenfolge
bearbeitet werden: 
$(d, i)$, $(f, k)$, $(g, i)$, $(b, g)$, $(a, h)$, $(i, j)$,
$(d, k)$, $(b, j)$, $(d, f)$, $(g, j)$, $(a, e)$, $(i, d)$.

Zeigen Sie den Status der Union-Find Datenstruktur nach der Bearbeitung
jeder Kante. Verwenden Sie Union-By-Rank und Pfadkompression. Geben Sie
auch die R\"ange der einzelnen Knoten an.
\end{enumerate}

\AUFGABE {Blocksatz}{10 Zusatzpunkte}

Gegeben sei ein Text, also eine Folge $(w_1,\ldots,w_n)$ von $n$ W\"ortern. 
Dabei habe Wort $w_i$ die L\"ange $l_i$. Wir m\"ochten diesen Text 
m\"oglichst gut als Blocksatz mit gegebener Zeilenl\"ange $M$ setzen
(alle W\"orter haben h\"ochstens $M$ Buchstaben). 
Das Kriterium f\"ur ``m\"oglichst gut'' wird im Folgenden beschrieben:

Angenommen eine Zeile $z$ besteht aus den W\"ortern $w_i,\dots,w_j$.
Dann enth\"alt diese Zeile 
\[
M-\sum_{k=i}^j l_k
\]
%zusätzliche 
Leerzeichen. Sei nun die \emph{Strafe} $p_z$ f\"ur eine Zeile $z$ definiert als
\[
p_z:=\left\{\begin{array}{ll}
            \left(\frac{M-\sum_{k=i}^j l_k}{j-i}\right)^3\cdot(j-i), & 
	    \text{ falls $j> i$}\\[1.7ex]
            \bigl(M-l_i\bigr)^3                  , & \text{ falls $i=j$}.
            \end{array}\right.
\]
Ein Blocksatz gilt als ``gut'', wenn die Summe der Strafen 
$p_z$ \"uber alle Zeilen $z$ au\ss{}er der letzten minimal ist. 
\\
\textbf{Beispiel:}
\[
\begin{array}{|c|c|c|c|c|c|c|c||rcl}\hline
a&a&a&\rule{1ex}{0ex}&a&a&\rule{1ex}{0ex}&a&\quad (2/2)^3\cdot 2&=&2\\ 
\hline
b&b& &               & &b&b&     b          &\quad (3/1)^3\cdot 1&=&27\\ 
\hline
c&c&c&c              & & & &                &\quad 4^3&=&64\\ \hline
d&d&d&d              &d& & &                &\\ \hline\hline
 \multicolumn{8}{r||}{}                       &\quad &&93
\end{array}
\]
\begin{enumerate}
\item
L\"osen Sie dieses Problem mittels Dynamischer Programmierung. 
Analysieren Sie die Laufzeit und den Speicherbedarf Ihres Algorithmus 
und begr\"unden Sie Ihr Vorgehen. 
\\
\emph{Anmerkung}: Nat\"urlich sollen zwei aufeinander folgende 
W\"orter einer Zeile durch mindestens ein Leerzeichen getrennt sein.
%

\item
Implementieren Sie Ihren Algorithmus  
in Java. Testen Sie Ihr Programm mit 
verschiedenen Texten und vergleichen Sie ``Ihren'' Blocksatz mit dem 
einer Textverarbeitungssoftware (z.B. MS Word, \LaTeX, LibreOffice). 
Zeigen Sie ein Beispiel, bei dem das 
Programm eine bessere Ausgabe erzeugt als das triviale Greedy-Verfahren 
(jede 
Zeile wird so weit wie m\"oglich gef\"ullt und dann ausgerichtet).
\end{enumerate}

\AUFGABE{Viterbi-Algorithmus}{10 Zusatzpunkte}

Auf dem 4. Aufgabenblatt haben Sie sich in Aufgabe 3(c) eine
M\"oglichkeit \"uberlegt, wie man mit dem Viterbi-Algorithmus
Rechtschreibfehler korrigieren kann.
Setzen Sie nun Ihre Idee in die Tat um. Modellieren und implementieren
Sie  versteckte Markov-Modelle in Java und implementieren Sie sodann
den Viterbi-Algorithmus. Entwickeln Sie auch eine Klasse, welche
die \"Ubergangswahrscheinlichkeiten f\"ur Ihr Modell durch Abz\"ahlen
ermittelt
(Beachten Sie auch den Trick aus Aufgabe 3(b)).

Nehmen Sie dann einen repr\"asentativen Text mittlerer 
L\"ange (etwa 200 KB). Verwenden Sie die ersten 50 KB zum
Lernen und ver\"andern Sie den Rest, indem Sie jedes
Zeichen mit Wahrscheinlichkeit 10\% durch ein zuf\"alliges
Zeichen ersetzen. Wie gut schneidet Ihr Algorithmus auf diesen
Testdaten ab? Experimentieren Sie mit verschiedenen Trainingsl\"angen
und Fehlerraten.

\AUFGABE{Dynamisches Programmieren und Divide-and-Conquer}{10 Zusatzpunkte}

In dieser Aufgabe wollen wir uns \"uberlegen, wie man beim dynamischen
Programmieren Speicherplatz einsparen kann. Dabei wird die 
Laufzeit nur wenig schlechter. Als Beispiel soll
das Einkaufsproblem (Rucksackproblem) dienen.

\begin{enumerate}
  \item In der Vorlesung haben Sie gesehen, wie man das Einkaufproblem
  mit $n$ Artikeln und Budget $B$ in Zeit und Platz $O(nB)$ l\"osen
  kann. Argumentieren Sie, dass man mit  $O(n + B)$ Platz auskommen kann, 
  wenn man nur den \emph{Wert} einer optimalen L\"osung sucht.

  \item Erinnern Sie sich, dass ein optimaler Einkauf einem
    Weg in der Tabelle $E$ von $E[n,B]$ zu $E[0,0]$ entspricht,
    wobei die einzelnen Schritte von dem Array \texttt{kaufen} 
    abh\"angen (siehe Notizen auf der Vorlesungsseite). Zeigen
    Sie: Man kann die Stelle, an der ein optimaler Weg die
    Zeile $n/2$ kreuzt, in $O(B)$ Platz berechnen.
  \item Benutzen Sie das Divide-and-Conquer Prinzip, um einen optimalen
    Weg von $E[n,B]$ nach $E[0,0]$  in $O(n + B)$ Platz
    zu berechnen. Was ist die resultierende Laufzeit?

    \emph{Hinweis}: Verwenden Sie (b), um die Stelle zu
      finden, an der ein optimaler Weg die Zeile $n/2$
      kreuzt. Berechnen Sie dann rekursiv einen optimalen
      Weg von Zeile $n$ zu Zeile $n/2$ und von Zeile
      $n/2$ zu Zeile $0$. Beachten Sie, dass sich
      Speicherplatz wiederverwenden l\"asst.
\end{enumerate}


\end{description}
\end{document}
