CS 584 Algorithms: Design and Analysis
Fall term 2013
Solutions for Homework 2
1. In our MERGE-SORT algorithm we merged two sorted lists into one
sorted list in O(n) time. Describe an O(n log k)-time algorithm to
me
...
CS 584 Algorithms: Design and Analysis
Fall term 2013
Solutions for Homework 2
1. In our MERGE-SORT algorithm we merged two sorted lists into one
sorted list in O(n) time. Describe an O(n log k)-time algorithm to
merge k sorted lists into one sorted list, where n is the total number of
elements in all the input lists. (Hint: Use a min-heap.)
Solution:
2. In class we showed using an adversary argument that any algorithm
to compute the MAX and the MIN of a set of n distinct numbers
simultaneously using pairwise comparisons must, in the worst-case, use
at least d3n=2e ¡ 2 comparisons.
(a) Use the decision tree argument (flnding a lower bound on the number of possible responses, which is a lower bound on the number
of leaves, and using this as a bound on the height of the tree)
to develop a worst-case lower bound on the number of pairwise
comparisons.
(b) If this bound is difierent than d3n=2e ¡ 2, explain how seemingly
contradictory bounds can both be correct.
Solution:
3. Show that the second largest element can be found with n+dlog ne¡2
comparisons in the worst case.
Solution:
4. In our linear-time selection algorithm, the inputs are divided into groups
of 5. What if you used groups of 3 instead? What if used groups of 7
or larger (odd integers)?
Solution:
5. Show that 2n¡1 comparisons are necessary in the worst case to merge
two sorted lists containing n elements each.
Solution:
6. Describe a O(n) worst-case time algorithm that, given a set S of n
distinct numbers and a positive integer k • n, determines the k numbers in S that are closest to the median of S in the sorted order of S
3
(for simplicity we assume that both n and k are odd, so there is one
median).
4
[Show More]