3. On stable matchings. Suppose there are four medical residents (ri,T2,T3,T4) and four hospitals (hi, h2, h3, h4) with the preference lists below T4 T3 T1 T2 T2 3 4 2 4 T2 T4 T1 T3 a. Use the Gale-Shapley algorithm to find two stable matchings for the residents and hospitals. For the first stable matching, let the residents do the proposing and the hospitals the accepting of proposals; in the second stable matching, flip their roles b. Briefly explain why M(ri, hi), (T2, h2), (r3, h3), (r4, h4) is not a stable matching Let's generalize. Suppose there are n residents Ti,... ,Tn and n hospitals h1,... ,hn. Their preferences are described by two nxn matrices Rand H respectively. Specifically, the rows and columns of both R and H are indexed from 1 to n so Ri,j]- k means that the jth choice of resident r ishk. Similarly, H[i,j] denotes the jth choice of hi For example, the matrices R and H for the instance above will look like this 1 3 42 2 3 1 4 41 23 We also specify a matching using an array M, also indexed from 1 to n, where Mi indicates the hospital matched to ri. That is, [(ri, hi), (r2, h2), (r3, h3), (rA, h4)) is rep- resented as M 1,2,3,4 c. Given R, H and M, describe an efficient algorithm that returns "yes" if M is stable matching and otherwise returns "no" together with the indices of a blocking pair Please explain why your algorithm is correct and determine its running time 4. C-1.27 of your book 3. On stable matchings. Suppose there are four medical residents (ri,T2,T3,T4) and four hospitals (hi, h2, h3, h4) with the preference lists below T4 T3 T1 T2 T2 3 4 2 4 T2 T4 T1 T3 a. Use the Gale-Shapley algorithm to find two stable matchings for the residents and hospitals. For the first stable matching, let the residents do the proposing and the hospitals the accepting of proposals; in the second stable matching, flip their roles b. Briefly explain why M(ri, hi), (T2, h2), (r3, h3), (r4, h4) is not a stable matching Let's generalize. Suppose there are n residents Ti,... ,Tn and n hospitals h1,... ,hn. Their preferences are described by two nxn matrices Rand H respectively. Specifically, the rows and columns of both R and H are indexed from 1 to n so Ri,j]- k means that the jth choice of resident r ishk. Similarly, H[i,j] denotes the jth choice of hi For example, the matrices R and H for the instance above will look like this 1 3 42 2 3 1 4 41 23 We also specify a matching using an array M, also indexed from 1 to n, where Mi indicates the hospital matched to ri. That is, [(ri, hi), (r2, h2), (r3, h3), (rA, h4)) is rep- resented as M 1,2,3,4 c. Given R, H and M, describe an efficient algorithm that returns "yes" if M is stable matching and otherwise returns "no" together with the indices of a blocking pair Please explain why your algorithm is correct and determine its running time 4. C-1.27 of your book