Homework 6

CS 482 - Spring 2005

Due: Friday, Apr 1 (the week after Break)

Note: Include your Cornell NetID on your each section of your homework. This simplifies the process of recording your grades.

Part A

  1. Problem 3 at the end of Chapter 8. 

    Suppose you're helping to organize a summer sports camp, and the following problem comes up. The camp is supposed to have at least one counselor who's skilled at each of the n sports covered by the camp (baseball, volleyball, and so on). They have received job applications from m potential counselors. For each of the n sports, there is some subset of the m applicants that is qualified in that sport. The question is: for a given number k < m, is it possible to hire at most k of the counselors and have at least one counselor qualified in each of the n sports? We'll call this the Efficient Recruiting Problem.

    Show that the Efficient Recruiting Problem is NP-complete.

Part B

  1. Problem 8 at the end of Chapter 8.

    Your friends' pre-school-age daughter Madison has recently learned to spell some simple words. To help encourage this, her parents got her a colorful set of refrigerator magnets featuring the letters of the alphabet (some number of copies of the letter A, some number of copies of the letter B, and so on), and the last time you saw her the two of you spent a while arranging the magnets to spell out words that she knows.

    Somehow with you and Madison, things always end up getting more elaborate than originally planned, and soon the two of you were trying to spell out words so as to use up all the magnets in the full set -- that is, picking words that she knows how to spell, so that once they were all spelled out, each magnet was participating in the spelling of exactly one of the words. (Multiple copies of words are okay here; so for example, if the set of refrigerator magnets includes two copies of each of C, A, and T, it would be okay to spell out CAT twice.)

    This turned out to be pretty difficult, and it was only later that you realized a plausible reason for this. Suppose we consider a general version of the problem of Using Up All the Refrigerator Magnets, where we replace the English alphabet by an arbitrary collection of symbols, and we model Madison's vocabulary as an arbitrary set of strings over this collection of symbols. The goal is the same as in the previous paragraph.

    Prove that Using Up All the Refrigerator Magnets is NP-complete.

Part C

  1. Problem 19 at the end of Chapter 8.

    Suppose you're acting as a consultant for the Port Authority of a small Pacific Rim nation. They're currently doing a multi-billion dollar business per year, and their revenue is constrained almost entirely by the rate at which they can unload ships that arrive in the port.

    Handling hazardous materials adds additional complexity to what is, for them, an already complicated task. Suppose a convoy of ships arrives in the morning and delivers a total of n canisters, each containing a different kind of hazardous material. Standing on the dock is a set of m trucks, each of which can hold up to k containers.

    Here are two related problems, which arise from different types of constraints that might be placed on the handling of hazardous materials. For each of the two problems, give one of the following two answers:

    1. For each canister, there is a specified subset of the trucks in which it may be safely carried. Is there a way to load all n canisters into the m trucks so that no truck is overloaded, and each container goes in a truck that is allowed to carry it?
       
    2. In this different version of the problem, any canister can be placed in any truck; however, there are certain pairs of canisters that cannot be placed together in the same truck. (The chemicals they contain may react explosively if brought into contact.) Is there a way to load all n canisters into the m trucks so that no truck is overloaded, and no two canisters are placed in the same truck when they are not supposed to be?