CPSC 131 Homework 3

#1

Choose the equivalent Big O notation for the functions given below. If there is more than one option, circle the tightest asymptotic bound.

a) function f(n) = 2n + 3 belongs to

O(1) O(n) O(n2) O(log n)

b) function f(n) = n2 + n + 1 belongs to

O(1) O(n) O(n2) O(log n) c) function f(n) = n2 + log n belongs to

O(1) O(n) O(n2) O(log n)

#2

Given the following pieces of code, choose the Big O complexity. (If there is more than one option, circle the tightest asymptotic bound.)

Give a 1-2 sentence explanation of your reasoning.

a)

p = 1;

for (int j=0; j < n; j++) {

if (a[j] != 0) {

p = p * a[j];

}

} return p;

where n is a positive integer and array a[] has all float values. i) O(1) ii) O(n) iii) O(n2)

iv) O(log n) b)

bool isUndirected (int n, float **a) {

bool result = true;

for (int i=0; i < n; i++) {

for (int j = 0; j < n ; j++) {

if ( (i != j) && (a[i][j] != a[j][i])) {

result = false;

}

}

} return result;

}

where n is a positive integer and the 2D matrix a[ ][ ] has all float values. i) O(1) ii) O(n) iii) O(n2)

iv) O(log n) c) float p1 = 1;

for (int i=0; i < n; i++) {

if (a[i] < 0) {

p1 = p1 * a[i];

}

}

float p2 = 1;

for (int j=0; j < n; j++) {

if (a[j] > 0) {

p = p * a[j];

}

} float pp = (abs(p1) > p2)? abs(p1) : p2;

return pp;

i) O(1) ii) O(n) iii) O(n2)

iv) O(log n)

#3

Working with char vector using Array

The class FixedVector has been declared and was implemented. The code is available here. You want to use additional operations within the class, so the function member insert needs to be changed, as well as two new functions members, find and operator == need to be added to the class definition and implemented. Consider the new class definition below, and the new/modified functions being in bold.

// Augmented Declaration template class FixedVector { private: size_t size_; // number of elements in the data structure const size_t capacity_; // length of the array T* array_; // pointer to dynamically allocated array public: // Constructors FixedVector(size_t arraysize = 0); // Also serves as default constructor FixedVector(const FixedVector& input ); // Copy constructor ~FixedVector(); // Getters / Setters T& at(size_t index); T& operator[](size_t index); void push_back(const T& value); void set(size_t index, const T& value); void erase(size_t index);

size_t find(const T& value); size_t insert(size_t beforeIndex, const T& value); size_t size(); bool empty(); void clear();

// Overloaded Operators FixedVector& operator= (const FixedVector& rhs); //Copy assignment

bool operator== (const FixedVector& rhs) };

// Function member to look for value in FixedVector

// If value is in the FixedVector, then return the index of FixedVector that contains // the value. If size_ is 0 (array is empty) or the value is not in FixedVector, then

// return size_

template

size_t FixedVector::find(const T& value) {

// to be completed

}

// Function member to insert value in the FixedVector at index beforeIndex and return // beforeIndex

// If beforeIndex is between 0 and size_, then insert the value by pushing all the // elements to the right of beforeIndex one position to the right, and increment size_

// If size would exceed capacity, then exit with an error

// If beforeIndex is >=size_ then display error and do not do any changes to FixedVector

template

size_t FixedVector::insert(size_t beforeIndex, const T& value) {

// to be completed

}

// Function member to test the equality between two FixedVectors

// It returns true if the two FixedVectors are exactly the same, false otherwise

template

bool FixedArray::operator== (const FixedVector& rhs){ // to be completed

}

int main() {

// testing the new implementation of a FixedVector

// declare & initialize a FixedVector of int with 10 elements

FixedVector Array1(5);

// place 1,5,10 in the array

cout << FixedArray gets the elements 1, 5, 10 << endl;

Array1.push_back(1);

Array1.push_back(5);

Array1.push_back(10);

// Try the find operation

cout << Value 5 is at index << Array1.find(5) << endl;

// Try the insert operation

cout << Value 2 is inserted at index << Array1.insert(1, 2) << endl;

// Try the == operator

FixedVector Array2(5);

Array2.push_back(1);

Array2.push_back(5);

Array2.push_back(10);

if (Array1 == Array2)

cout << The two arrays are the same. << endl;

else

cout << The two arrays are different. << endl;

return 0;

}

1. Turn in the complete code, including all of the above to be completed sections.

2. Test by running the main() function above and capture the console screen output, by attaching it as an captured image (use CTRL+PrtSc) or printed out as a file.