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 Leth be the first hospital that has not rejected 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 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 which has size (1) 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 Leth be the first hospital that has not rejected 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 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 which has size (1) altogether. How does the running time of your algorithm compare with n