Computer Science Graph Algorithm Design
You have been hired by the university to manage the
wireless network across campus. The network is set up as follows: there is one modem and many
routers, which need to be connected together by cables. A router can only function if there is
some path of cables (possibly through other routers) that connects it to the modem. Your job is to
establish this network and keep all the routers functioning properly. There are many cables already
in place between the routers, but they are old and malfunctioning. It is not within your budget
to replace them with new cables, and so you will need to manage this network by repairing faulty
cables. (Assume that it is possible to connect the whole network with these faulty cables, and that
all the cables can carry data in both directions.)
You think back to what you learned in 240, and remember that you can use DFS to find a tree
that connects every router to the modem. So, you run DFS from the modem (faulty cables are
edges and the routers/modem are vertices) and repair all the tree edges of the DFS tree. Good
job! We will denote this tree of now functioning cables as T .
However, since these cables are old and prone to failure, one of them might stop working at
any time! Therefore, the university wants to know how many malfunctioning cables can potentially
replace a repaired cable in case it permanently fails. To formalize this, let e be some repaired cable.
If this cable were removed, T would be split into two connected components. The modem would
be in one of these components, and all the routers in the other component would no longer be
connected to the modem! However, there may be other malfunctioning cables that connect these
two components; therefore, repairing one of those cables will reconnect the network. The university
wants to know how many such malfunctioning cables are there for each repaired cable.
Give an algorithm that computes all these counts (one for each edge in T ) in O(m) time, where
m is the total number of cables, both repaired and malfunctioning. You may assume that for a
pair of routers/modem u and v, you can determine if u is an ancestor of v in T in O(1) time.
(Hint: Recall that there are no cross edges in an undirected graph with respect to any DFS
Please include proof of correctness.
Get Help With a similar task to - Computer Science Graph Algorithm Design
Tutlance Experts offer help in a wide range of topics. Here are some of our top services:
- Math homework help
- Nursing homework help
- Statistics homework help
- Nursing coursework help
- Capstone project writing services
- Essay writers for hire
- Case study writing help
- Buy college papers online
- Buy college research papers
- College homework help
- Professional resume writing services
- Programming homework help
- Coursework writing help
- Term paper writing help
- Biology homework help
- Do my physics homework
- Dissertation data analysis help
- PhD Dissertation writing services
- Chemistry homework help
Post your project now for free and watch professional experts outbid each other in just a few minutes.