1. Create an ADT that contains a fixed-size array that holds 20 integers (i.e., int array[20]; ) and the following member functions:

A default constructor that initializes all the elements in this array to 20 random numbers (you can call the rand() function to generate a pseudo-random number).

A member function that recursively searches the largest number in the array. This function will return the value of the largest number.

A member function that recursively finds the value of the k-th smallest number in the array, where k is provided by the end-user. You are required to use the partition-based, recursive algorithm.

A member function that implements the recursive QuickSort algorithm to sort the array in increasing order.

You are required to use separate compilation. Specifically, your project will contain one header file, one .cpp file that implements all the member functions, and another .cpp file that contains the main() function. In the main() function, you will include test cases to call and test all your recursive functions. 2.

a) Complexity analysis: Represent the time complexity of the following recursive algorithm, T(n), as a recurrence equation:

int pow_2( int n ){ if ( n==1) return 2; if ( n > 1) return ( 2 * pow_2( n-1 ) ); } b) Complexity analysis: analyze the time complexity of the Top-Down implementation of the MergeSort algorithm on the following wikipedia webpage: http://en.wikipedia.org/wiki/Merge_sort For

TopDownMerge(A[], iBegin, iMiddle, iEnd, B[]) 

assume (iEnd - iBegin + 1) is n (that's the size of A), this algorithm will take c1.n + c0 to finish. Please represent the time complexity of TopDownSplitMerge(A[], iBegin, iEnd, B[]) as a recurrence equation. You don't need to solve this equation.