Divide and Conquer You have a list A[1...n] of n integers. A local minimum of a list is an index i such that A[i] < A[i −1] and A[i] < A[i +1]. A[1] and A[n] are local minimums only if they are less than their single neighbor. You will develop an algorithm to find one local minimum in a list (there may be more than one in the list but you only have to find one). a) Circle the local minimums in this list. A= [10,7,5,3,5,7,9,6,4,2
b) Write a formal statement of this problem. That is, state the input and output criteria as precisely as possible.
c) Let LM(A[a...b) express the output of the local minimum problem. State a self-reduction relating the solution to the main problem to solutions to its sub-problems.
d) What is the worst case running time of the algorithm you have designed.