Problem 3. Improve the MBTA (2+6+4+3 = 15 points) You have been commissioned to design a new bus system that will run along Huntington Avenue. The bus system must provide service to n stops on the eastbound route. Commuters may begin their trip at any stop i and end at any other step j>i. Here are some nave ways to design the system: 1. You can have a bus run from the western-most point to the eastern-most point making all n stops. The system would be cheap because it only requires n-1 route segments for the entire system. However, a person traveling from stop i = 1 to stop j = n has to wait while the bus makes n - 1 stops. 2. You can have a special express bus from i to j for every stop i to every other stop j> i. No person will ever have to make more than one stop. However, this system requires (n) route segments and will be expensive. Using divide-and-conquer, we will find a compromise solution that uses only (nlogn) route segments, but with the property that a user can get from any stop i to any stop j> i making at most two route segments in total. That is, it should be possible to get from any i to any j> i either by taking a direct route i jor by taking two routes i m and m j. The input to your algorithm should simply be a number n, describing how many stops there are, and the output should be a list of route segments i j. For example, if the input is n = 4, the output could be the list [(12), (1-3), (2-3), (34)], which is a set of 4 route segments such that we can travel from any stop i to any stop j>i using at most two route segments. (a) For the base cases n = 1,2, design a system using at most 1 route segment. Solution: (b) For n > 2 we will use divide-and-conquer. Assume that we already put in place routes connecting the first [n/2] stops and routes connecting the last [n/2] stops so that if i and j both belong to the first half, or both belong to the second half, then we can get from i to j in at most two segmets. Show how to add O(n) additional route segments so that if i is in the first half and j is in the second half we can get from i to j making only two stops. Solution: (c) Using part (b), write (in pseudocode) a divide-and-conquer algorithm that takes as input the number of stops n and outputs the list of all the route segments used by your bus system. Solution: (d) Write the recurrence for the number of route segments your solution uses and solve it. You may use any method for solving the recurrence that we have discussed in class.