Select Page

3 Question HWfeel free to ask any question
homework_6.docx

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.
#include
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