CAS CS 330 Study Guide - Midterm Guide: Topological Sorting, Stable Marriage Problem, Priority Queue
15 May 2017
School
Department
Course
Professor
Document Summary
How to recognize: two distinct sets of people w preferences. How to recognize: one set/ group of people w preferences. There is not always a stable matching. Unlike the stable marriage problem , a stable matching may fail to exist for certain sets of participants and their preferences. For a minimal example of a stable pairing not existing, consider 4 people. A, b, c, and d, whose rankings are:a:(b,c,d), b:(c,a,d), In this ranking, each of a, b, and c is the most preferable person for someone. In any solution, one of a, b, or c must be paired with. Initialize each person to be free. while (some man is free and hasn"t proposed to every woman) { False: if there is a pair (m,w) that prefer each other they will always be in the stable matching set. True a man will ask his first preference first. If he is her first preference as well, then she will never switch.
