After Graduation, you start working for a company that has a hierarchical supervisor structure in the shape of a tree, rooted at the CEO. The personnel office has ranked each employee with a conviviality rating between 0 and 10. Your first assignment is to design a dynamic programming algorithm to construct the guest list for the office Christmas party. The algorithm has input consisting of the hierarchy tree, and conviviality ratings for each employee. The output is to be a guest list that maximizes the total conviviality, and ensure that for every employee invited to the party, his or her immediate supervisor (that is, their parent in the tree) is not invited.
a) Design and implement such a dynamic programming algorithm and analyze it.
b) You are not sure if the CEO should get invited to the party, but you suspect that you might get fired if he is not. Can you modify your algorithm to ensure that the CEO does gets invited.