\documentclass{article} 

\usepackage{booktabs} 
\usepackage{amsmath,amsfonts}
\usepackage{subcaption}
\usepackage{amssymb}
\usepackage{wasysym}
\usepackage{libertine}
\usepackage{graphicx}
\usepackage{wrapfig}
\usepackage{url}
\usepackage[labelfont=bf,textfont=it]{caption}
\usepackage{color}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumitem}
\usepackage{fullpage}
\usepackage{parskip}

\newcommand{\mI}{\mathcal{I}}
\newcommand{\matroid}{\ensuremath{M=(S,\mathcal{I})}}
\newcommand{\B}[1]{\boldsymbol{\mathrm{#1}}}


\begin{document}

\title{Dynamic Programming}

\author{Adam W. Bargteil}
\maketitle

We typically apply dynamic programming to {\bf optimization problems}. We follow a sequence of 4 steps:
\begin{enumerate}
\item Characterize the structure of an optimal solution.
\item Recursively define the value of an optimal solution.
\item Compute the value of the optimal solution.
\item Construct the optimal solution from computed information.
\end{enumerate}

\paragraph{Rod Cutting Problem:}
Given a rod of length $n$ and a table pf prices $p_i$ for $i=1,2,\dots,n$, determine the maximum revenue $r_n$ obtainable by cutting the rod and selling the pieces.
There are $2^{n-1}$ different ways to cut the rod since we can choose to include or not include cut $i$.
$$r_n = \max(p_n,r_1+r_{n-1},r_2+r_{n-2},\cdots,r_{n-1},r_1).$$

{\bf Optimal substructure:} optimal solutions to a problem incorporate optimal solutions to related subproblems, which we may solve independantly.
$$r_n = \max_{1\le i\le n}\left(p_i+r_{n-1}\right).$$

%\setlength{\textfloatsep}{0.25in}
\begin{algorithm}
  %\begin{spacing}{1.2}
  Cut-Rod $(p,n)$
\begin{algorithmic}[1]
\IF{n == 0}
\RETURN 0
\ENDIF
\STATE $q = -\infty$
\FOR{$i = 1$ \TO $n$}
\STATE $q = \max(q, p[i] + $ Cut-Rod $(p,n-i))$
\ENDFOR
\RETURN $q$
\end{algorithmic}
%\end{spacing}
\end{algorithm}

Easy to prove correct by induction. Running time?
$$T(n) = 1 + \sum_{j=0}^{n-1} T(j) = 2^n$$

%\setlength{\textfloatsep}{0.25in}
\begin{algorithm}
  %\begin{spacing}{1.2}
  Memoized-Cut-Rod $(p,n)$
\begin{algorithmic}[1]
\STATE $r = $ new int[$n$]
\FOR{$i = 0$ \TO $n$}
\STATE $r[i] = -\infty$
\ENDFOR
\RETURN Memoized-Cut-Rod-Aux $(p,n,r)$
\end{algorithmic}

\medskip
Memoized-Cut-Rod-Aux $(p,n,r)$
\begin{algorithmic}[1]
\IF{$r[n] \ge 0$}
\RETURN $r[n]$
\ENDIF
\IF{$n==0$}
\STATE $q = 0$
\ELSE
\STATE $q=-\infty$
\ENDIF
\FOR{$i = 1$ \TO $n$}
\STATE $q = \max(q, p[i] + $ Memoized-Cut-Rod-Aux $(p,n-i))$
\ENDFOR
\STATE $r[j] = q$
\RETURN $r[n]$
\end{algorithmic}
%\end{spacing}
\end{algorithm}


\begin{algorithm}
  %\begin{spacing}{1.2}
  Bottom-Up-Cut-Rod $(p,n)$
\begin{algorithmic}[1]
\STATE $r = $ new int[$n$]
\STATE $r[0] = 0$
\IF{n == 0}
\RETURN 0
\ENDIF
\STATE $q = -\infty$
\FOR{$j = 1$ \TO $n$}
\STATE $q = -\infty$
\FOR{$i=1$ \TO $j$}
\STATE $q = \max(q, p[i] + r[j-1])$
\STATE $r[j] = q$
\ENDFOR
\ENDFOR
\RETURN $r[n]$
\end{algorithmic}
%\end{spacing}
\end{algorithm}

Both $\Theta(n^2)$.

\paragraph{Subproblem Graph:} A ``reduced'' or ``collapsed'' version of call tree. Bottom-up uses reverse topological sort.
Typically, the time to compute the solution of a subproblem is proportional to out-degree and the number of subproblems is the number
of vertices.

\begin{algorithm}
  %\begin{spacing}{1.2}
  Extended-Bottom-Up-Cut-Rod $(p,n)$
\begin{algorithmic}[1]
\STATE $r = $ new int[$n$]
\STATE $s = $ new int[$n$]
\STATE $r[0] = 0$
\IF{n == 0}
\RETURN 0
\ENDIF
\STATE $q = -\infty$
\FOR{$j = 1$ \TO $n$}
\STATE $q = -\infty$
\FOR{$i=1$ \TO $j$}
\IF {$q < p[i]+r[j-i]$}
\STATE $q = p[i]+r[j-i]$
\STATE $s[j] = i$
\ENDIF
\STATE $r[j] = q$
\ENDFOR
\ENDFOR
\RETURN $r[n]$
\end{algorithmic}

\medskip
Print-Cut-Rod-Solution($p,n$)
\begin{algorithmic}[1]
  \STATE ($r,s$) = Extended-Bottom-Up-Cut-Rod($p,n$)
  \WHILE{$n>0$}
  \STATE print $s[n]$
  \STATE $n = n-s[n]$
  \ENDWHILE
\end{algorithmic}
  
\end{algorithm}

\paragraph{Matrix-chain Multiplication:}
Given a sequence of matrices $\left<A_1,A_2,\dots,A_n\right>$ of $n$ matrices, where $i = 1,2,\dots,n$, matrix $A_i$ has dimension $p_{i-1}\times p_i$, fully parenthesize the product
$A_1A_2\dots A_n$ in a way that minimizes the number of scalar multiplications.
Matrix multiplaction rules: $p\times q$ times $q\times r$ gives $p\times r$, cost $pqr$.

Number of possible parenthesizations, $P(n)$,
$$P(n) = \sum_{k=1}^{n-1} P(k)P(n-k).$$
Catalan numbers $\Omega(4^n/n^{3/2})$.

Dynamic Programming:
\begin{enumerate}
\item Characterize the structure of an optimal solution.
\item Recursively define the value of an optimal solution.
\item Compute the value of the optimal solution.
\item Construct the optimal solution from computed information.
\end{enumerate}

\paragraph{Structure:}
$A_{i..j} = A_iA_{i+1}\dots A_j$. We must break the problem up into $A_{i..k}$ and $A_{k+1..j}$ for some $k$. The cost is computing $A_{i..k}$ and $A_{k+1..j}$ and then multiplying them together.

Optimal substructure: the optimal paranthesization of the subchain $A_{i..k}$ within the optimal parenthesization of $A_{i..j}$ must be an optimal
parenthesization of $A_{i..k}$. Because if there were a better way to parenethesize $A_{i..k}$ then we would substitute that and find a better parenthesization of $A_{i..j}$.

Given optimal substructure, we can build the optimal solution by optimally splitting the problem into two sub-problems.

Let $m[i,j]$ be the {\bf minimum} cost of computing $m[i,j]$.
$$m[i,j] = m[i,k]+m[k+1,j]+p_{i-1}p_kp_j.$$
$$m[i,j] = \min_{i\le k<j} m[i,k]+m[k+1,j]+p_{i-1}p_kp_j.$$

Number of subproblems: one for each choice of $i,j$ s.t. $1\le i \le j \le n = \binom{n}{2}+n=\Omega(n^2)$. {\bf Overlapping subproblems.}

\begin{algorithm}
  %\begin{spacing}{1.2}
  Matrix-Chain-Order($p$)
\begin{algorithmic}[1]
\STATE $n = p.length-1$
\STATE $m = new int[1..n][1..n]$
\STATE $s = new int[1..n-1][2..n]$
\FOR{$1 = 1$ \TO $n$}
\STATE $m[i,i] = 0$
\ENDFOR
\FOR{$l = 2$ \TO $n$}
\FOR{$i = 1$ \TO $n-l+1$}
\STATE $j = i+l-1$
\STATE $m[i,j] = \infty$
\FOR{$k=i$ \TO $j-1$}
\STATE $q = m[i,k]+m[k+1,j]+p_{i-1}p_kp_k$
\IF{$q < m[i,j]$}
\STATE $m[i,j]=q$
\STATE $s[i,j]=k$
\ENDIF
\ENDFOR
\ENDFOR
\ENDFOR
\RETURN $m$ and $s$
\end{algorithmic}
  
\medskip
Print-Optimal-Parens($p,i,j$)
\begin{algorithmic}[1]
  \IF{$i==j$}
  \STATE print ``$A_i$''
  \ELSE
  \STATE print ``(``
  \STATE Print-Optimal-Parens($s,i,s[i,j]$)
  \STATE Print-Optimal-Parens($s,i[i,j]+1,j]$)
    \STATE print ``)``
    \ENDIF
\end{algorithmic}
\end{algorithm}

\paragraph{Elements of Dynamic Programming:}
\paragraph{Optimal Substructure:}
Characterize the structure of an optimal solution.
{\bf Optimal Substructure} if an optimal solution contains optimal solutions to subproblems.
\begin{enumerate}
\item Solution requires a choice that results in subproblems.
\item Assume you are given the choice that leads to an optimal solution.
\item determine ensuing subproblems and how to characterize the space of subproblems.
\item Show that the solutions to the subproblems used within an optimal solution to the problem must themselves be
  optimal by the ``cut-and-paste'' technique.Assume the the subrpoblem solutions are not optimal and derive contradiction.
  ``Cut out'' the nonoptimal solution to subproblem, ``paste in'' the optimal one and shoe that you get a better solution
  resulting in a contradiction, since we assumed an optimal solution.
\end{enumerate}

Keep the space of subproblems as simple as possible. We could work from the left on rod cutting, but had to allow ``both sides'' for matrix-mult.

Optimal substructure varies in two ways:
\begin{enumerate}
\item how many subproblems an optimal solution uses
\item how many choices we have in determining which subproblems to use in an optimal solution
\end{enumerate}

Rod-cutting: one subproblem, but $n$ choices. Matrix-chain-mult: 2 subproblems, $j-i$ choices.

Running time depends on two factors: number of subproblems and choices for each subproblem. Rod cutting $\Theta(n)$ subproblems, and $n$ choices for each, $O(n^2)$.
Matrix-chain had $\Theta(n^2)$ subproblems and $n-1$ choices, $O(n^3)$

Subproblem graph gives alternate analysis, each node is a subproblem and each edge is a subproblem we must consider.

Cost of a problem is the cost of subproblems plus the cost of the decision itself.

{\bf Optimal substructure does not always apply.}
Unweighted longest simple path: The path $u$ to $w$ includes $v$, but the longest simple path from $u$ to $v$ is not necessarily part of the path from $u$ to $w$
because there could be edges in the longest simple path from $u$ to $v$ that are {\bf also} on the longest simple path from $v$ to $w$, creating a cycle. The subproblems
must be {\bf indpendent}.

\paragraph{Overlapping Subproblems:}
The space of subproblems is ``small,'' polynomial in the problem size and a recursive algorithms solves the same subproblems repeatedly.
Divide-and-conquer usually generates {\bf new} subproblems at each step of recursion.

{\bf It is important to note, we only care about the {\em optimal} solution.}

We often have to store additional information to reconstruct the optimal solution.

\paragraph{Longest-common-subsequence problem}: given two sequences
$X=<x_1,x_2,\dots,x_m>$ and 
$Y=<y_1,y_2,\dots,y_n>$ find a maximum-length common subsequence of $X$ and $Y$.

Naive: check whether every subsequence of $X$ is in $Y$. There are an exponential number of subsequences of $X$.

Define {\bf prefix}, $X_i$ as the first $i$ entries in $X$.

Given $X$ and $Y$, let $Z$ be any LCS.
\begin{enumerate}
\item 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}$
\item if $x_m\ne y_n$ then $z_k\ne x_m$ and $Z_{k-1}$ is an LCS of $X_{m-1}$ and $Y$
\item if $x_m\ne y_n$ then $z_k\ne y_n$ and $Z_{k-1}$ is an LCS of $X$ and $Y_{n-1}$
\end{enumerate}
If $z_k\ne x_m$ then we could append $x_m = y_n$ to $Z$ to obtain a longer subsequence, contraditing that $Z$ is longest.
$Z_{k-1}$ is a subsequence of $X_{m-1}$ and $Y_{n-1}$ (length $k-1$). Show it is an LCS. Suppose (for contradiction) that there is a common
subsequence $W$ of $X_{m-1}$ and $Y_{n-a}$ greater length than $k-1$. Then appending $x_m=y_n$ produces a common subsequence greater than $k$,
which is a contradiction.

If $z_k\ne x_m$, then $Z$ is a common subsequence of $X_{m-1}$ and $Y$. If there were a common subsequence $W$ of $X_{m-1}$ and $Y$ with
length greater than $k$, then $W$ would also be a common subsequence of $X_m$ and $Y$, contradicting the assumption that $Z$ is an LCS of
$X$ and $Y$.

Symmetry for (3).

\pagebreak
Let $c[i,j]$ be the length of the LCS of $X_i$ and $Y_i$.
$$c[i,j] = c[i-1,j-1]+1$$
if $x_i=y_i$, otherwise
$$c[i,j] = \max(c[i,j-1],c[i-1,j])$$


\begin{algorithm}
  %\begin{spacing}{1.2}
  LCS-Length($X,Y$)
  \begin{algorithmic}[1]
    \STATE $m = X$.length
    \STATE $n = Y$.length
\STATE $b =$ new int$[1..m][1..n]$
\STATE $c =$ new int$[0..m][0..n]$
\FOR{$1 = 1$ \TO $m$}
\STATE $c[i,0] = 0$
\ENDFOR
\FOR{$1 = 1$ \TO $n$}
\STATE $c[o,j] = 0$
\ENDFOR
\FOR{$i=1$ \TO $m$}
\FOR{$i=1$ \TO $n$}
\IF{$x_i==y_j$}
\STATE $c[i,j]=c[i-1,j-1]+1$
\STATE $b[i,j]=0$
\ELSIF{$c[i-1,j]\ge c[i,j-1]$}
\STATE $c[i,j] = c[i-1,j]$
\STATE $b[i,j] = 2$
\ELSE
\STATE $c[i,j] = c[i,j-1]$
\STATE $b[i,j] = 2$
\ENDIF
\ENDFOR
\ENDFOR
\RETURN $c$ and $b$
\end{algorithmic}
  
\medskip
Print-LCS($b,X,i,j$)
\begin{algorithmic}[1]
  \IF{$i==0$ or $j==0$}
  \RETURN
  \ENDIF
  \IF{$b[i,j] == 0$}
  \STATE Print-LCS($b,X,i-1,j-1$)
  \STATE print $x_i$
  \ELSIF{$b[i,j] = 1$}
  \STATE Print-LCS($b,X,i-1,j$)
  \ELSE
  \STATE Print-LCS($b,X,i,j-1$)
  \ENDIF
\end{algorithmic}
\end{algorithm}




\end{document}
