CSc 340 Final Examination Monday 14 May 2001 SUGGESTED ANSWERS 1. Below I give the adjacency matrix of a weighted, undirected graph. The nodes are a, b, c, d, ..., m. If there is no arc between two nodes, nothing is shown. If there is an arc between two nodes I list the weight of the arc. Note: Because the graph is undirected the matrix (should be) is symmetric. a b c d e f g h i j k l m a 1 3 4 4 b 1 2 4 5 c 2 3 3 2 d 3 4 2 4 e 4 1 1 5 f 1 1 1 5 g 1 1 1 1 h 3 1 1 3 i 4 4 4 j 3 2 2 k 1 1 4 l 1 1 2 m 4 5 2 4 5 5 1 3 4 2 4 2 Show each step as you use Prim's algorithm for finding a MINIMUM spanning tree for the graph of the above adjacency matrix. Tree Fringe(node,wt) a b(a,1),h(a,3),i(a,4),m(a,4) ab c(b,2),h(a,3),i(a,4),m(a,4) ab,bc m(c,2),h(a,3),d(c,3),j(c,3),i(a,4) ab,bc,cm g(m,1),j(m,2),l(m,2),h(a,3),d(c,3),i(a,4),k(m,4),e(m,5), f(m,5) ab,bc,cm,mg f(g,1),h(g,1),l(g,1),j(m,2),d(c,3),i(a,4),k(m,4),e(m,5) ab,bc,cm,mg h(g,1),l(g,1),k(f,1),e(f,1),j(m,2),d(c,3),i(a,4) gf ab,bc,cm,mg l(g,1),k(f,1),e(f,1),j(m,2),d(c,3),i(a,4) gf,gh ab,bc,cm,mg k(f,1),e(f,1),j(m,2),d(c,3),i(a,4) gf,gh,gl ab,bc,cm,mg e(f,1),j(m,2),d(c,3),i(a,4) gf,gh,gl,fk ab,bc,cm,mg j(m,2),d(c,3),i(a,4) gf,gh,gl,fk, fe ab,bc,cm,mg d(j,2),i(a,4) gf,gh,gl,fk, fe,mj ab,bc,cm,mg i(a,4) gf,gh,gl,fk, fe,mj,jd ab,bc,cm,mg wt of tree is sum of wts of the nodes to the left gf,gh,gl,fk, = 1 + 2 + 2 + 1 + fe,mj,jd,ai 1 + 1 + 1 + 1 + 1 + 2 + 2 + 4 = 19 2. Show each step as you use Kruskal's algorithm for finding a MAXIMUM spanning tree for the graph of the adjacency matrix in problem 1. Set of Edge Sets Edge Q (wt) a b c d e f g h i j k l m bm(5),em(5),fm(5),ai(4),am(4),bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) a bm c d e f g h i j k l em(5),fm(5),ai(4),am(4),bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) a bm,me c d f g h i j k l fm(5),ai(4),am(4),bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) a bm,me,mf c d g h i j k l ai(4),am(4),bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai bm,me,mf c d g h j k l am(4),bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf c d g h j k l bi(4),de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf c d g h j k l de(4), dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed c g h j k l dm(4),im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed c g h j k l im(4),km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed c g h j k l km(4),ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk c g h j l ah(3),cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah c g j l cd(3),cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc g j l cj(3),hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj g l hm(3), bc(2),cm(2),dj(2),jm(2),lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj g l lm(2),ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj,ml g ab(1),ef(1), ek(1),fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj,ml g fg(1),fk(1),gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj,ml,fg gh(1),gl(1),gm(1),hl(1) ai,am,bm,me,mf,ed,mk,ah,dc,cj,ml,fg wt of tree is 43 3. Show each step as you use Dijkstra's algorithm for finding a single source, shortest path tree for the graph of the adjacency matrix in problem 1, where node a is the source. Step Tree Fringe Node PriorityQ (path,d(a,node)) --------------------------------------------------------------------------- 1 a b(ab,1),h(ah,3),i(ai,4),m(am,4) 2 ab h(ah,3),c(abc,3),i(ai,4),m(am,4) 3 ab,ah c(abc,3),g(ahg,4),l(ahl,4),i(ai,4),m(am,4) 4 ab,ah,bc g(ahg,4),l(ahl,4),i(ai,4),m(am,4),d(abcd,6),j(abcj,6) 5 ab,ah,bc,hg l(ahl,4),i(ai,4),m(am,4),f(ahgf,5),d(abcd,6),j(abcj,6) 6 ab,ah,bc,hg,hl i(ai,4),m(am,4),f(ahgf,5),d(abcd,6),j(abcj,6) 7 ab,ah,bc,hg,hl, m(am,4),f(ahgf,5),d(abcd,6),j(abcj,6) ai 8 ab,ah,bc,hg,hl, f(ahgf,5),d(abcd,6),j(abcj,6),k(amk,8),e(ame,9) ai,am 9 ab,ah,bc,hg,hl, d(abcd,6),j(abcj,6),e(ahgfe,6),k(ahgfk,6) ai,am,gf 10 ab,ah,bc,hg,hl, j(abcj,6),e(ahgfe,6),k(ahgfk,6) ai,am,gf,cd 11 ab,ah,bc,hg,hl, e(ahgfe,6),k(ahgfk,6) ai,am,gf,cd,cj 12 ab,ah,bc,hg,hl, k(ahgfk,6) ai,am,gf,cd,cj,fe 13 ab,ah,bc,hg,hl, ai,am,gf,cd,cj,fe,fk Node b c d e f g h i j k l m d(a,Node) 1 3 6 6 5 4 3 4 6 6 4 4 4. Assume the adjacency matrix in problem 1 is for a directed graph. a. List the nodes in order of discovery in a depth first search of the graph, starting at node g. At any step assume the nodes are checked in alphabetical order. discovered dfs(g) g dfs(f) f dfs(e) e dfs(d) d dfs(c) c dfs(b) b dfs(a) a dfs(b) dfs(h) h dfs(a) dfs(g) dfs(l) l dfs(g) dfs(h) dfs(m) m dfs(a) dfs(b) dfs(c) dfs(d) dfs(e) dfs(f) dfs(g) dfs(h) dfs(i) i dfs(a) dfs(b) dfs(m) dfs(j) j dfs(c) dfs(d) dfs(m) dfs(k) k .... all discovered, back out..... b. List the nodes in order of discovery in a breadthwise search, starting at node g. Discovered Queue g g f, h, l, m f h, l, m, e, k h l, m, e, k, a l m, e, k, a m e, k, a, b, c, d, i, j e k, a, b, c, d, i, j k a, b, c, d, i, j a b, c, d, i, j b c, d, i, j c d, i, j d i, j i j j 5. Prove the following algorithm is correct. First explain why the form in which it is written is not useful for proving correctness, using the book's techniques. Second, put the algorithm in a form which can be proved correct, using the book's techniques. Then prove it correct. Algorithm: Binary location Input: E, an array of doubles, indexed from 1 to n, E[i]=2 X, a double such that E[1] <= X <= E[n] Output: index j such that E[j] <= X <= E[j+1] int binLoc(double E[], double X) int low,mid,high low=1 high=E.length while(high-low>1) mid=(high+low)/2 if(X>=E[mid]) low=mid else high=mid return low The algorithm has a loop. It also changes some of the values of low, mid, and high. Remark: The top level call should be binLoc(E,X,1,E.length) Preconditions: high>low, E[low]<=X<=E[high] E[i]=E[mid]) 5. result=binLoc(E,X,mid,high) else 6. result=binLoc(E,X,low,mid) 7. return result Proof: If (1) is true we have that high>=low, high-low<=1, which means that high<=low+1. Thus, by the preconditions, E[low]<=X<=E[low+1]. Assigning result=low in this case implies that E[result]<=X<=E[result+1], and the post conditions are satisfied. If (1) is false, high-low>1, which means that low<=mid<=high. If (2) is true E[mid]<=X<=E[high]. Thus the preconditions of the call to binLoc are satisfied. Thus, E[result]<=X<=E[result+1], and the postconditions are satisfied. Finally, if (2) is false, E[low]<=X<=E[mid] and the preconditions of the call to binLoc are satisfied. Thus, E[result]<=X<=E[result+1], and the postconditions are satisfied. Thus, in all situations, result satisfies the postconditions of binLoc. Note that in the above argument, the values of E[j] never change so that the pre and post conditions on E (E[j]=mid-low. But high-mid = ceiling of (high-low)/2. Thus, until high=low+1, in the worst case, we reduce the number of entries by 1/2 (in the best case by 1/2 + 1) 6. Derive upper and lower bounds for 9*ln(3)+16*ln(4)+...+n^2ln(n). The difference between the upper and lower bounds should be small, thus precluding a simple answer like 0 and n^3ln(n). I(a,b,f) stands for the definite integral of the function f from a to b, I(f) stands for the indefinite integral of f, and S(n)=9*ln(3)+16*ln(4)+...+n^2ln(n). We use the integration formulae I(2, n, x^2ln(x)) <= S(n) S(n) <= I(3, n+1, x^2ln(x)) We first find the anti-derivative of n*n*ln(n). We start by integrating by parts, with u=ln(x) and dv=x^2 I(x*x*ln(x)) = x^3ln(x)/3 - I(x^3/3 * (1/x)) = x^3ln(x)/3 - I(x^2/3) = x^3ln(x)/3 - x^3/9 Thus, n^3 (ln(n) - 1/3)/3 - 8(ln(2) - 1/3)/3 <= S(n) S(n) <= (n+1)^3 (ln(n+1)-1/3) - 9ln(3) + 3 7. Write the specification of an IntList ADT. Then write one or more additional IntList functions which give the IntList ADT the properties of a dequeue (a dequeue has the properties of both the stack and the queue) IntList cons(int element,IntList oldList) Precondition: none Postcondition: If x=cons(element, oldList) 1. x refers to a newly created list 2. first(x) = element 3. rest(x) = oldList int first(IntList list) precondition: list != nil int rest(IntList list) precondition: list !=nil IntList nil //static constant denoting the empty list Now to add functionality. As specified, cons corresponds to a stack push, first corresponds to a stack top, and rest corresponds to a stack pop. We can also think of cons as corresponding to the addition to the queue. Thus, we only need add a function for removing from the other end of the IntList precondition: oldList != nil postcondition: return a list with the last element removed IntList removeLast(IntList oldList) IntList result,fir,res,ret if(rest(oldList)==nil) result=nil else fir=first(oldList) res=rest(oldList) ret=removeLast(res) result=cons(fir,ret) return result 8. State the algorithm for Construct Heap (you can assume you have the function FixHeap). Show the steps in applying the alogrithm to constructing a heap in descending order, when the original data are x[1]=1, x[2]=2,...,x[10]=10. Note that the original data are in reverse order. preconditions: array E[] has max elements r is the root of subHeap r<=max r's children are 2r and 2r+1 postconditions: the subheap with root r satisfies the heap condition Note: Original call is constructHeap(heap,1,max) void constructHeap(Element [] heap,int rt, int max) int left, right left=2*rt right=2*rt+1 if(left<=max || right<=max) //not a leaf, which gets left alone constructHeap(heap,left,max) constructHeap(heap,right,max) fixHeap(heap,rt,max) Data Call to constructHeap 1 2 3 4 5 6 7 8 9 10 1 2 4 8 9 Fix(4) 9 4 5 10 Fix(5) 10 5 Fix(2) 10 5 2 3 6 7 Fix(3) 7 3 Fix(1) 10 9 8 1 The final result 10 9 7 8 5 6 3 1 4 2 10 / \ 9 7 / \ / \ 8 5 6 3 / \ / 1 4 2 9. Create an O(n) algorithm for finding the third largest in an array of numbers. Apply it to the array x[]={14, 2, 12, 13, 7, 8, 4, 6} Use the same tournament method as in the case of finding the second largest (have a tournament among all the data, and the winner of a second tournament among all losers to the winner of the first tournament is the second largest). Discard the first and second largest, and find the largest among all the losers to the second largest, both in the original tournament and in the tournament to find the second largest. For the above data, the tournament looks like: 14 13 / \ / \ / \ 8 13 / \ / \ 14 8 2 8 / \ / \ / \ / \ 14 13 8 6 / \ / \ / \ / \ 14 2 12 13 7 8 4 6 Discard the winner, 14, and the largest loser to 14, which is 13. Now look for max among all of the losers to 13 (8, 12). One more comparison to find 12. 10. Show each step of quicksort when applied to the data of question 9, when sorting in descending order. Recall the alogrithm: To sort from location n to location m, choose x[n] as a pivot and partition (rearrange) the array so that all elements to the left of the pivot are larger and all elements to the right of the pivot are smaller. Then quicksort all elements to the left of the pivot and quicksort all elements to the right of the pivot. The partition removes the first element, starts at the opposite end and moves a larger element into the vacancy, creating a new vacancy at the opposite end. That vacancy is filled by scanning from the other end until an item smaller than pivot is found, etc. Call (low,high) Pivot (location before, after) Data 14 2 12 13 7 8 4 6 (1,8) 14 (1,1) 14 2 12 13 7 8 4 6 (1,0) (2,8) 2 (2,8) 14 6 12 13 7 8 4 2 (2,7) 6 (2,6) 14 8 12 13 7 4 2 14 8 12 13 7 6 4 2 (2,5) 8 (2,4) 14 13 12 8 7 6 4 2 (2,3) 13 (2,2) 14 13 12 8 7 6 4 2 (2,1) 14 13 12 8 7 6 4 2 (3,3) 14 13 12 8 7 6 4 2 (5,5) 14 13 12 8 7 6 4 2 (7,7) 14 13 12 8 7 6 4 2 (9,8) 14 13 12 8 7 6 4 2