Some Solutions

CS 280 - Spring 2002

These are solutions to problems that have come up during cs280: (1) a better solution to HW6 problem 6 (the one about finding the best TV channel) and (2) a recursive solution to Review Questions for Prelim II problem 7 (the one about bit strings of length 6 with two consecutive zeros) and a variant of problem 7 (the question about triple-zeros asked in class).  You aren't required to study these solutions as part of cs280, but you might find the solutions interesting, particularly if you've spent some time thinking about the problems.

  1. Due to your relentless channel flipping, a new rule for TV-watching is being enforced.  You're allowed to flip once through all the channels, visiting each channel exactly once.  You can choose to stop at any point, but you cannot backup and you cannot change your mind.  Somehow, at a glance, you are able to determine a numerical rating for each TV show (even if a commercial is currently showing).  Your goal, of course, is to end up watching the show with the highest numerical rating.  For example, one strategy would be to always choose the last channel; using this strategy, the probability that you end up watching the highest rated show is 1/n where n is the number of channels.  Design a strategy (i.e., a set of simple rules) by which you are guaranteed, with probability at least 1/4, to end up at the highest-rated show  regardless of the number of channels.  Describe your strategy and show that the desired probability is 1/4 or more.  For simplicity, you can assume that the number of channels is even, that each channel is equally likely to be showing something interesting, and that no two shows have the same numerical rating.

    Let n be the number of channels.  The strategy is: Find the best program p among the first k channels, then choose the first channel you find with a rating better than that of program p.  The goal is to choose k so that this strategy ends up at the best channel with high probability.

    Let best(m) represent the best channel among channels 1 to m.  Suppose the overall best channel is actually at position x in the list of n channels (in other words, best(n) = x).  Then we will end up at channel x only if best(x-1) falls within the first k channels and k < x.  The probability that best(x-1) falls within the first k channels is k / (x-1) for k < x.  Note that
    P(best is found) 
    = sumall x>k [P(best is found | best is at position x) * P(best is at position x)]
    = sumall x>k [(k / (x-1)) * (1 / n)]
    = (k / n) sumall x>k [ 1 / (x-1) ]

    For large n, this sum is closely approximated by an integral:
    (k / n) integralkn (1 / x) dx = (k / n) [ ln n - ln k] = -(k / n) ln (k / n) where ln( ) represents the natural log function.

    Let y = k / n.  The goal now becomes: Find y such that -y ln y is maximized.  This can be done with some simple calculus.  Let f(y) = -y ln y.  Then f'(y) = -y/y - ln y.  Setting this equal to 0, we get ln y = -1 or y = 1/e where e is the base of the natural logarithm.

    We conclude that, using the strategy outlined above, the best value for k is that which makes k/n close to 1/e.  The resulting probability of finding the best channel is approximately 1/e (which is significantly better than the value 1/4 requested in the original problem).

  2. How many strings of length n=6 have two consecutive 0's?  Also, the variant asked in class: How many strings of length n=6 have three consecutive 0's?

    An answer to the first question appears in Answers to Review Questions for Prelim II where the problem is solved by finding the number of strings with no consecutive 0's.  Alternately, one can solve this problem by building a recursive formula for the answer.  This technique is discussed in section 5.1 of the text, a section we are not covering as part of cs280.  For those who are interested, a recursive solution follows.

    For the first question, let N(i) represent the number of valid strings of length i (i.e., those with two consecutive zeros).  Observe that all valid strings of length i can be divided into three disjoint groups: (1) those that begin with 1, (2) those that begin with 01, and (3) those that begin with 00.  Further we know how many strings are in each group:
    # that begin with 1 = N(i-1) because there must be a 00-pair in the remaining string,
    # that begin with 01 = N(i-2) because there must be a 00-pair in the remaining string,
    # that begin with 00 = 2i-2 because all such strings are valid.

    This gives us a recurrence relation: N(i) = N(i-1) + N(i-2) + 2i-2.  We can "start" the recurrence relation by observing that there are no strings of length 0 or 1 that have two consecutive zeros and there is exactly on string of length 2 with two consecutive zeros.  In other words, N(0) = N(1) = 0 and N(2) = 1.  Using the recurrence relation we can fill in the following table.
    i 0 1 2 3 4 5 6 7
    N(i) 0 0 1 3 8 19 43  94

    For the second question, we let M(i) represent the number of valid strings of length i (i.e., those with three consecutive zeros).  The valid strings of length i can be divided into 4 disjoint sets and we know how many are in each set:
    # that begin with 1 = M(i-1),
    # that begin with 01 = M(i-2),
    # that begin with 001 = M(i-3),
    # that begin with 000 = 2i-3.

    This gives us a recurrence relation: M(i) = M(i-1) + M(i-2) + M(i-3) + 2i-3.
    i 0 1 2 3 4 5 6 7
    M(i) 0 0 0 1 3 8 20 47

    The recurrences make it easy to calculate answers for relatively short strings, but to really complete the problem, we should find closed-form solutions for the two recurrences.  Methods for doing this are discussed in Chapter 5 of the text.  With a closed-form solution, we would be able to quickly answer such questions for strings of length 100 or more.