CS180 Assignment 1 | Question 2 Solved

Assignment 1.  CS180: Algorithms and Complexity

Guidelines for submitting the solutions:

It is strongly recommended to use LATEX or other word processing software for submitting the homework. This is not mandatory but will be helpful both for you and for us. If submitting electronically, send your solutions to

Grades will take into account both the correctness and the clarity ofthe solutions. You are responsible for communicating your solution ina simple and understandable way. Sloppy answers will receive feweror no points even if they are correct". Unless otherwise speci ed,all answers will need to be throughly justi ed with complete proofs.However, you may use results proved in class without proofs as longas you state them clearly. Most importantly, make sure you adhere to the policies for academic honesty set out on the course webpage. The policies will be enforced strictly.
Problems:

2. Give an example of an instance of stable matching problem with at least three di erent stable matchings. That is, for some positive integer n, give ranking lists for each of n doctors L1; :::;Ln and ranking lists for each of n hospitals L0
1; :::;L0 n such that there are at least three di erent stable matchings with these rankings. To get full points, it is enough to specify the lists and write down (or clearly draw) three stable matchings in your instance. [3 points]