Suppose you are tracking objects floating in the ocean. The ocean currents can be variable, so...

Transcribed Image Text:

Suppose you are tracking objects floating in the ocean. The ocean currents can be variable, so you've modeled the system as a directed graph G, where each vertex representing a region of ocean can have multiple outgoing edges indicating possible places the current will flow next. The graph can be cyclic: it's possible for objects to repeatedly circumnavigate the world, for example. However, it's also the case that once objects enter certain regions, they can't float back to where they were before: e.g. if they wash up on a beach. It's too expensive for you to pay for detailed satellite imagery of the whole ocean, so you want to find the least number of edges you can monitor so that you can detect whenever objects make progress towards washing ashore. For example, in the following graph, it would suffice to monitor edges (x,y). (x, z). (y,a). and (z,b), since once an object passes through one of those edges it can never do so again (unlike edge (y, z), for instance). b Design a linear-time algorithm to find the smallest set of such edges, analyze its runtime, and give a short argument why it is correct. Suppose you are tracking objects floating in the ocean. The ocean currents can be variable, so you've modeled the system as a directed graph G, where each vertex representing a region of ocean can have multiple outgoing edges indicating possible places the current will flow next. The graph can be cyclic: it's possible for objects to repeatedly circumnavigate the world, for example. However, it's also the case that once objects enter certain regions, they can't float back to where they were before: e.g. if they wash up on a beach. It's too expensive for you to pay for detailed satellite imagery of the whole ocean, so you want to find the least number of edges you can monitor so that you can detect whenever objects make progress towards washing ashore. For example, in the following graph, it would suffice to monitor edges (x,y). (x, z). (y,a). and (z,b), since once an object passes through one of those edges it can never do so again (unlike edge (y, z), for instance). b Design a linear-time algorithm to find the smallest set of such edges, analyze its runtime, and give a short argument why it is correct.

Answer rating: 100% (QA)

To solve this problem we can use a variant of depthfirst search DFS algorithm to traverse the graph ... View the full answer