(10 points) A group of n dancers will be performing while while holding flags. It's optimal...

 

Transcribed Image Text:

(10 points) A group of n dancers will be performing while while holding flags. It's optimal if each dancer is holding a flag as close as possible to their height. You have a collection of n flags of varying lengths and you want to assign a flag to each dancer such that you are minimizing the total difference in heights. That is minimizing i=1 Id; - fil where d; is height of a dancer and f; is height of flag. Consider the following two strategies and prove or disprove that they work. 1. (5 points) Greedly, pick the dancer and flag that have the minimum difference in height. 2. (5 points) Sort the two lists and then assign the ith dancer to the ith flag. Does this algorithm work? If it doesn't, show a counter example. (10 points) A group of n dancers will be performing while while holding flags. It's optimal if each dancer is holding a flag as close as possible to their height. You have a collection of n flags of varying lengths and you want to assign a flag to each dancer such that you are minimizing the total difference in heights. That is minimizing i=1 Id; - fil where d; is height of a dancer and f; is height of flag. Consider the following two strategies and prove or disprove that they work. 1. (5 points) Greedly, pick the dancer and flag that have the minimum difference in height. 2. (5 points) Sort the two lists and then assign the ith dancer to the ith flag. Does this algorithm work? If it doesn't, show a counter example.