Created: Tue 06 Oct 2009
Wed 07 Oct 2009
Wed 14 Oct 2009
- Please review the course syllabus and make sure that you understand the course policies for grading, late homework, and academic honesty.
- On the first page of your solution write-up,
you must make explicit which problems are to be graded for
"regular credit", which problems are to be graded for "extra credit",
and which problems you did not attempt.
Please use a table something like the following
where "RC" is "regular credit", "EC" is "extra credit", and "NA"
is "not applicable" (not attempted). Failure to do so will result
in an arbitrary set of problems being graded for regular
credit, no problems being graded for extra credit, and a five percent
- 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 four of the five problems below. Problem 1 is an exercise in the book but counts as a problem here.
Points: 20 points per problem.
Unless otherwise indicated, exercises and problems are from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. The edition (2nd or 3rd) will be indicated if the numbering differs.
- Exercise 16.2-5
- Nubert is a high-level manager in a software firm and is managing n software projects. He is asked to assign m of the programmers in the firm among these n projects. Assume that all of the programmers are equally (in)competent.
After some careful thought, Nubert has figured out how much benefit
i programmers will bring to project j. View this benefit as a
number. Formally put, for each project j, he has 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-seemingly-sound
assumption that the marginal benefit obtained by assigning an ith
programmer to a project is nonincreasing as i increases. Thus, for
all j and i ≥ 1, Aj[i+1] - Aj[i] ≤ Aj[i] - Aj[i-1].
Help Nubert design a greedy algorithm to determine how many
programmers to assign to each project such that the total benefit
obtained over all projects is maximized. Justify the correctness of
the algorithm and analyze its running time.
- Consider a set of m rectangular paving stones where the ith stone
is li units long and wi units wide, li ≥ wi ≥ 1. Assume
that paving stone i can be stacked on top of paving stone j iff
li ≤ lj and wi ≤ wj. Give an efficient dynamic
programming algorithm for computing the maximum number of paving
stones that can be stacked together. Briefly justify its correctness
and analyze the asymptotic running time of your algorithm.
Consider a version of the activity selection problem, in which each
activity has a weight, in addition to the start and finish
times. (For example, the weight may signify the importance of the
activity.) The goal is to select a maximum-weight set of mutually
compatible activities, where the weight of a set of activities is the
sum of the weights of the activities in the set.
- (a) Give a counterexample to show that the greedy choice
made for the activity selection problem will not work for the weighted
activity selection problem.
- (b) Use dynamic programming to solve the weighted
activity selection problem. Briefly justify its correctness and
analyze the running time of your algorithm.
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 constraints. (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.
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: