1. For this problem we're trying to rank items according to particular criteria. Say we're trying to rank automobiles - perhaps we have measures of criteria like gas mileage, safety rating, etc. - and we want to know what automobiles are better than other automobiles in every criteria (assume we all have the same opinion of what's good: high gas mileage, safe, etc). More formally, suppose we have k criteria for items r and y denoted by D1, D2, ..., Ik and y1, y2, ... , Yk. We will say I dominates y if 81 > yi and 12 > y2 and ...Tk > Sk: (a) Show the dominating relationship is transitive. (b) Assume you are given n items 11, 12, ..., In. Your job is to find the longest dominating sequence, [Is, 152,- -- , Ism], of items such that Is; dominates 153+1 for all j =1,2,...,m-1. Show how to phrase this as a graph problem. First explain how to construct a graph that represents this problem. Then explain what you need to do to this graph to solve this problem of finding the longest dominating sequence. State the running time needed to build the graph (expressed in terms of n and k) separate from the running time needed to carry out your algorithm on the graph (expressed in terms of V and E). (C) A Pareto optimal set of items would be those that are not dominated by any other items. Explain how to find a Pareto optimal set of the n items from the graph you built. 1. For this problem we're trying to rank items according to particular criteria. Say we're trying to rank automobiles - perhaps we have measures of criteria like gas mileage, safety rating, etc. - and we want to know what automobiles are better than other automobiles in every criteria (assume we all have the same opinion of what's good: high gas mileage, safe, etc). More formally, suppose we have k criteria for items r and y denoted by D1, D2, ..., Ik and y1, y2, ... , Yk. We will say I dominates y if 81 > yi and 12 > y2 and ...Tk > Sk: (a) Show the dominating relationship is transitive. (b) Assume you are given n items 11, 12, ..., In. Your job is to find the longest dominating sequence, [Is, 152,- -- , Ism], of items such that Is; dominates 153+1 for all j =1,2,...,m-1. Show how to phrase this as a graph problem. First explain how to construct a graph that represents this problem. Then explain what you need to do to this graph to solve this problem of finding the longest dominating sequence. State the running time needed to build the graph (expressed in terms of n and k) separate from the running time needed to carry out your algorithm on the graph (expressed in terms of V and E). (C) A Pareto optimal set of items would be those that are not dominated by any other items. Explain how to find a Pareto optimal set of the n items from the graph you built
