Homework 10 (Last One!)

CS 482 - Spring 2007

Due: Wednesday, May 2

Part A

[Cost Sharing] Do Problem 5 in Chapter 13 of the text. [Hint: It helps to consider the random variable X(i,k) = the cost town i pays for the k^th link.]

Part B

[Genome Mapping] Do Problem 6 in Chapter 13 of the text.

Part C

1. [One-Pass Auction] Do Problem 9 in Chapter 13 of the text.
    
2. [Updating the Bid] Do Problem 10 in Chapter 13 of the text.