 # Problem 3: (6 points) Product Sum Given a list of n integers, V1 ...

## Question

Show transcribed text

## Transcribed Text

Problem 3: (6 points) Product Sum Given a list of n integers, V1 Vr. 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 x 3) + (2 x 8), and given the list 2, 2, 1, 3, 2, 1, 2, 2, 1, 2 the product sum is 19 = (2 x 2) + 1 + (3 x 2) + 1 + (2 x 2) + 1+2. a) Compute the product-sum of 2, 1, 3, 5, 1, 4, 2. b) Give the dynamic programming optimization formula OPT[]] 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). Problem 4: (5 points) Making Change: Given coins of denominations (value) 1=V1 to make change for an amount A using as few coins as possible. Assume that vis and A are integers. Since V1= 1 there will always be a solution. Formally, an algorithm for this problem should take as input: An array V where v[i] is the value of the coin of the ith denomination. A value A which is the amount of change we are asked to make The algorithm should return an array C where c[i] is the number of coins of value v[i] to return as change and m the minimum number of coins it took. You must return exact change so n A The objective is to minimize the number of coins returned or: n. m - min E C[i] a) Describe and give pseudocode for a dynamic programming algorithm to find the minimum number of coins to make change for A. b) What is the theoretical running time of your algorithm? 1

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

Problem 3
a).
Observation – this part can be easier done after designing the dynamic programming algorithm from subsequent parts.
The resulting vector-sum is: 2+1+3 x 5 + 1+ 4 x 2 = 27

b).
The optimization process is based on the key observation that, on each step, the decision is made between 1) the previous optimum value + current element (if we take itby summing-up) and 2) the optimum value from two steps behind + the product between the current element and the previous element of the array (if we choose the multiplication instead of summing-up). Combined with the initial conditions for trivial cases (n=0 –no array and n=1 –one-element array), we obtain the following formulation for the optimum value to be used by the dynamic programming algorithm:

Optimum[j]= MAX (Optimum[j-1] + v[j], Optimum[j-2] + v[j-1] x v[j]).Optimum[j] = v1, when j=1 and Optimum[j]=0, when j=0.

The optimization process is based on the key observation that, on each step, the decision is made between 1) the previous optimum value + current element (if we take it by summing-up) and 2) the optimum value from two steps behind + the product between the current element and the previous element of the array (if we choose the multiplication instead of summing-up)....

By purchasing this solution you'll be able to access the following files:
Solution.pdf.

\$27.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.