Answers to 59.255 Mid-Semester Test 1, Tue Apr 20 1999

Duration: 45 minutes

Note: The Big-oh notations refer to the tightest bounds unless otherwise noted, i.e. Assume that O(n3) is not the desired form for a function that can be shown to be O(n2).

  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 (4) above with the value of the loop counter i set to k, then the value of x at that point will be 22k-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 T1(n) and T2(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 n0 and c that show that (2n+1)2 is O(n2) 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 = nid-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)n 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