ICS 311 Chapter 15 solutions
15.2-1
Matrix A1 has dimension 5x10, A2 10x3, A3 3x12, A4 12x5, A5 5x50, A6 50x6
m[1,1] = m[2,2] = … = m[6,6] = 0
m[1,2] = m[1,1]+m[2,2]+5x10x3 = 150
m[2,3] = m[2,2] + m[3,3] + 10x3x12 = 360
….
m[1,3] = min {m[1,1] + m[2,3] + 5x10x12, m[1,2]+m[3,3]+5x3x12} = 330
etc.
15.2-2
Steps for the complete solution:
1.use dynamic programming approach to minimize the number of scalar multiplications, m[1,n], and to calculate the optimal placement of parenthesis, s[i, j].
2. multiply the matrices using s[i,j] parenthesis position, i.e.
MatrixChainMultiply(A, s, 1, n).
//using optimal parenthesis position s, multiply the matrix chain Ai Ai+1 …. Aj
MatrixChainMultiply(A, s, i, j) {
if i > j error
if i = j return A[i] //only one matrix to multiply with itself
if i < j
LeftChain = MatrixChainMultiply(A, s, i, s[i,j]) //LeftChain is a matrix
RightChain = MatrixChainMultiply (A, s, s[i,j] + 1, j) //RightChain is a matrix
Total = MatrixMultiply(LeftChain, RightChain)
return Total
}
15.3-2 MergeSort(A, 1, 16) means: merging an array which has slots 1 to 16.
The order of recursive calls is represented as a tree, similar to the RecursiveMatrixChain which we will have on the final exam.
1…16
1….8 9…16
1…4 5….8 similar to the left subtree
1…2 3…4 5…6 7…8
1..1 2..3 3...3 4…4 5..5 6..6 7…7 8…8
Memoization is not effective because there is no overlapping.
15.3-4
f1[n] = min(f1[n-1] + a1n, f2[n-1] + t2 n-1 + a1n
f2[n] = min(f2[n-1] + a2n, f1[n-1] + t1 n-1 + a2 n)
There is an overlap between f1[] and f2[]. If you don’t save e.g. all f2[]s, then you have to calculate them at least twice: once when calculating f1[], and once for calculating f2[].
15.4-3
Recursive:
LCSRec(s, i, j) {
if i < 0 or j < 0
return error
if (i = 0 or j = 0
c[i,j] = 0
return 0
if xi = yi
return LCSRec(i-1, j-1) +1
if xi ≠ yi
return max (LCSRec(i, j-1), LCSRec(i-1, j)
}
Initial call: LCSRec(s, length(x), length(y))
Memoized:
LCSMem(s, i, j) {
initialize all c[i,j] to NIL
LookupLCS(s, length(x), length(y)), c)
}
LookupLCS(s, i, j, c) {
if i < 0 or j < 0
return error
if c[i, j] is not NIL
return c[i, j]
if i = 0 or j = 0
c[i, j] = 0
else if xi = yi
c[i, j] = LookupLCS(i-1, j-1) +1
else if xi ≠ yi
c[i, j] = max { LookupLCS(i, j-1) , LookupLCS(i-1, j) }
return c[i, j]
}
Iterative bottom up: in the book.