Two arrays A and B contain a and b elements respectively. The values in these arrays are in decreasing order. Together, the arrays contain n unique elements (i.e. no duplicates) where n = a +b. (a) Design an algorithm for merging the two arrays into one sorted array X with a worst-case runtime of O(n) element comparisons. Describe the general approach of your algorithm in a few sentences. The sentences can be fairly broad, just giving an overall description of your approach, since you will provide pseudocode in the next subquestion. (b) Provide complete pseudocode for your algorithm. (c) Prove that your algorithm meets the constraint on the worst-case running time. (d) Assuming that a and b are large (but unknown) values, express the best-case running time of your algorithm in terms of a and b. Describe a family of input cases that can be merged in this time and justify why no other input could require fewer comparisons. (e) Next, we want to calculate an average-case complexity of your algorithm. In order to do this, we need to make the following assumption about the distribution of possible inputs. Let X be the resulting sorted array. Assume that every combination of A and B that could have led to creating X is equally likely. For this subquestion, we are no longer assuming that neither array is empty. So one valid input (of many) is that A is empty and all n elements are originally in B. (f) Now suppose that we have k sorted arrays all in decreasing order with a total number of n unique elements. We would like to merge these arrays into one sorted array. Devise an algorithm with worst-case runtime O(n log k), using a data structure that we learned in class. Your data structure can hold at most k elements. Give a detailed description of your algorithm (write pseudocode if necessary), and argue that your algorithm works correctly and has the desired worst-case runtime. Two arrays A and B contain a and b elements respectively. The values in these arrays are in decreasing order. Together, the arrays contain n unique elements (i.e. no duplicates) where n = a +b. (a) Design an algorithm for merging the two arrays into one sorted array X with a worst-case runtime of O(n) element comparisons. Describe the general approach of your algorithm in a few sentences. The sentences can be fairly broad, just giving an overall description of your approach, since you will provide pseudocode in the next subquestion. (b) Provide complete pseudocode for your algorithm. (c) Prove that your algorithm meets the constraint on the worst-case running time. (d) Assuming that a and b are large (but unknown) values, express the best-case running time of your algorithm in terms of a and b. Describe a family of input cases that can be merged in this time and justify why no other input could require fewer comparisons. (e) Next, we want to calculate an average-case complexity of your algorithm. In order to do this, we need to make the following assumption about the distribution of possible inputs. Let X be the resulting sorted array. Assume that every combination of A and B that could have led to creating X is equally likely. For this subquestion, we are no longer assuming that neither array is empty. So one valid input (of many) is that A is empty and all n elements are originally in B. (f) Now suppose that we have k sorted arrays all in decreasing order with a total number of n unique elements. We would like to merge these arrays into one sorted array. Devise an algorithm with worst-case runtime O(n log k), using a data structure that we learned in class. Your data structure can hold at most k elements. Give a detailed description of your algorithm (write pseudocode if necessary), and argue that your algorithm works correctly and has the desired worst-case runtime
