Computer Science 3650
Spring 2012
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.

  2. 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.)

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

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

  4. 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)).