C++ Data Structures homework
CPSC 131 Homework 6
Deadline: 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.
#include <iostream>
using namespace std;
int mysteryrecursion(int a, int b) {
if ( b==1) {
return a;
} else {
return a + mysteryrecursion(a, b1);
}
}
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 BigO
 a) What are the differences between worstcase and amortized case in terms of BigO performance we went over in lecture, for a given solution to a problem? What do they mean? Answer in 23 sentences.
b) What is the BigO 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 ith position in a Singly Linked List.
 iv) Returning the element of the ith position in a fixed array.
 v) Returning the last element of a Doubly Linked List with two dummy nodes.
#3 Extendable Vector
 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 “increaseby10” implementation be less or more efficient compared to the “doublethecapacity” implementation? [Hint: what would be the worstcase and amortizedcase complexity of the two implementations?]
 Draw a sketch of the stack implemented using an ExtendableVector after each of the following steps:
ExtendableVectorStack<int> s;
push(11);
s.push(19);
s.push(6);
s.push(12);
s.push(13);
Assume that an ExtendableVector starts with default capacity 1.