# CS5800 09F: Homework 05

Created: Tue 06 Oct 2009

Assigned: Wed 07 Oct 2009
Due: Wed 14 Oct 2009

## Instructions

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

2. 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

Problem01020304 0506070809...
CreditRCRCRCECRC RCNARCRC...

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 penalty assessment.

3. 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 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.

1. Exercise 16.2-5
2. 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.

3. Consider a set of m rectangular paving stones where the ith stone is li units long and wi units wide, liwi ≥ 1. Assume that paving stone i can be stacked on top of paving stone j iff lilj and wiwj. 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.
4. 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.

5. 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.

### Switch to:

Harriet Fell
College of Computer Science, Northeastern University
360 Huntington Avenue #340 WVH,
Boston, MA 02115
Email: fell@ccs.neu.edu
Phone: (617) 373-2198 / Fax: (617) 373-5121
The URL for this document is: http://www.ccs.neu.edu/home/fell/CS5800/F09/Homeworks/hw.05.html