Introduction to Algorithms/Dynamic Programming

Video Link

Dynamic programming is a design tech, like D & C.

Ex. LCS.

LCS

Given two seqs $x[1,\dots,m]$ and $y[1,\dots,n]$, find a longest common sequence to both.

Brute force: check every subseq of $x$ to see if it’s also a subseq of $y$.

Analysis:

• Check$=O(n)$.
• $2^{m}$ subseq of $x$.
• W-c running time is $O(n\cdot 2^{m})=$ slow.

Simplification:

1. Look at len of LCS($x,y$)
2. Extend the alg to find LCS itself.

Notation: $

S

$ denotes len of seq $S$.

Strategy: Consider prefixes of $x$ and $y$.

Define $c[i,j]=

\text{LCS}(x[1,\dots,i],y[1,\dots,j])

$.. Then $c[m,n]$ is the result.

Theorem:

\[c[i,j]=\begin{cases} c[i-1,j-1]+1, &\text{if }x[i]=y[j], \newline \max (c[i,j-1],c[i-1,j]), &\text{otherwise} \end{cases}\]

Proof: case $x[i]=y[j]$: Let $z[i,\dots,k]=\text{LCS}(x[1,\dots,i],y[1,\dots,j])$ where $c[i,j]=k$. Then $z[k]=x[i]=y[j]$, or else $z$ could be extended by tacking on $x[i]$. Thus, we claim $z[1,\dots,k-1]$ is LCS of $x[1,\dots,i-1]$ and $y[1,\dots,j-1]$.

Suppose $w$ is a larger CS, that is $

w

>k-1$. Cut & paste: $w

z[k]$ (string concatenatium) is a CS of $x[1,\dots,i]$ and $y[1,\dots,j]$ with len $>k$. Contradiction.

Other cases similar.

---

Dynamic-programming hallmark 1: Optimal substructure: An opt. solution to a problem(instance) contians opt. solutions to subproblems.

If $z=\text{LCS}(x,y)$, then any prefix of $z$ is an LCS of a prefix of $x$ and a prefix of $y$.

---

Recursive alg for LCS

LCS(x,y,i,j) //ignoring base case
  if x[i] = y[j]
    then c[i,j]<-LCS(x,y,i-1,j-1)+1
  else c[i,j]<-max(LCS(x,y,i-1,j),LCS(x,y,i,j-1))
    return c[i,j]

Worst-case: $x[i]\neq y[j], \forall i,j$. Slow.

---

Dynamic-programming hallmark 2: Overlapping subproblems: A recursive solution contains a “small” number of distinct subproblems repeated many times.

---

LCS subproblem space contains $n\cdot m$ distinct subproblem.

Memo-ization alg

LCS(x,y,i,j)
  if c[i,j] is nil
    then if x[i] = y[j]
            then c[i,j]<-LCS(x,y,i-1,j-1)+1
	 else c[i,j]<-max(LCS(x,y,i-1,j),LCS(x,y,i,j-1))
  return c[i,j]

Time is $\Theta (mn)$. Space is $\Theta(mn)$.

Dynamic-prog alg

Idea: compute the table bottom-up.

Time is $\Theta(mn)$. Can reconstruct LCS by tracing backwards.

Space is $\Theta(mn)$, can do $\Theta(\min (m,n))$.

• 1 row + $O(1)$ elem.