10 Pages
Unlock Document

Computer Science
CS 5800
Karl Lieberherr

CS5800 - Yaxin.Huang.HWM10- Solution Q1(Exercise 22.1-5.) Solution: (1) The algorithm for the adjacency-list: Assuming that the input of the algorithm is an array A[1..n], which contains |V| elements. Each index represents a node in the graph, and each element is a pointer to the list of nodes which is the end of edges from the node of this index. (So this adjacency-list is exactly the same as the one described in section 22.1.) The algorithm designed below will output the square of the directed graph in the form of adjacency-list. SQUARE-GRAPH-ADJ-LIST(A) let B[1..n] be a new array n = A.length for i = 1 to n adj-node-ptr = A[i] //A pointer to travel the list of //nodes adjacent to node i. while adj-node-ptr != NIL if (*adj-node-ptr) not in the adj-list of B[i] //linear search add (*adj-node-ptr) to the head of list B[i] //(*adj-node-ptr) denotes the node index adj-adj-ptr = A[(*adj-node-ptr)] //the next while-loop explores the nodes adjacent //to node (*adj-node-ptr) while adj-adj-ptr != NIL if (*adj-adj-ptr) not in the adj-list of B[i] add (*adj-adj-ptr) to the head of list B[i] adj-adj-ptr = adj-adj-ptr.next adj-node-ptr = adj-node-ptr.next return B Running time analysis: The graph has |V| nodes and |E| edges. The for loop needs to examine |V| nodes. The first while loop examines the nodes adjacent to node i and the second while loop examines the nodes adjacent to the nodes that are adjacent to node i. Therefore, each directed edge is at most examined twice. Because the insertion always happens at the head of the list, we only need O(1) time to finish the insertion. The two bold if need to do searching in the adjacency list. In the worst case, when the graph is fully connected, all together you need to search O(|V| * |E|) times. CS5800 - Yaxin.Huang.HWM10- Solution ∴ The running time of this algorithm is O(|V| * |E|) . (2) The algorithm for the adjacency-matrix: Assuming that the input of the algorithm is a matrix A[1..n, 1..n]. If there is an edge from node u to node v, then A[u,v] is 1, otherwise it is 0. SQUARE-GRAPH-ADJ-MATRIX(A,n) // 1 ... n is the indices of nodes // A[u,v] denotes there is a directed edge (u,v) in G let B[1..n, 1..n] be a new table for i = 1 to n for j = 1 to n if A[i,j] == 1 B[i,j] = 1 for k = 1 to n if A[j,k] == 1 B[i,k] = 1 return B Running time analysis: There are |V| nodes in graph G and |E| edges. The first for loop examines every node in graph G. So this for loop has to execute |V| times. The second for loop also needs to execute |V| times. If there is an edge from the adjacent node to another adjacent-adjacent nodes, then the third for loop needs to be executed. Thus, the third for loop in total needs to be executed at most |E| times. ∴ The running time is O(2|V| + |E|). Q2(Exercise 22.2-6.) Solution: CS5800 - Yaxin.Huang.HWM10- Solution Given the graph above, it can be represented by an adjacency-list as: A B C (or C B) B D E (or D E) C D E (or D E) C NIL E NIL For example we choose A as the source, then we may have these trees because the different orders of vertices in the adjacency-list: And here is one tree consisting of shortest paths and it has these edges: (A B) (B D) (A C) (C E), you can see that non of the trees produced by BFS starting from A is the tree with shortest paths to each vertices. Q3(Exercise 22.2-7.) There are two types of professional wrestlers: “babyfaces” (“good guys”) and “heels” (“bad guys”). Between any pair of professional wrestlers, there may or may not be a rivalry. Suppose we have n professional wrestlers and we have a list of r pairs of wrestlers for which there are rivalries. Give an O.n C r/-time algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce CS5800 - Yaxin.Huang.HWM10- Solution it. Solution: The rivalries between the wrestlers can be represented by an undirected graph. If there is a rivalry between wrestler u and wrestler v, then there exists an edge (u,v) in the graph G. And so this problem can be solve by doing some modifications on BFS. The input A is an array, and each index denotes a vertex. It is the same representation as the adjacency-list introduced in section 22.1. Each element in A is an object, which has the fields : color, d, π and adj. (adj is the pointer to the adjacency-list). BFS-DESIGNATION(A) n = A.length let B[1..n] be a new array //B is to store the result of the designation. //true is babyface, false is heel. for i from 1 to n A[i].color = WHITE A[i].d = ∞ A[i].π = NIL B[i] = NIL // NIL represents no designation s = the index of the node with the most out-edges //here we need θ(|V|) time to search s. A[s].color = GRAY A[s].d = 0 A[s].π = NIL B[s] = true //assign it as the babyface let Q be a new queue(empty). ENQUEUE(Q,s) while Q is nonempty u = DEQUEUE(Q) for each vertex index v in the list that A[u].adj points to: if A[v].color == WHILE A[v].color = GRAY A[v].d = A[u].d + 1 A[v].π = u if B[v] == NIL B[v] = not B[u] elseif B[v] == false if B[u] == false return false //no way to designate else if B[u] == true return false CS5800 - Yaxin.Huang.HWM10- Solution return B //B is the final designation Q4(Exercise 22.3-7.) Rewrite the procedure DFS, using a stack to eliminate recursion. Solution: The input of the algorithm below is a graph G, who has the DFS-STACK-VERSION(G) let S be a new empty stack let Q be a new empty set //here we use a set to maintain the unvisited vertices //so we don’t need coloring for each vertex u belongs to G.V u.π = NIL add u to Q time = 0 while Q is nonempty time = time + 1 if EMPTY(S) == true u = pick one vertex from Q u.d = time u.π = NIL PUSH(S, u) else v = TOP(S) //This will only return the value // of the top element if G.Adj[v] is nonempty for each vertex u belongs to G.Adj[v] kick out u from Q //need to do searching here u.d = time u.π = v PUSH(S, u) time = time + 1 else time = time + 1 v.f = time POP(V) Q5(Exercise 22.3-10.)Modify the pseudocode for depth-first search so that it prints out every edge in the directed graph G, together with its type. Show what modifications, if any, you need to make if G is undirected. Solution: CS5800 - Yaxin.Huang.HWM10- Solution DFS-directed-print-edge(G) for each vertex u belongs to G.V u.color = WHITE u.π = NIL time = 0 for each vertex u belongs to G.V if u.color == WHITE DFS-VISIT-directed-print-edge(G,u) DFS-VISIT-directed-print-edge(G,u) time = time + 1 u.d = time u.color = GRAY for each v belongs to G.Adj[u] if v.color == WHITE v.π = u print “(u,v)|tree edge “ DFS-VISIT-directed-print-edge(G,v) elseif v.color == GRAY print “(u,v)|back edge “ else // v.color == BLACK if u.d < v.d print “(u,v)|forward edge “ else print “(u,v)|cross edge” u.color = BLACK time = time + 1 u.f = time If given an undirected graph, the code in the blue box should be modified into this one: for each v belongs to G.Adj[u] if v.color == WHITE v.π = u prin
More Less

Related notes for CS 5800

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.