Problem 3. Improve the MBTA (2+6+4+3 = 15 points) You have been commissioned to design a...

Transcribed Image Text:

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 naïve 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. 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 naïve 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.

Answer rating: 100% (QA)

This is a problem that involves designing an efficient bus route system with divided routes to minimize wait times and expenses Lets go through each p... View the full answer