Description
Problem 1 (40 Points) Write a C++ program for sorting an array A of n integers. First you need to implement both the MERGE‐ SORT and MERGE algorithms (shown below). The main() function of the program carries out the following tasks: 1. Ask the user to input the value of n, where 1< n ≤ 50 2. Fill A with random integers in the range 0 to 100. To generate such random numbers, you need to use the header. Check the following link for an example: http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution 3. Call the MERGE‐SORT function to sort the contents of A (where MERGE‐SORT needs to call the MERGE function). 4. Display on the screen the contents of the sorted array A. EECE7205 Homework 2 3 / 3 Problem 2 (20 Points) In the above MERGE algorithm and to avoid having to check whether either list is empty in each basic step, a sentinel value of is placed at the end of each list. Rewrite the algorithm so that it does not use sentinels, instead it stops once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A. No need to submit any updated C++ program code for this problem (on the updated algorithm in pseudo code as presented in the previous problem). Problem 3 (20 Points) The above code is for ProcedureX that takes list A of integers as an input parameter. a) In 70 words or less, explain the purpose of ProcedureX and how it achieves that purpose. b) If n = A.length, determine the worst‐case running time formula of ProcedureX. Write the formula as a function of n (show your steps). Problem 4 (20 Points) In the lecture we implemented the insertion sort algorithm using iterative approach. Write a recursive version of that algorithm (only the algorithm not its C++ implementation). In order to sort the contents of array A[1..n] using a recursive version of the insertion sort algorithm, you can recursively sort A[1..n-1] and then insert A[n] into the sorted array A[1..n-1]. Follow the same level of abstraction used in writing our recursive merge sort algorithm in slide 28 of the 4th lecture slides. Following the same approach that we used with analyzing the merge sort algorithm, analyze your recursive insertion sort algorithm to find its running time recurrence equation. Solve the recurrence equation to find the asymptotic notation of the running time.
