Answer Happy

1. (a) Describe or write pseudocode for a divide-and-conquer algorithm to find the product of the numbers in an array Aſ with n integers A[1] A[n]. (b) Explain why the time complexity T(m) of your algorithm in can be described by the following recurrence if n = 1 2 x T)+1 if > 1 T(n) = {2xTig)
2. (a) Suppose we are given the following numbers: 40, 23. 11, 35, 15, 30, 18, 25. If we apply merge sort to sort these numbers into ascending order, the final merge step would be to merge the two sorted sequences: (11, 23, 35, 40) and (15.18. 25.30) Draw figures to show this final merge step. Use two pointers to point to the two sorted sequences. Show step by step how the pointers move to obtain the final merged sequence (b) Merge sort makes use of an algorithm to merge two sorted sequences. Assume that the given two sequence are already in descending order. Modify the pseudo code Merge() in the lecture notes to merge two descending ordered sequences into one descending ordered sequence.