Problem 4 (25 points +10 BONUS points) You are organizing the perfect party and you are given a list A of people that can potentially attend the party. Each person in the list is assigned a positive integer (between 1-100) that rates how much this person can contribute to the success of the party. However, the list is organized in such a way such that if you select the i-th person from the list to attend the party then you cannot select any of its neighbors because they do not mix well with each other. So, given the list and the ratings of the people, come up with a Divide & Conquer algorithm that returns the maximum sum achieved by people that can attend, subject to the constraint mentioned above. For example if the list of ratings is 7, 3, 5, 8, 2, 1, 2, 3, then the best sum is 19, achieved by the underlined numbers. (a) (3 points) Suppose you divide the list into parts L, R of size n/2 (assume n is a power of 2) and you compute the best sum of ratings that can be achieved recursively for each part. Then simply return the sum of these numbers. Does this solve the problem? Explain why or why not. Now present your own D&C approach, again splitting the input in half. For full credit, you need to: (b) (8 points) Give a high level description of your algorithm. (c) (4 points) Show how you handle the base cases. (d) (7 points) Explain carefully why your algorithm is correct. (e) (3 points) Justify the recurrence T(n) of its running time and solve it using any method we learned in class. (1) (10 points BONUS) Implement your algorithm and run it on the test instances shown in the web page. Show screenshots of its execution. Hint: Your D&C algorithm should return additional values. The running time should be linear, given by the expression T(n) = 2T(n/2) + O(1)