Assigned:
Wed 14 Oct 2009
Due:
Wed 21 Oct 2009
This assignment must be turned in on time so that I can distribute solutions. No late papers will be accepted.
Required: Do all three problems below.
Points: 20 points per problem.
Assuming that both the lists are of size n give an algorithm that finds the median salary by probing the lists O(lg n) times. For convenience, you may assume that the 2n keys are all distinct.
Generalize your algorithm to apply to the case when the lists are of different lengths, say m and n, and you need to select a key of an arbitrary rank (not necessarily the median). What worst-case running time does your algorithm achieve? Again, for convenience, you may assume that the m + n keys are all distinct.
*For those who are not familiar with professional baseball, it suffices to know for this problem that the teams in Major League Baseball are grouped into two leagues -- the American League and the National League.
Hint: As a preliminary step, you should first prove that there is never an advantage to "cross matching"; i.e., reversing the length/height ordering of skis and skiers. In other words, if h_{1} < h_{2} and λ_{1} < λ_{2}, you should argue that there is no advantage to matching h_{1} ←→ λ_{2}and h_{2} ←→ λ_{1}.