COP 3530, Discrete Data Structures and Algorithms, Summer 1999, Homework 7 :: UFL Florida Computer Programming Homework

Class Notes: Data Structures and Algorithms Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344 Homework #7 -- Due Wed 21 July 1999 : 09.30am (Revised Date) In class, we discussed minimum spanning trees (MSTs) and the algorithms that derive MSTs from a graph specification. Using your class notes as a guide, answer the following questions. Note: The graph specifications from Homework #5 have been used with slight modifications, to make the data structures more familiar for you. Comments in response to student questions are in red typeface. * Question 1. Write pseudocode (not Java code) for Prim's algorithm that we discussed in class. Beside each step, write the number of external I/O, memory I/O, incrementation, comparison, and other types of operations employed. Note in the above description that Prim's algorithm (for MST) is to be used, not Dijkstra's (for Shortest Path). The use of Dijkstra's was a typo...my apologies... Then, construct a work budget for each type of operation, together with a Big-Oh estimate of complexity for each of the following graph representations: (a) adjacency matrix, (b) edge list, and (c) adjacency list. * Question 2. Repeat Question 1 for Kruskal's algorithm that we discussed in class. * Question 3. Given the following graph specification (assume directed edges only) for G = (V,E), write out the order of edges with which Prim's algorithm constructs the MST, starting at vertex a. (The third value (integer) in each edge triple is its weight.) (1 point each): (a) V = {a,b,c,d,e,f}, E = {(a,b,1), (b,c,3), (a,c,2), (c,d,4), (c,e,5), (e,f,2),(b,f,3)}. (b) V = {a,b,c,d,e,f}, E = {(d,a,2), (b,c,4), (a,b,2), (e,b,3), (c,e,1), (b,d,1)}. (c) Analyze the complexity of each case ((a) and (b), above) by constructing a work budget similar to Question 1, but for the adjacency list representation only, followed by a Big-Oh estimate. (2 points total) * Question 4. Repeat Question 3 with b as the start vertex. * Question 5. Repeat Question 3 for Kruskal's instead of Prim's, without regard to the start vertex. * Question 6. Repeat Question 3 for Kruskal's instead of Prim's, using the following graph specifications, without regard to the start vertex: