1. _______ The probability that a slot with n available slots and r keys will have x keys hash to it, is modeled by (r/n)x * e (r/n)/x !, which is the _?_ distribution. (a) binomial (b) exponential (c) harmonic (d) poisson 2. _______ A graph which has 1% of its possible edges is best represented in a computer program using a(n) _?_. (a) adjacency list (b) 2-D array (c) adjacency matrix (d) inverted queue 3. _______ A graph for airline travel of US cities needs to find the cheapest connection between two cities. The best algorithm would be _?_. (a) shortest path (b) traveling salesman (c) least cost path (d) depth first search 4. _______ Given a 2-D space into non-overlapping partitions, the 3-Color Problem tries to find if it is possible to assign each partition a color (R,GB) so that any other adjacent partition has a different color. Given a space with 1,000 partitions and each partition has on average 4 adjacent partitions. What is the complexity of testing a particular color assignment vector ? (a) (n) (b) (nlnn) (c) (n2) (d) (2n) 5. _______ In FFT we used the nth roots of unity for fast polynomial multiplication. Given n is even, the value of 1 n is _?_. (a) 0 (b) 1 (c) -1 (d) the principal root (e) none correct 6. _______ If we square an 8th root of unity we obtain a(n) _?_. (a) 4th root of unity (b) another 8th root of unity (c) -1 (d) i 7. As you raise the principal nth root of unity to higher powers they begin to _?_. (a) cycle (b) approach zero (c) approach 1 (d) none correct 8. _______ A way to handle colliding to the same location does not include _?_. (a) boxing (b) folding (c) linear probing (d) rehashing (e) a&b

9. _______ The Radix Sort, which sorts alphabetically will use _?_ lists for splitting and merging. (a) 26 (b) 2 (c) 10 (d) 16 10. _______ How many times Radix sort iterates is a function of the count of _?_. (a) digits in the numbers being sorted (b) elements in the array (c) letters in the strings being sorted (d) a&c 11. _______ In the Master theorem if f(n) = n b a log that means that the amount of work at each level is _?_. (a) constant (b) increasing exponentially (c) decreasing exponentially (d) b&c 12. _______ If quicksort partition always splits 90/10 (not 50/50), then its complexity will be closest to _?_. (a) bubble sort (b) its worst case (c) average case (d) best case 13. _______ Finding the kth smallest element can be done be modifying quicksort. If were searching for the 23 smallest element in an array of 50 elements, and partition level 0 places the pivot element into index 21, then we need to find the 2nd smallest element in the right part of the partition. Assuming partition is close to 50/50, this complexity is given by the recurrence _?_. (a) T(n) = 2T( 2 n ) + n (b) T(n) = 2T( 2 n ) + lnn (c) T( 2 n ) + n (d) 2T( 2 n ) + 1 14. _______ Given an algorithm with a (n3) complexity and a computer 8 times faster, how much bigger a problem can the faster computer solve in the same time t as the slower computer? _?_ (a) 3 (b) 38 (c) 3 8 (d) 8 (e) none correct 15. _______ A genetic algorithm crossover can _?_ take of each parents encoding to produce a child. (a) never (b) always (c) sometimes (d) none correct

16. _______ The Master Theorem compares f(n), the work done in level 0 of the recursion to n b a log , which corresponds to _?_. (a) # total nodes (b) height of the recursion tree (c) # nodes at bottom level (d) none correct 17. _______ Given ordinary hashing with packing density = 80%, we expect about _?_ % of the slots to have no records hash to them. (a) 10 (b) 20 (c) 45 (d) 80 18. _______ A priority queue with an insert (enqueue) operation with complexity (lnn) is typically implemented by a _?_ data structure. (a) queue (b) stack (c) heap (d) binary tree 19. _______ How many different shapes can a binary tree with 5 nodes have? (a) 26 (b) 36 (c) 14 (d) 42 20. _______ A graph for airline travel of US cities needs to find the cheapest connection between two cities. The best algorithm would be _?_. (a) shortest path (b) traveling salesman (c) least cost path (d) depth first search

21. X is a large array of n elements, indexed a to b. The kth index (with a < k < b) has a unique property. All elements in the array have strictly decreasing keys from X[a]..X[k]; all elements have strictly increasing keys from X[k]..X[b]. X[k], then is a minimum element of X. The obvious algorithm for finding this element is to examine each element in turn while there is a decrease, and return the index just before an increase occurs. This has complexity O(n). a. Design a more efficient algorithm - using words to describe it. Do not write any code or pseudocode. b. What is its worst case complexity of your algorithm? Explain with a clear argument.

22. A large Binary Search Tree (BST) is maintained for a statistical numeric data set. The Tree, originally empty, has had insertions into it occur as data becomes available - we can assume a random order of insertions as well as no duplicate keys. The analysis of a randomly created binary search tree is well known, and discussed in class. The reason for using the BST is for fast insertions and retrievals. There is another operation which needs maximum performance: The researchers need to find the value k-th element. For example, the 25,073 element in a Tree with 33,000 elements. This operation has a worst case performance of O(n) if a traditional traversal is used. To improve the performance of this function the program designer used a standard BST node with two additional fields - lcount and rcount. The node name is BST_LR. The lcount field in a BST_LR node is an integer which holds the number of nodes in the left subtree of the node (rcount similarly handles the right subtree). a. Describe the algorithm to find the kthElement, making it as efficient as possible. b. Find the worst case complexity of the algorithm c. Discuss the average complexity. Make reasonable assumptions and state them in support of your arguments.