Problem Set #2, CS 255, due March 14, 2007

FINAL VERSION

Problems are worth 20 points unless otherwise specified; there are 80 points in all.

1. Find the asymptotic time complexity of the algorithm that constructs a uniform random permutation by repeating the entire PERMUTE-BY-SORTING algorithm until there is no duplication among the values of P. You should assume that Line 4 of the algorithm uses a comparison-based sort, and that duplicate elements cannot be found until the sort of this line is complete.
2. Consider the variant of the PERMUTE-BY-SORTING algorithm that avoids a comparison-based sort by simply inserting item A[i] into location P[i] of a new array, and then traversing this new array to collect the elements of the output array. Assuming that no two items are inserted into the same location of the new array, what is the time and space complexity of this algorithm?
Consider the slight modification of the RANDOMIZE-IN-PLACE algorithm of Section 5.3 of the text that first constructs the random sequence of indices, stores it in an array R, and then uses these indices to compute the permutation. This algorithm could be written as follows:
```
  NEW-RANDOMIZE-IN-PLACE(A)
    n <- length[A]
    for i <- 1 to n
      do R[i] = RANDOM(i,n)
    for i <- 1 to n
      do swap A[i] <-> A[R[i]]
```
Assuming without loss of generality that A[i] has the initial value i for all i, show by performing each of the steps below that NEW-RANDOMIZE-IN-PLACE produces a uniform random permutation.
1. determine how many different sequences are produced by the first for loop, and what the probability of each one is.
2. show that for each permutation of A, there is a sequence of indices that builds the permutation.
3. conclude that the mapping of index sequences to permutations is a one-to-one and onto mapping
4. conclude that each permutation has probability 1/n! of occurring
Show that the 0-1 integer-programming problem of Exercise 34.5-2 is in NP.
Consider the version of the bin packing problem for which the number of bins is fixed, the capacity of the bins is to be minimized, and the weights of the items are integers. For the decision problem version of this problem, an instance of the problem would consist of integers b and T and a set of n items each with an integer weight w(i), and the question would be whether there's an assignment of items to bins (that is, a function mapping {1,2, ..., n} to {1,2,...,b}) such that the sums of the weights of the items assigned to each bucket is at most T. So for example, for b=3 and {w(i)} is {1,2,3,4,5}, the answer is "yes" (with items 1-5 mapped to bins 1, 2, 2, 1, and 3) for T>=5, while for T< 5 the answer is "no".
Show that (the decision problem version of) this problem is NP-complete. You may assume membership in NP. You may assume the NP-completeness of any problem asserted in class to be NP-complete.
Hint: reduce from the partition problem.