dynamic_programming.tex

\chapter{Dynamic Programming}

So far we have considered two major strategies in algorithms design:
greedy, in which we repeatedly take the local optimum choice; and
divide and conquer, in which we divide the greater problem into
similar subproblems and recurse.

There may be problems for which these strategies are suboptimal.  In
which case, we have a third strategy which may be of use: dynamic
programming.  This strategy divides the problem into sub problems, but
rather than recursing on each sub problem individually, we identify
easy to compute base cases from which we can build towards the
solution to the larger problem, storing the results of previous
computations to use in later computations.  This technique differs
from a similar technique called ``memoization'' which computes
recursively top-down, whereas dynamic programming begins at the base
case(s) and works up.

Dynamic programming has these important steps:

\begin{enumerate}
\item Determine structure of optimal solution
\item Set up recurrences for optimal solution
\item Solve recurrences bottom-up
\item Construct the optimal solution
\end{enumerate}

And the final step is most often neglected since we can typically add
some small amount of information to the process so we can trivially
reconstruct the optimal solution.

\section{Matrix Chain Multiplication}

Assuming knowledge of matrices and how they are multiplied.

The problem is to find the way to multiply $n$ matrices $A_1,...,A_n$
with dimensions $p_0,...,p_n$ (e.g. $A_i$ has dimensions $p_{i-1}
\cross p_i$) using the least number of calculations.  Notice that
multiplying $A_iA_{i+1}$ takes $p_{i-1}p_ip_{i+1}$ calculations.

We start by determining the structure of the optimal solution.
Observe that the optimal solution will necessarily involve splitting
$A_1A_2...A_n$ into two subproblems at some optimally chosen
$A_kA_{k+1}$ so we multiply $A_1...A_k$ then $A_k...A_n$ and then
multiply the results together.  If we define the function $m(i,j)$ to
be the minimum cost of multiplying $A_i...A_j$, then the cost of the
optimal solution is $m(1,n) = m(1,k) + m(k+1,n) + p_0p_kp_n$.

We then define the recurrence $m(i,i) = 0$ and $m(i,j) = min \{ m(i,k) +
m(k+1,j) + p_{i-1}p_kp_j \}$ for all $k$ such that $i < k \leq j$.

We then compute all $m(i,i)$ for $1 \leq i \leq n$, then all
$m(i,i+1)$, $m(i,i+2)$, ... until we have calculated $m(1,n)$.

The time complexity of this solution is

\[
  \summ{l=2}{n}\summ{i=1}{n-l+1}\summ{k=i}{i+l+2}\BigOh{1} = \BigOh{n^3}
\]

\section{Longest Common Subsequence}

For a string $S = (s_1,s_2,\dots,s_n)$, a subsequence of $S$ is string $S'$ such that every element of $S'$ is in $S$, and if an element $a \in S'$ comes before $b \in S'$, this also holds for $S$. The longest common subsequence of two strings $A=(a_1,a_2,\dots,a_n)$ and $B = (b_1,b_2,\dots,b_m)$, is the longest string $C = (c_1,c_2,\dots,c_k)$, such that $C$ is a subsequence of $A$ and $B$.

Let the substring $(s_i,s_{i+1},\dots,s_j)$ be denoted as $S(i,j)$. Further, let $LCS(i,j)$ to be the length of the LCS of $A(0,i)$ and $B(0,j)$. Assume that we have computed $C(1,k)$, and that it is unique. Then if we remove $c_k$ and everything after it from $B$ and $A$, $C(1,k-1)$ is now the LCS of our modified $A$ and $B$. 

In general 
$LCS(i,j) =$

\begin{math}
   \left\{
    \begin{array}{l l}
      \emptyset 		& \text{if $i=0$ or $j=0$}\\
      LCS(i-1,j)+1 	& \text{if $a_i=b_j$}\\
      					& \text{and $LCS(i-1,j)>LCS(i,j-1)$}\\
      LCS(i,j-1)+1 	& \text{if $a_i=b_j$}\\
      					& \text{and $LCS(i-1,j)<LCS(i,j-1)$}\\
      
    \end{array} \right.
\end{math}

To compute this, we compute $LCS(0,0)$, $LCS(0,1)$,\dots,$LCS(0,m)$; then $LCS(1,0)$,\dots,$LCS(1,m)$; \dots;$LCS(n,0)$,\dots,$LCS(n,m)$. At which point we have our solution, which is $LCS(n,m)$.

\section{Optimal Triangulation of a Convex Polygon}

% page 91 in John's notes

First some definitions.  A \emph{polygon} is a list of vertices
$(v_1,...,v_n)$ such that for any $v_i$, there exists an edge
$(v_i,v_{i+1})$ and also there exists an edge $(v_1,v_n)$.  A polygon
is said to be \emph{convex} if any line passing through the polygon
crosses the edges of the polygon at most twice.  A \emph{chord} is an
edge between two non-adjacent vertices in a polygon.  A
\emph{triangulation} is a set of chords which divide a polygon into
triangles.

The problem is to build a triangulation of a given convex polygon
which minimizes total edge length.  We define the function $w(a,b,c)$
to be the weight of the triangle $(v_a,v_b,v_c)$, which in this case
will be the length of the edges $(v_a,v_b)$, $(v_b,v_c)$, and
$(v_c,v_a)$.  We also define the function $t(a,b)$ to be the optimal
triangulation of points $(v_a,...,v_b)$.  We would like to solve
$t(1,n)$.

We start by defining the structure of an optimal solution.  Notice
that the optimal triangulation contains the triangle $(v_1,v_k,v_n)$
for some $k$.  The cost of this triangulation is $t(1,k) + t(k,n) +
w(1,k,n)$.

We then define the recurrence $t(i,i+1) = 0$ for all $i$, and $t(i,j)
= min \{ t(i,k) + t(k,j) + w(i,k,j) \}$ for all $k$ such that $i < k < j$.

We then compute all $t(i,i+1)$, then all $t(i,i+2)$, $t(i,i+3)$,
... until we have calculated $t(1,n)$.

\hypertarget{sec:floyd_warshall}{\section{All-Pairs Shortest Path
    (Floyd-Warshall)}}

Given a graph $G=(V,E)$ where edges have an associated weight $w(e)$
for $e \in E$, compute the shortest path between $u$ and $v$ for all
$u,v \in V$.

We start by defining the structure of an optimal solution.  Let us
decompose the problem into finding the optimal path between $v_i$ and
$v_j$.  All of the vertices on this path are contained in $\{
v_1,...,v_k \}$ except perhaps $v_i,v_j$.  Notice that if $k=0$ then
if there is an edge $(v_i,v_j) \in E$ then the distance is the weight
of that edge, and if there is no such edge then the weight is
infinite.  Otherwise, we take the minimum of either including or
excluding $v_k$ on the path.  This gives the recurrence:

\begin{math}
  d^k_{i,j} = \left\{
    \begin{array}{l l}
      weight((v_i,v_j)) & \text{if $k=0$ and} \\
                        & (v_i,v_j) \in E \\
      \infty            & \text{if $k=0$ and} \\
                        & (v_i,v_j) \not \in E \\
      min \{ d^{k-1}_{i,j},d^{k-1}_{i,k} + d^{k-1}_{k,j} \} & \text{if $k>0$}
    \end{array} \right.
\end{math}

We then compute $d^0_{i,j}$ for all $v_i,v_j \in V$, then all
$d^1_{i,j}$, $d^2_{i,j}$, ... until we have computed $d^{n-2}_{i,j}$.

Running time: $\BigOh{n^3}$.  Analysis is left as an exercise to the
reader.

\section{Knapsack}

Given a knapsack (or bag) which can carry $W$ units of weight, and $n$
items where item $i$ has weight $w_i$ and value $v_i$, what is the
most valuable list of items which can fit in the given bag?  Notice
that this may include multiples of a particular item.

We start by defining the structure of an optimal solution.  Let $p(w)$
be the value of the optimal packing of a bag which can carry $w$ units
of weight, and let $p_i(w)$ be the same but necessarily including item
$i$.

\begin{align*}
  p_i(w) &= p(w - w_i) + v_i & \\
  p(0)   &= 0 & \\
  p(w)   &= max \{ p(w - w_i) + v_i \} & \text{where $i : w_i \leq w$} \\
\end{align*}

We then calculate $p(0), p(1), ..., p(W)$.

The running time for this algorithm is $\BigOh{nW}$.  Notice that $W$
requires $\BigOh{logW}$ bits to represent.  Since the input to the
problem is $\BigOh{n + logW}$, and $W = 2^{logW}$, the time complexity
is $\BigOh{n2^{logW}}$ so this solution is exponential with respect to
the input.

\section{String Edit Distance}

We define the edit distance between two strings as the minimum number
of edits necessary to transform one string into another, where edits
are insertions, deletions, or replacements of a single character.

The problem is to compute this edit distance, given strings $X$ of
length $m$ and $Y$ of length $n$.

We start by defining the structure of an optimal solution.  Let us
define $E[i,j]$ as the minimal edit distance between $X[1..i]$ and
$Y[1..j]$.  We would like to know $E[m,n]$.

It should be easy to see that $E[0,0] = 0$ and $E[1,1]$ is either $0$
if $X[1] = Y[1]$ or $1$ otherwise.  $E[0,j] = j$ and $E[i,0] = i$.

This gives the recurrence:

\begin{math}
  E[i,j] = \left\{
    \begin{array}{l l}
      0 & \text{if } i=0,j=0 \\
      i & \text{if } j=0 \\
      j & \text{if } i=0 \\
      min \{ 1 + E[i-1,j], 1 + E[i,j-1], 1 + E[i-1,j-1] \} & \text{if } X[i] \neq Y[j] \\
      min \{ 1 + E[i-1,j], 1 + E[i,j-1], E[i-1,j-1] \} & \text{otherwise} \\
    \end{array} \right.
\end{math}

Then we calculate $E[i,j]$ from $i=0,j=0$ to $i=m,j=n$.