Created: Tue 06 Oct 2009
Wed 14 Oct 2009
Wed 21 Oct 2009
This assignment must be turned in on time so that I can distribute solutions. No late papers will be accepted.
- Please review the course syllabus and make sure that you understand the course policies for grading, late homework, and academic honesty.
- 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.
Required: Do all three problems below.
Points: 20 points per problem.
- 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
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.
- Recurrences (review)
Solve the following recurrences. Show your work.
- T(n) = √nT(√n) + n
- T(n) = 5T(n/5) + n/(lg n)
- T(n) = T(n - 1) + 1/n
- T(n) = T(n - 2) + 2lg n
- T(n) = T(n/2) + T(n/4) + T(n/8) + n
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 hi.
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 h1 < h2 and λ1 < λ2, you should argue that there is no advantage to matching h1 ←→ λ2and
h2 ←→ λ1.
College of Computer Science, Northeastern University
360 Huntington Avenue #340 WVH,
Boston, MA 02115
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: