University of Maryland, College Park CMSC 351 hwk9-sol-ALL ANSWERS CORRECT-GRADED A

Document Content and Description Below

CMSC351 (Kruskal) Homework 9 Due: Wednesday, July 5, 2017 Problem 1. Let G = (V; E) be a directed graph. (a) Assuming that G is represented by an adjacency matrix A[1::n; 1::n], give a Θ(n2)-time ... algorithm to compute the adjacency list representation of G. (Represent the addition of an element v to a list l using pseudocode by l l [ fvg.) Solution: This procedure runs through the adjacency matrix looking for 1’s. Clearly this is Θ(n2). for x := 1 to n do Adj[x] empty list; for x := 1 to n do for y := 1 to n do if A[x; y] = 1 then Adj[x] Adj[x] [ fyg; (b) Assuming that G is represented by an adjacency list Adj[1::n], give a Θ(n2)-time algorithm to compute the adjacency matrix of G. Solution: This procedure runs through the adjacency list and sets the 1’s in the adjacency matrix. The Θ(n2) term comes from initiallizing the adjacency matrix. for x := 1 to n do for y := 1 to n do A[x; y] := 0; for x := 1 to n do for each y in Ad [Show More]

Last updated: 1 year ago

Preview 1 out of 2 pages