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

#include

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 dont 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 )