Warning: call_user_func_array() expects parameter 1 to be a valid callback, function 'wpdocs_custom_excerpt_length' not found or invalid function name in /home/myonysqo/myonlinehomeworkhelper.com/wp-includes/class-wp-hook.php on line 287

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

1. 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:
2. i) Traversing an SLL to find the first element less than a given value, find(ptr, value)
Recursive Step:

Base Case:

1. ii) Returning the sum of the first K elements in an array of size N, sum(array, N, K, index)
Recursive Step:

Base Case:

1. 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, 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

1. 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.

1. iv) Returning the element of the i-th position in a fixed array.
2. v) Returning the last element of a Doubly Linked List with two dummy nodes.

## #3 Extendable Vector

1. 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 worst-case and amortized-case complexity of the two implementations?]
2. 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.   • 100% Original Essays Guaranteed
• 8 Hrs Delivery Available
• Original and creative work
• Timely delivery guaranteed
• 100% confidentiality guarantee
• Variety of disciplines, topics, and deadlines
• Discounts offered on every custom-ordered paper
• Original papers written from scratch;
• 100% confidential;
• 100% plagiarism-free;
• Fast turn-around time;
• Direct communication with the writer;
• Instant email delivery;
• Free plagiarism reports; 