CS5800 09F: Homework 05

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

   Problem	01	02	03	04	05	06	07	08	09	...
   Credit	RC	RC	RC	EC	RC	RC	NA	RC	RC	...

   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 (2^nd or 3^rd) 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 A_j[0..m] where A_j[i] is the benefit obtained by assigning i programmers to project j. Assume that A_j[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, A_j[i+1] - A_j[i] ≤ A_j[i] - A_j[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 l_i units long and w_i units wide, l_i ≥ w_i ≥ 1. Assume that paving stone i can be stacked on top of paving stone j iff l_i ≤ l_j and w_i ≤ w_j. 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:

• CS5800 F09 Home Page
• Homework 4
• Homework 6