Reference no: EM131573144

Question: This exercise deals with the problem of finding the largest sum of consecutive terms of a sequence of n real numbers. When all terms are positive, the sum of all terms provid This exercise deals with the problem of finding the largest sum of consecutive terms of a sequence of n real numbers. When all terms are positive, the sum of all terms provide

a) Use pseudocode to describe an algorithm that solves this problem by finding the sums of consecutive terms starting with the first term, the sums of consecutive terms starting with the second term, and so on, keeping track of the maximum sum found so far as the algorithm proceeds.

b) Determine the computational complexity of the algorithm in part (a) in terms of the number of sums computed and the number of comparisons made.

c) Devise a divide-and-conquer algorithm to solve this problem

d) Use the algorithm from part (c) to find the maximum sum of consecutive terms of each of the sequences: -2, 4,-1, 3, 5,-6, 1, 2; 4, 1,-3, 7,-1,-5, 3, -2; and -1, 6, 3, -4, -5, 8, -1, 7.

e) Find a recurrence relation for the number of sums and comparisons used by the divide-and-conquer algorithm from part (c)

f) Use the master theorem to estimate the computational complexity of the divide-and-conquer algorithm. How does it compare in terms of computational complexity with the algorithm from part (a)?