3. Lets consider a long, quiet country road with houses scattered very sparsely along it. (We can
picture the road as a long line segment, with an eastern endpoint and a western endpoint.)
Further, lets suppose that despite the bucolic setting, the residents of all these houses are
avid cell phone users. You want to place cell phone base stations at certain points along the
road.
Assume the country road has mile-markers: 0 at the extreme west end of the road and N at
the extreme east. Each house hi denotes the mile at which it is located. For instance, hi = k
means the i-th house is k miles from the west end of the road. Also assume that each base
station has a range of R miles. That is, if the base station is placed at t miles from the west
end, then all houses It - hil< R are covered by that base station.
Give an efficient algorithm that achieves the goal of covering all houses, using as few base
stations as possible. Prove the correctness of your algorithm.
The solution algorithm need only be in pseudocode
Answers
Answer:
Claim 1:there exists an optimal solutionOwhich puts a base station atP1.Proof.LetO={P1, . . . Pm}be any optimal solution. ClearlyP1cannot be to the right ofP1, orelseH1is not covered. Thus, the set of housesP1covers (all houses within8miles to the right ofH1)contains the set of housesP1covers. Consequently,O={P1, P2, . . . , Pm}is a feasible solution whichis optimal since it has as many base stations asO.Claim 2:letO={P1, P2, . . . Pm}be an optimal solution which containsP1, thenO={P2, . . . , Pm}is optimal for the sub-problemHcontaining houses thatP1does not cover.Proof.If there is a better solution to the sub-problemH, then that solution along withP1would befeasible (all ofHare are covered) and would be better thanO, violating the optimality ofO.Conclusion. The cost of our solution is1 + (k-1) = 1 +OPT(H) = 1 +cost(O) =cost(O) =OPT(H).The first equality follows from the induction hypothesis that our algorithm is optimal forH. The secondequality follows from Claim 2. The third follows from the definition ofOin Claim 2.If theHiare already sorted, the algorithm runs in timeO(n). If not,O(nlgn)is needed.