(Solved): 2. (Not from text) (a) Write the pseudocode for a Divide-and-Conquer algorithm that finds the inde ...

2. (Not from text) (a) Write the pseudocode for a Divide-and-Conquer algorithm that finds the index of the minimum element of an array. Hints: - Emulate the pseudocode examples in our text, e.g. the first lines could be - Algorithm \( \operatorname{Minim}(\mathrm{A}, 1, \mathrm{r}) \) - //Input: ... - //Output: ... \( \begin{array}{lll}0 & \text { If } \ldots & / / \text { base case } \\ 0 & \text { Else } \ldots / / \text { recursive case }\end{array} \) - The base-case of the recursion is when \( 1=r \), i.e. the array has only 1 element. What is the minimum in this case? - Just like Binary Search or MergeSort, divide the array in half at each step. Let \( m \) be the index of the middle element. Use \( 1= \) left and \( \mathrm{r}= \) right, as in the above-mentioned algorithms. - It is \( \mathrm{OK} \) to assume that the nr. of elements is a power of \( 2: \mathrm{n}=2^{\mathrm{k}} \), so do not worry about floors and ceilings. Simply use integer division by 2 . Write complete pseudocode here: (b) What is the basic operation that we should count for the order of growth? Argue that the best-, worst- and average-cases are all identical. (Explain in words, do not calculate anything yet!) (c) Write the Master Theorem for the recursion, identify a, b, d, and find the theta for \( \mathrm{C}(\mathrm{n}) \). (d) Solve the recursion by back-substitution for \( \mathrm{n}=2^{\mathrm{k}} \), and find the exact solution for \( \mathrm{C}(\mathrm{n}) \). - Hint: You will have to use the summation for the geometric series in App. A. Does your exact solution have the same theta as found above with the Master Theorem?