3. (4 pts.) The Gale-Shapley algorithm. To analyze the running time of the Gale-Shapley algorithm, you need to be specify the data structures you'll use to implement the algo- rithm so the time it takes to do each step can be determined. function GALE-SHAPLEY(n, R, H) Initially all n residents and n hospitals are free. while Some resident r is free do Let h be the first hospital that has not rejected r yet. if h is free then Match r to h; r and h are no longer free. else Letr be the resident h is currently matched to. if h prefers r to r' then h rejects r' and r' becomes free. Match r and h; r is no longer free. else h rejects r;r remains free. end if end if end while Add all pairs to M and return M. end function Figure 1: The Gale-Shapley algorithm with residents on one side and hospitals on the other side. a. Implement the Gale-Shapley algorithm. Describe the data structures you'll use to keep track of which residents and hospitals are free, how you find the first hospital that has not rejected a resident r, etc. b. Determine the running time of your implementation in terms of n. (Explanation please!) The input consists of n, R and H which has size O(na) altogether. How does the running time of your algorithm compare with n? 3. (4 pts.) The Gale-Shapley algorithm. To analyze the running time of the Gale-Shapley algorithm, you need to be specify the data structures you'll use to implement the algo- rithm so the time it takes to do each step can be determined. function GALE-SHAPLEY(n, R, H) Initially all n residents and n hospitals are free. while Some resident r is free do Let h be the first hospital that has not rejected r yet. if h is free then Match r to h; r and h are no longer free. else Letr be the resident h is currently matched to. if h prefers r to r' then h rejects r' and r' becomes free. Match r and h; r is no longer free. else h rejects r;r remains free. end if end if end while Add all pairs to M and return M. end function Figure 1: The Gale-Shapley algorithm with residents on one side and hospitals on the other side. a. Implement the Gale-Shapley algorithm. Describe the data structures you'll use to keep track of which residents and hospitals are free, how you find the first hospital that has not rejected a resident r, etc. b. Determine the running time of your implementation in terms of n. (Explanation please!) The input consists of n, R and H which has size O(na) altogether. How does the running time of your algorithm compare with n