College of Computer & Information Science Fall 2006 Northeastern University Handout 16 CSU690: Algorithms and Data 1 November 2006

Problem Set 5 (due Friday, November 10)

1. (12 points) Planning a company party

You are consulting for a corporation that is planning a company party. The company has a hierarchical structure that can be captured as a tree rooted at the president. Thus, every node of the tree represents a person and the parent of any node (except the root) represents the immediate supervisor of the person. The personnel office has ranked each employee with a convivialty rating, which is a real number. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.

Given the tree structure of the company hierarchy and the conviviality ratings of each person, describe an algorithm to make up a guest list that maximizes the sum of the conviviality ratings of the guest.

2. (12 points) Chapter 6, Exercise 17, page 327.

3. (12 points) Chapter 7, Exercise 7, page 417.

4. (12 points) Chapter 7, Exercise 8, page 418.

5. (12 points) Updating the maximum flow in a network

You are given a directed network G with n nodes and m edges, a source s, a sink t and a maximum flow f from s to t. Assume that the capacity of every edge is a positive integer. Describe an O(m + n) time algorithm for updating the flow f in each of the following two cases.

(a) The capacity of an edge e increases by 1.

(b) The capacity of an edge e decreases by 1.