22C:21: Computer Science II: Data Structures

Final. 12/20. 7:30-9:30 am

Problem 1.
I will lead you through a couple of steps for solving the following problem: Given a collection of integers (some of which may be negative), find a subset that adds up to exactly 0. For example, the collection of integers {2, -3, 11, -4, 2, 1} contains subsets {-3, 2, 1}, {2, -4, 2}, etc. that add up to exactly 0. More precisely, you are given a collection of integers stored in an int[] and have to design and code a boolean method called subsetSum that returns true if there is a subset that adds up to 0 and returns false otherwise.

This problem, like TSP, is a notoriously hard problem to solve efficiently. So, like in the case of TSP, we will try a "brute force" solution that generates all possible subsets of the collection and checks each subset for the property of adding up to 0. We will use a boolean array to track the current subset being generated. The boolean array will have the same size as the array that stores the collection. For example, if subset is the name of our boolean array, then subset[i] indicates if the ith element from the collection is in the subset or not. In the above example, the subset {-3, 2, 1} will be represented by the subset array:

	false true false false true true

	Place the first element of the collection into the subset being generated;
	Generate the rest of the subset;
	Do not place the first element of the collection into the subset being generated;
	Generate the rest of the subset;

This pseudocode can be translated into the following incomplete Java function. This function aims to generate all subsets of the elements in the subarray collection[start..collection.length-1]. This means that start should be initially passed in as 0.

	void generateSubsets(int start, int[] collection, boolean[] subset)
	{
		subset[start] = true;				// Line 1
		generateSubsets(start + 1, collection, subset);	// Line 2

		subset[start] = false;				// Line 3
		generateSubsets(start + 1, collection, subset);	// Line 4
	}	

1. This function is missing base cases and produces no output. Modify the function so that it has base cases and produces as output each subset that is generated. You don't have to rewrite the entire function; just your new code. Use the line numbers given above to indicate where your new code needs to be inserted. You may assume that there is a method called printArray that takes as arguments subset and collection and prints those elements in collection that are turned on in subset.
2. The solution to the above problem can be used, with minor modifications, to implement the function

   	boolean subsetSum(int start, int[] collection, boolean[] subset)
   

   which returns true if the given collection has a subset that adds up to 0 and returns false otherwise. You may assume that there is boolean method called checkSum that checks if the elements in collection that are turned on in subset add up to 0.

Problem 2.
This problem is on the heap data structure.

1. Consider a binary max-heap with 20 elements. It is clear that the element with highest priority can only occupy slot 0 in heapArray. However, there is some flexibility in where the element with second highest priority could go. In particular, the element with second highest priority could be in slot 1 or in slot 2. What about the element with lowest priority? Specifically, list all possible slots, in the range 0 through 19, that the element with lowest priority could be in?
   Hint: Recall that the element with lowest priority has can have no children.

2. A natural extension of a binary heap is a ternary heap in which each element has a maximum of 3 children (rather than 2). For example, the sequence

                                           50 21 10 18 12 15 13
   

   would correspond to the ternary heap

                                   50
                                 /  |  \
                                21  10  18
                              / | \
                             12 15 13
   

   For an element in slot i, write down the locations of its 3 children. For an element in slot i, write down the location of its parent.

3. Your friend tells you that her implementation of a ternary heap is much, much faster than her implementation of a binary heap. In other words, the heap operations insert, delete, and change run significantly faster on a ternary heap, than on a binary heap. Would you believe your friend (yes/no)? Explain your belief, in one sentence.

Problem 3.
Here is an edge-weighted graph.

1. Show the running of Prim's algorithm for computing an MST on this graph. Use vertex A as the source. In particular, before each iteration show the following pieces of information:
   • The vertices placed in the partial MST constructed thus far.
   • The min-heap that holds the non-tree vertices. For each node in the min-heap show its identity (i.e., name of the vertex it corresponds to) and its priority.
   Also show the MST that is constructed by the algorithm and the int[] that is returned.
2. Show the running of Dijkstra's shortest path algorithm on the above graph. Use vertex A as the source. In particular, before each iteration show the following pieces of information:
   • The vertices that are settled, i.e., the vertices whose distance-estimates from the source have become correct. For each settled vertex, show its distance.
   • The min-heap that holds the unsettled vertices. For each node in the min-heap show its identity (i.e., name of the vertex it corresponds to) and its priority.
   Also show the shortest path tree that is constructed by the algorithm and the int[] that is returned.

Problem 4.
This problem is on AVL trees. Start with an empty AVL tree and insert the items

        1, 2, 3, 4, 5, 6, 7, 8, 9, 10

1. Show the new tree, let us call this T', obtained by inserting x. Show the balances of all the nodes and indicate if T' is an AVL tree or not.
2. If T' is not an AVL tree, specify how to fix it. The choices are (i) single left rotation, (ii) single right rotation, (iii) a double rotation in which we first perform a left rotation and then a right rotation, and (iv) a double rotation in which we first perform a right rotation followed by a left rotation.
3. If T' is not an AVL tree, turn it into an AVL tree by performing the operation specified above. Show the tree after the operation has been performed and show the balances of all the nodes so that it is clear that the resulting tree is an AVL tree.