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

Class Notes Data Structures and AlgorithmsSummer-C Semester 1999 - M WRF second Period CSE/E119, Section 7344 formulation 7 -- Due Wed 21 July 1999 09.30am (Revised Date)In club, we discussed minimum spanning trees (MSTs) and the algorithmic rules that derive MSTs from a interpret specification. Using your class nones as a guide, answer the avocation questions.Note The graph specifications from Home tap 5 have been used with slight modifications, to make the data structures to a greater extent familiar for you.Comments in response to student questions are in trigger-happy typeface. * interrogative 1. Write pseudocode (not Java code) for Prims algorithm that we discussed in class. Beside individually step, salve the number of external I/O, memory I/O, incrementation, comparison, and other types of operations employed. Note in the above description that Prims algorithm (for MST) is to be used, not Dijkstras (for Shortest Path). The use of Dijkstras was a typo...my apo logies... Then, construct a work budget for severally type of operation, together with a Big-Oh estimate of complexity for each of the following graph patterns (a) adjacency matrix, (b) edge list, and (c) adjacency list. * Question 2. Repeat Question 1 for Kruskals 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 Prims 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 Kruskals alternatively of Prims, without regard to the start vertex. * Question 6. Repeat Question 3 for Kruskals alternatively of Prims, using the following graph specifications, without regard to the start vertex