Class Notes: COP3530

Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

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):
(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:

Note: Ask the TAs if you have questions about the homework. You must complete the homework by yourself, but you can work together on general approaches to solving the homework problems. Show your work to get full credit. Any copying will be construed as cheating.