Computer Science 3650
Summer 2002
Practice Questions for Exam 1

This is a closed book exam, but you may use one page of prepared notes. Answer all of the questions.

1. To within a constant factor, what is the fastest that a comparison algorithm can sort a list of n values?

2. 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/3) + n

3. Let f(n) = n³lg(n) and g(n) = n⁴. Is f(n) O(g(n))? Is g(n) O(f(n))? Justify your answer.

4. A particular divide-and-conquer algorithm, when run on an input of size n, works by spending O(n) time splitting the problem in half, then does a recursive call on each half, 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?

5. You are given a list x₁, ..., x_n of n different positive numbers, in no particular order, and a positive integer k < n. You need to find k values a₁, ..., a_k from the input list, where a₁ < a₂ < ... < a_k, with the following property.

   For convenience define a₀ = 0 and a_k+1 = infinity. Let set s_j be {x_i | a_j <= x_i < a_j+1}, for j = 0, ..., k. That is, s_j consists of all members of the input list that lie between a_j and a_j+1. The desired property is that all of the sets s₀, ..., s_k have approximately the same size. (Their sizes should differ by at most 1.)

   (If k = 2, then the idea is to select values that divide the list into thirds, by cutting it at two places. If k = 99, the list is being divided into 100 equal sections by the selected values.)

   1. Explain an algorithm that solves this problem in time O(nk).
   2. Explain an algorithm that solves this problem in time O(n lg n).
   3. Approximately how large must k be, in terms of n (to within a constant factor) before algorithm (b) is faster than algorithm (a)?

6. The fast divide-and-conquer integer multiplication algorithm gets its speed from a clever trick that allows it to do only three recursive calls instead of four. Does the trick mean that it takes only 3/4 as long as our first divide-and-conquer algorithm (which does four recursive calls), or is it not that much better, or does it take even less than 3/4 as much time?

7. A complex number is represented by a pair of real numbers. (The pair (a,b) is usually written (a + bi), but we will just write a complex number as a pair of real numbers here.) The product of two complex numbers (a,b) and (c,d) is defined to be the complex number (ac-bd, ad+bc). Clearly, the product of two complex numbers can be computed by doing four multiplications of real numbers. Show how to compute the product of two complex numbers using only three multiplications of real numbers. You can do any constant number of additions and subtractions, but you must assume that real numbers are stored to arbitrary precision, and the number of additions and subtractions that you do must not depend on the precision of the numbers.