.LP .tl 'CS 250'Final Exam'Spring 1998' .LP 1 and 2) Short answer questions: each worth 5 points. a) Describe the algorithm for performing FIND operations in our most efficient UNION-FIND algorithm. climb the tree to reach the root, and make everything along the path to the root a child of the root. b) Describe the failure links for the KMP algorithm if every character in the pattern is distinct. all failure links but the first point to the first position of the pattern c) Rank the following functions in terms of O notation (grouping those of the same order together): $n sup 1.5$, $2 sup n$, 3$n sup 1.5$ + 27n, nlogn, n! nlogn, {$n sup 1.5$,$n sup 1.5$+27n}, $2 sup n$, n! d) Show a graph and a pair of vertices s,t such that the path from s to t in the minimum spanning tree for G is not the shortest path from s to t. s to a and s to 2 with cost 2, while s to t has cost 3 1 3) Answer the following questions; explain your answer very briefly: These were discussed in class so answers not given. a) If I prove that an algorithm takes O($n sup 2$) worst case time, is it possible that it takes O(n) time on some inputs? b) If I prove that an algorithm takes O($n sup 2$) worst case time, is it possible that it takes O(n) time on all inputs? c) If I prove that an algorithm takes $THETA$($n sup 2$) worst case time, is it possible that it takes O(n) time on some inputs? d) If I prove that an algorithm takes $THETA$($n sup 2$) worst case time, is it possible that it takes O(n) time on all inputs? 4) In binary insertion sort, one inserts each element by performing a binary search to find the position, and then inserting the element. Analyze the worst case number of comparisons and time complexity of binary insertion sort; state the data structures used in your implementation. worst case comparisons $THETA$(nlogn): each insertion corresponds to a binary search in list of length O(n) and thus takes O(logn), giving an O(nlogn) upper bound; the $OMEGA$ bound comes from the $OMEGA$(nlogn) bound on comparison sorting. If you use an array, always inserting in the center position gives $THETA$($n sup 2$), which is also clearly an upper bound since no insertion takes more than n. 5) Describe an approximation algorithm for the bin packing problem (next fit, first fit, NIFF, or best fit will all do) and show that it never produces a solution which uses more than twice the number of bins used in the optimal solution. This can be found directly in the book. 6) A sequence "changes directions" each time it goes from increasing to decreasing or vice-versa. For example, the sequence 1 2 9 8 7 6 5 8 12 26 changes directions twice (at 9, and at 5). Design an O(n+kn) algorithm which sorts a sequence with at most k changes of direction. One can easily find the k places it changes directions in O(n) time, and divide the list into k sorted sublists. We then perform k merge operations, which take O(n) time each. 7) Show that for all n, there are depth first search trees for directed graphs on n vertices such that the number of crossedges of $G$ with respect to the tree is $OMEGA$($n sup 2$). Consider a DFS tree with root 1 and children 2 .. n and crossedges from all children with higher number to those with lower number. The number of crossedges is 1 + 2 + ... + n-2 which is $OMEGA$($n sup 2$) 8) A set of n activities meet during the day; each activity meets for a consecutive portion of the day. You are given the meeting times of each activity, and want to determine the maximum number of activities you can go to (note: you must go for the entire length of the activity). Design and analyze an algorithm to solve this problem. Create a graph with all times of the day of endpoints as vertices, and edges with weight 0 from a time of day to the next time of day, and edges with weight 1 for each activity which go from the start time to the end time. You now want to find the longest path in this dag. Longest path in a dag takes O(n+m) time; sorting the endpoints takes O(nlogn). 9) In the baseball card problem, you are given many different packs of baseball cards (the packs may have different size), and want to know whether there is a set of k packs which include every player in the set. Show that the baseball card problem is NP-complete; use the vertex cover problem to do this and make your reduction explicit! The problem is in NP, since you can show me a set of k packs, and I can check to see that they include every player. To transform from vertex cover, create one pack of cards {x,y} for each edge x - y. I will leave the proof of correctness of the reduction for you to fill in. 10) A graph is chordal if every cycle $x sub 1$,$x sub 2$,...,$x sub k$, $x sub 1$ has a chord; that is there is an edge of $G$ between some pair of vertices which are not consecutive on a cycle. Design a polynomial time algorithm to determine whether a graph is chordal, and analyze its time complexity. Hint: try to determine whether there is a chordless cycle through a path i-j-k. Although there are famous algorithms for solving this in O(n+m) time, I certainly did not expect anyone to find them! For each trio i,j,k such that there are edges from i to j and j to k but no edge from i to k, eliminate all neighbors of j except for i and k, and check whether there is a path from i to k in the remaining graph. Since there are O($n sup 3$) trios, this gives an O($n sup 3$m) algorithm.