Using dynamic programming, find an optimal parenthesization of a
matrix-chain product of 4 matrices whose dimensions are p = { 1,
10, 5, 20, 2}. Show your work.
Find an optimal parenthesization of matrices whose sequence of
dimensions is: <5, 10, 12, 5, 50>. Please write out both the
m[·, ·] and s[·, ·] tables.
Recall the Matrix Chain Multiplication Algorithm for determining
the optimal parenthesization for a product of matrices. Provide a
recursive implementation of the function
void print_parenth(Matrix K[], int i, int j);
that takes as input the matrix K of k values that are needed to
construct the optimal parenthesization for Ai · · · Aj . Assume
access to a print function that takes as input a string and prints
its value. You may also assume a “+” operation for string...
Construct the visualization matrix for the following coin
problem and find its optimal solution:
Coins: Penny, Nickle, Dime, and Quarter The amount= 27cents
USE DYNAMIC PROGRAMMING METHOD
Dynamic Programming
Let c[k,x] be the minimum number of
coins for the amount x using the first k coins.
Goal: find a
recurrence relation for c[k, x].
There are only two possible choices:
1.
amount x includes the largest coin which is dk
c[k, x] = 1 + c[k,...