CS5800 Assignment 7 solution

Instructions:
• The assignment is due at the time and date specified. Late assignments will not be accepted.
• You must work on all the problems and write the solutions by yourself! Finding solutions to homework
problems on the web, or by asking students in and outside the course is strictly prohibited. This would be
defeat the purpose of learning by doing the assignment.
• You must submit typed solutions. You may use plain text or a word processor like Microsoft Word or LaTeX
for your submissions. You may hand-sketch and scan any diagrams that you support your answer.
• If you are not comfortable with Word or Latex, please solve these problems by hand before devoting time to
typing them. Do not waste precious time investigating typesetting up front!
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