Instructions
EECE7205 – Spring 2020 ‐ Homework 2
Northeastern University
College of Engineering
Department of Electrical & Computer Engineering
EECE7205: Fundamentals of Computer Engineering
Spring 2020 ‐ Homework 2
‐ For programming problems:
o Your code must be well commented by explaining what the lines of your
program do. Have at least one comment for every 4 lines of code.
o You are not allowed to use any advanced C++ library unless it is clearly allowed by the problem. For example, you cannot use a library function to sort a list of
data if the problem is asking you to implement an algorithm to sort the list.
o At the beginning of your source code files write your full name, students ID,
and any special compiling/running instruction (if any).
o Test your code on the COE Linux server before submitting it:
If your program does not compile in the COE server due to incompatible text encoding format, then before uploading your source code file to the server make sure it is saved with Encoding Unicode (UTF‐8). In visual studio, Save As ‐> Click on the arrow next to Save ‐> Save with Encoding ‐> Yes ‐> Unicode (UTF‐8) ‐> Ok
Compile using: g++ ‐std=c++11
‐ Submit the following to the homework assignment page on Blackboard:
o Your homework report submitted as one PDF file. The report includes the answers to the non‐programming problems and the screen shots of your program’s sample runs for the programming problems. Your report must be developed by a word processor (no handwritten or drawn contents are
acceptable).
o Your well‐commented source code files (i.e., the .cc or .cpp files) for the
programming problems.
o Do NOT submit any files as a compressed (zipped) package. Rather, upload
individually each of the source code files (cpp or cc files) and the pdf report file. Note: Yon can submit multiple attempts for this homework, however, only your last
submitted attempt will be graded.
1/3
4. Display on the screen the contents of the sorted array A.
EECE7205 – Spring 2020 ‐ Homework 2
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. Asktheusertoinputthevalueofn,where1
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).
2/3
EECE7205 – Spring 2020 ‐ Homework 2
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 (only the updated algorithm in pseudo code similar to what is 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.
3/3