Exercise 1. Given an Array A of 6 elements [4, 6, 3, 8, 5, 2].

The goal is to find the max value in A using binary search method with divide and conquer strategy.

1.1. Draw the tree corresponding to the recursive call to search the maximum value in array A (from level 0 to the last level k.) Use two (2) different colors to distinguish between forward and backward steps. Use numbers to enumerate clearly the different steps (in order).

1.2. Suppose that searchMax is the name of the function that returns the max value, illustrate the state of the stack memory since the first call of searchMax to its end.

Exercise 2.

Let E be an array of n elements. We assume that the only known operation to perform on the elements of E is to check whether two elements are equal or not. We say that an Level k Level 0 4 6 3 8 5 2 element x E is a majority if the set Ex = {y E | y = x} has strictly more than n / 2 elements. We assume that n is a power of 2, and we are interested in complexity in the worst case.

2.1. Write a nave (iterative) algorithm calculating the cardinal cx of Ex for a given x. Deduce an algorithm to check if E has a majority element. What is the complexity of this algorithm?

2.2. Write a recursive algorithm based on dividing E into two equally sized subarrays. What it its complexity?