1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tex/theory1_ex7.tex Wed Jul 06 17:00:17 2011 +0200
1.3 @@ -0,0 +1,108 @@
1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
1.5 +\usepackage{graphicx}
1.6 +%\usepackage[latin1]{inputenc}
1.7 +\usepackage{amsmath, amsthm, amssymb}
1.8 +\usepackage{typearea}
1.9 +\usepackage{algorithm}
1.10 +\usepackage{algorithmic}
1.11 +\usepackage{fullpage}
1.12 +\usepackage{mathtools}
1.13 +\usepackage[all]{xy}
1.14 +\title{Theory I, Sheet 7 Solution}
1.15 +\author{Eugen Sawin}
1.16 +\renewcommand{\familydefault}{\sfdefault}
1.17 +\include{pythonlisting}
1.18 +
1.19 +\pagestyle{empty}
1.20 +\begin{document}
1.21 +\maketitle
1.22 +
1.23 +\section*{Exercise 7.1}
1.24 +For this exercise I've used a slightly different implementation of the KMP algorithm, which is semantically equal to the one presented in the lecture.
1.25 +
1.26 +In this version the $next$ array is prepended with a $-1$, which I omit from the solutions to correspond to the lecture's algorithm's output.
1.27 +\begin{python}
1.28 +def kmp(text, pattern):
1.29 + l = []
1.30 + n = next(pattern)
1.31 + j = 0
1.32 + for i in range(len(text)):
1.33 + while j >= 0 and text[i] != pattern[j]:
1.34 + j = n[j]
1.35 + j += 1
1.36 + if j == len(pattern):
1.37 + l.append(i - len(pattern) + 1)
1.38 + j = n[j]
1.39 + return l
1.40 +
1.41 +def next(pattern):
1.42 + n = [-1]
1.43 + j = -1
1.44 + for i in range(len(pattern)):
1.45 + while j >= 0 and pattern[i] != pattern[j]:
1.46 + j = n[j]
1.47 + j += 1
1.48 + n.append(j)
1.49 + return n
1.50 +\end{python}
1.51 +
1.52 +\subsection*{1}
1.53 +\begin{align*}
1.54 +P &= rlrrlr\\
1.55 +next &= [0, 0, 1, 1, 2, 3]\\
1.56 +\end{align*}
1.57 +
1.58 +\subsection*{2}
1.59 +\begin{align*}
1.60 +P' &= rrllrrll\\
1.61 +next &= [0, 1, 0, 0, 1, 2, 3, 4]\\
1.62 +\end{align*}
1.63 +
1.64 +\subsection*{3}
1.65 +\begin{align*}
1.66 +P &= rlrrlr\\
1.67 +T &= lrrrlrrlllrrrlrrlrrllrlrrlrrlr\\
1.68 +next &= [0, 0, 1, 1, 2, 3]\\
1.69 +matched &= [12, 21, 24]\\
1.70 +\end{align*}
1.71 +You can find the full KMP-execution table in the attached text file \emph{kmp-output.txt}.
1.72 +
1.73 +\section*{Exercise 7.2}
1.74 +\begin{figure}[h]
1.75 +\entrymodifiers={+[F-]}
1.76 +\xymatrix
1.77 +{
1.78 + & & C & H & U & P & A & C & A & B & R & A & S\\
1.79 + & 0\ar@{-->}[dr] \ar[d] \ar[r] & \ar[r]1\ar[dr] & 2\ar[dr]\ar[r] & 3\ar[dr]\ar[r] & 4\ar[dr]\ar[r] & \ar[r]5 & 6\ar[r]\ar[dr] & 7\ar[r] & 8\ar[r] & 9\ar[dr]\ar[r] & 10\ar[r] & 11\\
1.80 +A & 1\ar[dr] \ar[d] & 1\ar[d]\ar[dr] \ar@{-->}[r] & 2\ar[r]\ar@{-->}[dr] & 3\ar[r]\ar[dr] & 4\ar[dr] & 4\ar[d]\ar[r]\ar[dr] & 5\ar[dr]\ar[r] & 6\ar[r]\ar[dr] & 7\ar[r] & \ar[r]8 & 9\ar[r] & 10\\
1.81 +B & 2\ar[dr] \ar[d] & 2\ar[d]\ar[dr] & 2\ar[d]\ar[r]\ar[dr] & 3\ar[r]\ar@{-->}[dr] & 4\ar[r]\ar[dr] & 5\ar[dr] & 5\ar[d]\ar[r]\ar[dr] & 6\ar[dr] & 6\ar[d]\ar[r]\ar[dr] & 7\ar[r] & 8\ar[r] & 9\\
1.82 +R & 3\ar[dr] \ar[d] & 3\ar[d]\ar[dr] & 3\ar[d]\ar[dr] & 3\ar[d]\ar[r]\ar[dr] & 4\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[dr] & 6\ar[r]\ar[dr] & 7 & 6\ar[d]\ar[r]\ar[dr] & 7\ar[r] & 8\\
1.83 +A & 4\ar[dr] \ar[d] & 4\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[dr] & 4\ar[d]\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[r] & 7 & 7 & 6\ar[d]\ar[r]\ar[dr] & 7\\
1.84 +C & 5 \ar[d] & 4\ar[d]\ar[r]\ar[dr] & 5\ar[dr] & 5\ar[d]\ar[dr] & 5\ar[d]\ar[dr] & 5 & 4\ar[d]\ar[r]\ar@{-->}[dr] & 5\ar[r] & 6\ar[r] & 7\ar[dr] & 7\ar[dr] & 7\ar[d]\\
1.85 +A & 6 \ar[d] & 5\ar[d]\ar[dr] & 5\ar[d]\ar[r]\ar[dr] & 6\ar[dr] & 6\ar[d] & 5\ar[d]\ar[dr] & 5\ar[d] & 4\ar[r]\ar[dr] \ar@{-->}[d] & 5\ar[r]\ar[dr] & 6\ar[r]\ar[dr] & 7\ar[r]\ar[dr] & 8\\
1.86 +D & 7 \ar[d] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[r]\ar[dr] & 7\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr] & 5\ar[dr] \ar@{-->}[d] & 5\ar[d]\ar[dr]\ar[r] & 6\ar[r]\ar[dr] & 7\ar[r] & 8\\
1.87 +A & 8 \ar[d] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d]\ar[dr] & 7\ar[d] & 6\ar[d] \ar@{-->}[dr] & 6\ar[dr] & 6\ar[d]\ar[dr] & 6\ar[d]\ar[dr]\ar[r] & 7\\
1.88 +B & 9 \ar[d] & 8\ar[d]\ar[dr] & 8\ar[d]\ar[dr] & 8\ar[d]\ar[dr] & \ar[dr]8\ar[d] & 8\ar[d]\ar[dr] & 8\ar[d] & 7\ar[d] & 6\ar[d]\ar[r] \ar@{-->}[dr] & 7 & 7\ar[dr] & 7\ar[d]\\
1.89 +R & 10 \ar[d]& 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[d]\ar[dr] & 9\ar[dr] & 9\ar[d]\ar[dr] & 8\ar[d] & 7\ar[d] & 6\ar[d]\ar[r] \ar@{-->}[dr] & \ar[r]7 & 8\\
1.90 +A & 11 & 10& 10& 10& 10& 9\ar[r] & 10& 9 & 8 & 7 & 6 \ar@{-->}[r] & 7\\
1.91 +}
1.92 +\end{figure}
1.93 +\newpage
1.94 +\noindent We specify the edit operations:
1.95 +\begin{enumerate}
1.96 +\item replace A with C
1.97 +\item insert H
1.98 +\item replace B with U
1.99 +\item replace R with P
1.100 +\item keep A
1.101 +\item keep C
1.102 +\item keep A
1.103 +\item delete D
1.104 +\item delete A
1.105 +\item keep B
1.106 +\item keep R
1.107 +\item keep A
1.108 +\item insert S
1.109 +\end{enumerate}
1.110 +And we get $D(A, B) = 7$.
1.111 +\end{document}