Question

In organization ABC, the employees have an underlying hierarchy, where the CEO is at the top and every other employee has exactly one manager. An employee can be the manager to one or more employees. Any employee is familiar with the work of her manager and the works of her immediate sub-ordinates. It was decided to give away gift coupons for all employees(including the CEO) as New year presents. By mistake, the gift coupons ordered were of three different denominations - 1000, 2000 and 3000. It was decided that every employee will receive a gift coupon of denomination different from her manager. However, if an employee receives a gift coupon of larger denomination than her manager, she is sure to be given a negative rating by her manager in a fit of jealousy. Design an algorithm to decide how to distribute gift coupons among employees so that the number of employees who gets a negative rating is minimized.

If you are giving a Dynamic programming algorithm, state and prove the recurrence relation and also give the bottom-up implementation. If you are giving a greedy algorithm, please provide a proof of correctness and pseudo-code.

Answer 1

To distribute the gift coupons with minimal negative ratings, we use a greedy algorithm that assigns the lowest denomination to each employee, avoiding higher denominations than their managers.

Step-by-step explanation:

To distribute the gift coupons while minimizing the number of negative ratings, we can utilize a greedy algorithm. The algorithm will distribute the coupons starting from the lowest level employees and moving up to the CEO, ensuring that each employee receives a different denomination than their manager and that nobody receives a higher denomination than their manager. This can be achieved by assigning the lowest possible denomination to the employees and then assigning the next higher denomination to their managers recursively up the hierarchy. This way, no manager receives a lower denomination than their subordinates, thus minimizing jealousy.

Here is the pseudo-code for the proposed algorithm:

• Start with each employee at the bottom of the hierarchy.
• Assign the lowest denomination coupon that is not equal to the denomination received by their manager.
• Move up the hierarchy, assigning coupons to each manager that are of the same or lower denomination than their subordinates.
• Repeat the process until the CEO is assigned a coupon.

With this approach, the algorithm ensures that the distribution of coupons adheres to the rules, and the likelihood of negative ratings due to jealousy is minimized since no employee receives a higher denomination than their immediate manager.