CSc 340 Test 3 Wednesday 18 April 2001 ---------------------------------------------------------------- SUGGESTED ANSWERS ---------------------------------------------------------------- 1. Show the nine comparisons which would occur when the tournament algorithm is applied to find the 2nd largest entry in the array x[1],...,x[8] = {8, 4, 9, 7, 3, 2, 6, 1}. In practice, of course, the algorithm does not know the entries and only compares them. 8 -- 8 -- 4 --/ \ 9 -- 9 -- 9 --- 9 Now we search for the 8 -- 8 -- 8 7 --/ / maximum among the losers 7 --/ / 3 -- 3 -- / to 9 6 ------/ 2 --/ \ / 6 -- 6 -- 6 -- 1 --/ Every pair of parallel lines stand for 1 comparison. There are 9 such comparisons. 2. Assume G=(V,E,W) is a weighted, directed graph such that the subgraph of all nodes reachable from node 1 is a tree rooted at node 1. Also assume that int A[][] is the adjacency matrix for G, where A[i][j]=0 indicates the lack of an arc from i to j, and A[i][j]>0 is the weight when there is an arc from i to j. Write a Depth First Search or a Breadth First Search algorithm for finding the weight of the tree rooted at node 1. int DFS(int A[][]) return DFS(A,1) int DFS(int A[][],int v) int sum=0, next, n=A[1].length for(next=1; next<=n; next++) if(A[v][next]>0) sum += A[v][next]+DFS(A,next) return sum int BFS(int A[][]) Queue q int sum=0, n=A[][].length, v, next enqueue(q,1) while (!empty(q)) v=front(q) dequeue(q) for(next=1; next<=n; next++) if(A[v][next]>0) sum+=A[v][next] enqueue(q,next) return sum 3. Define a 1-cycle in a directed graph as a cycle consisting of a node with an arc from the node to itself (that is, node j forms a 1-cylce if A[j][j]=1, where A is the adjacency matrix for the graph). (a) Describe an adversary argument that proves that an algorithm to determine whether a directed graph of n vertices has a 1-cycle requires at least n accesses of the adjacency matrix in the worst case. (b) Build on the argument in part (a) to describe an adversary argument that proves that an algorithm to determine whether a directed graph with n vertices is acyclic in the worst case requires at least 2n accesses of the adjacency matrix when n>=2. (a) Anytime the algorithm asks about the existence of any edge (A[i][j]>0?) respond no. The algorithm must ask about A[j][j] for each j, implying at least n comparisons. (b) Anytime the algorithm asks about the edge A[j][j] say no. The first time the algorithm asks about the edge A[j][j+1] or A[j+1][j] say yes, and when the algorithm asks about the edge in the opposite direction say no. Say no whenever the algorithm asks about any other edge. This requires at least n + 2(n-1)=3n-2>=2n queries for n>=2. 4. Below are the adjacency matrices for two directed graphs. For each determine whether the graph is a DAG. Then, if the given graph is a DAG, find a topological ordering for the graph, or if the given graph is not a DAG, list a cycle in the graph. (a) (b) 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 (a) DFS search for a cycle. 1->3->5->2->1 ==> a cycle. (b) DFS search for a cycle. x indicates a dead end 1->x 2->1->x 3->1->x ->2->1->x ->5->1->x ->2->x 4->1->x ->2->1->x ->3->1->x 2->1->x 5->1->x ->2->x 5->1->x ->2->x No cycles Now DFS search to provide topological order We have five nodes, thus start with topNum = 5 tNum TopoNum 5 0 0 0 0 0 DFS(1) 5 DFS(2) 4 4 DFS(3) 3 DFS(5) 3 2 2 DFS(4) 1 1