5 A free lunch (10 marks) In this question, we consider a robot that is moving...

Transcribed Image Text:

5 A free lunch (10 marks) In this question, we consider a robot that is moving around a single-story building with n rooms. At any point in time, the robot is only allowed to go from its current room r; to any room r; E A, where A, is a subset of the overall set of rooms. Also, once it reaches its destination room, it will have consumed some amount of power Pij and also will get to recharge at the end by some amount cij, for a net power consumption of Pij - Cij. The robot wonders if there is a "free lunch". In physics, a free lunch is a situation where one can obtain an infinite amount of energy. In our case, this would be a sequence of rooms with the same starting and ending room such that the total net power consumption (summing over the net power consumption along each trip) is negative. For the questions below, assume that the robot knows the sets A,..., An and it knows all of the pij and Cij values. (a) The main idea of this part is to show how the Floyd-Warshall algorithm can be modified in order to identify whether or not there is a free lunch; if it discovers a free lunch at any point in time, it should return "True" immediately. In more detail, suppose that if there is a free lunch, then the free lunch uses vertices in the set S = {Uk, Vk2, Uk} (where the algorithm does not know S nor t). Try to design your algorithm so that in the case that there is a free lunch, the smaller the second largest index among k, k2,..., kt, the lower the algorithm's runtime (i.e., the quicker it detects that there is a free lunch). Your modification should be structurally similar to Floyd-Warshall (i.e., have the 3 for loops). (b) Explain why your algorithm is correct. Please try to be concise. You do not need to write a formal proof. (c) Assuming that there is a free lunch, give the best runtime bound that you can for your algorithm. Please use big-O notation; your bound can depend on any of k1, k2,,kt as well as t and n (but this does not mean it needs to depend on all of them!). 5 A free lunch (10 marks) In this question, we consider a robot that is moving around a single-story building with n rooms. At any point in time, the robot is only allowed to go from its current room r; to any room r; E A, where A, is a subset of the overall set of rooms. Also, once it reaches its destination room, it will have consumed some amount of power Pij and also will get to recharge at the end by some amount cij, for a net power consumption of Pij - Cij. The robot wonders if there is a "free lunch". In physics, a free lunch is a situation where one can obtain an infinite amount of energy. In our case, this would be a sequence of rooms with the same starting and ending room such that the total net power consumption (summing over the net power consumption along each trip) is negative. For the questions below, assume that the robot knows the sets A,..., An and it knows all of the pij and Cij values. (a) The main idea of this part is to show how the Floyd-Warshall algorithm can be modified in order to identify whether or not there is a free lunch; if it discovers a free lunch at any point in time, it should return "True" immediately. In more detail, suppose that if there is a free lunch, then the free lunch uses vertices in the set S = {Uk, Vk2, Uk} (where the algorithm does not know S nor t). Try to design your algorithm so that in the case that there is a free lunch, the smaller the second largest index among k, k2,..., kt, the lower the algorithm's runtime (i.e., the quicker it detects that there is a free lunch). Your modification should be structurally similar to Floyd-Warshall (i.e., have the 3 for loops). (b) Explain why your algorithm is correct. Please try to be concise. You do not need to write a formal proof. (c) Assuming that there is a free lunch, give the best runtime bound that you can for your algorithm. Please use big-O notation; your bound can depend on any of k1, k2,,kt as well as t and n (but this does not mean it needs to depend on all of them!).