1. his assignment tests the concepts of:

• Classes
• Containers
• BigOh

Program Objective:

1. Implement the 5 missing implementations in student.cpp
2. Evaluate the BigOh for your solutions

DELIVERABLES:

DescriptionfilenameYour implementationstudent.cppBigOh solutionsIn the

You should not modify any files other than student.cpp.

Submitted assignments without the above file named correctly will render your assignment as uncompilable and will be detrimental to your assignment grade.

Submission Text Template

• Copy and paste this into the submission area to receive full credit for this lab:

BIGOH SRAND: O(1) BIGOH SUMONE: O() BIGOH SUMTWO: O() BIGOH UNIQUE: O() BIGOH MEDIAN: O() 

In between the parenthesis type in your answer. Use ^ to depict exponents. Such as n^2 for n2

. Please do not use the Formula wizard built into Blackboard. SRAND is already done for you, it is constant time.

Example output (due to rand, you will not see the same output):

Sum: 2384207 Sum: 61702649 Unique: false Median: 268 

Files

student.cpp starter code

//This file implements the functions //prototyped in functions.h and numbers.h #include "functions.h" #include "numbers.h" namespace DS { //Precondition: n is the size of the array //Postcondition: The sum of all values in the array is returned long sumArrayOfLong(const long in[], size_t n) { return 0; //TODO: remove this line } //Precondition: n is the size of the array //Postcondition: The sum of all values in the numbers array is returned //Hint: Make use of the member function sum, however, the cost of sum // must be taken into account when doing your BigOh analysis long sumArrayOfNumbers(const numbers in[] , size_t n) { return 0; //TODO: remove this line } //Implementation of member function numbers::sum //I realize that in CP2 this would of gone in numbers.cpp //However, for simplicity of uploading to Blackboard, //we use one file for all of your work //See numbers.h for pre/post long numbers::sum() const { return 0; //TODO: remove this line } //Implementation of member function numbers::unique //See numbers.h for pre/post bool numbers::unique(const numbers& r) const { return true; //TODO: complete the implementation } //Implementation of member function numbers::median //See numbers.h for pre/post long numbers::median() const { return 0; //TODO: remove this line } } #include  #include  #include  #include  #include "functions.h" #include "numbers.h" using namespace DS; int main() { const size_t MIN_SIZE = 2; const size_t MAX_SIZE = 10000; const size_t MAX_INNER = 100; const size_t MAX_NUMBER = 500; //Seed the random generator based on time //BIGOH SRAND: O(1) //It is constant since timer(0) returns the current system time from the OS //and srand basically copies this number to a static variable maintained internally //and it does not matter if the current time is 1am or 4pm, the number of operations //is the same srand(time(0)); //Fill in a vector of random size with random numbers std::vector nl(rand() % (MAX_SIZE - MIN_SIZE) + MIN_SIZE); for ( size_t i = 0 ; i < nl.size() ; ++i ) nl[i] = rand() % MAX_NUMBER; //BIGOH SUMONE: O() std::cout << "Sum: " << sumArrayOfLong(nl.data(), nl.size()) << std::endl; //Create and fill in a vector of numbers where numbers is //a custom class which also contains a vector of long //Basically, a multidimensional array, however, //each row will have a variable length std::vector vn(rand() % (MAX_SIZE - MIN_SIZE) + MIN_SIZE); for ( size_t i = 0 ; i < vn.size() ; ++i ) { size_t numbers_count = rand() % MAX_INNER; for (size_t j = 0; j < numbers_count; ++j) vn[i].append(rand() % MAX_NUMBER); } //BIGOH SUMTWO: O() std::cout << "Sum: " << sumArrayOfNumbers(vn.data(), vn.size()) << std::endl; //BIGOH UNIQUE: O() std::cout << "Unique: " << std::boolalpha << vn.at(0).unique(vn.at(1)) << std::endl; //Sort the numbers so that we can run median //WE ignore the cost of the sort when coming up with the BIGOH for median vn[0].sort(); //BIGOH MEDIAN: O() std::cout << "Median: " << vn[0].median() << std::endl; return EXIT_SUCCESS; } #ifndef LAB_BIG_OH_NUMBERS_H #define LAB_BIG_OH_NUMBERS_H #include  #include  // std::sort namespace DS { /* CLASS Numbers Really just a class that contains a bunch of numbers in a vector Value Semantics: Is it safe to use the copy constructor and the assignment operator Dynamic Memory Usage: Used by the vector Static & Global variable list: none Invariant declaration: single private vector of long */ class numbers { public: //CONSTRUCTOR (both default and value constructor) //When n is specified, updates the size of data numbers(size_t n=0) { data.resize(n); } //Modification Members / Mutator Methods //Precondition: i < data.size //Postcondtion: A reference to the number at position i is returned long& operator[](size_t i) { return data.at(i); } long& at(size_t i) { return data.at(i); } //Precondition: n/a //Postcondtion: Increase the size of data by one and insert the passed value at the end void append(long in) { data.push_back(in); } //Precondition: n/a //Postcondtion: Sorts the numbers in data to be in numerical order //ONLY DRIVER MAY CALL THIS //Please DO NOT call this method from any of your functions //Since this function alone has a cost of at least O(n log n) void sort() { std::sort(data.begin(), data.end()); } //Non-Modification Members / Assessor Methods //Precondition: n/a //Postcondtion: Returns the number of items in data void size() const { data.size(); } //Precondition: None //Postcondition: Returns the sum of all the numbers in the vector //TODO BY STUDENT, IMPLEMENT IN student.cpp long sum() const; //Precondition: None //Postcondition: Returns true when NONE of the numbers in this object are contained // within the passed object //TODO BY STUDENT, IMPLEMENT IN student.cpp bool unique(const numbers&) const; //Precondition: Data/Numbers is already SORTED in numerical order and data.size > 0 //Postcondition: Returns the integer median of the numbers in the collection (data) // Hint: https://www.mathsisfun.com/median.html //TODO BY STUDENT, IMPLEMENT IN student.cpp long median() const; private: std::vector data; }; } #endif //LAB_BIG_OH_NUMBERS_H #ifndef LAB_BIG_OH_FUNCTIONS_H #define LAB_BIG_OH_FUNCTIONS_H #include  #include "numbers.h" namespace DS { //Precondition: n is the size of the array //Postcondition: The sum of all values in the array is returned long sumArrayOfLong(const long[], size_t n); long sumArrayOfNumbers(const numbers[] , size_t n); } #endif //LAB_BIG_OH_FUNCTIONS_H