- Consider the following game. You are given a board consisting of
3 rows and n columns of squares, where each square
(i,j) has an associated numerical value
V[i,j]. A 3 by 6 board is shown below.
You are also given a bag of n pebbles.
These n pebbles are to
be placed on the board subject to the following rules:
- each column must contain exactly one pebble, and
- pebbles in adjacent columns must not be in the same row.
For example, the following pebble placement is legal
while the following pebble placement is not.
The value of a pebble placement is equal to the sum
of the associated square values covered by the pebbles.
For example, the value of the legal pebble placement given
above is 10 + 98 + 86 + 68 + 16 + 53 = 331.
Devise an efficient algorithm for this game which maximizes
the value of a legal pebble placement. Given a 3 by n matrix
V[i,j], your algorithm should output both the maximum
value of any legal pebble placement as well as the corresponding positions
of the n pebbles. Analyze the running time and space requirements
of your algorithm, and argue that it is correct.
- Problem 15-4. You may include a penalty on the last line as well,
if you wish. However, any such solution can be easily modified to
solve the problem as stated. (If you have a solution which
includes a ``last line penalty,'' stop by my office, and I'll give
you a hint.)
- Suppose that you are the curator of a large zoo. You have just
received a grant of $m to purchase new animals at an auction
you will be attending in Africa. There will be an essentially
unlimited supply of n different types of animals, where each
animal of type i has an associated cost
ci. In order to obtain the
best possible
selection of animals for your zoo, you have assigned a value
vi to each animal type, where
vi may be quite different than
ci. (For instance, even though
panda bears are
quite rare and thus expensive, if your zoo already has quite a few
panda bears, you might associate a relatively low value to them.)
Using a business model, you have determined that the best selection of
animals will correspond to that selection which maximizes your
perceived profit (total value minus total cost); in other words,
you wish to maximize the sum of the profits associated with the animals
purchased.
Devise an efficient algorithm to select your purchases in this manner.
You may assume that m is a positive integer and that
ci and
vi are positive
integers for all i. Be sure to analyze the running time and
space requirements of your algorithm.
- A ski rental agency has m pairs of skis,
where the length of the i-th pair of skis is
li. There are n
skiers who wish to rent skis (n < m),
where the height of the i-th
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
l1 <
l2,
you should argue that there is no reason to match
h1 --
l2
and
h2 --
l1.
- Prof. Curly is planning a cross-country
road-trip from Boston to Seattle on Interstate 90,
and he needs to
rent a car. His first inclination was to call up the various car
rental agencies to find the best price for renting a vehicle from
Boston to Seattle, but he has learned, much to his dismay, that this
may not be an optimal strategy. Due to the plethora of car rental
agencies and the various price wars among them, it might actually be
cheaper to rent one car from Boston to Cleveland with Hertz,
followed by a second car from Cleveland to Chicago with Avis,
and so on, than to rent any single car from Boston to Seattle.
Prof. Curly is not opposed to stopping in a major city along
Interstate 90 to change rental cars; however,
he does not wish to
backtrack, due to time contraints. (In other words, a trip from
Boston to Chicago, Chicago to Cleveland, and Cleveland to Seattle is
out of the question.) Prof. Curly has selected
n major cities along Interstate 90
and ordered them from East to West, where City 1 is
Boston and City n is Seattle.
He has constructed a table T[i,j]
which for all i < j
contains the cost of the cheapest single rental
car from City i to City j.
Prof. Curly wants to travel as cheaply
as possible. Devise an algorithm which solves this problem, argue
that your algorithm is correct, and analyze its running time and space
requirements. Your algorithm or algorithms should output both the
total cost of the trip and the various cities at which rental cars
must be dropped off and/or picked up.
- Prof. Howard has decided to spend
her vacation traveling the world. She lives in City 0,
and she will
first fly to City 1, then City 2,
and so on until she reaches
City n, which is just another name for her
hometown, City 0. There
are m differrent airlines that service these various cities, and
Prof. Howard has created an n by m
table
A containing airfare
information. The entry A[i,j] corresponds to the airfare
required to fly from City (i-1) to
City i on Airline j.
Unfortunately, Prof. Howard has learned that switching from
one airline to another isn't necessarily free and that a penalty is often
charged. Prof. Howard has created an (n-1) by
m by m table P
containing the penalty information. The entry
P[i,j,k] corresponds
to the penalty incurred when switching from
Airline j to Airline k
in City i. Prof. Howard wants to fly
as cheaply as possible.
Devise an algorithm which solves this problem, argue that your
algorithm is correct and analyze its running time and space
requirements. Your algorithm or algorithms should output both the
total cost of the trip and the airlines that will be taken at each
city. (You may assume that all airfares and penalties have been
rounded to the nearest dollar.)
(Hint: Review the ``chessboard'' problem.)