1. Hobbies. Suppose you are given a group of n people each of which have exactly one hobby (though their specific hobbies are unknown to you). Suppose that you can find out if any two people have the same hobby by asking them to compare hobbies and then they tell you yes or no-in the process you do not learn what their hobbies are, only that they are the same or different. Now, you are tasked with determining if more than n/2 people in the group have the same hobby. Describe an algorithm that determines if more than n/2 people have the same hobby by asking O(nlg n) pairs of people to compare hobbies. Hints: Consider the following when designing your algorithm. (a) The combine step here is critical: the recursion fairy must return more than just "yes" or "no" as the solution to a subproblem (b) Consider all 4 combinations of "yes"/"no" from the recursion fairy. i. Is a "yes" answer possible when both subproblems are "no"? ii. How many subproblems must return "yes" for the total problem to be "yes"? ii. Do you need to compare additional hobbies in case of a "yes" answer? How many comparisons can you do and still have O(n lgn) running time'? (i.e., what should your recurrence be?) 1. Hobbies. Suppose you are given a group of n people each of which have exactly one hobby (though their specific hobbies are unknown to you). Suppose that you can find out if any two people have the same hobby by asking them to compare hobbies and then they tell you yes or no-in the process you do not learn what their hobbies are, only that they are the same or different. Now, you are tasked with determining if more than n/2 people in the group have the same hobby. Describe an algorithm that determines if more than n/2 people have the same hobby by asking O(nlg n) pairs of people to compare hobbies. Hints: Consider the following when designing your algorithm. (a) The combine step here is critical: the recursion fairy must return more than just "yes" or "no" as the solution to a subproblem (b) Consider all 4 combinations of "yes"/"no" from the recursion fairy. i. Is a "yes" answer possible when both subproblems are "no"? ii. How many subproblems must return "yes" for the total problem to be "yes"? ii. Do you need to compare additional hobbies in case of a "yes" answer? How many comparisons can you do and still have O(n lgn) running time'? (i.e., what should your recurrence be?)