Dynamic Programming - LCS, Matrix Chain, Optimal BST, Knapsack

Dynamic Programming

• DP is general approach to solving problems much like Divide and Conquer, except that subproblems will typically overlap.
• Break the problem into reasonable number of subproblems in such a way that we can give optimal solution to subproblem to achieve optimal solution to large ones.
• The dynamic programming idea doesn't tells us how to find solution, it just gives us a way of making the solution more efficient once we have.

Top down solution and Bottom up solution
Bottom up solution involves recursive solution this is also usually done in tabular form calculates smaller values first and then build larger values from them moves from f(0) to f(1) f(2) so on
Top down memoization store the result of caculation which are later used
first break the problem then calculate and store its result move from f(n) to f(n-1) f(n-2) ...

Difference from Divide and Conquer
Subproblem size is of additive order in dynamic programming that is little smaller than original problem but in  case of divide and conquer subproblem size is of multiplicative order that is its n times small than original problem

Types of DP problems
Dijkstra shortest path problem, Bellman Ford shortest path problem, Fibonacci sequence, balance 0-1 matrix,Tower of Hanoi,Flyod all pair shortest path

Longest Common Subsequence Problem

Given two strings: string S of length n, and string T of length m. Our goal is to produce their longest common subsequence, the longest sequence of characters that appear left-to-right (but not necessarily in a contiguous block) in both strings.

S = ABAZDC

T = BACBAD

LCS of length four ABAD

It is like finding  a 1-1 matching between some of the letters in S and some of the letters in T such that none of the edges in the matching cross each other.

Problem definition
consider two sequences
X =(x1,x2,...xm)
Y=(y1,y2,... yn)
Find longest common subsequence  Z=(z1,z2...zk)  of X and Y

Optimal substructure
1. If xm = yn that is last element is same then LCS also should have that last element

• zk = xm = yn because if it is not in Z then there exist some other sequence with xm that is longest
• remaining LCS will be of Xm-1 and Yn-1 
• LCS(X,Y) =(LCS(Xm-1,Yn-1),xm)

2. If xm != yn then either Z is common sequence which ends in 

•   yn i.e LCS(X,Y) = LCS(Xm-1,Y) or
•   xm i.e LCS(X,Y) = LCS(X,Yn-1)

Overlapping Substructure 
Finding solution now includes solving case 1 when x=yn or solving two possibilities for case 2
Solving both the possibility of case 2 needs to solve case 1 as their subproblems.

Recurrence Solution
c[i,j] be length of LCS of Xi and Xj which is
1) 0 when i=0 j=0
2)  c[i-1,j-1]+1  when i,j>0 and xi=yj
3)  max(c[i,j-1], c[i-1,j])  when i,j>0 and xi != yj

Using simple recursive solution will give exponential time, since there are Th(mn) distinct problems we use Dynamic programming to find solution bottom up.

Time Complexity
takes time O(mn)
space O(mn) if we want to retrace the path also but if we need only the length we need to keep only two rows current and previous
The problem can be solved in polynomial time if number of sequences are constant but otherwise ........

Problem 

For X= 010110110 Y=10010101 Find LCS with matrix table

tracking back the LCS we get 010101

Matrix Chain Multiplication

Problem definition
Given A1, A2, …,An  compute the product: A1xA2x…xAn , find the fastest way (i.e., minimum number of multiplications) to compute it.

two matrices A(p,q) and B(q,r), compute their product C(p,r) in pqr multiplications

Different parenthesization will have different number of multiplications for product of multiple matrices.

There are an exponential number of different possible parenthesizations, in fact 2(n−1)C(n-1) /n or
P(n)   = 1 if n=1
         = sum(k=1 to n-1)P(k)P(n-k) if n>=2
catalan number, so we don’t want to search through all of them. Dynamic Programming gives us a better way.

Example: A(10,100), B(100,5), C(5,50)
– If ((AB) C), 10 *100*  5 +10 *5 * 50 =7500
– If (A(BC)), 10 *100* 50+100*5*50=75000
 The first way is ten times faster than the second

Denote matrices with their row columns as
A1(p0,p1), A2(p1,p2), …, Ai(pi-1,pi),… An(pn-1,pn)

so multiplying Ai..Ak Ak+1...Aj takes  pi-1 pk pj multiplications
that is multiplying A[2,2] and A[3,5] takes p1*p3*p5

Optimal Substructure
optimal parenthization of Ai,Ai+1...Aj splits the product between Ak and Ak+1  The parenthization of prefix subchain Ai...Ak must be optimal within Ai...Aj

Recursive Solution
Let m[i,j] be the minimum number of multiplications for Ai x Ai+1,…,x Aj where 1<=i<=j<=n
and thus for complete problem it would be m[1,n]
m[i,j]    = 0  if i = j
            = min(over i <= k< j) {m[i,k] + m[k+1,j] +pi-1pkpj } if i

Optimal Cost  and Overlapping Structure
Recursive solution will encounter the same subproblems  many time and hence running time becomes exponential but actual number of subproblems are Th(n^2), since one subproblem for each choice of i and j
that is C(n 2) + n
Tabling the answers for subproblems, each subproblem is only solved once. exploring the Overlapping structure

Running Time
O(n^3)
space Th(n^2)

Observations
we can fill the nodes A[i,j] where i=j and where j = i+1 initially
For solving each m[i j] we only use all the splits between i and j for calculation along with the cost to calculate
For A1A2A3A4 the nodes splits are like

Fig showing the split for A1A2A3A4

1-4 gets split into: 1-1,2-4;  1-2, 3-4;  1-3,4-4. similar for 1-2, 3-4; 1-3,4-4.
From the diagram we can find the order in which nodes are evaluated that is m[i,j]

Optimal Binary search Trees 

we are given n distinct keys and propabbility pi for each key that a search will be for ki
we also have dummy keys for key not in tree
Number of leaf nodes for  n keys = n+1

Probability of finding some search key key(success)  + probability of finding some dummy(unsuccessful) = 1

Assume that actual  cost of search is number of nodes examined i.e the depth of node found by search in T plus 1

Expected cost of search Tree  T is
E[search cost in T] = sum{0 to n} ((depth(ki + 1) * (pi) ) +sum{i=0 to n}((depth(di) + 1) * (qi))
1+ sum{0 to n} ((depth(ki ) * (pi) ) +sum{i=0 to n}((depth(di) ) * (qi))
because {sum 1 to n} pi + {sum 0 to n}qj = 1

expected cost of subtree when it becomes subtree of node
the depth of each node in subtree increases by 1
expected search cost increases by sum of all probabilities in tree that is  increase of
w(i,j)= {sum l= i to j} pi + {sum l= i-1 to j}qj  for nodes i to j in subtree 

Recurrence Relation
e[i,j] expected cost of searching an OBST containing keys ki ... kj.

e[i,j] =  qi-1 when j=i-1
        =  min{ e[i,r-1] + e[r+1,j] + w(i,j) }  when i≦j,i≦r≦j

Observations 
consider nodes  a, b, c, d in increasing order
with probability P(a) = .1, P(b) = .2, P(c) = .3, P(d) = .4


1) Possible BST

Fig. possible BST

search cost of node = (depth of node + 1) * probability of node
Average Cost = 1*0.4 + 2*0.3 + 3*0.2 + 4*0.1 = 2.0

2)OBST

   Average Cost = 1*.3+.2*2+.4*2+.1*3 = 1.8

Example 2

i   |   1     2    3     4    5
P  | .24 .22  .23  .3   .01

we find values of table e[i,j]
for i= j its
www.cs.wpi.edu/~songwang/ta/recitation6.ppt

 Knapsack Problem

Problem definition
we are given a set of n items, where each item i is specified by a size si and a value vi . We are also given a size bound S (the size of our knapsack). The goal is to find the subset of items of maximum total value such that sum of their sizes is at most S (they all fit into the knapsack).

Input:
Capacity of knapsack k
n items with weight wi and value vi
Output:
set S of items such that
sum of weight of items in S <= k
and sum of values of items in S is maximized

c[i,w] be solution for items 1,2..i for maximum weight w
When we are considering ith item either we include it or exclude it
If we include the ith item then value of that item will be added and remaining problem should give optimal soution for remaining weight that is c[i-1,w-wi ]
If we exclude the ith item then value then still we have weight w to fill and remaining i-1 items to check
that is c[i-1,w]

Recurrence Relation
c[i,w]         =     0     if i = 0 or w = 0
                  =    c[i-1, w]     if wi  ≥  w
                  =  max [vi + c[i-1, w-wi], c[i-1, w]}     if i>0 and w ≥  wi

Computing the maximum value in weight
 c[i, j] is table, that is, a two dimensional array,  c[0 . . n, 0 . . w]

for w = 0 to W
 c[0,w] = 0
for i = 1 to n

 c[i,0] = 0

for i = 1 to n
  for w = 0 to W
   if wi <= w // item i can be part of the solution
     if bi + c[i-1,w-wi] > c[i-1,w]

       c[i,w] = bi + c[i-1,w- wi]
    else

     c[i,w] = c[i-1,w]
   else c[i,w] = c[i-1,w] // wi > w

Example
consider  n =4 W=5 and following
weight and values (2,3), (3,4), (4,5), (5,6)

consider evaluation
for 1st row v1= 3, w1=2,

for c[1,1] w=1
since w1 > w 
   c[1,1]= c[0,1] = 0
for c[1,2] w=2
 c[1,2] = max(3+c[0,0] ,c[0,2]) = 3

 for c[2,1]  v2=4 w2=3 w=1

since w2>w, we have c[2,1] = [1,1] =0

for c[3,5] v3=5 w3=4 w=5

c[3,5] = max(5+c[2,1] , c[2,5])

similarly filling all we have

//incomplete
//travelling salesman problem
//all pair shortest path