3. Facebook has all sorts of personal information and thus, can entice advertisers by promising they can deliver ads targeted to specific demographic groups. Ad- vertisers are drooling and ready to fork over some big bucks. Now Facebook is trying to figure out an efficient method to deliver targeted ads to as many users as possible. The first step in this process is to classify people into demographic groups. On Facebook these classifications might be based on things such as geographic loca- tion, age, interest in a type of music, college major. We'll assume this step is taken care of by the data mining group and they have identified k demographic groups G1,G2,...,Gk. Note that these groups can overlap; G could be people who live in Bellingham, G, could be people who like pizza, G3 could be students majoring in computer science, The marketing department at Facebook is forging contracts with m different ad- vertisers to show a certain number of ads to users of the site. Here's what a contract with the ith advertiser looks like: For a subsct of the demographic groups, X; C{G1,G2,...,Ge}, advertiser i will have its ads shown only to users who belong to at least one of the demographic groups in Xi For a number ri, the advertiser will have its ads shown to at least r; users cach inute Now consider the problem of showing ads for a single minute. Specifically, you want to create a way to show no more than one ad to cach user at this minute to satisfy as many of the advertising contracts as possible. Suppose at a given minute there are n users on the site and we we know that user j belongs to a particular subset of the demographic groups. Can you phrase the problem as a maximum flow problem and explain how to determine if it's possible to show a single ad to cach user at this minute so that the Facebook's advertising contracts with each of the m advertisers are satisfied? If it is possible, you should explain how to pair users with advertisements to satisfy the contracts. 3. Facebook has all sorts of personal information and thus, can entice advertisers by promising they can deliver ads targeted to specific demographic groups. Ad- vertisers are drooling and ready to fork over some big bucks. Now Facebook is trying to figure out an efficient method to deliver targeted ads to as many users as possible. The first step in this process is to classify people into demographic groups. On Facebook these classifications might be based on things such as geographic loca- tion, age, interest in a type of music, college major. We'll assume this step is taken care of by the data mining group and they have identified k demographic groups G1,G2,...,Gk. Note that these groups can overlap; G could be people who live in Bellingham, G, could be people who like pizza, G3 could be students majoring in computer science, The marketing department at Facebook is forging contracts with m different ad- vertisers to show a certain number of ads to users of the site. Here's what a contract with the ith advertiser looks like: For a subsct of the demographic groups, X; C{G1,G2,...,Ge}, advertiser i will have its ads shown only to users who belong to at least one of the demographic groups in Xi For a number ri, the advertiser will have its ads shown to at least r; users cach inute Now consider the problem of showing ads for a single minute. Specifically, you want to create a way to show no more than one ad to cach user at this minute to satisfy as many of the advertising contracts as possible. Suppose at a given minute there are n users on the site and we we know that user j belongs to a particular subset of the demographic groups. Can you phrase the problem as a maximum flow problem and explain how to determine if it's possible to show a single ad to cach user at this minute so that the Facebook's advertising contracts with each of the m advertisers are satisfied? If it is possible, you should explain how to pair users with advertisements to satisfy the contracts