Archive for October 19th, 2013

Cormen Dynamic Programming Problem 15-6

October 19th, 2013 No comments

15-6: Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is supervisor relation forms a tree rooted at the president. The personnel office has ranked each employee with a conviviality 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. Professor Stewart is given the tree that describes the structure of the corporation, using the left-child, right-sibling representation method. Each node of the tree holds, in addition to the pointers, the name of an employee and that employee’s conviviality ranking. Describe an algorithm to make up a guest list that maximizes the sun of the conviviality ratings of the guests. Analyze the running time of the algorithm.

The solution can be found here.

Update: The analysis part for Algorithm 1 is incorrect.  The complexity for Algorithm 1 is also O(n) as there are no redundant computation during the recursion.  So, Algorithm 2 is infact an overkill, but still linear.  Just by remembering the solutions of the sub-problems in the recurrence structure, it is possible to get the solution to the problem in linear time.