Homework 4: Due 11/28, 2005

1. Show all possible binary max-heaps with the five elements shown below.

   		11  7  18   9  15
   

   For each binary heap, show the array representation as well as how the heap can be visualized as a binary tree.

   What to submit: A list of all the heaps.

2. During our study of the mergeSort function, we encountered the merge function that takes two sorted arrays A and B and returns a sorted array that contains all the elements in A and B. The running time of the merge function is O(n) where n is the number of elements in A plus the number of elements in B.

   For this problem you will have to implement a generalization of the merge function, called kWayMerge. The kWayMerge function takes k sorted arrays and merges these into one large, sorted array. The input to the function is provided as a 2-dimensional array, with k rows (of possibly different lengths), each row sorted in increasing order. Just like the merge function had to repeatedly find the smaller of two elements to place in the output array, kWayMerge has to repeatedly pick the smallest of k elements to place in the output array. This task of picking the smallest of k elements is done most efficiently by using a min-heap.

   To ensure that your solutions are consistent, I would like you to use Lafore's implementation of the heap class. Note that this is a max-heap, but you may assume that there is a min-heap with identical functionality.

   Use the following function header.

   	int[] kWayMerge(int[][] kArrays)
   

   Thus kWayMerge returns a single array obtained by "merging" the k sorted arrays it is provided.

   What is the worst running time of your function? Express you answer in terms of n and k, where n is the total number of elements in the k arrays. What would the running time have been, had you not used a heap and simply found the smallest element at each step scanning all k candidates?
   

   What to submit: Printout of code for kWayMerge. The worst case running time of your implementation of kWayMerge. A justification for why this is the running time. The worst case running time of the alternative implementation in which heaps are not used. A justification for why this is the running time.

3. The hash function that we discussed in class is implemented in pages 561-566 in Lafore's book. The function hashFunc3 is the most efficient of the different implementation discussed. This problem asks you to experiment with this function.

   For your experiment assume that you intend to store 10,000 strings in a table. Further assume that you are comfortable with a load factor of about 10. Recall that the load factor of a hash table is the total number of items you want to store divided by the number of slots you have in the table. This means that you want to use a table with at least 1000 slots. 1009 is the smallest prime number larger than 1000. So let us use a table with 1009 slots.

   Generate 10000, length-4 strings by using letters `a' through `j' for each of the 4 slots in the string. For each such string, compute its hash value by using hashFunc3. Finally, count the number of strings that hash on to each of the 1009 slots. Report the maximum and the minimum number of strings that hash on to any slot in the table. Do you think the hash function spread the strings evenly around the table? Repeat the experiment by generating 10000, length-4 strings by using the letters `b' through `k'. Again, report the maximum and the minimum number of strings that hash on to any slot in the table. Do you think the hash function spread the strings evenly around the table?

   Note: You do not actually have to implement a hash table or store strings in a table. You just have to keep a count of how many strings hashed onto each slot.
   

   What to submit: Printout of the code for your experiment. The results for each of the two experiments. Your impressions on whether the strings are well spread by the hash function or not.

4. Consider the graph given below. For this problem, you need to show the performance of breadth first traversal, starting at vertex A. Assume that the neighbors of each vertex are examined in alphabetical order.
   In particular, I want you to show the following information.
   • The order in which vertices in the graph are discovered by breadth first traversal. You can show this by simply listing the vertices in the order in which they are discovered.
   • The breadth first traversal tree.
   
   

   What to submit: The list of vertices of the graph in the order in which they are visited by breadth first traversal and a picture of the breadth first traversal tree. There is no need to submit any code for this problem.

5. For this problem, suppose that Darth Vader has tampered with your implementation of the queue data structure. When you perform a peekFront or a remove operation, you don't get the element at the front of the queue; instead you get the element just behind the first element. Of course, if the queue has only one element, then that is what you get when you perform a peekFront or a remove.

   Using the queue so maliciously tampered by Lord Vader, perform breadth first traversal on the graph shown in Problem 4, starting first from vertex A. Again, show (i) the order in which vertices are discovered by breadth first traversal and (ii) the breadth first traversal tree.