1.Problem #1: For the program below, which one or more of the following are corr

Question

1.Problem #1: For the program below, which one or more of the following are correct? and why?

(A) The output is: 3 5 -5 -3 (B) The output is: 3 5 -3 -5 (C) The output is: 3 5 (D) The output is: 2 4 -4 -2 (E) The output is: 2 4 -2 -4 (F) The output is: 2 4 (G) The output is: 2 4 -3 -5 (H) The output is: 2 4 -5 -3 (I) There is a memory leak in this program. (J) There is no memory leak in this program.

#include<iostream>

#include<vector>

using namespace std;

class myClass {

public: myClass(int v): value( v + 1 ) {

cout << v << " ";

}

~myClass() {

cout << -value << " ";

} private: int value;

};

int main() {

vector vec; vec.push_back( new myClass(2) );

vec.push_back( new myClass(4) );

}

2.Problem #2: A Fibonacci number is defined as one of a sequence of numbers such that every number is the sum of the previous two numbers except for the first two numbers being 1. Thus, a Fibonacci number is one of: 1 1 2 3 5 8 13 … etc. Below are two implementations to calculate Fibonacci numbers. Which of the following descriptions are TRUE? and why? (A) Fib( 5 ) = 8 (B) The Big-O complexity of Fib() is O( N ) (C) The Big-O complexity of Fib2() is O( N ) (D) Fib() runs faster than Fib2() when N > 10 (E) Fib2() runs faster than Fib() when N > 10

#include using namespace std;

int Fib(int N) { if( N == 0 || N == 1) return 1; return Fib(N-1) + Fib(N-2); }

int Fib2(int N) { int *arr = new int[N+1];

arr[0] = 1; arr[1] = 1;

for(int i = 2; i <= N; i++)

arr[i] = arr[i-1] + arr[i-2];

int value = arr[N];

delete [] arr;

return value;

}

3. Problem #3: Suppose an array holds a sequence of N unique numbers that are sorted in decreasing order. If we move the last P numbers ( P < N ) to the beginning of this sequence of numbers, then what is the best possible Big-O time complexity you can achieve to search for a specific given number? For example, suppose we have the following sequence of numbers: { 10 , 9 , 8 , 7 , 6 , 5 , 4 , 3 , 2 , 1 } Suppose P were 4 and someone moved the last P numbers to the beginning: { 4 , 3 , 2 , 1 , 10 , 9 , 8 , 7 , 6 , 5 } If we don’t know P and want to search for a number (say, 7), what is the most efficient algorithm then? why?

(A) O( N ) (B) O( log N ) (C) O( N log N) (D) O( 1 )

Explanation / Answer

1. Answer is (F) The output is 2 4. and (I) There is memory leak in this program
   destructors are not called after program termination thats why we get prints only from consructors and also there is memory leak as allocated memory did not get    freed up.

2 The correct answers are:
(A) Fib(5) = 8
(B) The Big-O complexity of Fib() is O(N) ( The total number of terms to be added will be N)
(C) The Big-O complexity of Fib2() is O (N) (The for loop runs for N times)
(E) Fib2() runs faster than Fib() when N > 10   (Iterative versions are faster than recursion as function jumps makes recursion slow)

3. The most efficient algorithm will be of O(N) as we don't know P so it is as good as an unsorted list of numbers. So we need to compare with each number.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.