Your goal is to create a guest list for the ABC Employee End of Summer party. Th

Question

Your goal is to create a guest list for the ABC Employee End of Summer party. The employees of ABC are organized as a tree, with the president at the root. The parent of an employee in the tree is their immediate supervisor. The first requirement of the guest list is that an employee and their direct supervisor should not both be invited to the party (this would ruin the fun). Second, each node of the tree, in addition to containing links and an employee field, contain a "fun" ranking of that employee as a positive integer. Design an algorithm to create a guest list that maximizes the total fun value of the people at the party. Analyze the running time of your algorithm.

Explanation / Answer

Naive-Recursive-Way:

We determine the most clear recursive solution to this questions: to find the maximum fun value of the people at the party , we can recursive on every node in the tree until the leaves, and return back the maximum fun value of the people at the party .

Algorithm for this is

Find-Max-Fun_at_Party(Node n)
1 if n.child = null
2 return max(0, n.fun_rating)
3 return max( Sum(Find-Max-Fun_at_Party(i)) for all i = n.child),
Sum(Find-Max-Fun_at_Party(i) for all i = n.grandchild) + n.fun_rating)

Let's take a quick look at what this recursion does: the base case (leaves) in lines (1, 2) simply returns the maximum value of not 0 (not inviting someone) and the fun rating of the person. (We need the comparison with 0 in case the fun rating 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 child, and thus we sum the current value with the maximum ratings of the current node's grandchild. If we don't invite the current node, then the maximum value would be the sum of maximum fun rating over all child.

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.

Dynamic Programming Optimal Solution:

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 fun value 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 idea is to then, is to start from node n and work back to the root, each time basing the current optimal fun value on previously computed sub-problems that have been stored in some memorization table. Below is the pseudo-code:

Find-Max-Fun_at_Party(Tree t)

1 Let MaxFun[ ] be an array of length n that contains max fun from this node down in the tree
2 for i = Node n downto 1
3MaxFun[i] = max(i.fun_rating + Sum of all MaxFun[i.grandchild], Sum of all MaxFun[i.child])
(If node i has no grandchild or child, replace i.grandchild and/or i.child with 0)
4.return MaxFun[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)).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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