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.

## Reviews

There are no reviews yet.