## Description

CptS 223 Homework #1

Please complete the homework problems on the following page. Be sure to show your work when appropriate. This

assignment must be turned in by the due date via Blackboard in PDF format. You may use any

editor you like (or even print it out, legibly write in answers, and scan it in), but convert it to PDF

for submission. I have provided MS Word (doc) and LibreOffice (ODF) versions for your platform

of choice.

1. [5] Order the following set of functions by their growth rate:

1) N

2) √N

3) N^1.5

4) N^2

5) N log N

6) N log(log(N))

7) N log^2 N

8) 2/N

9) 2^N

10) 2^(N/2)

11) 37

12) N^2 log(N)

13) N^4

2. [5] A program takes 35 seconds for input size 20 (i.e., n=20). Ignoring the effect of

constants, approximately how much time can the same program be expected to take if

the input size is increased to 100 given the following run-time complexities?

1. O(N)

2. O(N + log N)

3. O(N^3)

4. O(2^N)1

4. [8] Given the following two functions:

1 You might need an online calculator with arbitrarily large numbers for this one. Scientific

notation and 8 significant figures is just fine.

int g(int n)

{

if(n <= 0)

{

return 0;

}

return 1 + g(n – 1);

}

int f(int n)

{

int sum = 0;

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

{

sum += 1;

}

return sum;

}

A. [2] State the runtime complexity of both f() and g()

B. [2] State the memory (space) complexity for both f() and g()

C. [4] Write another function called “int h(int n)” that does the same thing, but is significantly

faster.

5. [5] State g(n)’s runtime complexity:

int f(int n){

if(n <= 1){

return 1;

}

return 1 + f(n/2);

}

int g(int n){

for(int i = 1; i < n; i *= 2){

f(i);

}

}

7. [5] What is the runtime complexity of Adam’s famous string splitter code? Hint: Make

sure to look into the source code for string.find() in the C++ std library. I’ve included that

code (downloaded from GNU).

static vector<string split(string text, string delimiter)

{

vector<string pieces;

int location = text.find(delimiter);

int start = 0;

//while we find something interesting

while (location != string::npos){

//build substring

string piece = text.substr(start, location – start);

pieces.push_back(piece);

start = location + 1;

//find again

location = text.find(delimiter, start);

}

string piece = text.substr(start, location – start);

pieces.push_back(piece);

return pieces;

}

GCC/G++ source downloaded from: http://mirrors.concertpass.com/gcc/releases/gcc-6.3.0/

Source file: gcc-6.3.0/libstdc++-v3/include/ext/vstring.tcc

template<typename _CharT, typename _Traits, typename _Alloc,

template <typename, typename, typename class _Base

typename __versa_string<_CharT, _Traits, _Alloc, _Base::size_type

__versa_string<_CharT, _Traits, _Alloc, _Base::

find(const _CharT* __s, size_type __pos, size_type __n) const

{

__glibcxx_requires_string_len(__s, __n);

const size_type __size = this-size();

const _CharT* __data = this-_M_data();

if (__n == 0)

return __pos <= __size ? __pos : npos;

if (__n <= __size)

{

for (; __pos <= __size – __n; ++__pos)

if (traits_type::eq(__data[__pos], __s[0])

&& traits_type::compare(__data + __pos + 1,

__s + 1, __n – 1) == 0)

return __pos;

}

return npos;

}

6. [10] (adapted from the 2012 ICPC programming competition) Write an algorithm to

solve the following problem and specify its runtime complexity using the most relevant

terms:

Given a nonnegative integer, what is the smallest value, k, such that

n, 2n, 3n, …, kn

contains all 10 decimal numbers (0 through 9) at least once? For example, given an input of

“1”, our sequence would be:

1, 2(1), 3(1), 4(1), 5(1), 6(1), 7(1), 8(1), 9(1), 10(1)

and thus k would be 10. Other examples:

Integer Value K value

10 9

123456789 3

3141592 5

(space for #6)

7. [18] Provide the algorithmic efficiency for the following tasks. Justify your answer,

often with a small piece of pseudocode or a drawing to help with your analysis.

A. [3] Determining whether a provided number is odd or even

B. [3] Determining whether or not a number exists in a list

C. [3] Finding the smallest number in a list

D. [3] Determining whether or not two unsorted lists of the same length contain all of the

same values (assume no duplicate values)

E. [3] Determining whether or not two sorted lists contain all of the same values (assume

no duplicate values)

F. [3] Determining whether a number is in a BST

8. [6] Fill in what these Linux commands do.

For example:

ls list files/directories

cp ____________________________________________________________

rm ____________________________________________________________

mkdir _________________________________________________________

ssh ___________________________________________________________

g++ ___________________________________________________________

scp ___________________________________________________________

9. [4] How do these variables get set and what do they get set with?

int main(int argc, char* argv[]) {

return(0);

}