1. Create an ADT that contains a fixed-size array that holds 20 integers (i.e.,

ID: 3822304 • Letter: 1

Question

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

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.

Explanation / Answer

HI, I have answered Q2.

Please repost Q1 in separate post.

Please let me know in case of any issue in Q2.

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 ) );
}

Here Recursive relation:

T(n) = T(n-1) + C (constant)

So, T(n) = O(n)

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

T(n) = O(n + m) : Mergint of two sorted array

m+n = sum of elements of A and B

TopDownSplitMerge(A[], iBegin, iEnd, B[])

T(n) = 2T(n/2) + O(n)

O(n) = to merger sorted array

So, Solving using Master theorem:
T(n) = O(nlogn)

Navigate

1. Create a website using Bootstrap with a minimum of three pages a. Template/th

1. Create an Evaluator class that will evaluate the sorting algorithms. Create 1

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

1. Create an ADT that contains a fixed-size array that holds 20 integers (i.e.,

Question

Explanation / Answer

Related Questions

Navigate