1. Consider the following instance of the Stable Matching Problem: We have two men m and m and two women w and w.m prefers w to w.m prefers w to w.w prefers m to m.w prefers m to m. (a) Use the Gale-Shapley algorithm to find a stable matching of this instance. (b) Show why the matching {(m,w),(m,w)} is not stable. 2. Decide whether you think the following statements are true or false. If it is true, give a short explanation. If it is false, give a counterexample. (a) In every instance of the Stable Matching Problem, there is a stable matching containing a pair (m,w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. (b) Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m,w) belongs to S. 3. Apply the optimal greedy algorithm for the interval scheduling problem to obtain a compatible subset of requests of maximum possible size for the following set of requests: (s(i),f(i))=(0,3),(0,2),(4,7),(2,6),(2,3). 4. Apply the optimal greedy algorithm for the interval partitioning problem to schedule all of the requests using as few resources as possible for the following set of requests: (s(i),f(i))=(0,3),(0,2),(5,7),(2,4),(4,6)