maximum element in an array: // Find a maximum element in the array A. findMax(A) findMaxHelper(A, 0, A.length) // Return the maximum element in A[left…right-1]
Questions 1. Consider the following code for finding a maximum element in an array: // Find a maximum element in the array A. findMax(A) findMaxHelper(A, 0, A.length) // Return the maximum element in A[left…right-1] findMaxHelper(A, left, right) if left == right – 1 return A[left] else { max1 = findMaxHelper(A, left, (right + left) / 2) max2 = findMaxHelper(A, (right + left) / 2, right) if max1 > max2 return max1 else return max2 } (a) (2 points) Let n be the length of the parameter A, where n = 1. Let T(n) be the run time of this algorithm. Express T(n) as a recurrence relation. Use repeated substitution (ignore floors/ceilings when calculating n/2) to determine a closed-form solution for T(n) (i.e., express T(n) as a non-recursive function of n with no summations. (b) (3 points) Use induction to prove that this code correctly returns the maximum element in the array (again, where the array is of length at least 1). 1 2. We want to prove that the following function ss sorts the first n elements of array x. void ss( int *x, int n ) { int i = 0; while( i < n-1 ) { // A // int iom = i; int j = i+1; while( j < n ) { // B // if( x[j] < x[iom] ) iom = j; j++; } swap(x[i], x[iom]); i++; } } (a) (4 points) State an appropriate loop-invariant for location B in the code and prove that it is true. (b) (4 points) State an appropriate loop-invariant for location A in the code and prove that it is true, using your invariant from B. (c) (2 points) Prove that the code sorts the first n elements of array x, using the two invariants. 3. (5 points) A room contains 6 computers. Each computer is directly connected to 0 or more of the other computers in the room. Show that there are at least two computers in the room that are directly connected to the same number of other computers. Hint: You might first try the problem assuming each computer is directly connected to 1 or more of the other computers. 4. (5 points) I want to place red, green, blue, and yellow balls into eight buckets so that no matter which four buckets I choose, one contains a red ball, another contains a green ball, a third contains a blue ball, and the final one contains a yellow ball. Each bucket might contain other balls as well. Find the least number of balls (in total) that I need to achieve this. Prove that your answer is correct (i.e., show how to do it with that number and why it can’t be done with fewer). Hint: This is not an application of the Generalized Pigeonhole Principle but it uses the same techniques. 2 5. Draw the Dictionary data structure obtained after inserting: 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 93, 97, 96 one after the other into the following initially empty structures. (a) (5 points) A Hash Table of size 11 that uses chaining (with unsorted linked-list chains, insert items at the front of the chain). Use hash function hash(k) = k mod 11. (b) (5 points) A Hash Table of size 23 that uses open addressing with double hashing. The first hash function is: hash1(k) = k mod 23. The second is: hash2(k) = 13-(k mod 13). For each key, indicate the table slots probed. (c) (5 points) A B+-Tree with M = 5 and L = 3. When nodes split, put half of the items on the left and half on the right, and put the extra item on the left if there is one. Draw the tree after every insertion that causes a split as well as the final tree. (d) (5 points) A B+-Tree with M = 100 and L = 20. Draw the tree after every insertion that causes a split as well as the final tree. 6. Professor Twiddle decides to implement AVL trees without left and right child pointers by using the same trick we used for heaps: store the tree nodes in an array so that the node stored at index i has its left child at index 2i + 1 and its right child at index 2i + 2. Brilliant! except that many of the array locations might be empty because an AVL tree may not be nearly complete. Your task is to determine if Professor Twiddle’s method is always more space efficient (for large enough AVL trees). (a) (3 points) Let N(h) be the smallest number of nodes in an AVL tree of height h. For example, N(0) = 1 and N(1) = 2. Write a recurrence relation for N(h). (b) (4 points) Solve your recurrence relation to express N(h) as a function of some Fibonacci number. (c) (3 points) At this point, you should know (using what you know about Fibonacci numbers) that if an AVL tree has n nodes then its height can be ˜ 1.44 log2 n. Approximately what size array is required by Professor Twiddle’s heap-like data structure to store an n node AVL tree in the worst case? Does Professor Twiddle’s method always save space? Why or why not? 3
