(3) Problem 15.6 (page 408). Your input is a a tree whose vertices are the employees and which represents the management hierarchy. (That is, if employee A reports directly to B, then the node representing A is a child of the node representing B. No employee reports directly to more than one person.) The value stored at each node, x, will be the optimum conviviality rating, C[x], of the subtree which has that node as the root. Note that for each node, you have to decide whether or not to invite the individual represented by that node. Assume that nobody has a negative conviviality rating. In your answer, show the derivation of the dynamic programming expression (i.e., a recursion for C[x]). 15-6 Planning a company party Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the 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 described in Section 10.4. 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 sum of the conviviality ratings of the guests. Analyze the running time of your algorithm. (3) Problem 15.6 (page 408). Your input is a a tree whose vertices are the employees and which represents the management hierarchy. (That is, if employee A reports directly to B, then the node representing A is a child of the node representing B. No employee reports directly to more than one person.) The value stored at each node, x, will be the optimum conviviality rating, C[x], of the subtree which has that node as the root. Note that for each node, you have to decide whether or not to invite the individual represented by that node. Assume that nobody has a negative conviviality rating. In your answer, show the derivation of the dynamic programming expression (i.e., a recursion for C[x]). 15-6 Planning a company party Professor Stewart is consulting for the president of a corporation that is planning a company party. The company has a hierarchical structure; that is, the 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 described in Section 10.4. 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 sum of the conviviality ratings of the guests. Analyze the running time of your algorithm