Final. 12:00-2:00. 5/8/07

1. Given below is a recursive function that outputs to the console all permutations of a set of integers. For example, when the function recursiveGenPerms is called with n = 3, perms = (0, 1, 2), and m = 0 then the output it produces is the 6 permutations of (0, 1, 2) shown below.

   	0 1 2
   	0 2 1
   	1 0 2
   	1 2 0
   	2 1 0
   	2 0 1
   

   Here is the method recursiveGenPerms.

           public static void recursiveGenPerms(int n, int[] perms, int m)
           {
   
                   if (m == n)
                   {
                           printArray(perms, n);
                           return;
                   }
   
                   for(int i = 0; i < n-m; i++)
                   {
                           swap(perms, m, m+i);
                           recursiveGenPerms(n, perms, m+1);
                           swap(perms, m, m+i);
                   }
           }
   
   

   1. [25 points] Draw the recursion tree for a call to recursiveGenPerms with n = 3, perms = (0, 1, 2), and m = 0. As usual, represent each function call as a circle in which the three arguments to that call are clearly shown. Also, label the nodes of the recursion tree 1, 2, 3, 4, etc. showing the order in which these calls are made.
   2. [25 points] The above function works fine as long as perms contains distinct items. If we called the function with n = 3, perms = (0, 0, 1), and m = 0, we would get the output

      	0 0 1 
      	0 1 0 
      	0 0 1
      	0 1 0
      	1 0 0
      	1 0 0
      

      Notice that the output contains repeats - the first and the third permutation are identical and so are the last two. Ideally, the output should be

      	0 0 1
      	0 1 0
      	1 0 0
      

      This problem asks you to modify the function recursiveGenPerms so that it outputs only distinct permutations of a given sequence, of possibly non-distinct integers. Use the following idea: each distinct element should be placed exactly once in slot m of perms before the recursive call is made. For example, if (0, 2, 0, 1) is the input array then we should place each of 0, 1, and 2 in slot 0 exactly once and generate all permutations of the rest of the elements in the rest of the slots.

      To simplify your code you may assume that the input array will only contain integers in the range 0 through n-1, where n is the size of the array. For example, if n = 4, the input array will contain integers between 0 and 3, though it may contain multiple occurances of some of these integers. Using the idea and the assumption mentioned above it took me about 4 additional lines of code to get recursiveGenPerms working.

2. In some applications, we get edge-weighted graphs for which it is possible to implement Dijkstra's shortest path algorithm more efficiently. For example, suppose that the input graph has edge weights that are all non-negative integers. Furthermore, suppose that for some integer constant D, every pair of vertices are at most D units away from each other. For example, D may be 100, and this means that even though the graph may contain a million vertices, all vertices are fairly close (i.e., at most 100 units) from each other. We can take advantage of this situation and implement a PRIORITY QUEUE ADT, all of whose operations have constant worst case running time. Note that this critically depends on our assumption that D is a constant. To be specific, imagine a class called betterMinHeap that provides the same functionality as minHeap, but all of its methods run in O(1) time. Think about how you might implement betterMinHeap and answer the following questions.
   1. [10 points] List the data members of betterMinHeap. Describe in one sentence, the purpose of each data member.
   2. [10 points] Suppose that D = 2. Suppose that we insert the following items (in the given order) into an empty betterMinHeap object:

      	(A, 0)
      	(B, 2)
      	(C, 0)
      	(D, 0)
      	(E, 2)
      	(F, 0)
      	(G, 0)
      	(H, 1).
      

      Here each item consists of a name and a priority. Notice that all priorities are integers in the range [0, 2]. Draw a picture of the betterMinHeap object after all insert operations are completed. Clearly, indicate the values of all your data members.
   3. [15 points] Describe in 1-2 sentences how the DELETE-MIN method in the betterMinHeap class works. In one sentence, argue your implementation takes constant time.
   4. [15 points] What is the running time of Dijkstra's shortest path algorithm, if we use betterMinHeap instead of minHeap to maintain the vertices in V - S? Justify your answer in 2-3 sentences.

3. We have discussed the InOrderTreeIterator in class and you have implemented the PostOrderTreeIterator for Homework 9. Here you are asked to implement two other tree iterators.
   1. [25 points] Implement the next() method in the PreOrderTreeIterator class. Recall that a preorder tree traversal visits the root first, then the left subtree of the root, and finally the right subtree of the root. As in the case of the InOrderTreeIterator class, assume that the PreOrderTreeIterator class is a nested class inside the binary search tree class. Furthermore, assume that the data members of the PreOrderTreeIterator class are:

                 Stack<Node<E>> s = new Stack<Node<E>>();
                 int numProcessed = 0;
      

      Use the following function header for the next method:

      		public E next()
      

   2. [25 points] A level tree iterator visits the nodes of a tree level by level. The nodes in level 0 (i.e., the root) are visited first, followed by the nodes in level 1 (i.e., the children of the root), followed by nodes in level 2, etc. Within each level, the nodes are visited in a left-to-right order.

      List the data members of the LevelOrderTreeIterator class. Then implement the next() method for the LevelOrderTreeIterator class.
      (Hint: Recall breadth-first search.)

4. These two problems are about AVL trees.
   1. [30 points] Construct an example of the delete operation on AVL trees with the following characterestics:
      • A level-2 node, call it a, gets deleted.
      • Let x be the parent of a. The balance of x goes out of range because of the deletion of a.
      • Let w be the parent of x. Since a is at level 2, w is the root of the tree. After the rotations are applied to the subtree rooted at x, the balance of w goes out of range.
      Draw the following sequence of AVL trees.
      1. The tree before a is deleted.
      2. The tree after a is deleted, but before any rotations.
      3. The tree after rotations are applied to balance the subtree at x.
      4. The tree after rotations are applied to balance the subtree at w.
      For each tree show the balances of all the nodes.
   2. [20 points] Draw a tallest possible AVL with 12 nodes.