3 Question HWfeel free to ask any question

Unformatted Attachment Preview

CPSC 131 Homework 6
Wednesday, March 13 (MoWe sections), Thursday, March 14 (TuTh sections)
Turn in your submission as hard copy in class. Do not upload on TITANium.
#1 Recursion
a) For each of the following problems, what is the recursive step and what is the base case? Answer
in one sentence; no need to write C++ code:
i) Traversing an SLL to find the first element less than a given value, find(ptr, value)
Recursive Step:
Base Case:
ii) Returning the sum of the first K elements in an array of size N, sum(array, N, K, index)
Recursive Step:
Base Case:
b) Trace the recursion given by the following code for the data: 7 4
similar to the examples provided by the instructor in class. Do not forget to include the parameters’
values at each call and the value returned by the called function.
using namespace std;
int mysteryrecursion(int a, int b) {
if ( b==1) {
return a;
} else {
return a + mysteryrecursion(a, b-1);
int main() {
int x = 6;
int y = 2;
cin >> x >> y;
cout << mysteryrecursion(x, y) << endl; return 0; } Trace: What does the code above accomplish? (If you’re not sure try different values until you see a pattern.) #2 Big-O a) What are the differences between worst-case and amortized case in terms of Big-O performance we went over in lecture, for a given solution to a problem? What do they mean? Answer in 2-3 sentences. b) What is the Big-O performance of the following operations? i) Searching for an arbitrary value through a Singly Linked List. ii ) Searching for an arbitrary value through an arbitrary fixed size array. iii) Returning the element of the i-th position in a Singly Linked List. iv) Returning the element of the i-th position in a fixed array. v) Returning the last element of a Doubly Linked List with two dummy nodes. #3 Extendable Vector a) The ExtendableVector doubles its capacity everytime it gets full. Consider a different implementation of an ExtendableVector that adds 10 to its capacity instead of doubling it every time it gets full. Would this “increase-by-10” implementation be less or more efficient compared to the “double-the-capacity” implementation? [Hint: what would be the worstcase and amortized-case complexity of the two implementations?] b) Draw a sketch of the stack implemented using an ExtendableVector after each of the following steps: ExtendableVectorStack s; s.push(11); s.push(19); s.push(6); s.push(12); s.push(13); Assume that an ExtendableVector starts with default capacity 1. ... Our essay writing service fulfills every request with the highest level of urgency. attachment