Problem Set #1

CS 155
due September 22, 1999

Each problem is worth 10 points.
  1. Use the asymptotically efficient divide-and-conquer algorithm discussed in class to find the product of 243 and 1221.

  2. Consider a version of the simultaneous max and min algorithm in which the input set is divided into three elements of equal size (you may assume that the input size is a power of 3). Set up, and solve exactly, a recurrence relation that describes the time complexity of this algorithm. How does your solution compare to the optimal solution found in class for the corresponding problem?

  3. State what's wrong with the following argument -- other than the fact that it comes to an obviously incorrect conclusion.

    Consider the sequential search algorithm for a sequence of size n, in the case where the desired item is guaranteed to be in the sequence. A recurrence describing the number of elements comparisons required is t(n) = 1 + t(n-1), which has the solution t(n) = an + b. Since t(0) = 0 and t(1) = 0, we have 0 = a0 + b and 0 = a1+ b, so 0 = a and therefore 0 = b. So the sequential search algorithm takes no time at all.

  4. Suppose that a certain application deals with n binary switches, and finds it necessary to test all of the 2n sequences of on/off values for the switches, and then return to the initial position. There are therefore 2n-1 operations of changing the switches after each test. It is desired to minimize the total number of flippings of individual switches. For example, when n=2, using the natural binary ordering 00, 01, 10, and 11 would require 3 operations, flipping respectively 1, 2, and 1 switches (where the last 2 are needed to get back to the initial position), for a total cost of 1 + 2 + 1 = 4. This is not the minimum value for n=2.

    The example suggests that we are really looking at sequences of bit strings, so consider the following algorithm for constructing a sequence of 2n different bit strings.

    For n=1, use the sequence (0 1). For n>1, recursively construct two identical copies of a sequence for n-1, prefix all strings in the first sequence by 0, and prefix all strings in the second sequence by 1. Finally, concatentate the new first sequence with the reverse of the second sequence. So for example, for n=2 we start with (0 1), get the two new sequences (00 01) and (10 11), and reverse and concatenate to get (00 10 01 11).

    Let A(n) be the total number of switches needed to be flipped, using the sequence generated by this algorithm with input n. Set up, and solve exactly, a recurrence for A(n).

  5. (EXTRA CREDIT) Redo the previous problem under the assumption that the switches have to be reset to their initial position, and that the cost to be minimized includes the cost of doing so. So in the first example given for n=2, the cost is 1+2+1+2, or 6 (which is still not minimal).