(85 pts.) Interference, Revisited In Question 2 on HW 2, we considered a set of cell phone towers T arranged on a line, where tower i had an interval (li, ri] CR indicating where its signal could be received. There, the problem was to find all towers which were subject to interference because their interval overlapped the interval of another tower. Suppose we've already computed for each tower i a list 0; of other towers overlapping it. Now imagine that you're concerned about someone hacking into a few of the towers and deliberately causing interference to jam the signals from overlapping towers. You want to determine how many towers someone would need to hack into in order to jam all the towers. (a) (30 pts.) Describe an efficient algorithm to find a subset A CT of the towers which is sufficient to jam all other towers (i.e., every tower in T overlaps at least one tower in A) and which is as small as possible. (b) (40 pts.) Prove that your algorithm is correct, i.e., every tower overlaps with a tower in your set A, and no set with this property is smaller than A. (Hint: Use the inductive approach, showing that the towers jammed by the first j towers in an optimal set B [with a suitable order] are also jammed by the first j towers in A, or equivalently, that a tower not jammed by A so far is not jammed by B so far either.) (c) (15 pts.) What is the asymptotic runtime of your algorithm? (85 pts.) Interference, Revisited In Question 2 on HW 2, we considered a set of cell phone towers T arranged on a line, where tower i had an interval (li, ri] CR indicating where its signal could be received. There, the problem was to find all towers which were subject to interference because their interval overlapped the interval of another tower. Suppose we've already computed for each tower i a list 0; of other towers overlapping it. Now imagine that you're concerned about someone hacking into a few of the towers and deliberately causing interference to jam the signals from overlapping towers. You want to determine how many towers someone would need to hack into in order to jam all the towers. (a) (30 pts.) Describe an efficient algorithm to find a subset A CT of the towers which is sufficient to jam all other towers (i.e., every tower in T overlaps at least one tower in A) and which is as small as possible. (b) (40 pts.) Prove that your algorithm is correct, i.e., every tower overlaps with a tower in your set A, and no set with this property is smaller than A. (Hint: Use the inductive approach, showing that the towers jammed by the first j towers in an optimal set B [with a suitable order] are also jammed by the first j towers in A, or equivalently, that a tower not jammed by A so far is not jammed by B so far either.) (c) (15 pts.) What is the asymptotic runtime of your algorithm