Description

A pdf copy of your own solutions should be submitted at SUCourse.
One of the matching problems described in 1962 by David Gale and Lloyd S. Shapley is Stable Marriage Problem (SMP).
(i) Define SMP as a computational problem: What is the input? What is the output?
(ii) Give an example for SMP.
Problem 2 (Gale-Shapley Algorithm) In 1962, David Gale and Lloyd S. Shapley proved that, for any equal number of men and women, it is always possible to solve SMP and make all marriages stable. They presented an algorithm (called the Gale-Shapley algorithm) to compute a solution for SMP.
(i) Present the Gale-Shapley algorithm with a pseudocode.
(ii) Analyze the asymptotic time complexity of this algorithm. [Hint: Use the big-oh notation.]
Problem 3 (BONUS) Implement the Gale-Shapley algorithm in Python, based on your pseudocode from Problem 2, and illustrate it with your SMP example from Problem 1.
1