[SOLVED] Cs301 homework 0

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).
(i) Define SMP as a computational problem: What is the input? What is the output?
(ii) Give an example for SMP.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.1(ii) Analyze the asymptotic time complexity of this algorithm. [Hint: Use the big-oh notation.]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
Pseudocode reference by Prof. Sanjeev Arora: http://www.cs.princeton.edu/courses/
archive/spr11/cos116/handouts/Pseudocode_Reference.pdf
1