The Gale-Shapley Stable Matching Algorithm Let w be the set of Women and M be the set of Men 2. 3. 4. 5. 6. 7. 8. Initially, all me M and we W are free While there is a man m who is free and hasn't proposed to every woman w: Choose a man m Let w be the highest-ranked woman in m's preference list to whom m has not yet proposed If w is free then (m, w) become engaged Else w is currently engaged to m If w prefers m' to m then m remains free Else w prefers m to mi (m, w) become engaged m' becomes free End While Return the set s of engaged pairs 9. 10. 11. 12. 13. 14. 15. How to Implement Prepare an implementation of the algorithm in a lower level pseudocode, use known data structures. If you are confused with pseudocode, try to use C++ using known ADT. Determine the time complexity of your algorithm