EE360C: Algorithms
University of Texas at Austin Homework #11
Dr. Christine Julien Due: April 20, 2014 (in class quiz)
Homework #11
You should try to solve these problems by yourself. I recommend that you start early
...
EE360C: Algorithms
University of Texas at Austin Homework #11
Dr. Christine Julien Due: April 20, 2014 (in class quiz)
Homework #11
You should try to solve these problems by yourself. I recommend that you start early and get help
in office hours if needed. If you find it helpful to discuss problems with other students, go for it.
The goal is to be ready for the in class quiz that will cover the same or similar problems.
Problem 1: Planning a Company Party
You are 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 the most fun for all of the attendees, the president does not
want both an employee and his or her immediate supervisor to attend.
You are given the tree that describes the structure of the corporation, where each node represents
an employee, and a node’s children represent the employees under his or her direct supervision.
Each node of the tree holds, in addition to the child pointers, the name of the employee and the
employee’s conviviality rating.
Give a dynamic programming 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.
Hints:
• Construct your solution as a binary choice.
• Even the president of the company may end up not invited if that turns out to be optimal.
• Argue that the problem exhibits optimal substructure, define the optimal solution via recursion, provide a description or pseudocode of the bottom-up algorithm, and analyze the
running time.
[Show More]