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

\newcommand{\ZETTELNUMMER}{11}
\newcommand{\ABGABEDATUM}{on 18. January~2019, 10:00, in the
respective TA's mailbox}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem \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{\R}{\mathbb{R}}



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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Problem Set on

\smallskip
\noindent
\large
\textbf{Algorithms, Data Structures and Data 
Abstraction}\hfill WS 18/19 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm

\begin{description}


\AUFGABE{Greedy Change}{10 Points}
 
Consider the problem of making change at a 
cash register. We are supposed to return 
an amount of $n$ cents, while using
the minimum number of coins.
Recall that there are Euro-coins for 
1, 2, 5, 10, 20, 50, 100, and 200 cents.

\begin{enumerate}
\item Describe a greedy algorithm for the problem,
  and implement it. What is the running time?
\item
  Prove that your algorithm from (a) always gives an optimal solution.

  \emph{Hint}: Think about the structure of an optimal
  solution. How many 1-cent coins can it have
  at most? How many 2-cent coins? etc?
  What is the maximum partial amount in an optimal solution that can
  be represented by coins of value
  at most $c$, for 
 $c \in \{2,5,10,20,50, 100\}$?

\item Give a family of coin denominations for which 
   the greedy algorithm fails to give an optimal solution. 
  There should be a 1-cent coin, so that
  we can make change for every possible amount.

%\item Let $c > 1$ and
%  $k \geq 1$ be natural numbers, and assume that we have coins 
%  of value $1, c, c^2, \dots, c^k$. Prove that the greedy algorithm
%  also gives an optimal solution for these coin denominations.
\end{enumerate}

\AUFGABE{Edit Distance}{10 Points}

The 
\emph{edit distance} between two strings
$s$ and $t$ is the minimum number of 
\emph{edit operations} needed to convert $s$ into $t$.
There are three edit operations:
(i) insert a character; (ii) delete a character;
and (iii) replace a character by another one.
For example, the edit distance between 
``APFEL'' and ``PFERD'' is $3$: delete A, replace
L by R, insert D.

Give an algorithm that determines the edit distance between
two strings 
$s$ and $t$ in $O(k\ell)$ time, where
$s$ has length  $k$ and $t$ has length $\ell$. Moreover, explain
how to find an optimal sequence of edit operations.

\noindent
\emph{Hint:} Use dynamic programming similar to the
LCS-problem: 
consider the respective last character of  $s$ and
$t$ and distinguish three possibilities:
(a) convert  $s$ to $t'$ and add a character;
(b) convert $s'$ to $t$  and delete a character; or (c)
convert $s'$ to $t'$ and replace a character, if necessary.
Here, 
$s'$ and $t'$ denote $s$ and $t$ without the last character.

\newpage
\AUFGABE{String Search}{10 Points}

\begin{enumerate}
\item 
  Implement the naive algorithm for string search 
  as well as the algorithm of Rabin-Karp.
  Then, determine how often the word 
  \emph{whale} appears in the novel \emph{Moby Dick} 
  (ignoring case). How do the two implementations
  compare?

  \noindent
  \emph{Hint:} You can find \emph{Moby Dick} under \\
  \texttt{https://algs4.cs.princeton.edu/63suffix/mobydick.txt}.
\item
  The algorithm of  Rabin-Karp can be extended easily to
  \emph{several} search patterns.
  Given a string  $s$ and search patterns 
  $t_1, \dots, t_k$, determine the first position in $s$, where
  one of the patterns $t_1, \dots, t_k$ occurs. Describe 
  how to adapt the Rabin-Karp Algorithm to this situation.
  What is the heuristic running time of the algorithm
  (assuming that collisions are rare)?

  \emph{Hint:} First, assume that all search patterns 
  have the same length.
   The general case can be reduced to this case, e.g.,
   by truncating all search patterns to the same length.
\item
  (\emph{voluntary, 5 extra points})
  Implement the algorithm from (b). Then, determine
  who occurs most often in Moby Dick: Ishmael, Queequeg
  or Ahab?
\end{enumerate}

\end{description}

\end{document}
