# Practice Final

There are ten questions, all of equal weight. This exam is open-book, open-notes: you may use the textbook, your notes, your corrected homework, and any handouts or on-line materials.
1) Consider a file which happens to be all sorted except for two or three records (position unknown) that happen to be out of place. Which of the elementary sorting methods (bubble, insertion, selection) would do best on such a file and why?

2) A priority queue is "stable" if items with equal keys come out in the order that they were inserted. Describe how to implement a stable priority queue with guaranteed logarithmic performance for the insert and remove operations.

3) Draw the top-down 2-3-4 tree that results when the keys N O W I S T H E are inserted in that order into an initially empty tree.

4) Using the hash functions h1(x) = x mod 11 and h2(x) = 1 + x mod 9, show the result of inserting the keys 31 41 59 26 53 58 97 into an initially empty table of size 11 using double hashing.

5) Draw a nondeterministic pattern matching machine for the pattern description (1+ (01 + 001))*

6) Here is a proposed algorithm for solving the Euclidean minimum spanning tree problem: "Sort the points on their x coordinates, then find the minimum spanning trees of the first half and the second half of the points, then find the shortest edge that connects them". Does it work? Justify your answer.

7) Draw the subdivision of the plane that corresponds to inserting the points (10, 15) (2, 3) (5, 6) (8, 9) into an initially empty 2D tree.

8) Give two different Huffman encoding trees for the string ABCCDD, with different heights.

9) Consider the graph on six nodes, labelled A through F, with seven (undirected) edges AB BC CD DE EC FB FA. Draw a breadth-first-search forest for this graph.

10) Show the steps carried out by the divide-and-conquer matrix multiplication algorithm (the one that takes O(nlg 3) time) when multiplying the polynomials 3x3+x2-x+9 and x3+6x-2.

Copyright (c) 1995, Edward W. Felten