Problem 1: The process of designing an algorithm consists of a few significant steps. Define these steps to highlight all necessary features. (25 points) Problem 2: Using a graphical illustration, provide an example of a stable-matching scenario between two men (e.g., m and m') and two women (e.g., w and w') assuming that men initiates the matching process. In your answer, show the preference lists of all men and women then identify the stable-matching scenario(s) between them. (25 points) Problem 3: In a stable matching problem, consider a group of 4 men, M = {A, B, C, D), and a group of 4 women, W = {1,2,3,4}, who have the following matching preferences: (40+10 points) 1 A 4, 1, 3, 2 B 1, 2, 4, 3 ? 1, 2, 4, 3 D 2, 4, 1, 3 2 3 A, B, C, D D, B, A, C D, C, A, B D, C, B, A Men's preferences Women's preferences Find the stable matching between all men and women assuming i) men propose women and ii) the algorithm chooses free men in a round-robin fashion (i.e., A, B, C, D, A, B, ...). Finally, draw a bipartite graph of the stable matching between M and W.
