Suppose you are evaluating a set T = {t,...,tn} of football teams. For each team ti,...

Transcribed Image Text:

Suppose you are evaluating a set T = {t₁,...,tn} of football teams. For each team ti, you have a numerical rating x > 0 of its offense and yi> 0 of its defense. We say that ti dominates another team t; if xi > xj and Yi > Yj. Given a subset T'CT, we say that ti is viable in T' if there is no team t; € T' that dominates tį. (a) Suppose that you have already divided T into two halves, T₁ and T2, such that for all ti € T₁ and all tj E T2, we have x ≤ xj. Furthermore, suppose that you have already found sets S₁ = {ti E Ti ti is viable in T₁} and S₂ = {t₁ T₂ : ti is viable in T₂}. E Design a O(n)-time algorithm that uses S₁ and S₂ to find S = {tį € T: ti is viable in T}. (b) Design a O(n log n)-time algorithm to find S = {t₁ € T : t₁ is viable in T} without making the suppositions of part (a). Suppose you are evaluating a set T = {t₁,...,tn} of football teams. For each team ti, you have a numerical rating x > 0 of its offense and yi> 0 of its defense. We say that ti dominates another team t; if xi > xj and Yi > Yj. Given a subset T'CT, we say that ti is viable in T' if there is no team t; € T' that dominates tį. (a) Suppose that you have already divided T into two halves, T₁ and T2, such that for all ti € T₁ and all tj E T2, we have x ≤ xj. Furthermore, suppose that you have already found sets S₁ = {ti E Ti ti is viable in T₁} and S₂ = {t₁ T₂ : ti is viable in T₂}. E Design a O(n)-time algorithm that uses S₁ and S₂ to find S = {tį € T: ti is viable in T}. (b) Design a O(n log n)-time algorithm to find S = {t₁ € T : t₁ is viable in T} without making the suppositions of part (a).

Answer rating: 100% (QA)

a To find the set S t ET t is viable in T given S and S you can follow this Ontime a... View the full answer