CSCI 3650
Summer 2000
Solutions to practice questions for exam 1

You will have 90 minutes for the exam, and can bring one sheet of prepared notes, writing on both sides of the paper.

  1. To within a constant factor, what is the solution to the following recurrence? Assume that T(n) is bounded by a constant for small values of n.
    T(n) = 9T(n/4) + O(n)

    Use the master theorem with a = 9, b = 4 and f(n) = n. Then logb(a) is about 1.58, and the solution is THETA(nlog4(9)).

  2. Let f(n) = n3log2(n) and g(n) = n2(log2(n))3. Is f(n) O(g(n))? Is g(n) O(f(n))? Justify your answer.

    f(n)/g(n) = n/(log2(n))2. But n grows much faster than (log2(n))2. (Remember that any fixed power of log(n) grows slower than any fixed positive power of n.) So the limit as n goes to infinity of f(n)/g(n) is infinity.

    g(n) is O(f(n)), but f(n) is not O(g(n)).

  3. A particular divide-and-conquer algorithm, when run on an input of size n, works by spending O(n) time splitting the problem into three roughly equal size parts, then does a recursive call on each of the three parts, then spends O(n) time combining the solutions to the recursive calls. On small inputs, the algorithm takes a constant amount of time. To within a constant factor, how long does this algorithm take, in terms of n?

    The recurrence is T(n) = 3T(n/3) + O(n). The master theorem tells us that the solution is T(n) = THETA(n log(n)).

  4. You have a list of n different numbers x1, x2, ..., xn, in an arbitrary order, and also a value k < n. You would like an algorithm that prints the smallest k values in the list, in any order. For example, if k = 3, you are asked to print the smallest 3 of x1, x2, ..., xn.

    Describe an algorithm that solves this problem in time O(n), independent of the value of k.

    The values sought are those that are less than or equal to the k-th smallest value in the list. Use the fast selection algorithm to find the k-th smallest value (call it V), then examine each of the values in the original list, printing those that are less than or equal to V.

  5. You have an unsorted array of size n. You need to search for k different values in the array. You consider two strategies.

    1. Do k linear searches, searching the entire array for each value.

    2. Sort the array using mergesort, and then do k binary searches. (A binary search in a sorted array of size n takes time O(log n).)

    To within a constant factor, how large should k be before method (b) is faster than method (a)?

    Method (a) takes time O(nk), since it calls for k linear searches, each having cost O(n).

    Method (b) takes time O(n log(n) + k log(n)), since sorting takes time O(n log(n)), and then the k binary searches cost O(k log(n)) time (O(log(n)) time each).

    The two functions cross where they are equal. So set nk = n log(n) + k log(n). Solving this yields

    k(n - log(n)) = n log(n)

    k = (n log(n)) / (n - log(n))

    Notice that log(n) is very small compared to n, so n - log(n) is approximately n. Since we are only getting the crossover value k to within a constant factor anyway (having ignored the big-O),
    k = log(n)
    will do. For k larger than log(n), solution (b) is preferred.