Problem Set #5, CS 255, due May 13, 2008

final version (70 points)

(20 points) There is a First-Fit Decreasing approximation algorithm for the Bin Packing optimization problem that corresponds to the Bin Packing decision problem defined on the problems slides presented in the NP-completeness portion of class. In this algorithm, the items are considered in nonincreasing order and assigned to the oldest bin in which they fit. If they fit in no bin, a new bin is allocated.
1. How many bins are needed for the instance with 30 items, of which 6 have weight 0.51, 6 have weight 0.27, 6 have weight 0.26, and 12 have weight 0.23?
2. Show that the sum of all the weights is an integer B.
3. Show that the optimal solution of this Bin Packing instance uses only B bins.
4. What lower bound do these results give for the approximation ratio of the First-Fit Decreasing approximation algorithm for the Bin Packing problem?
(10 points) Trace the behavior of the FAST-MAX algorithm of Secction 30.2 of CRW (this is the maximization algorithm discussed in class) on the sequence (7 8 8 1 0). Assume that the processors are numbered from 0 through 24, where processor 0 corresponds to the first element of the 5 by 5 array. You needn't show the details of how the input values or the value of n are sent to each processor, or the details of how values are read from and written to shared memory.
(20 points) Both parts of this problem deal with applying the ECHO distributed algorithm to the network below. Note that any terminating execution of this algorithm will result in the sending of 14 messages -- 2 per edge. Also, recall that any terminating execution of this algorithm constructs a spanning tree for the graph that underlies the network.
```
         0---1---2
         |   |   |
         3---4---5 
```
1. Show that the spanning tree below may be constructed by the algorithm, if vertex 0 is the initiator. Specifically, give an order of the 14 messages such that sending of the messages in the given order will guarantee that the spanning tree below will be constructed.
```
         0---1---2
             |    
         3---4---5 
```
2. Show that any spanning tree for the network may be constructed, if vertex 0 is the initiator. Specifically, show that for any spanning tree, there is an order of the 14 messages such that sending of the messages in the given order will guarantee that the spanning tree will be constructed. Half credit will be given for specifying a correct order (of all 14 messages); for the other half you will need to say why the order will yield the specified spanning tree.
(20 points) Apply the probabilistic primality testing algorithm described in class, with a confidence level of 95%, to the numbers 19 and 5x, where x is the 10-bit integer whose first 5 bits are the last 5 bits in the ASCII representation of the initial of your given name and whose last 5 bits are the last 5 bits in the ASCII representation of the initial of your given name. Use as witnesses the integers in the sequence 2, 3, 5, 7, ... of primes (you may assume these are independent witnesses). Note that 5x cannot be prime.

Don't forget to turn in the last problem of Problem Set #4!