Fundamentals of Computer Engineering Homework 2

EECE7205: Fundamentals of Computer Engineering
Homework 2
Problem 1 (30 Points)
Write a C++ program for sorting an array A of n integers using the Merge Sort algorithm. First you need
to implement both the MERGE-SORT and MERGE algorithms (shown below). The main() function of
your program must carry 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 <random> 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 array A before and after calling MERGE-SORT on it.
5. Modify the MERGE function code so that if all elements in both sub-arrays are already sorted
(best case scenario where all elements in one sub-array are less than all the elements in the other
sub-array), then the function skip the merge process. Test your modified MERGE function by
calling MERGE-SORT with an array with already sorted content.

EECE7205 – Homework 2
3 / 4
Problem 2 (10 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 copies the remainder of the other array back into A.
No need to submit any C++ program code for this problem (only the updated algorithm in pseudo code
similar to what is presented in the previous problem).
Problem 3 (20 Points)
Write a C++ program to test the following two functions. Call the functions with values for n between 1
and 10.
int F1(int n)
{
if (n == 0) return 1;
return F1(n ‐ 1) + F1(n ‐ 1);
}
int F2(int n)
{
if (n == 0) return 1;
if (n % 2 == 0) {
    int result = F2(n / 2);
    return result * result;
}
else
    return 2 * F2(n ‐ 1);
}
Submit your test program and in your report answer the following questions:
a. What does each function do?
b. Which function is faster (hint: test them with n = 30)?
c. Guess the running time growth of each function and hence explain why one function is faster
than the other.

EECE7205 – Homework 2
4 / 4
Problem 4 (20 Points)

The above code is for ProcedureX that takes list A of integers, with starting index 1, 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 5 (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]. Only provide the insertion sort algorithm
and no need to write the algorithm to perform the “insert” task. Following the same level of abstraction
used in writing our recursive merge sort algorithm, your recursive insertion sort algorithm should be
about 3 or 4 lines of pseudo code.
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.