11 7 18 9 15For 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.
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.
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.
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.
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.