For the following, design an algorithm using a greedy heuristic. Justify your \"

Question

For the following, design an algorithm using a greedy heuristic. Justify your "value" function for making decisions (Why is it reasonable or natural?) If your algorithm will produce an optimal answer, give a reason (need not be rigorous) and if not, explain why with a counterexample. What is the time complexity for each cases?

A) A ski shop in a resort has n pairs of skis for n skiers. No two pairs of skis are the same length and no two skiers are the same height. The disparity in assigning skis to skiers is defined to be the sum of the absolute value of the difference between the height of the skier and the length of the pair of assigned skis. An optimal assignment is when the disparity is as small as possible. Design an algorithm to assign skis to skiers, minimizing disparity.

Explanation / Answer

Greedy algorithm:
There will be n^2 skis and skier pairs and each pair has a score(absolute difference between the height of the skier and the length of the pair of assigned skis).

Insert scores(along with their skis-skier pair) into a min heap.
Maintain two boolean arrays of size n for skis and skiers. Initialize all to false.
remove all the scores from heap one by one until no ski or skier is left to match.
If pair associated with the score are free(both ski and skier in the pair are not matched with any other ski or skier(i.e value in the array for this ski and skier are false)) then match them and change boolean array for this ski and skier to true.
If not then move on to next score in minheap.

Time complexity: There are O(n^2) nodes in heap.
We know that bulding a heap takes O(n) time.
In this case as there are O(n^2) nodes therefore bulding heap takes O(n^2).
similarly removing all nodes takes O(n^2) time.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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