For each of these problems, you may want to show partial results while carrying out the algorithm, either to help both of us keep track, or possibly to receive partial credit.
1. [Priority Queues]
1a) Using the initialization phase of heap-sort for a max-heap, give the initial priority queue based on priorities for the following (task, priority) pairs.
(a, 77), (b, 18), (c, 49), (d, 62), (e, 35), (f, 25), (g, 90), (h, 82), (i, 7), (j, 30), (k, 72).
1b) Show the result of each of the following operations in sequence (that is, (ii) assumes (i) has occurred). For each operation, count the number of comparisons of tasks and the number of swaps needed to restore the heap property.
[You need not show the array/hash table of tasks and the pointers to and from that structure.]
i. Insert the task (l, 52).
ii. Finish and remove the maximum priority task.
iii. Decrease the priority of task e to 21.
iv. Remove task d.
v. Increase the priority of task b to 76.
2. [Disjoint Sets] Consider the set of vertices A-P, and the relationships {(D, A), (B, E), (C, P), (I, J), (L, N), (O, D), (K, L), (L, A), (F, M), (G, M), (H, P), (L, G), (E, K)}. Show the final forest if
2a) The tree for the right element is always pointed at the left element.
2b) The smaller tree is always pointed at the larger tree, pointing right at left if of equal rank.
2c) The smaller tree is always pointed at the larger tree, and path compression is used.
In each case, give the total number of pointers followed in searching and the number of pointers added or changed during the algorithm. Then, for each forest, give (1) the maximum depth of a node, (2) the cost of searching, averaged over the 16 nodes. [Remember that a search starts at the node and runs to the root. Do not use path compression on those searches.]
3. [Hash tables] Using a hash table with 19 slots (and primary address key % 19), enter the following information for each of the following conflict resolution schemes (a)-(c). Show the final table, including any soft deletes remaining.
i. Enter the keys 2183, 1142, 1477, 1800, 2128, 3590, 3095, 2482, 3144
ii. Search for 2482, 3095, 4002
iii. Delete 1477, 3590
iv. Insert 2677
3a) Using linear reprobing.
3b) Using external chaining.
For each operation, count the number of entries looked at. For the final table, give the average cost of a successful search, and the average cost of an unsuccessful search.