Computer Science 3650
Spring 2015
Practice Questions for Quiz 1

  1. What is a closed form for the sum 1 + 2 + 3 + ... + n? That is, express this sum as a function of n using standard arithmetic operators. Answer

  2. What is a closed form for ∑nk=1(k + 3)? Answer

  3. What is the value of sum 1 + 2/3 + 4/9 + 8/27 + ... ? (The sum is infinite, and each term is 2/3 of the previous term.) Answer

  4. What is the value of sum 3/4 + 9/16 + 27/64 + ... ? (The sum is infinite, and each term is 3/4 of the previous term.) Be careful. The sum does not start with 1. Answer

  5. Suppose that f(n) = 2n2 + n. Which of the following are true, and which are false?

    1. f(n) is O(n). Answer
    2. f(n) is O(n2). Answer
    3. f(n) is O(n3). Answer
    4. f(n) is O(2n). Answer
    5. f(n) is Ω(n). Answer
    6. f(n) is Ω(n2). Answer
    7. f(n) is Ω(n3). Answer
    8. f(n) is Ω(2n). Answer

  6. A median of a list of n numbers is defined to be a value x in the list such that at least n/2 values in the list are ≤ x, and at least n/2 values in the list are ≥ x. (Note that at least one value in the list is ≤ x, since x is in the list.) Describe an algorithm that finds a median of a list in time O(nlg(n)). Answer

  7. To within a constant factor, what is a solution to recurrence T(n) = 2T(n/4) + 1? Answer

  8. To within a constant factor, what is a solution to recurrence T(n) = 4T(n/2) + 1? Answer

  9. To within a constant factor, what is a solution to recurrence T(n) = 2T(n/4) + n? Answer

  10. To within a constant factor, what is a solution to recurrence T(n) = 4T(n/2) + n2? Answer