Homework 5

CS 482 - Spring 2007

Due: Wednesday, March 14

Reminder: Please include your Cornell NetID on your each part of your homework. We plan to start taking off points for those who neglect to include their NetID.

Part A

[Helping the President] George W. Shrub, President of an unspecified country, has a problem.  Vice President Linkey has been moved to an undisclosed location and President Shrub must decide which important government personnel to move to the undisclosed location with the Vice President. The undisclosed location has certain advantages; in particular, personnel in the undisclosed location can work more efficiently since no reporters are able to contact them.  On the other hand, there is an efficiency cost if person p and person q must work together while one is in the undisclosed location and the other is in the capital.  For person p, the net efficiency benefit for moving to the undisclosed location is bp.  For persons p and q, the net efficiency cost for working in different locations is dpq.

The obvious solution is to move everyone {1,..., n} to the undisclosed location achieving benefit sum bp with no efficiency loss due to different locations. Unfortunately, President Shrub and Vice President Linkey both count as important government personnel and they must remain where they are: the capital and the undisclosed location, respectively.

So which of the people should be moved?  Give a polynomial time algorithm to find a set S (subset of {1,...,n}) of personnel to move to the undisclosed location for which the sum of the efficiency benefits minus the efficiency costs is maximized.

Part B

[Cell Phone Connectivity] Do Problem 26 in Chapter 7 of the text.

Part C

[Nesting Boxes] Do Problem 31 in Chapter 7 of the text.