College of Computer & Information Science Fall 2006 Northeastern University Handout 9 CSU690: Algorithms and Data 6 October 2006

Problem Set 3 (due Friday, October 13)

1. (10 points) DAGs and cycles

Chapter 3, Exercise 3, page 107.

2. (10 points) Number of shortest paths in social networks

Chapter 3, Exercise 10, page 110. (Hint: Use breadth-first search.)

3. (10 points) Scheduling daily jobs

Chapter 4, Exercise 17, page 197.

4. (15 points) Project management

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

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. Justify the correctness of your algorithm and analyze its running time.

5. (15 points) Planning an expedition

Chapter 4, Exercise 18, page 197.