Design and Analysis of Algorithms Neal Young

Computer Science 45

Midterm Exam, due in class Monday, May 12, 1997

Do three of the following problems.gif You can consult your notes, the text, or me when working on this exam, but please don't consult any other source. If you get stuck on a problem, you can come to me and ``buy'' a hint at the expense of part of the credit for the problem.

  1. Two-dimensional pattern matching:

    Design and analyze an algorithm for the following problem. Your algorithm may be randomized. It should be as efficient as you can make it, in the ``big-O'' sense. Give as complete an analysis as you can. (``Complete'' does not mean overly detailed, it just means that there are no gaps or ``hand waving''.)

    Given: Two two-dimensional arrays T[1..n,1..n] and P[1..m,1..m], where tex2html_wrap_inline63 and each array entry is a digit in tex2html_wrap_inline65 .

    Question: Does P occur in T? More specifically, are there an a and a b such that T[i+a,j+b] = P[i,j] for all i and j between 1 and m?

  2. Riemann zeta function:

    This problem asks you to consider an example of a different style of generating function.

    Define tex2html_wrap_inline85 .

    1. Define tex2html_wrap_inline87 so that tex2html_wrap_inline89 . Express the quantity tex2html_wrap_inline87 in words.
    2. Argue that

      displaymath93

      where p ranges over all the primes.gif

      Why does this imply that there are infinitely many primes?gif

  3. Lift-to-front algorithm:

    Read section 27.5 of CLR to understand the lift-to-front algorithm, then give a different analysis of the algorithm. Your analysis should be an amortized analysis based on a potential function. (The challenge here is to design the potential function.)

  4. Integer factorization:

    Professor Bo Zo wanted to assign an exam question on the Pollard-Rho algorithm, but he couldn't understand it. Read section 33.9, to understand Pollard-Rho, then help clear up Bo's questions:

    1. Instead of using the function tex2html_wrap_inline103 , wouldn't any function do, as long as it ``looks random''? For each of the following functions suggested by Bo, explain whether that function will do as well, and if not what is wrong with it.
      1. tex2html_wrap_inline105
      2. tex2html_wrap_inline107
      3. tex2html_wrap_inline109
      4. tex2html_wrap_inline111
    2. Does the argument given really use the assumption (made in the last paragraph of page 846) that tex2html_wrap_inline113 ?gif

      If it doesn't use that assumption, then can't the analysis be improved, because the time to find a factor will be tex2html_wrap_inline119 , rather than tex2html_wrap_inline121 (an improvement when tex2html_wrap_inline123 )?

      If it does use that assumption, then how does the algorithm work when applied to a prime power (i.e., tex2html_wrap_inline125 with tex2html_wrap_inline127 )? If it doesn't work, how do you handle this case?


Neal Young
Fri May 2 14:47:17 EDT 1997