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

\newcommand{\ZETTELNUMMER}{12}
\newcommand{\ABGABEDATUM}{am 26. Januar~2018 bis 10 Uhr in die 
  jeweiligen Tutorenf\"acher}

\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}}
\newcommand{\N}{\mathbb{N}}

\renewcommand{\labelenumi}{(\alph{enumi})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Algorithmen, Datenstrukturen und Datenabstraktion}\hfill WS 17/18 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Katharina Klost

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm
\noindent

\begin{description}
    \AUFGABE{Editierabstand}{10 Punkte}

Der \emph{Editierabstand} zwischen zwei Zeichenketten
$s$ und $t$ ist die minimale Anzahl von
\emph{Editieroperationen}, um $s$ nach $t$ zu \"uberf\"uhren.
Es gibt drei Editieroperationen:
(i) Einf\"ugen eines Zeichens; (ii) L\"oschen eines Zeichens;
und (iii) Ersetzen eines Zeichens durch ein anderes.
Zum Beispiel betr\"agt der Editierabstand zwischen 
``APFEL'' und ``PFERD'' drei: L\"osche A, ersetze
L durch R, f\"uge D ein.

Beschreiben Sie einen Algorithmus, der den Editierabstand zwischen
zwei Zeichenketten $s$ und $t$ in $O(k\ell)$ Zeit berechnet, wobei
$s$ L\"ange $k$ und $t$ L\"ange $\ell$ hat. Erkl\"aren
Sie au\ss{}erdem, wie man eine optimale Folge von Editieroperationen
findet.

\noindent
\emph{Hinweis:} Benutzen Sie dynamisches Programmieren
analog zum LCS-Problem: 
betrachten Sie das jeweils letzte Zeichen in $s$ und
$t$ und unterscheiden Sie drei M\"oglichkeiten:
(a) \"uberf\"uhre $s$ nach $t'$ und f\"uge dann ein Zeichen an;
(b) \"uberf\"uhre $s'$ nach $t$ und l\"osche dann ein Zeichen; (c)
\"uberf\"uhre $s'$ nach $t'$ und ersetze dann ein Zeichen, falls n\"otig.
Hierbei bezeichnen $s'$ und $t'$ jeweils $s$ und $t$ ohne den letzten 
Buchstaben.

\AUFGABE{Suchen in Zeichenketten}{10 Punkte}

\begin{enumerate}
\item 
  Implementieren Sie den naiven Algorithmus und
  den Algorithmus von Rabin-Karp zur Suche in Zeichenketten. 
  Finden Sie dann heraus, 
  wie oft das Wort \emph{whale} in Moby Dick vorkommt
  (ignorieren Sie dabei Gro\ss{}- und Kleinschreibung). Wie schneiden Ihre
  Implementierungen im Vergleich ab?

  \noindent
  \emph{Hinweis:} Den Roman Moby Dick finden Sie unter\\
  \texttt{http://www.gutenberg.org/files/2701/2701-0.txt}.
\item
  Der Algorithmus von Rabin-Karp l\"asst sich
  leicht auf \emph{mehrere} Suchmuster verallgemeinern.
  Gegeben eine Zeichenkette $s$ und Suchmuster 
  $t_1, \dots, t_k$, bestimme die erste Stelle in $s$, an der
  eines der Muster $t_1, \dots, t_k$ vorkommt. Beschreiben
  Sie, wie man den Algorithmus von Rabin-Karp f\"ur diese Situation 
  anpassen kann. Was ist die heuristische Laufzeit Ihres Algorithmus
  (unter der Annahme, dass Kollisionen selten sind)?

  \emph{Hinweis:} Nehmen Sie zun\"achst an, dass alle Suchmuster die gleiche
    L\"ange haben. Der allgemeine Fall l\"asst sich darauf zur\"uckf\"uhren,
    z.B., indem man zum Hashen alle Suchmuster auf die Minimall\"ange 
    verk\"urzt.
\item
  (\emph{freiwillig, 5 Zusatzpunkte})
  Implementieren Sie Ihren Algorithmus aus (b). Beantworten Sie sodann
  folgende Frage: Was kommt \"ofter in dem
  Roman Sense \& Sensibility vor: \emph{sense} oder 
  \emph{sensibility}/\emph{sensible}?

  \noindent
  \emph{Hinweis:} Siehe \texttt{http://www.gutenberg.org/files/161/161.txt}.
\end{enumerate}

\end{description}

\noindent
\emph{Hinweis}:
Bitte formatieren Sie Ihre Abgaben mit \LaTeX\xspace oder einem
vergleichbaren elektronischen Textverarbeitungssystem. Ansonsten droht
der Abzug von bis zu 10\% der erreichbaren Punkte.



\end{document}
