A pdf copy of your own solutions should be submitted at SUCourse.
Problem 1 (Stable Marriage Problem) Matching problems are about markets where individuals are matched with individuals or firms or items, typically across two sides, as in employment (e.g., who works at which job), university admissions (e.g., which students go to which school), and kidney donation (e.g., who receives which transplantable organ). In each problem, preferences of individuals, firms or items are given. The aim is to identify matchings that have nice properties such as stability. The importance of matching problems is recognized by a Nobel Prize in 2012 given to Lloyd S. Shapley and Alvin E. Roth.
One of the matching problems described in 1962 by David Gale and Lloyd S. Shapley is Stable Marriage Problem (SMP).
Define SMP as a computational problem: What is the input? What is the output?
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.
Present the Gale-Shapley algorithm with a pseudocode.1
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.
Pseudocode reference by Prof. Sanjeev Arora: http://www.cs.princeton.edu/courses/ archive/spr11/cos116/handouts/Pseudocode_Reference.pdf
1
