
diff -r 15594952470f -r a3feee84f858 tex/theory1_ex7.tex
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tex/theory1_ex7.tex	Wed Jul 06 17:00:17 2011 +0200
@@ -0,0 +1,108 @@
+\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}  
+\usepackage{graphicx}
+%\usepackage[latin1]{inputenc}
+\usepackage{amsmath, amsthm, amssymb}
+\usepackage{typearea}
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\usepackage{fullpage}
+\usepackage{mathtools}
+\usepackage[all]{xy}
+\title{Theory I, Sheet 7 Solution}
+\author{Eugen Sawin}
+\renewcommand{\familydefault}{\sfdefault}
+\include{pythonlisting}
+
+\pagestyle{empty}
+\begin{document}
+\maketitle
+
+\section*{Exercise 7.1}
+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. 
+
+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.
+\begin{python}
+def kmp(text, pattern):    
+    l = []
+    n = next(pattern)
+    j = 0
+    for i in range(len(text)):        
+        while j >= 0 and text[i] != pattern[j]:           
+            j = n[j]
+        j += 1
+        if j == len(pattern):            
+            l.append(i - len(pattern) + 1)
+            j = n[j]        
+    return l
+
+def next(pattern):
+    n = [-1]
+    j = -1
+    for i in range(len(pattern)):        
+        while j >= 0 and pattern[i] != pattern[j]:
+            j = n[j]        
+        j += 1
+        n.append(j)        
+    return n
+\end{python}
+
+\subsection*{1}
+\begin{align*}
+P &= rlrrlr\\
+next &= [0, 0, 1, 1, 2, 3]\\
+\end{align*}
+
+\subsection*{2}
+\begin{align*}
+P' &= rrllrrll\\
+next &= [0, 1, 0, 0, 1, 2, 3, 4]\\
+\end{align*}
+
+\subsection*{3}
+\begin{align*}
+P &= rlrrlr\\
+T &= lrrrlrrlllrrrlrrlrrllrlrrlrrlr\\
+next &= [0, 0, 1, 1, 2, 3]\\
+matched &= [12, 21, 24]\\
+\end{align*}
+You can find the full KMP-execution table in the attached text file \emph{kmp-output.txt}.
+
+\section*{Exercise 7.2}
+\begin{figure}[h]
+\entrymodifiers={+[F-]}
+\xymatrix
+{
+  &   & C & H & U & P & A & C & A & B & R & A  & S\\
+  & 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\\
+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\\
+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\\
+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\\
+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\\
+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]\\
+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\\
+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\\
+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\\
+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]\\
+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\\
+A & 11 & 10& 10& 10& 10& 9\ar[r] & 10& 9 & 8 & 7 & 6 \ar@{-->}[r]  & 7\\
+}
+\end{figure}
+\newpage
+\noindent We specify the edit operations:
+\begin{enumerate}
+\item replace A with C
+\item insert H
+\item replace B with U
+\item replace R with P
+\item keep A
+\item keep C
+\item keep A
+\item delete D
+\item delete A
+\item keep B
+\item keep R
+\item keep A
+\item insert S
+\end{enumerate}
+And we get $D(A, B) = 7$.
+\end{document}




