Question 2 (Roadtrip Planning, 50 points). Molly is planning a roadtrip to visit her grandfather. The road system she is travelling on is given by a directed graph G with her initial location at a vertex s and final destination a vertex t. Each edge e of G has associated to it a positive integer r(e), which is the number of daus that it will take Molly to travel along this edae. Molly wants to do some siahtseeina on this trip and so also associates another value V(e) to each edge proportional to the value to her of traversing this edge. (a) Suppose that Molly needs to arrive at her grandfather's after exactly k days. Provide an algorithm to determine the greatest total value of any path with this traversal time. For full credit, your algorithm should run in time 0(k(Vl+ |E|)) or better. 120 points0 (b) Suppose instead that Molly is allowed to spend as much time as she wants travelling, but instead wants to optimize the average value per day of travel. For any real number x, give an algorithm to determine whether or not there is a path that allows Molly to reach her grandfather with an average value per day of travel of at least x. For full credit, your algorithm should run in time O(IVlIEI). [20 points/ (c) As in part (b), assume that Molly is trying to optimize her average value. Suppose that all edge values are between 0 and 1. Give an algorithm that given an ? > 0 approximates the best average value Molly can achieve to within error at most e in time O(Vl|E| log(2/E)). [10 points [Note: For all of these algorithms we will need to make the slightly unrealistic assumption that Molly is allowed to traverse the same edge multiple times, getting the same value from it each time.] Question 2 (Roadtrip Planning, 50 points). Molly is planning a roadtrip to visit her grandfather. The road system she is travelling on is given by a directed graph G with her initial location at a vertex s and final destination a vertex t. Each edge e of G has associated to it a positive integer r(e), which is the number of daus that it will take Molly to travel along this edae. Molly wants to do some siahtseeina on this trip and so also associates another value V(e) to each edge proportional to the value to her of traversing this edge. (a) Suppose that Molly needs to arrive at her grandfather's after exactly k days. Provide an algorithm to determine the greatest total value of any path with this traversal time. For full credit, your algorithm should run in time 0(k(Vl+ |E|)) or better. 120 points0 (b) Suppose instead that Molly is allowed to spend as much time as she wants travelling, but instead wants to optimize the average value per day of travel. For any real number x, give an algorithm to determine whether or not there is a path that allows Molly to reach her grandfather with an average value per day of travel of at least x. For full credit, your algorithm should run in time O(IVlIEI). [20 points/ (c) As in part (b), assume that Molly is trying to optimize her average value. Suppose that all edge values are between 0 and 1. Give an algorithm that given an ? > 0 approximates the best average value Molly can achieve to within error at most e in time O(Vl|E| log(2/E)). [10 points [Note: For all of these algorithms we will need to make the slightly unrealistic assumption that Molly is allowed to traverse the same edge multiple times, getting the same value from it each time.]
