Problem 1.Consider the weighted graph below:

(a) Demonstrate Prim’s algorithm starting from vertex A.  Write the edges in the order they were added to the minimum spanning tree.  (3 points)

(b) Demonstrate Dijkstra’s algorithm on the graph, using vertex A as the source. Write the vertices in the order which they are marked and compute all distances at each step.(3 points)

Problem 2.(3 points)A Hamiltonian path in a graph G=(V,E) is a simple that includes every vertex in V. Design an algorithm to determine if a directed acyclic graph (DAG) G has a Hamiltonian path. Your algorithm should run in O(V+E). Provide a written description of your algorithm including why it works, pseudocode and an explanation of the running time.

Compute a topological sort and check if there is an edge between each consecutive pair of vertices in the topological order.  If each consecutive pair of vertices are connected, then every vertex in the DAG is connected, which indicates a Hamiltonian path exists.  Running time for the topological sort is O(V+E), running time for the next step is O(V) so total running time is O(V+E).

PSEUDOCODE:

HAS_HAM_PATH(G)

                1. Call DFS(G) to computer finishing time v.f for each vertex v.

2. As each vertex is finished, insert it into the front of the list

                3. Iterate each through the lists of vertices in the list

                4. If any pairs of consecutive vertices are not connected RETURN FALSE

                5. After all pairs of vertices are examined RETURN TRUE

Problem 3.  Below is a list of courses and prerequisites for a factious CS degree.

(a)  Draw a directed acyclic graph (DAG) that represents the precedence among the courses.(1 points)

(b)  Give a topological sort of the graph.(2 points)

Several correct variations

CS150 CS151 CS370 CS 351 CS221 CS325 CS222 CS425 CS375 CS 401 MATH 200 MATH 201 or

MATH 200 MATH 201 CS150 CS151 CS370 CS 351 CS221 CS325 CS222 CS425 CS375 CS 401

(c) Find an order in which all the classes can be taken.(1 point)

Again several correct variations.

(d) Determine the length of the longest path in the DAG. How did you find it? What does this represent?

(2 points total)

Algorithm to find the longest path in a DAGO(E+V)

            1) Topologically sort the graph

            2) Initialize the distances associated with vertices in the graph to 0. That is d(v)=0 for all v in G.

            3) Start with the first vertex v in the topological sort.

·         For each u in Adj[v]  set d(u) = max { d(u), d(v)+1 }

4) Repeat step 4 with the next vertex in the topological sorted order until all vertices have been examined.

The length of the longest path is 5 which corresponds to the courses( 1 point)

                CS150, CS151, CS 221, CS222, CS375, CS401.

The length of the path+1 = 5+1 = 6 represented the minimum number of terms required to complete all courses with the given prerequisites.   (Note: this is often called the Critical Path)

Problem 4.(4 pts total )Suppose you have an undirected graph G=(V,E) and you want to determine if you can assign two colors (blue and red) to the vertices such that adjacent vertices are different colors.This is the graph Two-Color problem.  If the assignment of two colors is possible, thena 2-coloring is a function C: V -> {blue, red} such that C(u) ¹ C(v) for every edge (u,v) Î E.  Note: a graph can have more than one 2-coloring.Give an O(V  + E) algorithm to determine the 2-coloring of a graph if one exists or terminate with the message that the graph is not Two-Colorable.  Assume that the input graph G=(V,E) is represented using adjacency lists.

(a) Give a verbal description of the algorithm and provide detailed pseudocode.(3 points)

There are several variations. The basic idea is to select an uncolored vertex v and set the color=color1. Then examine all of the “children” u of v in Adj[v] and color them color2.  If any of the children are the same color as there parent then a two coloring is impossible.  You next examine the adjacency lists of the children and color them color1.  This continues in a DFS or BFS fashion until all the vertices have been colored and all the edges have been examined for conflicts.  This is also equivalent to determining if a graph is bipartite.

(b) Analyze the running time.O(E+V)(1 point)

Problem 5.A region contains a number of towns connected by roads.  Each road is labeled by the average number of minutes required for a fire engine to travel to it.  Each intersection is labeled with a circle.  Suppose that you work for a city that has decided to place a fire station at location G. (While this problem is small, you want to devise a method to solve much larger problems).

(a) What algorithm would you recommend be used to find the fastest route from the fire station to each of the intersections?  Demonstrate how it would work on the example above if the fire station is placed at G.  Show the resulting routes. (2 points)

(b)  (2 points) Suppose one ”optimal” location (maybe instead of G) must be selected for the fire station such that it minimizes the distance to the farthest intersection.  Devise an algorithm to solve this problem given an arbitrary road map.  Analyze the time complexity of your algorithm when there are f possible locations for the fire station (which must be at one of the intersections) and r possible roads.(Again several possible answers).

Note: If Using a binary heap the running time would be O( f(r lgf ))  and for a Fibonacci heap O(f²lgf + r)

(c)  (2 pts)Location E is optimal for the firestation since it’s longest shortest path is 10 from E to A.  All other locations have at least one longer shortest path.

In the table below we see the lengths of the shortest distances from each intersection to another intersection.  E has the minimum max of 10.  Table not required.

EXTRA CREDIT:  2 points for explanation , 1 point run time, 1 point solve problem above best locations are C and H.   ( 4 points total possible)

( + 3 points for O(f³) algorithm )Note: If Using a binary heap the running time would be O( f(r lgf ))  and for a Fibonacci heap O(f²lgf + r)

1) Compute as in part 6 b) keeping track of the minimum distance from each potential firestation location to all other intersections.  This takes time O(f³), O(f²logf + fr) as discussed above.  Results can be stored in an fxf matrix.

2)  For each possible pair of placements of fire stations compare the distances to each other intersection, keeping track of the maximum length of the minimum path.  There are O(f²) possible pairs and it takes O(f) for the comparisons to find the max min for that combination.  The result is O(f³).

3) Combining the results from 1) and 2) we have O(f³) + O(f³) = O(f³) 

Another algorithm may give O(f⁴) running time.  (+ 2points)Note: If Using a binary heap the running time would be O( f²(r lgf ))  and for a Fibonacci heap O(f³lgf + r)

The optimal location for the two fire stations can be determined by using Dijkstra’s algorithm to calculate the shortest path lengths from each possible pair of locations to an intersection.  For each pair you can run Dijkstra algorithm on each vertex and keep track of the shortest distances. Compare the distances of to the two vertices and keep the smallest in the shortest path.  You need to record the maximum path among the shortest paths for that pair.  Repeat with all pairs of vertices.  Select the pair of locations with the smallest maximum distance to an intersection.  Runtime depends on implementation probably O(f⁴).

Best locations are H and C