Description
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 split(string text, string delimiter) { vector 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 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); }