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.
(b) How is the size of a problem instance measured?
(c) Give a measure of progress for your algorithm.
(d) What is the running time of your algorithm.
(e) Prove that the algorithm is correct, i.e. always produces an optimal solution.
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.
(b) How is the size of a problem instance measured?
(c) Give a measure of progress for this algorithm.
(d) Discuss the running time of the algorithm.
(e) Prove that the algorithm is correct.
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.