Design and Analysis of Algorithms Neal Young

Computer Science 45

Due: in class Wednesday, April 2, 1997

Problem Set 1 Warm up (don't hand in):

  1. Read CLR section 33.3, do 33.3-2 and 33.3-4.
  2. CLR 33.4-2

    hint: First prove that for any three integers a, b, and n, if n divides tex2html_wrap_inline42 and tex2html_wrap_inline44 , then n divides b.

Hand in:

  1. CLR 33.4-4

    Try to be careful to get the details right in this exercise.

    hint: Don't be fooled by the star. Remember long division on polynomials from high-school algebra? Use it to prove that if a is any number and f(x) is any polynomial, then f(x) = g(x)*(x-a) + c, where g is a polynomial of lesser degree and c is some number. What can you say about c if tex2html_wrap_inline62 ?

  2. (Better analysis of Rabin-Karp)

    CLR gives a ``hand-waving'' analysis of the expected time spent due to spurious hits when the pattern does not occur in the text. We'll improve this analysis.

    Recall that m is the number of digits in the pattern, n is the number of digits in the text, and q is the modulus used for the arithmetic.

    Suppose q is chosen uniformly at random from the primes less than some number N (to be determined later). (Later in the course we'll discuss how to choose such a q.) We want to know how big N has to be in order for the expected time spent checking spurious hits to be small.

    1. Prove that any m-digit number has at most 4m prime factors.
    2. Let a and b be any two m-digit numbers. Consider the event that tex2html_wrap_inline88 . Prove that, over all random choices of q, the probability of this event is

      displaymath92

      no matter what a and b are. hint: Use Theorem 33.37 on page 837 of CLR.

    3. Assume for this part that Theorem 33.37 is exact.

      Suppose you want to implement the algorithm (with q chosen randomly as described above) so that the expected time spent on any text and pattern not in the text is linear.

      How big should N be?

      What does this analysis tell you about how big a pattern you can handle, and still do all the arithmetic on 4-byte words?

  3. extra credit. CLR 34.2-3 (Extending Karp-Rabin to two-dimensional patterns)

    There may not be just one ``right'' answer. Describe the best solution you can. Discuss its merits and shortcomings.





Neal Young
Mon Mar 31 11:21:16 EST 1997