Problem 3. Improve the MBTA (2+6+4+3 = 15 points) You have been commissioned to design a...
Fantastic news! We've Found the answer you've been seeking!
Question:
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.
Expert Answer:
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
Related Book For
Systems Analysis And Design
ISBN: 978-1119496489
7th Edition
Authors: Alan Dennis, Barbara Wixom, Roberta M. Roth
Posted Date:
Students also viewed these programming questions
-
Find the field lines and sketch the field portrait (a) F(x, y)=(y,-2x) (b) F(x, y) = (x, x) X y (c) F(x, y) = ((2 + 2)3/2 (22 +82)3/2 ==
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
Managing Scope Changes Case Study Scope changes on a project can occur regardless of how well the project is planned or executed. Scope changes can be the result of something that was omitted during...
-
PWX Inc. has the following information for its years ended June 30: Required: Calculate the accounts receivable turnover and average collection period for 20X3 and 20X2. Comment on the trend. What...
-
A super train (proper length 100 m) travels at a speed of 0.950c as it passes through a tunnel (proper length 50.0 m). As seen by a trackside observer, is the train ever completely within the tunnel?...
-
A quantity of 2.00 ( 102 mL of 0.862 M HCl is mixed with 2.00 (102 mL of 0.431 M Ba(OH)2 in a constant-pressure calorimeter of negligible heat capacity. The initial temperature of the HCl and Ba(OH)2...
-
Report writing is very time-consuming. What should be added to a trending database to quickly interrogate vibration data yet yield a quality report?
-
You buy a share of The Ludwig Corporation stock for $21.40. You expect it to pay dividends of $1.07 $1.1449, and $1.2250 in Years 1, 2, and 3, respectively, and you expect to sell it at a price of...
-
How do these strengths enable the firm to meet customers' needs? How do these strengths differentiate the firm from its competitors? B. Weaknesses Weakness 1 Weakness 2 How do these weaknesses...
-
Street, Rhode and Close carried on business in partnership sharing profits and losses, in the ratio 5 : 4 : 3. Their draft statement of financial position as on 31 March 20X2 was as follows: Street...
-
. Our college is closing its dining hall for financial reasons, so we want to do something to help the students prepare their own food in their dorm rooms if they so choose. Your colourful ad in...
-
The currency for the country of Kuzcotopia is the Quatloo. 1 year ago, the Exchange Rate for the Quatloo to the Dollar was 12 Quatloos for one Dollar. Over the year, investment opportunities have...
-
How does emotional intelligence contribute to effective conflict resolution and negotiation strategies, enabling individuals to manage interpersonal conflicts constructively and navigate complex...
-
Compare and contrast the following strategic measurement tools used by business and human resource professionals as presented in the Required Unit Resources for this unit. Compare and contrast the...
-
What are three research objectives based upon the selected management question, research question and problem statement? Management question What are the risks of an avian flu outbreak for Perdue...
-
What impact do healthcare policymakers have on the other stakeholders (patients, providers, and payors) from access, cost, and quality of care perspectives? Include at least one example in your...
-
A black of mass 4kg is attached to a spring offer spring constant 100 N/m. One end of spring is attached to the roof. Initially the black is at rest. When released maximum speed attained by the block...
-
The packaging division of a company having considered several alternative package designs for the company's new product has finally brought down their choices to two designs of which only one has to...
-
Compare and contrast the online help resources at two different Web sites that enable you to perform the same function (e.g., make travel reservations, order books).
-
Birdie Masters is a chain of golf schools that operates throughout the southwestern United States and California.Using a combination of innovative teaching techniques and a staff of effective...
-
How would the following ERD be changed to incorporate the design decision listed next? 1 Register Student Read Record 3 Create Transcript Create/Read/Update/ Delete Record D1 Grades D2 Student...
-
(a) A car is speeding up in the negative \(x\) direction. In what direction do \(\vec{a}\) and \(\vec{v}\) point? (b) To which of the four graphs in Figures 3 . 2 and 3 . 3 does the situation...
-
The \(x\) component of the velocity of a car changes from \(-10 \mathrm{~m} / \mathrm{s}\) to \(-2.0 \mathrm{~m} / \mathrm{s}\) in \(10 \mathrm{~s}\). (a) Is the car traveling in the positive or...
-
A classmate leaves a message on your voice mail betting that you cannot throw a stone high enough so it lands on the roof of a 20 -m-high building. As you stare out of your window pondering whether...
Study smarter with the SolutionInn App