Problem Set #2, CS 255, due March 15, 2006

 

Problem #1 is worth 30 points; the others are worth 20 points each. All of the problem sets for this class combined will total 350 points.  

    1. Suppose that a random number is to be chosen uniformly from 1 to M, except that k specified values are not allowed. One algorithm for doing this is to repeatedly select random numbers from 1 through M until a value is found that is different from any of the specified values. What is the expected number of values that will have to be selected before a permitted one is found? Give an exact answer rather than an asymptotic answer.
    2. What is the asymptotic expected number of values, as a function of n and M, that will have to be computed if the algorithm of (a) replaces line 3 in the PERMUTE-BY-SORTING algorithm of Cormen et al, Section 5.3?
    3. Can M be chosen so that, if bucket sort with M buckets is used instead of line 4 in the PERMUTE-BY-SORTING algorithm, the algorithm's asymptotic expected time complexity can be reduced below n log n?

  2. Ex 5.3-5, Cormen et al, p 105.

    Hint: first show that for any sequence (xi) of values between 0 and 1, Π (1-xi) >= 1 - Σ xi.

    1. Show that the problem of determining whether an integer n is composite is in NP (hint: guess the factors).
    2. What's wrong with the following argument, that claims to show that the problem of part 1 is in P?
      Given n, it takes time polynomial in n to divide n by any integer i less than n. Since there are O(n) such integers, it takes time polynomial in n to divide n by all integers less than n. If any one of these divisions produces a zero remainder, we can conclude (in polynomial time) that n is composite. Otherwise n is not composite (and we can conclude this in polynomial time).

  4. Modify the proof of Theorem 34.15 of the text to show that the partition problem is NP-complete. Don't forget to show that the problem is in NP.

    To be consistent with the text, you may assume that an instance of the partition problem is a set of integers, rather than a set of items with integer weights.