Questions and Answers > Worcester Polytechnic Institute - CS 584Homework 2 Solutions. CS 584 Algorithms: Design and Analysis. Solutions for Homework 2

Document Content and Description Below

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)-t... ime 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]

Last updated: 1 year ago

Preview 1 out of 4 pages