Part 2. (12 points) Running Dijkstra's algorithm In this question, we will think about how to answer shortest path problems where we have more than just a sin gle source and destination. Answer each of the parts in English (not code or pseudocode). Each bullet point re quires at most a few sentences to answer. Answers significantly longer than required will not receive full credit (a) (3 points) You and k - 1 of your friends have all decided to meet at Odegaard for a study session. Unfor tunately you're scattered all over campus, and you'd like to start studying as soon as possible. You have a map of campus represented as the adjacency list for a weighted, directed graph (the graph has only positive edge weights), where the edge weights represent how much time it will take you to get from one way to another. In this version of UW, there are some one-way streets, which are represented in the graph as well. You have a list of the vertices representing the current locations of you and your friends. You also know which vertex corresponds to Odegaard. Figure 1 shows an example graph First, let's assume that you cannot alter the graph you have been given, and see what we can do i. Describe how to find the quickest way for each of you and your friends to arrive at Odegaard. You should say which algorithm(s) you run and any inputs you would pass into the functions described in ass Your answer should handle finding the path for each person, not just how long it will take them to get there ii. What is the big-O running time for this process in terms of k, V and |E? (b) (3 points) Now, By modifying the graph representation, we're going to discover a more efficient algorithm for this problem. Suppose we wanted to reverse every edge in the graph (i.e. an edge pointing from u to v should end up pointing from v to u) i. How long would it take to make a reversed copy of the graph? Assume that the adjacency list uses hash tables, and all inserts will take constant time. ii. What does a path from u to v in this new graph correspond to? iii. Describe an algorithm to find the quickest way for all of your friends to get to Odegaard (again you should be able to return the full route, not just how long it takes) iv. What is the big-O running time to find all of the routes? Your answer in this part should be more efficient than the previous algorithm 2 10 4 Figure 1: An example graph where k = 3 (the highlighted vertices). Odegaard library is L, and Q, F, R are other locations on campus. The shortest path from 1, 2, and 3 to L are 1-L, 2-Q-L, and 3-2-Q-L respectively (c) (1 point) Give another real-world path finding example that you could solve using the strategy of reversing edges (d) (4 points) You are in charge of routing ambulances to emergency calls. You have three ambulances in your fleet that are parked at different locations. There is an emergency and you have to dispatch the ambulance closest to the emergency to help as soon as possible. You have a map of Seattle represented as the adjacency list for a weighted, directed graph (the graph has only positive edge weights). You also have a list of vertices representing the locations of each of your ambulances and the vertex representing where the new emergency is located. You could run Dijkstra's from each of the three ambulance vertices, but since every second counts, you decide you'd like an algorithm that has better constant factors (even if you can't improve the big-O). Your goal is to modify the graph so that you only need to run Dijkstra's once. i. Add a "dummy node" (i.e. a new vertex that doesn't represent any real location) to the graph. We want to run Dijkstra's with our dummy node as the source. How should we connect it to the existing graph so Dijkstra's will still return paths for the ambulances to follow in real life, and so we only have to run Dijkstra's once? Be sure to describe both the direction and weight of any edges you add. ii. In your modified graph, once you have run Dijkstra's, how do you tell which ambulance to send? iii. How long will it take to add the dummy node and any edges you added? Assume the adjacency list is implemented as a hash table of hash tables, and you won't get any collisions when you insert. (e) (1 point) Give another real-world path finding example that you could solve using the strategy of inserting a dummy vertex. Part 2. (12 points) Running Dijkstra's algorithm In this question, we will think about how to answer shortest path problems where we have more than just a sin gle source and destination. Answer each of the parts in English (not code or pseudocode). Each bullet point re quires at most a few sentences to answer. Answers significantly longer than required will not receive full credit (a) (3 points) You and k - 1 of your friends have all decided to meet at Odegaard for a study session. Unfor tunately you're scattered all over campus, and you'd like to start studying as soon as possible. You have a map of campus represented as the adjacency list for a weighted, directed graph (the graph has only positive edge weights), where the edge weights represent how much time it will take you to get from one way to another. In this version of UW, there are some one-way streets, which are represented in the graph as well. You have a list of the vertices representing the current locations of you and your friends. You also know which vertex corresponds to Odegaard. Figure 1 shows an example graph First, let's assume that you cannot alter the graph you have been given, and see what we can do i. Describe how to find the quickest way for each of you and your friends to arrive at Odegaard. You should say which algorithm(s) you run and any inputs you would pass into the functions described in ass Your answer should handle finding the path for each person, not just how long it will take them to get there ii. What is the big-O running time for this process in terms of k, V and |E? (b) (3 points) Now, By modifying the graph representation, we're going to discover a more efficient algorithm for this problem. Suppose we wanted to reverse every edge in the graph (i.e. an edge pointing from u to v should end up pointing from v to u) i. How long would it take to make a reversed copy of the graph? Assume that the adjacency list uses hash tables, and all inserts will take constant time. ii. What does a path from u to v in this new graph correspond to? iii. Describe an algorithm to find the quickest way for all of your friends to get to Odegaard (again you should be able to return the full route, not just how long it takes) iv. What is the big-O running time to find all of the routes? Your answer in this part should be more efficient than the previous algorithm 2 10 4 Figure 1: An example graph where k = 3 (the highlighted vertices). Odegaard library is L, and Q, F, R are other locations on campus. The shortest path from 1, 2, and 3 to L are 1-L, 2-Q-L, and 3-2-Q-L respectively (c) (1 point) Give another real-world path finding example that you could solve using the strategy of reversing edges (d) (4 points) You are in charge of routing ambulances to emergency calls. You have three ambulances in your fleet that are parked at different locations. There is an emergency and you have to dispatch the ambulance closest to the emergency to help as soon as possible. You have a map of Seattle represented as the adjacency list for a weighted, directed graph (the graph has only positive edge weights). You also have a list of vertices representing the locations of each of your ambulances and the vertex representing where the new emergency is located. You could run Dijkstra's from each of the three ambulance vertices, but since every second counts, you decide you'd like an algorithm that has better constant factors (even if you can't improve the big-O). Your goal is to modify the graph so that you only need to run Dijkstra's once. i. Add a "dummy node" (i.e. a new vertex that doesn't represent any real location) to the graph. We want to run Dijkstra's with our dummy node as the source. How should we connect it to the existing graph so Dijkstra's will still return paths for the ambulances to follow in real life, and so we only have to run Dijkstra's once? Be sure to describe both the direction and weight of any edges you add. ii. In your modified graph, once you have run Dijkstra's, how do you tell which ambulance to send? iii. How long will it take to add the dummy node and any edges you added? Assume the adjacency list is implemented as a hash table of hash tables, and you won't get any collisions when you insert. (e) (1 point) Give another real-world path finding example that you could solve using the strategy of inserting a dummy vertex