CS5800 09F: Homework 06

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.

Instructions

1. Please review the course syllabus and make sure that you understand the course policies for grading, late homework, and academic honesty.

2. You must also write down with whom you worked on the assignment. If this changes from problem to problem, then you should write down this information separately with each problem.

Problems

Required: Do all three problems below.
Points: 20 points per problem.

1. Order statistics (review)
   You are assigned the task of finding the median salary in Major League Baseball. Fortunately for you, both the American and National Leagues* have, respectively, maintained the salaries of the players in their league in sorted order. Unfortunately for you, they do not want to release the complete lists. Each league allows you to issue probes of the form: "Give me the ith ranked salary in the list". And, of course, the more you probe the more you pay!

   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.

2. Recurrences (review)
   Solve the following recurrences. Show your work.
   1. T(n) = √nT(√n) + n
   2. T(n) = 5T(n/5) + n/(lg n)
   3. T(n) = T(n - 1) + 1/n
   4. T(n) = T(n - 2) + 2lg n
   5. T(n) = T(n/2) + T(n/4) + T(n/8) + n

3. Dynamic Progrmming
   A ski rental agency has m pairs of skis, where the length of the ith pair of skis is λ_i. There are n skiers who wish to rent skis (n ≤ m), where the height of the ith skier is h_i. Ideally, each skier should obtain a pair of skis whose length matches his or her height as closely as possible. Devise an efficient algorithm to assign skis to skiers so as to minimize the sum of the absolute differences of the height of each skier and the length of his or her skis.

   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₁ < h₂ and λ₁ < λ₂, you should argue that there is no advantage to matching h₁ ←→ λ₂and h₂ ←→ λ₁.

Switch to:

• CS5800 F09 Home Page
• Homework 5
• Homework 7