Dynamic Programming Practise Problem Set 3

1. Calculate M = M1 × M2 × M3 × M4, where the dimensions of the matrices are

M1: 10,20       M2: 20,50       M3: 50,1       M4: 1,100

a) Calculating M = M1 × ( M2 × ( M3 × M4 ) )
b) Calculating M = ( M1 × ( M2 × M3 ) ) × M4

2 Calculate the length of longest sub string in Hello and Aloha

3. Calculate longest sub sequence in  houseboat and computer.
Answers
1 a) 125000
   b)  2200

2
       A L O H A

    H  0 0 0 1 0
    E  0 0 0 0 0
    L  0 1 0 0 0
    L  0 1 0 0 0
    O  0 0 2 0 0
3.  out     is a common subsequence of     houseboat     and     computer .