1. Let Then a, b, c and d respectively are:

   	A.	3, 1, 2 and 0
   	B.	1/3, 1/2, 1/6 and 2
   	C.	1/3, 1/2, 1/6 and 1
   	D.	1/3, 1/2, 1/6 and 0

2. Consider the following C program fragment:

   (1) scanf ("%d", &n);
   (2) x = 2;
   (3) for (i = 1; i <= n; i++)
   (4)   x = x*x;
   

   A choice of loop invariant for this fragment is:

   If we reach the test for i <= n in the for loop of line (3) above with the value of the loop counter i set to k, then the value of x at that point will be 2^2k-1.

   For values of i > n, this statement is:

   	A.	false
   	B.	true
   	C.	not applicable
   	D.	undefined

3. Consider again the C program fragment in question 1. What will the value of x be when the loop terminates?

   	A.	22n
   	B.	22n-1
   	C.	22n+1
   	D.	None of the above

4. log(1000!) is closest to

   	A.	5000
   	B.	50,000
   	C.	500,000
   	D.	5,000,000

5. Which of the following is in ascending order of growth rate (slowest to fastest) reading left to right?

   	A.	log(n), sqrt(n), n*log(n), n2
   	B.	sqrt(n), log(n), n2, n*log(n)
   	C.	log(n), n*log(n), sqrt(n), n2
   	D.	log(n), n*log(n), n2, sqrt(n)

6. Suppose T₁(n) and T₂(n) are both O(f(n)). Which of the following is true?

   	A.	T1(n) + T2(n) = O(f(n))
   	B.	T1(n)/T2(n) = 1
   	C.	T1(n) is O(T2(n))
   	D.	All of the above

7. Minimal witnesses n₀ and c that show that (2n+1)² is O(n²) are:

   	A.	1 and 8
   	B.	2 and 6
   	C.	2 and 7
   	D.	3 and 5

8. Consider the following program fragment:

   scanf("%d", &n);
   for (i = 0; i < n; i++)
      for (j = 0; i < n; j++)
         A[i][j] = 0;
   for (i = 0; i < n; i++)
      A[i][i] = 1;
   

   It's tightest bound running time is:

   	A.	O(n)
   	B.	O(n2)
   	C.	O(n3)
   	D.	O(2n)

9. If f(n) is O(g(n)), then max(f(n), g(n)) is

   	A.	O(g(n) - f(n))
   	B.	O(g(n) * f(n))
   	C.	O(g(n))
   	D.	All of the above

10. In the for loop:

    for (i = 0; i <= b; i++) {
       loop body;
    }
    

    How many times is the body of the loop executed?

    	A.	b-a
    	B.	b-a+1
    	C.	b-a-1
    	D.	b-a+2

11. Suppose that A[0..n-1] is a sorted array containing n integers in non-descending order and x is a value guaranteed to be in it. Now consider the following program fragment:

    scanf("%d", &x);
    low = 0;
    high = n-1;
    while (low <= high) {
       mid = (low+high)/2;
       if (x < A[mid])
          high = mid-1;
       else if (x > A[mid])
          low = mid+1;
       else
          return mid;
    }
    

    Its running time is:

    	A.	O(n)
    	B.	O(log n)
    	C.	O(n*log n)
    	D.	O(n2)

12. In trying to solve the recurrence:

    T(1) = a	(1)
    T(n) = T(n-1) + b	(2)

    by repeated substitution where (2) is assumed to be the first substitution into T(n), we will find that after i substitutions into T(n), T(n) =

    	A.	T(n-i) + ib
    	B.	T(n-i-1) + (i-1)b
    	C.	T(n-i+1) + (i+1)b
    	D.	None of the above

13. If

    T(1) = a

    T(n) = 2T(n-1) + b

    for some positive constants a and b, then T(n) is

    	A.	O(n)
    	B.	O(n*log n)
    	C.	O(n2log n)
    	D.	None of the above

14. The binomial theorem states:
    
    If x >> y, then (x+y)ⁿ is approximated closest by

    	A.	xn + nyxn-1
    	B.	xn + yn
    	C.	xn + ny
    	D.	xn + nyn-1

15. In how many ways can you distribute 5 apples and 5 oranges to 3 children such that each child has at least one of each?

    	A.	180
    	B.	36
    	C.	66
    	D.	None of the above

You scored percent correct. Here are the Correct answers