(reposting because I can\'t read the other answer\'s handwriting) Given a list o

Question

(reposting because I can't read the other answer's handwriting)

Given a list of n integers, v1, . . . , vn, the product-sum is the largest sum that can be formed by multiplying adjacent elements in the list. Each element can be matched with at most one of its neighbors. For example, given the list 4, 3, 2, 8 the product sum is 28 = (4 × 3) + (2 × 8), and given the list 2, 2, 1, 3, 2, 1, 2, 2, 1, 2 the product sum is 19 = (2 × 2) + 1 + (3 × 2) + 1 + (2 × 2) + 1 + 2.

b) Give the dynamic programming optimization formula OPT[j] for computing the product-sum of the first j elements.

c) What would be the asymptotic running time of a dynamic programming algorithm implemented using the formula in part b).

Explanation / Answer

b.)

Given that the product-sum is the largest sum that can be formed by multiplying adjacent elements in the list.

To give the dynamic programming optimization formula OPT[j] for computing first j elements:

Notice that,

If j == 0, it means that there are no elements in the list and product-sum = 0

Hence OPT[0] = 0

If j == 1, it means that there is only 1 element in the list and product-sum will be equal to the first element of that list, because there are no other combinations possible.

Now, consider that case for j >= 2:

If we know the values of OPT[j-1] and OPT[j-2], then we can compute the product sum of OPT[j] as follows:

We can either add the jth element to OPT[j-1] to get product-sum for jth element, or we can multiply (j-1)th and jth element and add it to OPT[j-2] because product of only adjacent elements is allowed.

So these are the only 2 possible cases:

1. Either add the jth element to OPT[j-1]

2. Or add the product of (j-1)th and jth element and add it to OPT[j-2].

Hence Optimization formula OPT[j] can be given by:L

Given a list of elements v1, v2 .. vn,

OPT[0] = 0

OPT[1] = 1

OPT[j] = MAX( OPT[j-1] + vj , OPT[j-2] + vj-1*vj)

We can test the given example of list 2, 2, 1, 3, 2, 1, 2, 2, 1, 2 using this Optimization formula as follows:

There are total 10 elements in the list

OPT[0] = 0

OPT[1] = v1 = 2

OPT[2] = max(OPT[1] + v2 , OPT[0] + v1*v2) = max(2 + 2, 0 + 2*2) = 4

OPT[3] = max(OPT[2] + v3 , OPT[1] + v2*v3) = max(4 + 1, 2 + 2*1) = 5

Following in a similar manner:

OPT[4] = max( 5 + 3, 4 + 1*3) = 8

OPT[5] = max(8 + 2, 5 + 3*2) = 11

OPT[6] = max(11 + 1, 8 + 2*1) = 12

OPT[7] = max(12 + 2, 11 + 1*2) = 14

OPT[8] = max(14 + 2, 12 + 2*2) = 16

OPT[9] = max(16 + 1, 14 + 2*1) = 17

OPT[10] = max(17 + 2, 16 + 1*2) = 19

Hence max product sum = 19

c.)

The pseudocode for the dynamic programming algorithm implementation using optimization in part b is as follows:

//Given an array a of elements, and size n

Product-Sum(int[ ]a; n):

//If size is 0 then return 0
if (n == 0) return 0;

//If size is 1 then return a[1], assuming indexing starts from 1 till n.

if(n==1) return a[1]

//Declare an array for holding OPT at each iteration
int [ ] OPT = new int [n + 1];

//Base case:
OPT[0] = 0;
OPT[1] = a[1];

//Iteratively calculating OPT for each value of j
for int j = 2 to n
OPT[j] = max(OPT[j-1] + a[j] , OPT[j - 2] + a[j] * a[j - 1]);

//Return OPT[n] because that represent the optimization product sum of all elements.
return OPT[n];

Since there is only one for loop in the algorithm, the running time of this algorithm is O(n) where n is the number of elements in the array a.

Hence its a linear time algorithm.

Please give this solution a thumbs up if you find it helpful and comment if you have any doubts in it.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.