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

josh
March 12, 2019 0 Comment

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.
Facebook
Twitter
Google+
  • 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;
  • 24/7 customer support team.
  • Choose your font
  • 12 point font size
  • Double-sized
  • Over 275 words/page
  • Text aligned left
  • One inch margin

We Accept

myonlinehomeworkhelper

you have a money back guarantee if you are not satisfied with our services