(25 +5 bonus points) Assume you have an array A[1..n] of n elements. A majority element of A is any element occurring in strictly more than positions (e.g., if n = 6 or n 7, any majority element will occur in at least 4 positions). Assume that elements cannot be ordered or sorted, but can be compared for equality. Design an efficient divide and conquer algorithm to find a majority element in A (or determine that no majority element exists). Aim for a divide-and-conquer algorithm that does O(n log n) equality comparisons between the elements. There is an O(n) time algorithm for this problem (not necessarily using divide and conquer). You get 5 bonus points for finding it. Assume you have an array A[1..n] of n elements. A majority element of A is any element occurring in strictly more than n/ 2 positions (e.g., if n = 6 or n = 7, any majority element will occur in at least 4 positions). Assume that elements cannot be ordered or sorted, but can be compared for equality. Design an efficient divide and conquer algorithm to find a majority element in A (or determine that no majority element exists). Aim for a divide-and-conquer algorithm that does O(n log n) equality comparisons between the elements. There is an O(n) time algorithm for this problem (not necessarily using divide and conquer). Question 4. Let T = (V,E) be a balanced binary tree with nodes V and edges E that is rooted at node r, and let w(u) be the weight of node u. All weights are positive. A vertex cover is a subset U of V such that every edge has at least one endpoint in U. Give a divide and conquer algorithm to compute the weight of the minimum weight vertex cover in T. (Note that it's possible to design more efficient algorithms for this problem that aren't based on divide and conquer but, for the purposes of this homework, design a divide and conquer algorithm.)