2. (5 pts.) On stable matchings. Suppose there are four medical residents (...) and four hospitals (h. hz, hs, he) with the preference lists below. hy nha ha ha ha rzh ha ha ha The hs hi ha ra ha ha ha ha hin a. Use the Gale-Shapley algorithm (see fig. 1) to find two stable matchings for the res. idents and hospitals. For the first stable matching, let the residents do the proposing and the hospitals the accepting of proposals; for the second stable matching, swap their roles. b. Briefly explain why M = {ruh). (ra, ha). (rs, h),(a,h)} is not a stable matching. (Limit your explanation to a few sentences.) Let's generalize. Suppose there are n residents ...,r, and hospitals h .. . Their preferences are described by two nxn matrices R and H respectively. Specifically, the rows of Rand Hare indexed from 1 to n and represent the residents and hospitals respectively, the columns are also indexed from 1 to n but this time represent the rank of the preference. Thus, R[i]) = 3 means that the jth choice of resident rish, and HOG) = 10 means that the jth choice of hospital h, is To The matrices R and H for the instance above will look like this: 24131 1 3 4 2 2 3 1 4 4 1 3 2 4 3 1 21 1 2 3 1 2 3 4 RE H We also specify a matching using an array M, also indexed from 1 ton, where M ind cates the hospital matched to r.Thus, the matching {(rh), (rah). (rs, ha), (rez) is represented as M = 3.1, 4.2 c. Given R, Hand M, describe an efficient algorithm that returns "yes" of Mis stable matching and otherwise returns "no together with the indices of a blocking pair. Explain why your algorithm is correct and determine its running time. (Hint: how do you check if a resident is part of a blocking pair?) 2. (5 pts.) On stable matchings. Suppose there are four medical residents (...) and four hospitals (h. hz, hs, he) with the preference lists below. hy nha ha ha ha rzh ha ha ha The hs hi ha ra ha ha ha ha hin a. Use the Gale-Shapley algorithm (see fig. 1) to find two stable matchings for the res. idents and hospitals. For the first stable matching, let the residents do the proposing and the hospitals the accepting of proposals; for the second stable matching, swap their roles. b. Briefly explain why M = {ruh). (ra, ha). (rs, h),(a,h)} is not a stable matching. (Limit your explanation to a few sentences.) Let's generalize. Suppose there are n residents ...,r, and hospitals h .. . Their preferences are described by two nxn matrices R and H respectively. Specifically, the rows of Rand Hare indexed from 1 to n and represent the residents and hospitals respectively, the columns are also indexed from 1 to n but this time represent the rank of the preference. Thus, R[i]) = 3 means that the jth choice of resident rish, and HOG) = 10 means that the jth choice of hospital h, is To The matrices R and H for the instance above will look like this: 24131 1 3 4 2 2 3 1 4 4 1 3 2 4 3 1 21 1 2 3 1 2 3 4 RE H We also specify a matching using an array M, also indexed from 1 ton, where M ind cates the hospital matched to r.Thus, the matching {(rh), (rah). (rs, ha), (rez) is represented as M = 3.1, 4.2 c. Given R, Hand M, describe an efficient algorithm that returns "yes" of Mis stable matching and otherwise returns "no together with the indices of a blocking pair. Explain why your algorithm is correct and determine its running time. (Hint: how do you check if a resident is part of a blocking pair?)
