## Description

1. (30 points)

Boston MBTA has a network of bus routes. Each bus route follows a sequence of stops, and a stop

may be on multiple routes. Each bus route has a 24-hour schedule of when a bus will arrive at a particular

stop. The same schedule is followed for all days of the week.

You are given the charge to create a routing application for the Boston MBTA bus system. A customer

will primarily use your system to enter a “From” and “To” street address and an intended time of departure

from the “From” address. You must provide an itinerary that minimizes the total time for the journey.

The itinerary may include one or more bus routes with multiple stops and transition times.

To aid your application, your system is allowed to use a traditional mapping system that can provide

walking directions from the source address to a bus stop, and from a bus stop to the destination address.

The actual routing within the MBTA system must be done by your application.

Provide a description of how you will solve this problem. Your answer must include (a) a clear description of any graphs that you create (b) a statement of any technical problems you are solving (c) a

description of any algorithms you will use to solve this problem (if you are using a standard algorithm

as-is, you can simply cite it) (d) the efficiency of your solution and (e) a short justification of why your

approach is suitable and correct. Your solution must be as efficient as possible using any of the algorithms

studied in class.

Your solution must be clear, precise and detailed enough for one of your peers to implement it.

2. (30 points)

1

A dense network N of computers is working continuously on highly collaborative deep-learning problems. As part of this, the computers must broadcast a large number of messages throughout the network

to all other computers. The network engineer facilitates this message passing by overlaying a parallel,

high-speed wired network B over N, with B ⊆ N. The computers use B only to broadcast messages to

each other. The original network N is unchanged, and is used for other communication. It would have

been convenient to maintain just one network, but N is too dense and there aren’t enough high-speed

wires.

The engineer determines that B should be acyclic, because broadcast efficiency may decrease with

packets bouncing around in cycles in the network. B is chosen from edges in N based on the latency of

each edge (i.e. time required to send a message across it). The messaging quality of B is measured by the

sum of latencies of the individual wired connections (lower the sum, higher the quality). To facilitate the

message passing the network engineer correctly identifies that B should be a minimum spanning tree of N.

The complication arises from the fact that each computer’s workload, and hence its efficiency changes

arbitrarily with time. This has an effect on edge latencies, and thus the messaging quality of B may

degrade with time. Thus B must be periodically updated. As this requires physical wired connections,

this must be done manually. As such, the company has prepared the following workflow:

1. Every day at 2pm, latency measurements are used to compute a new minimum spanning tree for the

network.

2. A network engineer physically modifies the parallel wired network from how it has been, one wire at

a time, so that it aligns with this new minimum spanning tree.

(a) Provide an algorithm to implement the last step of the work flow using fewest wire changes. That

is, provide an algorithm that transforms a given spanning tree B into a given minimum spanning tree T

by a set of steps that exchange one edge of B for one edge of T. Your algorithm should output a sequence

of directions of the form “Move wire from (i,j) to (k,l)”.

(b) Prove that your algorithm terminates, works correctly and after each edge exchange, maintains a

valid broadcast network. That is, prove that your algorithm will end, and it will end only when B = T,

and all intermediate broadcast networks created between two moves are spanning trees.

(c) The supervisor is concerned that while B is being converted to T (the engineer is between moves),

the messaging quality temporarily goes down. Determine whether this will happen in your algorithm, and

justify your answer.

2