Given an integer V > 1 and a list of m distinct integers L[1..m] where L[i]...

Transcribed Image Text:

Given an integer V > 1 and a list of m distinct integers L[1..m] where L[i] <V, for i=1tom and L[m] = 1 Implement the greedy algorithm to represent V as the sum of products using minimum possible number of integers from L as discussed in class. You may use another array R[1..m] to keep track of the intermediate results. Then print the outcome using values from R and L. For instance, given V = 69, m = 5 and L = [14, 8, 6, 5, 1]. Then the algorithm will find R= [4,1,0,1,0], which will lead to V = 14 x 4+8x1+6x0+5x1+1 x 0, that is, V = 14 x 4+8x1+5x1 a- Test your algorithm for three cases of your choice. In each of the three cases V should be greater than 150, m should be at least 6, and the maximum value in L should be in the range [10, 20]. Keep in mind that the integers in L must be distinct. Two of your cases should produce minimum combinations, while the third example should not produce the actual minimum combination. In other words, the third example will illus- trate that the algorithm does not work for every given case. b- Find the complexity of your program c- Show that the implemented greedy algorithm is loop invariant. Given an integer V > 1 and a list of m distinct integers L[1..m] where L[i] <V, for i=1tom and L[m] = 1 Implement the greedy algorithm to represent V as the sum of products using minimum possible number of integers from L as discussed in class. You may use another array R[1..m] to keep track of the intermediate results. Then print the outcome using values from R and L. For instance, given V = 69, m = 5 and L = [14, 8, 6, 5, 1]. Then the algorithm will find R= [4,1,0,1,0], which will lead to V = 14 x 4+8x1+6x0+5x1+1 x 0, that is, V = 14 x 4+8x1+5x1 a- Test your algorithm for three cases of your choice. In each of the three cases V should be greater than 150, m should be at least 6, and the maximum value in L should be in the range [10, 20]. Keep in mind that the integers in L must be distinct. Two of your cases should produce minimum combinations, while the third example should not produce the actual minimum combination. In other words, the third example will illus- trate that the algorithm does not work for every given case. b- Find the complexity of your program c- Show that the implemented greedy algorithm is loop invariant.