Homework #1 Big-O and general Linux/Git topics Solution

Description

Please complete the homework problems on the following page. Note that this is an individual assignment and all work must be your own. Be sure to show your work when appropriate.

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.

Once you have your PDF file, put it into your Git repository in the HW1 directory, commit and push it. Once you’ve pushed your PDF file up, put something onto Blackboard so the TA knows to grade your work.

 

 

 

 

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

Unordered Complexities	Ordered Complexities
N
√N
N^1.5
N^2
N log N
N log(log(N))
N log^2 N
2/N
2^N
2^(N/2)
37
N^2 log(N)
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)¹

3. [8] Given the following two functions:

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

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

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

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

 

 

 

4. [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); } }

 

5. [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:

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.

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

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

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

4. [3] Determining whether or not two unsorted lists of the same length contain all of the same values (assume no duplicate values)

5. [3] Determining whether or not two sorted lists contain all of the same values (assume no duplicate values)

6. [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 __________________________________________________________

ssh __________________________________________________________

g++ __________________________________________________________

scp __________________________________________________________

9. [4] What is Git and what is it for?

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

int main(int argc, char* argv[]) {
return(0);
}