Sample input above: Let us say CEO of your company is planning a company party.

Question

Sample input above:

Let us say CEO of your company is planning a company party. Company's hierarchical structure is specified in tree structure, the root node being CEO. The personnel office has ranked each employee with a conviviality rating (i.e. how much (s)he can have fun? J), which is a real number. In order to make the party fun for all attendees, CEO does not want both an employee and his/her immediate boss to attend. Determine an algorithm to make up the guest list. The goal is to maximize the sum of the conviviality ratings of the guests.

Your immediate goal is to find the optimal solution for this instance, then try to get an idea for the general algorithm.

Best solution: A,B,C,F,& G,

Total conviviality: 3.8

Explanation / Answer

Let us first determine the most obvious recursive solution to this problem: to find the maximum conviviality, we can recurse on every node in the tree until the leaves, and return back the maximum values. This can be implemented in pseudo-code as such:

   Find-Max-Conv(Node n)
1 if n.children = null
2 return max(0, n.rating)
3 return max( Sum(Find-Max-Conv(i)) for all i = n.children),
Sum(Find-Max-Conv(i) for all i = n.grandchildren) + n.rating)

Let's take a quick look at what this recursion does: the base case (leaves) in lines (1, 2) simply returns the max value of not 0 (not inviting someone) and the conviviality rating of the person. (We need the comparison with 0 in case the conviviality is negative). Line 3 is our recursive call; the solution, given some node, will be the maximum of inviting the current node (person) and not inviting the current node (person). If we invite the current node, we cannot invite children, and thus we sum the current value with the maximum ratings of the current node's grandchildren. If we don't invite the current node, then the maximum value would be the sum of maximum convivialities over all children.

Consider the running time of this algorithm. We go through every node in the tree, and consider adding or not adding it. So there are two options for each of n nodes (0, 1), meaning the number of operations will be some function of 2^n. This is exponential running time and undesirable.
-----------------------------------------------------------------------------------------------------------------------------
2nd Approach(Optimized) : Dynamic Programming
Once the naive recursion has been laid out, it's usually not too difficult to come up with an efficient dynamic programming solution. First let's determine the optimal sub-structure that we can exhibit: looking at some person to invite, if we already know the maximum conviviality of all descendants in the tree, we can easily determine if we should include or not include the current node. If we compute these maximum values in a bottom-up fashion, we should be able to implement a much more efficient solution to the problem:

The principal idea then, is to start from node n and work back to the root, each time basing the current optimal conviviality on previously computed sub-problems that have been stored in some memoization table. Below is the pseudo-code:

   Find-Max-Conv(Tree t)
1 Let MC[ ] be an array of length n that contains max conviviality from this node down in the tree
2 for i = Node n downto 1
3 MC[i] = max(i.rating + Sum of all MC[i.grandchildren], Sum of all MC[i.children])
(If node i has no grandchildren or children, replace i.grandchildren and/or i.children with 0)
4   return MC[1]

So how does the running time improve? Ignoring the space of the table required (just O(n)), we can see that we do a constant number of calculations (sums, comparisons) once for every node in the tree. The solution thus runs in linear time (O(n)).

We can also make some improvements to the algorithm to get the actual list of people to invite. One way would be to have somewhat of an adjacency list that contained nodes that should be invited, assuming that we invite, and assuming that we don't invite a given node. At the end then, depending on if the root node is invited or not, we would take that appropriate list.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.