GS Unique Matching Teasers
During GS, when there are several free men who have not proposed to all women, how does the algorithm dictate how you choose which man proposes next?
1 point
Randomly
Prefer men who have proposed fewer times
Prefer men who have fewer remaining women on their list
It doesn't
For a given instance of the Stable Matching problem, how many different solutions (stable matchings) can the GS algorithm find for us?
1 point
0 or 1
1 or 2
Sometimes more than 2
For a given instance of the Stable Matching problem, how many different solutions (stable matchings) exist?
1 point
0 or more
1 or more
2 or more
For a given instance of the Stable Matching problem where some person (man or woman) has 3 distinct valid partners, how many different solutions (stable matchings) exist?
1 point
2 or more
Exactly 3
3 or more
During a run of GS on a given Stable Matching problem with four men and four women, what is the maximum number of proposers who could be rejected by a valid partner of theirs?
1 point
0
1
2
3
4
Which proof technique (
https://goo.gl/5urGYh
) have we seen in action while convincing ourselves of the properties of GaleShapley?
1 point
Proof by tautology
Proof by simplification
Proof by contradiction
Proof by authority
Submit
This form was created inside of Colorado State University.
Report Abuse

Terms of Service

Additional Terms
Forms