Solutions to Problem Set #1

CS 155
September 22, 1999

  1. The product of 243 and 1221 can be found in terms of 2*12, 43*21, and (2+43)*(12+21), or 45*33.

    The product of 2*12 can be found in terms of 0*1, 2*2, and (0+2)*(1+2), or 2*3. These products are 0, 4, and 6, so the desired product is 0*100 + (6-0-4)*10 + 4 = 24.

    The product of 43*21 can be found in terms of 4*2, 3*1, and (4+3)*(2+1), or 7*3. These products are 8, 3, and 21, so the desired product is 8*100 + (21-8-3)*10 + 3 = 903.

    The product of 45*33 can be found in terms of 4*3, 5*3, and (4+5)*(3+3), or 9*6. These products are 12, 15, and 54, so the desired product is 12*100 + (54-12-15)*10 + 15 = 1485.

    So the overall desired product is 24*10000 + (1485-24-903)*100 + 903 = 240000 + 55800 + 903 = 296703.

  2. Let t(n) be the number of comparisons required to find the max and min of a set of size n. Since it takes 2 comparisons to find the largest of the 3 maxima of the subsets, and 2 more to find the smallest of the 3 minima of the subsets, the recurrence becomes
    t(n) = 3t(n/3) + 4, and t(1) = 0

    Letting n=3u, and t(n)=s(u), we have
    s(u) = 3s(u-1) + 4, so
    (E-3) = <4>, so
    (E-3)(E-1) = <0>, and thus
    s(u) = a3u + b, or t(n) = an + b

    From the recurrence, we have t(1) = 0 and t(3) = 4, and from
    0 = a1 + b and 4 = a3 + b, we can determine that a=2 and b=-2, so that
    t(n) = 2n - 2.

    This result is not as good as the best result found in class. In fact, it is just the result found by the naive algorithm that finds the max and min separately. Like the naive algorithm, its asymptotic behavior is the same as the best algorithm found in class.

  3. The given recurrence and its general solution are correct. However the values for t(0) and t(1) are inconsistent with it. That is, if the recurrence is to hold for all nonnegative n, then the recurrence, and not the given value, must be used for t(1). In this case, t(1) = 1 + t(0), so if t(0) = 0, t(1) must be 1.

    To look at things another way, there is a version of the algorithm in which no element comparisons are made for n=1. Since no subproblem remains to be solved, this must be the base case, so the recurrence then describes the number of element comparisons for n>=1. Therefore the value of t(n) at n=0 is irrelevant -- indeed, when n=0 it's not clear that one can talk about a successful search.

  4. None of the first 2(n-1)-1 operations involve the new switch, so their total cost is just A(n-1). The same applies to the last 2(n-1)-1 operations. The cost of the remaining operation is just 1, since all of the n-1 old switches, both before and after this operation, are in the position given by the last sequence of the solution for n-1. So the new cost A(n) is given by A(n-1) + A(n-1) + 1. Thus
    A(n) = 2A(n-1) + 1, so
    (E-2) = <1>, and
    (E-2)(E-1) = <0>, so
    A(n) = a2n + b.
    We have A(1)=1, and so A(2)=2*1 + 1 = 3. A little algebra gives that a=1 and b=-1, so that A(n) = 2n-1.

    Note that this value must be optimal, since there are 2n different bit strings in the sequence. A similar observation applies to the algorithm in the next problem. A sequence that minimizes the cost as defined in that problem is called a Grey code.

  5. First note that in any sequence defined by the algorithm, the cost of getting from the last string in the sequence back to the first string is just 1. This is true by inspection for n=1, and for n>1, these strings differ only in their first bit (elsewhere they are both just the first string in the sequence constructed for n-1).

    In particular, if A(k) is the cost of the the cost of the 2k operations on k switches, then the cost of the first 2k-1 operations (that is, of all operations except the one that returns to the initial position) must be A(k)-1. So the first 2(n-1)-1 operations on n switches have cost A(n-1)-1, the next has cost 1, the next 2(n-1)-1 operations have cost A(n-1)-1, and the last has cost 1. Therefore A(n) = A(n-1) - 1 + 1 + A(n-1) - 1 + 1 = 2A(n-1). This recurrence has solution A(n) = a2n, and since A(1) = 2, a=1. So the sequence given by the algorithm for n switches has cost 2n. As in the previous problem, this cost is clearly optimal.