CMSC351 (Kruskal and Morawski) Homework 3 Due: February 24
1. (a) Assume that you wish to merge two sorted arrays, each of size m, where m is even. Assume
that the first and second smallest elements are next to each other in order somewhere in
the two arrays, the third and fourth smallest elements are next to each other in order, the
fifth and sixth smallest elements are next to each other in order, etc. For example the two
arrays, each of size 6, could be
10, 20, 50, 60, 110, 120 and 30, 40, 70, 80, 90, 100
Assume that you use the standard merging algorithm, so that the algorithm does not know
of this extra condition. What is the exact number of comparisons in the worst case (as a
function of m)? Briefly justify.
Solution: 2m − 2, since when one array is finished being inserted into the sorted
array, the other array will have at least two elements left over (that go in for free).
(b) Assume that you wish to sort an array of size n, where n is a power of 2. Assume that
the first and second smallest elements are next to each other in order somewhere in array,
the third and fourth smallest elements are next to each other in order, the fifth and sixth
smallest elements are next to each other in order, etc. For example the array, of size 12,
could be
50, 60, 110, 120, 10, 20, 70, 80, 90, 100, 30, 40
Assume that you use the standard mergesort algorithm, so that the algorithm does not
know of this extra condition. Write a recurrence for the exact number of comparisons in
the worst case (as a function of n)?
Solution: Using Part (a)
S(n) = 2S(n/2) + n − 2, S(1) = 0, S(2) = 1.
2. Consider an array of size nine with the numbers in the following order 50, 30, 10, 60, 80, 40, 90, 70, 20.
(a) Form the heap using the algorithm described in the lecture. Show the heap as a tree.
Show the heap as an array. Exactly how many comparisons did heap creation use?
Solution: 90 80 50 70 30 40 10 60 20 2+2+2+4 = 10 comparisons
(b) Finish heapsort: Start with the heap created in Part (a). Show the array after each
element sifts down after heap creation. How many comparisons does each sift use? What
is the total number of comparisons after heap creation?
Solution:
80 70 50 60 30 40 10 20 90 5 comparisons
70 60 50 20 30 40 10 80 90 4 comparisons
CMSC351 (Kruskal and Morawski) Homework 3 Due: February 24
60 30 50 20 10 40 70 80 90 4 comparisons
50 30 40 20 10 60 70 80 90 2 comparisons
40 30 10 20 50 60 70 80 90 2 comparisons
30 20 10 40 50 60 70 80 90 2 comparisons
20 10 30 40 50 60 70 80 90 1 comparison
10 20 30 40 50 60 70 80 90 0 comparisons
Total of 5 + 4 + 4 + 2 + 2 + 2 + 1 + 0 = 20 comparisons, after heap creation.
3. Consider a heap (or, more precisely, a max-heap) whose size n is large (say at least 351).
(a) i. Where can the second largest element be in the heap? Briefly justify.
Solution: It must be a child of the root, since the root is the largest.
ii. How can you find it?
Solution: Compare the two children of the root.
iii. Exactly how many comparisons do you need?
Solution: One comparison.
(b) i. Where can the third largest element be in the heap? Briefly justify.
Solution: It can be a child of the root (if the other child is the second largest),
or a grandchild of the root (if its parent is the second largest).
ii. How can you find it?
Solution: Find the larger child of the root. Then find the largest of its two
children and the other child of the root.
iii. Exactly how many comparisons do you need?
Solution: Three comparisons.
(c) Assume that k < lg n.
i. Give an efficient algorithm to find the kth largest element in the heap. You should
primarily minimize the number of comparisons, and secondarily minimize the extra
space. For full credit the running time of the algorithm should be proportional to the
number of comparisons. Briefly describe your algorithm clearly in English.
Solution: Create a new heap H of size k. Put the two children of the root of the
original heap into H. Do the following step k − 1 times: Remove the root of H.
Insert the two children of this value from the original heap into H. [The first can
Page 2 of 3
CMSC351 (Kruskal and Morawski) Homework 3 Due: February 24
be done by a sift down, and the second by a sift up.] The root of H is now the
kth largest.
ii. Give the pseudo-code.
Solution: OMITTED.
iii. How many comparisons does your algorithm use? Just give the exact high order term.
Solution: 3k lg k (or 2k lg k with Floyd’s improvement for sifting).
O(k) extra space.
Page 3 of 3