3979

Come up with a divide and conquer algorithm for the following scenario: You are studying different types of rocks on an island. There are MANY different types of rocks, but we are guaranteed that of the “N” rocks on the island, there exists a majority type. More specifically, we are guaranteed that there exists a quantity strictly greater than N/2 rocks of a single type. We have access to a method called isTheSame(rock1, rock2) returning true if the rocks are of the same type, false otherwise. We must use this method in the following problem as our sole means for comparison between two rocks. As an example of desired functionality: If rock type A is in fact the majority and in some array we have rocks 1,4,5,6, qualifying as typeA we can return any one of those rocks’ numbers at the end of the algorithm to indicate that this rock’s type is indeed the majority. The task is as follows: a) Design a deterministic divide and conquer algorithm that uses O(nlog(n) calls to isTheSame that returns a rock the belongs to the majority type. Explain in english and provide pseudocode for this algorithm. b) Explain why we make O(nlog(n)) calls to isTheSame. c) Prove using induction why this algorithm is correct including a hypothesis, base case, inductive step and conclusion.