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 #8 -- Due Wed 28 July 1999 : 09.30am (Revised Date)

In class, we discussed shortest paths (SPs) and the algorithms that derive SPs from a graph specification. Using your class notes as a guide, answer the following questions. Corrections to typos, or answers to student comments, are listed below in red typeface.

Note: The graph specifications from Homeworks #5 and #6 have been used with slight modifications, to make the data structures more familiar for you.

Question 1. Write pseudocode (not Java code) for Dijkstra'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.
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 Floyd's algorithm that we discussed in class.
Question 3. Given the following digraph specification (assume directed edges only) for G = (V,E), write out the order of edges with which Dijkstra's algorithm constructs the shortest path, 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 the graph having all edges undirected.
Question 5. Repeat Question 3 for Floyd's (all pairs shortest path) instead of Dijkstra's, without regard to the start vertex. Here, you must assume that the graph is a digraph. Your answer should include each matrix for each k-value, as we did in Exam #2.
Question 6. Repeat Question 4 for Floyd's (not Kruskal's) instead of Dijkstra's (undirected graph).

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.