CptS 223 Homework #1

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);
}