For each of these problems, you may want to show partial results while carrying
ID: 3822790 • Letter: F
Question
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.
Explanation / Answer
1 a) Since the data structure we are talking about here is a priority queue with max heap, we need to conserve the max heap property in the given array. We know the child nodes of every ith node are 2*i and 2*i+1.
Hence max_heapifying the given array to conserve the property that every parent node is greater than or equal to the child nodes would give:
(g, 90); (h,82); (a, 77); (d, 62); (k, 72); (f, 25); (c, 49); (b, 18); (i, 7); (j, 30); (e, 35)
(i) Now we need to insert a new job (l, 52)
it will be inserted at the end. it's parent node would (f,25) which is less than (l,52), hence it will get swapped. And now the heap looks like this :
(g, 90); (h,82); (a, 77); (d, 62); (k, 72); (l, 52); (c, 49); (b, 18); (i, 7); (j, 30); (e, 35); (f,25)
You can see that every parent node i is greater than or equal to the child node in the above case. Hence the total number of swaps involved is 1 and no. of comparisons are : 2. (between 25 and 52) and (between 52 and 77).
(ii) Finish and removing the top priority task means removing the task (g, 90). After removing it, to restore the property of heap in the remaining array would involvvw swapping it will 25 and then heapifying the n-1 elements excluding 90.
final heap would look like:
(h, 82); (k, 72); (a, 77); (d, 62); (e, 35); (l, 52); (c, 49); (b, 18); (i, 7); (f, 25); (j, 30)
Total number of swaps are 3 (25 and 82); (72 and 25) and (35 and 25). Total comparisons - 6.
(iii) Decreasing the priority of e to 21 would make j,30 bigger than the parent node. Hence it will get swapped. total comparison 2 and swap is 1.
(h, 82); (k, 72); (a, 77); (d, 62); (j, 30); (l, 52); (c, 49); (b, 18); (i, 7); (f, 25); (e, 21)
(iv) Removing task D means swapping it with a leaf node. We take (b, 18) as a leaf node to be the one to swap with (d, 62). Hence only 1 swap and 1 comparison is needed to heapify it back.
(h, 82); (k, 72); (a, 77); (b, 18); (j, 30); (l, 52); (c, 49); (i, 7); (f, 25); (e, 21)
(v) Increasing the priority of b to 76 would make k to swap with b. Hence one swap and two comparisons.
(h, 82); (b, 76); (a, 77); (k, 72); (j, 30); (l, 52); (c, 49); (i, 7); (f, 25); (e, 21)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.