4. Treasure Island [25 points] In your favorite computer game they have added a new reward...

Transcribed Image Text:

4. Treasure Island [25 points] In your favorite computer game they have added a new reward phase between rounds where you can collect gold coins that you can spend in future game rounds. In this phase you are parachuted in a clown car to a location on an island where you can start your quest to get as much treasure as possible. You have a map of the island with the locations of treasure chests and the number of gold coins that each holds. You would really like to visit all of them and collect all of the treasure, but you can't because your only way to travel between them is on roads with those "severe tire damage" strips, making them one-way and preventing you from travelling on them in the wrong direction. Instead, you will have to make do with trying to get as many gold coins as possible. All of the treasure chests are at intersections of the roads. Your map shows all of these roads and which direction they run. Once you have reached a point where there is no way to collect any more gold coins, your treasure hunt ends. Your goal is to determine how to collect the maximum possible number of gold coins you could hope for. You realize that you can think of the map as giving a directed graph G with each intersection a vertex v of G marked by an integer ≥ 0 describing the number of coins in the treasure chest at that intersection, each one-way road as a directed edge, and the location you are parachuted to as a vertex u in this graph. For this question, as usual you should analyze the running time for your algorithms, which should be efficient, but you do not have to give a full proof that your algorithms are correct for any part. Instead, you should explain why you think each works in 2-3 sentences per part. (a) Suppose that G is strongly connected. • Describe an algorithm to find the maximum number of coins you would be able to collect. • Describe how to find a route that lets you collect that number of coins. (b) Suppose that G is a DAG. Describe an algorithm to find the maximum number of gold coins you can collect. To make this more concrete, consider the example below, where the best route is: a, b, c, d, e, f, though your algorithm should work for any DAG. (Hint: you may find this part conceptually easier if you do a topological sort first!) (a, 2) (b, 1 (d, 4) (9,5) h, 5) 4) (c) Now, stitch together the last two parts and describe an algorithm to handle any directed graph. 4. Treasure Island [25 points] In your favorite computer game they have added a new reward phase between rounds where you can collect gold coins that you can spend in future game rounds. In this phase you are parachuted in a clown car to a location on an island where you can start your quest to get as much treasure as possible. You have a map of the island with the locations of treasure chests and the number of gold coins that each holds. You would really like to visit all of them and collect all of the treasure, but you can't because your only way to travel between them is on roads with those "severe tire damage" strips, making them one-way and preventing you from travelling on them in the wrong direction. Instead, you will have to make do with trying to get as many gold coins as possible. All of the treasure chests are at intersections of the roads. Your map shows all of these roads and which direction they run. Once you have reached a point where there is no way to collect any more gold coins, your treasure hunt ends. Your goal is to determine how to collect the maximum possible number of gold coins you could hope for. You realize that you can think of the map as giving a directed graph G with each intersection a vertex v of G marked by an integer ≥ 0 describing the number of coins in the treasure chest at that intersection, each one-way road as a directed edge, and the location you are parachuted to as a vertex u in this graph. For this question, as usual you should analyze the running time for your algorithms, which should be efficient, but you do not have to give a full proof that your algorithms are correct for any part. Instead, you should explain why you think each works in 2-3 sentences per part. (a) Suppose that G is strongly connected. • Describe an algorithm to find the maximum number of coins you would be able to collect. • Describe how to find a route that lets you collect that number of coins. (b) Suppose that G is a DAG. Describe an algorithm to find the maximum number of gold coins you can collect. To make this more concrete, consider the example below, where the best route is: a, b, c, d, e, f, though your algorithm should work for any DAG. (Hint: you may find this part conceptually easier if you do a topological sort first!) (a, 2) (b, 1 (d, 4) (9,5) h, 5) 4) (c) Now, stitch together the last two parts and describe an algorithm to handle any directed graph.

Answer rating: 100% (QA)

describes a problem in which you need to find the maximum number of gold coins you can collect on a treasure island The island is modeled as a directed graph where intersections are vertices and roads ... View the full answer