Program Analysis Term 1, 2015 Problem Sheet 5
1. Consider a long 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 west- ern endpoint. The residents of all these houses are mobile phone users, so you want to place mobile phone base stations at certain points along the road, so that every house is no more than four miles from one of the base stations.
(a) Giveanefficientalgorithmthatachievesthisgoal,usingasfewbasestations as possible.
Model Answer:
loc(h) is the distance of house h in miles from the eastern endpoint
hE is the most easterly house, and hW the most westerly house
B ← {loc(hE ) + 4} (B will be the set of base station locations)
let Q be a priority queue containing the houses prioritised by least loc(h)
while Q is not empty dequeue h from Q
if loc(h) > max(B) + 4
B ← B ∪ {min(loc(hW ), loc(h) + 4)} return B
(b) How is the size of a problem instance measured?
Model Answer: In terms of the number of houses on the road.
(c) Give a measure of progress for your algorithm.
Model Answer: The number of houses removed from Q. This increases by one on every iteration.
(d) What is the running time of your algorithm.
Model Answer: Setting up the priority queue takes O(n) time (assuming a heap is used). Removing each of the n houses takes log n time, so the total running time is O(n log n).
(e) Prove that the algorithm is correct, i.e. always produces an optimal solution.
Model Answer:
Proof. Suppose that the algorithm is applied to an arbitrary input.
Let A = (d1,…,dk) be the base station locations (arranged in order of in- creasing distance) as determined by the above algorithm.
Program Analysis Term 1, 2015 Let O = (o1, . . . , om) be base station locations that form an optimal solution
(also ordered in increasing distance).
If h1, . . . , hn are the houses ordered from east to west, then we say that the coverage of the first i base station locations in A is {h1,…,hj} if all of h1,…,hj, but not hj+1 are covered by locations d1,…,dj.
Similarly, we say that the coverage of the first i base station locations in O is {h1,…,hj} if all of h1,…,hj, but not hj+1 are covered by locations o1,…oj.
The coverage of a base station at distance d is the following set of all houses { h | d − 4 ≤ loc(h) ≤ d + 4 }
We prove correctness in two steps.
First we show that the solution produced by the algorithm keeps up with an optimal solution, in other words that for all i (1 ≤ i ≤ m), the coverage of the first i base station locations in A is a superset of the coverage of the first i base station locations in O. We prove this by induction. For i = 1 it is clear that d1 ≥ o1 since if o1 was any greater then the eastern most house, hE , would not be in range of o1 or any other location in O (since they are in order of increasing distance from the eastern endpoint of the road). Thus, the coverage of the base station location d1 must be as great as the coverage of the base station located at o1.
For the inductive step, we need to prove that the coverage of the first i base station locations in A is a superset of the coverage of the first i base station locations in O for an arbitrary i. From the algorithm we know that there is some house, say hj , located precisely at distance di − 4 that is not in range of di−1. By induction, we know that the coverage of the first i − 1 base station locations in A is a superset of the coverage of the first i − 1 base station loca- tions in O, so hj cannot be in range of oi−1 either. di is the greatest distance that has hj in range, so since oi is the next largest distance after oi−1 in the optimal solution, unless di ≥ oi, there would be no base station in the opti- mal solution in range of hj . Hence the extra coverage gained from including a base station located at di must be at least as good as the extra coverage gained by located one at oi, and the inductive step is complete.
Having shown that the algorithm’s solution keeps up with an arbitrary opti- mal solution, we now complete the proof by showing, by contradiction, that it is not possible that m < k. From the above inductive proof, we know that the coverage of the first m base station locations in A is as good as the cov- erage of the first m base station locations in O. But this is all of the locations in O, so these locations must cover all of the houses, because O is suppose to be an optimal solution to the problem. So the first m locations in A must cover all of the houses. But if k > m then the algorithm must have found a house location that was not covered by the base station location am because it was too far west, a contradiction.
Program Analysis Term 1, 2015
2. Your friend is working as a camp counsellor, and he is in charge of organising activities for a set of secondary-school-age campers. One of his plans is the fol- lowing mini-triathlon exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is to send the contestants out in a stag- gered fashion, via the following rule: the contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out of the pool, a second contes- tant begins swimming the 20 laps; as soon as he or she is out and starts biking, a third contestant begins swimming . . . and so on.
Each contestant has a projected swimming time (the expected time it will take him or her to complete the 20 laps), a projected biking time (the expected time it will take him or her to complete the 10 miles of bicycling), and a projected running time (the time it will take him or her to complete the 3 miles of running). Your friend wants to decide on a schedule for the triathlon: an order in which to sequence the starts of the contestants. Let’s say that the completion time of a schedule is the earliest time at which all contestants will be finished with all three legs of the triathlon, assuming they spend exactly their projected swimming, biking and running times on the three parts. (Again, note that participants can bike and run simultaneously, but at most one person can be in the pool at any time.)
(a) What’s the best order for sending people out, if one wants the whole com- petition to be over as early as possible? Give an efficient algorithm that produces a schedule whose completion time is as small as possible.
Model Answer:
let b(c) be the projected biking time of competitor c and r(c) be the projected running time of competitor c
let Q be a priority queue containing all the competitors prioritised by greatest b(c) + r(c)
while Q is not empty dequeue c from Q schedule c
(b) How is the size of a problem instance measured?
Model Answer: In terms of the total number of competitors.
(c) Give a measure of progress for this algorithm.
Model Answer: The number of elements removed from Q. This increases by one at every iteration.
(d) Discuss the running time of the algorithm.
Program Analysis Term 1, 2015
Model Answer: Setting up the priority queue takes O(n) time (assuming a heap is used). Removing each of the n competitors takes log n time, so the total running time is O(n log n).
(e) Prove that the algorithm is correct.
Model Answer:
Proof. We prove that this algorithm is produces an optimal solution using an exchange argument. We show that any arbitrarily chosen schedule can be transformed, by a series of exchanges, into the schedule produced by the algorithm, and that, crucially every exchange step produces a schedule that is no worse than the one prior to the exchange.
Consider an arbitrary schedule that is different from the one produced by the algorithm. There must be a pair of contestants that are adjacent in the arbitrary schedule, but ordered differently in the two schedules. Let c and c′ be the first such pair to appear in the arbitrary schedule. So c is scheduled before c′ in the arbitrary schedule, but not in the schedule produced by the algorithm. Consider a revision of the arbitrary schedule in which the only difference is that the positions of c and c′ are exchanged (so that c′ starts before c as in the schedule produced by the algorithm).
In this revised schedule, all contestants other than c and c′ are completely unaffected. The contestants before c and c′ are unaffected because they have been scheduled before both c and c′. The contestants after c and c′ are unaf- fected because all that prevents them from being scheduled is the time that c and c′ occupy the swimming pool, and this time is constant whether c is scheduled before c′ or not. It is possible to show that this swap will pro- duce a schedule that is at least as good as the original. This would be the case if both c and c′ in their new positions do not take longer than they did originally to complete the race.
In his/her new position, c′ will complete the race earlier than in the original arbitrary schedule, simply because he/she is now scheduled before c and will therefore start the race sooner than before. More precisely, if s(c′) is the projected swimming time of competitor c′ and b(c′) is the combined cycling and running time of c′, c′ will finish after s(c′) + b(c′) time units, as opposed to s(c) + s(c′) + b(c′) before the exchange (see Figure 1).
Furthermore, c will complete the race no later than c′ did in the original schedule. Before the exchange, c′ would have finished after s(c)+s(c′)+b(c′). After the exchange, c will finish after s(c′) + s(c) + b(c), which is less than the time it would have taken c′ to finish before the exchange (recall that b(c) < b(c′)) . Therefore, given that c and c′ together will complete the race no later than in the original schedule, and the rest of the contestants are unaffected, the new schedule must be at least as good as the original.
So we know that the revised schedule is no worse than the arbitrary sched- ule, and is closer than the arbitrary schedule to the schedule produced by
Program Analysis Term 1, 2015
the algorithm. We can repeat the above argument in such a way that the arbitrary schedule is repeatedly revised, without any reduction in quality, until it is equal to the schedule produced by the algorithm.
Figure 1: Exchange argument illustrated
Program Analysis Term 1, 2015
3. You are investigating swarm robotics, and are looking at the characteristics of a network off n mobile robots. As the robots move, they exchange information about the state of the environment. However, the communication range between any pair of robots is only 10 metres. In order to maintain a robust communication link between the robots, you have decided to limit the robot’s movements so that at all times, each robot is within 10 metres of at least n/2 of the other robots. For simplicity, you can assume that n is even. Does this guarantee that the network of robots will remain connected, that is, every robot can communicate (either directly or through other robots) with all other robot at all times?
Here’s a precise way to formulate the question as a problem about graphs.
Claim: Let G be a graph on n nodes, where n is an even number. If every node of G has a degree at least n/2 then G is connected.
Is this true or false, and justify your answer in detail.
Model Answer: The claim is true. Let G be a graph with the given properties, and suppose by way of contradiction that it is not connected. Let S be the nodes in its smallest connected component. Since there are at least two connected com- ponents, we have |S| ≤ n/2. Now, consider any node u ∈ S. Its neighbours must all lie in S, so its degree can be at most |S| − 1 ≤ n/2 − 1 < n/2. This contradicts our assumption that every node has degree at least n/2.