You're helping to organize a class on campus that has decided to give all its students...

Transcribed Image Text:

You're helping to organize a class on campus that has decided to give all its students wireless laptops for the semester. Thus there is a collection of n wireless laptops; there is also have a collection of n wireless access points, to which a laptop can connect when it is in range. The laptops are currently scattered across campus; laptop & is within range of a set S, of access points. We will assume that each laptop is within range of at least one access point (so the sets Se are nonempty); we will also assume that every access point p has at least one laptop within range of it. To make sure that all the wireless connectivity software is working correctly, you need to try having laptops make contact with access points in such a way that each laptop and each access point is involved in at least one connection. Thus we will say that a test set T is a collection of ordered pairs of the form (e, p), for a laptop & and access point p, with the properties that (i) If (e. p) e T, then & is within range of p (i.e., pe S₁). (ii) Each laptop appears in at least one ordered pair in T. (iii) Each access point appears in at least one ordered pair in T. This way, by trying out all the connections specified by the pairs in T, we can be sure that each laptop and each access point have correctly functioning software. The problem is: Given the sets S, for each laptop (i.e., which laptops are within range of which access points), and a number k, decide whether there is a test set of size at most k. Example. Suppose that n= 3; laptop 1 is within range of access points 1 and 2; laptop 2 is within range of access point 2; and laptop 3 is within range of access points 2 and 3. Then the set of pairs (laptop 1, access point 1), (laptop 2, access point 2), (laptop 3, access point 3) would form a test set of size 3. (a) Give an example of an instance of this problem for which there is no test set of size n. (Recall that we assume each laptop is within range of at least one access point, and each access point p has at least one laptop within range of it.) (b) Give a polynomial-time algorithm that takes the input to an instance of this problem (including the parameter k) and decides whether there is a test set of size at most k. You're helping to organize a class on campus that has decided to give all its students wireless laptops for the semester. Thus there is a collection of n wireless laptops; there is also have a collection of n wireless access points, to which a laptop can connect when it is in range. The laptops are currently scattered across campus; laptop & is within range of a set S, of access points. We will assume that each laptop is within range of at least one access point (so the sets Se are nonempty); we will also assume that every access point p has at least one laptop within range of it. To make sure that all the wireless connectivity software is working correctly, you need to try having laptops make contact with access points in such a way that each laptop and each access point is involved in at least one connection. Thus we will say that a test set T is a collection of ordered pairs of the form (e, p), for a laptop & and access point p, with the properties that (i) If (e. p) e T, then & is within range of p (i.e., pe S₁). (ii) Each laptop appears in at least one ordered pair in T. (iii) Each access point appears in at least one ordered pair in T. This way, by trying out all the connections specified by the pairs in T, we can be sure that each laptop and each access point have correctly functioning software. The problem is: Given the sets S, for each laptop (i.e., which laptops are within range of which access points), and a number k, decide whether there is a test set of size at most k. Example. Suppose that n= 3; laptop 1 is within range of access points 1 and 2; laptop 2 is within range of access point 2; and laptop 3 is within range of access points 2 and 3. Then the set of pairs (laptop 1, access point 1), (laptop 2, access point 2), (laptop 3, access point 3) would form a test set of size 3. (a) Give an example of an instance of this problem for which there is no test set of size n. (Recall that we assume each laptop is within range of at least one access point, and each access point p has at least one laptop within range of it.) (b) Give a polynomial-time algorithm that takes the input to an instance of this problem (including the parameter k) and decides whether there is a test set of size at most k.

Answer rating: 100% (QA)

Solution a To create an instance where there is no test set of size n we can set up a scenario where ... View the full answer