Drawing Call Stacks (C++)

// binary_search_rec.cpp #include  #include  template const T* binary_search_rec(const T* begin, const T* end, const T& value) { if (begin == end) { return nullptr; } const T* mid = begin + ((end - begin) >> 1); if (value  
 
 
 ___________________________________________________________________________________________________________
 
 
 
// binary_search_rec4.cpp #include  #include  template const T* binary_search_rec4(const T* begin, const T* end, const T& value) { if (begin == end) { return nullptr; } const T* newBegin; const T* newEnd; for (int i = 1; i > 2)); newEnd = begin + (i * ((end - begin) >> 2)); if (value > 2)) + 1, end, value); } 
  2. First obtain the source files for the functions binary_ search rec and rec4. Then read over the code and see how the iterative code for binary search was morphed into the code for binary_search_rec. In order to reduce the number of recursive calls, consider the code for the function binary_search_rec4 that splits the range of the search to 4 parts and then performs the search within one of the 4 quadrants. Does this actually improve performance? In the files you can run tests to compare the runtimes on large inputs. (3 points each for 15 total) Consider the following array of type int named data for the following questions. int data[16] (-3, 8, 2, 5, 8, 17, 23, 30, 41, 48, 62, 63, 7e, 75, 81, 99; You may assume data starts at address 0x4000. When drawing the call stacks, write values of memory addresses the pointers store. Do not draw arrows. Your call stack should have the values stored at the time the final return is called (not necessarily the values the function was called withot the values the loop initializes at/etc.). a. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) for the function call binary_search_rec (data, data+16, 17); for the function call binary_search_rec4 (data, data+16, 17) for the function call binary_search_rec (data+4, data+12, 5) b. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) c. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) CSE 250 Fall 2017 d. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) for the function call binary_search_rec4(data+4, data+12, 5); Write a set of valid parameters that, when passed to binary_search_rec and binary_search_rec4, result in the same number of recursive calls for both functions. e.  2. First obtain the source files for the functions binary_ search rec and rec4. Then read over the code and see how the iterative code for binary search was morphed into the code for binary_search_rec. In order to reduce the number of recursive calls, consider the code for the function binary_search_rec4 that splits the range of the search to 4 parts and then performs the search within one of the 4 quadrants. Does this actually improve performance? In the files you can run tests to compare the runtimes on large inputs. (3 points each for 15 total) Consider the following array of type int named data for the following questions. int data[16] (-3, 8, 2, 5, 8, 17, 23, 30, 41, 48, 62, 63, 7e, 75, 81, 99; You may assume data starts at address 0x4000. When drawing the call stacks, write values of memory addresses the pointers store. Do not draw arrows. Your call stack should have the values stored at the time the final return is called (not necessarily the values the function was called withot the values the loop initializes at/etc.). a. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) for the function call binary_search_rec (data, data+16, 17); for the function call binary_search_rec4 (data, data+16, 17) for the function call binary_search_rec (data+4, data+12, 5) b. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) c. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) CSE 250 Fall 2017 d. Draw the call stack up to the largest point (i.e., just before midor nullptr is returned) for the function call binary_search_rec4(data+4, data+12, 5); Write a set of valid parameters that, when passed to binary_search_rec and binary_search_rec4, result in the same number of recursive calls for both functions. e