\documentclass[12pt]{article}

\input{cps130}

\begin{document}

\title{Dynamic Programming: LCS (22)}
\author{Michael L. Littman}
\date{December 3rd, 1998}

\maketitle 

\section{REVIEW}

\subsection{Maximum Probability Segmentation}

\ni Recall how we developed an algorithm for this.

\ul
\li We began with a recursive formulation: The best way to break up a
sequence is the best combination of a first word with the best way to
break up the remainder of the sequence.

\li Then, we noticed that implementing this directly recursively would
result in lots of wasted work.

\li So, we decided to ``cache'' the results of our work and compute
answers in reverse order to fill in the table.  That way, whenever we
need the solution to a subproblem, it's already in our table.

\li Actually, a lot like solving problems on a DAG (since you can
write the computational dependencies as a graph and work in reverse
topological order).

\li Running time was $O(n^2)$, since each of the $n$ table entries
takes $O(n)$ to fill in.

\el


\section{LONGEST COMMON SUBSEQUENCE}

\subsection{Problem}

\ni Given a text file and a variation of the file, identify lines that
have been deleted, inserted, or changed.

\ni I use this all the time in the form of the UNIX {\tt diff} command.

\ul
\li source code control: efficiently store multiple versions of a large
program by keeping changes as ``diffs.''
\li collaborative authoring: focus attention on new edits.
\li software distribution: send updates as ``diffs'' instead of
resending entire tree.
\li debugging: compare the output of a newly compiled program to the
correct output (can be used for grading also).
\el

\subsection{Formal Definition}

\ni A {\em sequence\/} is a list $X = \langle x_1, x_2, \ldots,
x_m\rangle$ (e.g., $\langle A,B,C,B,D,A,B \rangle$).

\ni A {\em subsequence\/} of $X$ is an ordered sublist of $X$ (e.g., 
$\langle B,C,D,B \rangle$, but not $\langle D,C,B \rangle$).

\ni A {\em common subsequence\/} of two sequences $X$ and $Y=\langle
B,D,C,A,B\rangle$ is a subsequence of both of them.

\ni The LCS, or {\em longest common subsequence\/} of $X$ and $Y$ is,
well, their longest possible common subsequence.  What is it?

% bdab

\ni We'll also use $X_i$ to mean the $i$-element prefix of $X$.  So
$X_m = X$ if $X$ is length $m$.


\subsection{Algorithmic Ideas}

\ni How would you solve this?  Hint, it will involve filling in a
table!

\ul

\li Think of ``optimal substructure'' property (like when we talked
about paths).

\li Think of a recursive solution.

\el


\subsection{Optimal Substructure Theorem}

\ni Let $X=\langle x_1,x_2,\ldots,x_m\rangle$ and $Y=\langle
y_1,y_2,\ldots,y_n\rangle$ be sequences, and let $Z=\langle
z_1,z_2,\ldots,z_k\rangle$ be any LCS of $X$ and $Y$.

\ul

\li 1. If $x_m = y_n$, then $z_k = x_m = y_n$ and $Z_{k-1}$ is an LCS
of $X_{m-1}$ and $Y_{n-1}$.

\li 2. If $x_m \neq y_n$, then $z_k \neq x_m$ implies that $Z$ is an
LCS of $X_{m-1}$ and $Y$.

\li 3. If $x_m \neq y_n$, then $z_k \neq y_n$ implies that $Z$ is an
LCS of $X$ and $Y_{n-1}$.

\el

\subsection{Recursive Formula}

\ni Let $c[i,j]$ be the length of the LCS of $X_i$ and $Y_j$
(prefixes).

$$c[i,j] = \left\{ \begin{array}{ll}
                    0 & \mbox{if $i=0$ or $j=0$,}\\
                   c[i-1,j-1]+1 & \mbox{if $i,j>0$ and $x_i = y_j$,}\\
                   \max(c[i,j-1],c[i-1,j]) & \mbox{otherwise}.
		   \end{array} \right.$$

\subsection{Algorithm}

\begin{algorithm}{LCS-Length}{X,Y}
 m \= \mbox{\em length}[X] \\
 n \= \mbox{\em length}[Y] \\
 \begin{FOR}{i \= 1 \TO m}
  c[i,0] \= 0
 \end{FOR} \\
 \begin{FOR}{j \= 1 \TO n}
  c[0,j] \= 0
 \end{FOR} \\
 \begin{FOR}{i \= 1 \TO m}
  \begin{FOR}{j \= 1 \TO n}
   \begin{IF}{x_i = y_j}
    c[i,j] \= c[i-1,j-1]+1\\
    b[i,j] \= \mbox{``$\nwarrow$''}
   \ELSE
    \begin{IF}{c[i-1,j] \ge c[i,j-1]}
     c[i,j] \= c[i-1,j]\\
     b[i,j] \= \mbox{``$\uparrow$''}
    \ELSE
     c[i,j] \= c[i,j-1]\\
     b[i,j] \= \mbox{``$\leftarrow$''}
    \end{IF}
   \end{IF}
  \end{FOR}
 \end{FOR} \\
 \RETURN c \mbox{ and } b
\end{algorithm}

\subsection{General Running-Time Analysis for Dynamic Programming}

\ni Nearly any DP algorithm can be analyzed by multiplying the size of
the table by the time it takes to fill in a single cell of the table.

\ul

\li segmentation: $n$ table entries, $O(n)$ time to fill in, $O(n^2)$ total.

\li LCS: $n m$ table entries, $O(1)$ time to fill in,  $O(n m)$ total.

\el

\subsection{Beam Search}

\ni In practice, it doesn't make sense to fill in the whole table.

\ni Instead, consider a limited window (size $k$) at any one time.

\ni Not optimal, since might be more than $k$ added or deleted lines.

\ni Works well in practice, and brings running time down to $O(nk)$.


\subsection{Memoization}

\ni Can make the recursive formulation work, as long as you don't let
yourself compute the answer to the same question repeatedly.

\ul

\li Create a hash table for each subroutine associating inputs to
answers.

\li No side effects, so same input means same output.  

\li Each time we compute an output, store it in the hash table.

\li Before we try to compute a new answer, see if that one's already
in the hash table (and return right away if it is).

\li Get same worst-case bounds (often better best case).

\li (Can do the same with DFS to identify ``reachable'' subproblems.)

\el

\ni Turn an exponential algorithm into a quadratic one!

\section{OTHER PROBLEMS}

\subsection{Other Problems}

\ni If time, we could do optimal matrix chain.  Or stochastic shortest
paths.

\end{document}
