Description
1. (30 points)
Suppose you are a high-level manager in a software firm and you are managing n software projects.
You are asked to assign m of the programmers in your firm among these n projects. Assume that all of
the programmers are equally competent.
After some careful thought, you have figured out how much benefit i programmers will bring to project j.
View this benefit as a number. Formally put, for each project j, you have computed an array Aj [0..m] where
Aj [i] is the benefit obtained by assigning i programmers to project j. Assume that Aj [i] is nondecreasing
with increasing i. Further make the economically sound assumption that the marginal benefit obtained
by assigning an ith programmer to a project is non-increasing as i increases. Thus, for all j and i ≥ 1,
Aj [i + 1] − Aj [i] ≤ Aj [i] − Aj [i − 1].
(a) Design a greedy algorithm to determine how many programmers you will assign to each project such
that the total benefit obtained over all projects is maximized. Your answer should be in the form of
a sequence of clearly stated steps. Pseudo-code is optional.
(b) Justify the correctness of your algorithm and analyze its efficiency in space and time.
2. (30 points)
The Museum of Fine Art is planning to construct a new wing to showcase paintings of contemporary
art. The new wing consists of a single, long corridor. Paintings roughly of size 2×2 feet will be hung along
both walls of this corridor. Their centers are placed along distances x1, x2, …xn from the start of their
respective walls, all at the same height.
1
An architect is trying to design how to light this corridor. She has to fit linear panels of light (fluorescent
tube lights) above each wall, along it. Each panel of light reliably provides light within a horizontal span
of m feet at the height at which the paintings are hung (same for all panels). Each painting is lit if it is
within the horizontal span of at least one panel. Panels of lights are significantly longer than the span of
each painting (m 2), so she is ready to assume that each painting is a dot at its center. Her problem is
to place a minimum number of panels of lights along and above each wall so that each painting is lit.
(a) State the technical problem (i.e. state the actual computational problem without context, in a way
that it can be applied to any other context).
(b) Provide an efficient algorithm to compute the centers of the panels of light along one wall, obeying
the above constraints. Your algorithm should be in the form of a sequence of clear and precise steps.
Pseudo-code is optional.
(c) Justify the correctness of your algorithm and analyze its efficiency in space and time.
3. (30 points)
“Elixir of Life” is a milk bank that provides mother’s milk to newborn babies in their critical first few
months of life. They accept donations from mothers, homogenize and pasteurize it and then package them
into vials of 1, 5, 10, 20 and 50 ounces. Then they supply to local hospitals for a fee to cover their costs
for processing and packaging, which must be done in extremely hygienic conditions. As the milk bank is
sustained only through donations, there are a limited number of vials of each size.
(a) When new parents come to the bank with a prescription of m ounces, the bank must dispense the
amount to them. Note that due to hygiene issues the bank is not allowed to open the packaged vial
to dispense part of an amount. However you may assume that m is an integral number. Design an
algorithm to dispense exactly m ounces using the minimum number of vials. Your answer should
include a short description about why your algorithm returns the optimal answer. Your answer must
be in the form of a sequence of clear and precise steps. Pseudo-code is optional.
(b) Justify the correctness of your algorithm and analyze its efficiency in space and time.
(c) How will you know if dispensing the amount is even possible?
2
