## Description

1

CS 201

Homework Assignment 2

In this homework, you will merge two sorted integer arrays. That is, given two sorted integer arrays arr1 and arr2 of

size N, the problem is to create and return a third sorted array arr3 with the items of arr1 and arr2. It will have

size 2N. Assume that sorting is done in ascending order of the integer items.

Two alternative algorithms that solve this problem are given below in lay terms. Each algorithm has a different time

complexity. The goal of this homework is to evaluate the growth rates of both algorithms using different inputs.

Algorithm 1: Append all items in arr1 in the same order to arr3. Then, for all items in arr2 starting from the

beginning, find the right place to insert in arr3 by shifting the items in arr3 if needed.

Algorithm 2: Compare pairs of numbers across arr1 and arr2 and insert the smallest to arr3. In this

algorithm you are allowed to visit every item only once.

ASSIGNMENT:

1. Implement global functions for these algorithms and write a driver (main) function that calls these functions. Then,

create sorted arrays of different sizes. You are expected to try many different input sizes, both small inputs and

very large inputs. For each input size, N, consider the following ordering cases: (i) all numbers in arr1 are smaller

than arr2, (ii) all numbers in arr2 are smaller than arr1, and (iii) there is no such ordering between these

arrays. Run each array size and ordering combination and record the execution times. Do not include the time

elapsed to allocate the array and initialize their entries. If you want, you can use cstdlib library’s rand()

function to generate random integers and algorithm library’s sort() function to sort the input arrays arr1 and

arr2.

2. Use these results to generate a plot of running time (y-axis) versus the input size N (x-axis), per ordering case (i.e.,

for (i), (ii), and (iii) above). Specifically, you are expected to produce plots similar to Figure 2.3 of the handout

chapter on algorithm analysis.

3. Based on your plots indicate the best, average and worst cases for each algorithm and the corresponding worst

case time complexity.

4. Provide the specifications (processor, RAM, operating system etc.) of the computer you used to obtain these

execution times. You can use any computer with any operating system for this assignment, but make sure your

code compiles and runs on the dijkstra server.

5. Also, plot the expected worst case growth rates obtained from the theoretical analysis by using the same N values

that you used in your simulations. That is, using your theoretical analysis in (3), for each N value plot the expected

number of operations.

6. Finally, compare the expected growth rates obtained in step 5 and the worst case results obtained in step 3, and

discuss your observations in a paragraph.

You can use the following code segment to compute the execution time of a code block. For these operations, you

must include the ctime header file.

//Store the starting time

double duration;

clock_t startTime = clock();

//Code block

//…

//Compute the number of seconds that passed since the starting time

2

duration = 1000 * double( clock() – startTime ) / CLOCKS_PER_SEC;

cout << “Execution took ” << duration << ” milliseconds.” << endl;

An alternative code segment to compute the execution time is as follows. For these operations, you must include the

chrono header file.

//Declare necessary variables

std::chrono::time_point< std::chrono::system_clock startTime;

std::chrono::duration< double, milli elapsedTime;

//Store the starting time

startTime = std::chrono::system_clock::now();

//Code block

…

//Compute the number of seconds that passed since the starting time

elapsedTime = std::chrono::system_clock::now() – startTime;

cout << “Execution took ” << elapsedTime.count() << ” milliseconds.” << endl;

NOTES:

1. Put your code (single cpp file including the implemented global functions and the main function) and PDF report

into a folder and create a zip file. The name of this zip file should conform the following name convention:

secX-Firstname-Lastname-StudentID.zip where X is your section number.

2. Before the deadline, upload your zip file to Moodle. No hardcopy submission is needed. Type your report,

handwritten reports will not be graded. Note that you might get an FZ grade for this reason.

3. The standard rules about late homework submissions apply. Please see the course web page for further discussion

of the late homework policy as well as academic integrity.