ICS 161 — Algorithms — Spring 2002 — Goodrich — First MidtermName:ID:1:2:3:4:5:total:11. (50 points). Please define each of the following terms:(a) f(n) is O(g(n).(b) depth of a node v in a tree T .(c) stable sorting algorithm.22. (50 points). Draw the heap that r esults from perfor ming a removeMin() operation on thefollowing heap:4620781159121415251633. (50 points). Draw the AVL tree resulting from inserting an item with key 46 into thefollowing AVL tree:884417 7832 5048 622411231144. (50 points). The following questions all deal with sorting.(a) Suppose that we change quick-sort to always pick the first element in the input sequenceas the pivot. State what is the worst-case running time of this version of quick-sort a nd givean example input that would require this version of quick-sort to take this much time.(b) Is merge-sort an in-place sorting algorithm? Why or why not?(c) Name an algorithm discussed in class that would have the fastest worst-case runningtime for sorting a set of n items with integer keys in the range [0, 2n− 1]? You may a ssumethat integer comparisons and array indexing both take O(1) time. (Do not give any pseudocode for this—just say which known sorting algorithm you would use to do this.) What isthe running time o f your method?55. (50 points). The LowExpectations dating service has an array W of n women that itwants to match up with an array M of n men. It assigned each man in M a unique numberbetween 0 and n − 1 (in random order). The company is then doing the matching of womento men by using following algo r ithm:for i ← 0 to n − 1 doLet a ← W [i].Scan down the array M to find the man b assigned number i.Output “a’s date is b.”end for(a) What is the worst-case running time of the dat ing service’s algorithm?(b) Briefly explain how you could do the same kind of matching the LowExpectations serviceis doing, but in worst-case optimal time. (You may use a ny algorithm studied in class a s asubroutine.) What is the running time of your
View Full Document