Midterm 2 TA Devised Review Questions Please address all bugs/corrections to Jeff Schoner (cs61b-td). More questions are to come from Billy and Chris, so check back later! Jack's 1. Provide a hashfunction that maps an Integer into a positive int in such a way that inserting the Integer/Hashcode pairs with Integer values 1 to n into a Treap in order will take O(n^2) time for n<65000 public int hashcode(){ return hashme(myInteger); // Assume that myInteger is the Integer field // associated with } // this object. public int hashme(Integer anInt){ //Fill in this method } 2. Write an iterative method that takes as input a BST and an int and prints out all elements in the BST with depth equal to the int parameter. This method should not visit any elements with depth greater than the int parameter, and should print out the elements with specified depth from right to left. static void levelOfBST(BST someBST, int someLevel){ } 3. Given the hashfunction H:ints->ints+ where H(x)=(x mod (23/27)) * 10000 for all x, draw the Treap that results from inserting the following int labels: 74,111,104,110,32,82,101,101,100 Alice's 4. Perform a series of rotations to convert the binary search tree on the left to the one on the right, or explain why it can't be done. 15 8 / \ / \ 5 34 5 40 / \ \ / / 2 8 40 2 34 \ / 11 15 / 11 5. What does the following binary heap look like after inserting 42? After removing the maximum element? +---+---+---+---+---+---+---+---+---+---+ | 51| 37| 43| 25| 33| 40| 42| 21| 5 | 28| +---+---+---+---+---+---+---+---+---+---+ Geoff's 6. The following is a Binary Tree A / \ B C / \ /\ D E F G / \ \ H I J What is printed if the tree is traversed a. inorder? b. preorder? c. postorder? 7. Suppose someone wanted to create a HashTable of rational numbers. He anticipates storing a lot of numbers, so he decides to make the hashtable initially a 2163 length array. He uses the following hash function. static int HashCode(int num, int denom) { return 49 * num + 7 * denom; } Explain why this is a very poor hashing scheme, and how you would change it. (The problem has nothing to do with whether the function is static) 8. a. Suppose you put objects into a hashtable that are comparable. That is, they satisfy the well-ordering property where for any two elements A and B, A < B, A = B, or A > B. You are given an Item K, which is in the hashtable. Describe the time complexity of finding the next element after K. b. Describe the time complexity of inserting an element into a complete heap in terms of N, the number of elements in the heap, and in terms of H, the height of the tree. Jeff's 9. You have learned that Java has a built-in type java.util.Vector. Vector can be quite handy. Java's underlying implementation consists of arrays. In a lot of ways, Vectors function very much like arrays. Why would anybody ever use an array instead of a Vector? A Vector instead of an array? Answer these questions in the context of running time, space requirements as well as programmer ease of coding. 10. Selection sort is a simple sorting algorithm. It takes an array of integers as its argument. It sorts this array in place, so has no return type. This specific implementation sorts from biggest to smallest (descending). void selectionSort(int a[]) { int biggestsIndex; int biggestsValue; int temp; for (int i = 0 ; i < a.length ; i++) { biggestsIndex = i; biggestsValue = a[i]; for (int j = i ; j < a.length ; j++) { if (a[j] > biggestsValue) { biggestsValue = a[j]; biggestsIndex = j; } } temp = a[i]; a[i] = biggestsValue; a[biggestsIndex] = temp; } } a. What is the worst case running time of this algorithm? Give a tight bound. Give your answer in terms of n, given to be the length of array a. b. For inputs of the same number of elements, is it possible one will take longer than another (in terms of the number of statements executed by the code)? c. A heap sort is another sorting algorithm. Generally, it inserts all the elements of the array to be sorted into a heap. It then removes them one by one from the heap, putting them into the same (or a different) array. What is the O() running time of this algorithm? Give a tight bound for your answer. d. Will one algorithm (heap sort or selection sort) ALWAYS be faster than the other? Which one? Why or why not? Your answer should include a reference to the definition of big O notation. 11. a. Alyssa P. Hacker and Ben Bitdiddle are working on the Site Searcher project that you all did in this class. Both have numerous synchronize keywords in their code. Ben's code has nearly three times as many lines of code synchronized as Alyssa's code. Why might this be a bad thing? b. Cy D. Fect decided not to use the wait and notify methods in his code because he says they are hard to understand. Instead, he simply uses a series of while loops that constantly check for readiness. He argues that this is faster than using wait and notify. Why is this bad? c. Cy also claims that when he tried to use wait and notify, all of his threads didn't always execute. Certain ones always got "locked out". What function could Cy have called to help elliminate this problem? Billy's 12. a/ Write a java function, bTrees(), that takes an argument n, and returns the number of binary trees with n nodes (mutually indistinguishable) that could be created. For this part, it's ok if your solution is exponential. For example: bTrees(1) = 1 bTrees(2) = 2 since when there are two nodes, there are two possible trees: o and o / \ o o bTrees(3) = 5 since: o o o o o / / \ \ / \ o o o o o o / \ / \ o o o o b/ Rewrite your solution to part a so that it takes polynomial time in the number of nodes (hint: think memoization). c/ Write a java function, tTrees(), that takes an argument n, and returns the number of 3-way trees with n nodes (mutually indistinguishable) that could be created. For this part, it's ok if your solution is exponential. For example: tTrees(1) = 1 tTrees(2) = 3 since: o o o / | \ o o o d/ Write the mathematical expression (no java code necessary) for kTrees(), which computes the number of of k-way trees with n nodes. For this part, it's ok if your solution is exponential. e/ Extra for Experts: find an algorithm for part a that runs in constant time to the number of nodes (hint: this is hard - I haven't yet solved this - but it might be possible; hint to the hint: I would try solving the recurrence relation, or perhaps find a mapping from Pascal's triangle to the triangle created from the trees combinations) Chris' 13. Use a heap to implement a priority queue. The objects held by this queue will be of Prioritized type (refer to homework 3). The heap can either hold objects of Prioritized type, or just the integer priorities (in which case the prioritized objects will have to be stored in some other manner). The HeapPriorityQueue class should define the following methods, similar to homework 3: empty, peek, insert, and remove. The underlying heap class will have to be written.