CSCI 570 Fall 2021 HW 1 Due Sep 3rd 11 59 PM PST 1 Reading Assignment Kleinberg and Tardos Chapter 1 2 Solve Kleinberg and Tardos Chapter 1 Exercise 1 3 Solve Kleinberg and Tardos Chapter 1 Exercise 2 4 State True False An instance of the stable marriage problem has a unique stable matching if and only if the version of the Gale Shapely algorithm where the male proposes and the version where the female proposes both yield the exact same matching 5 A stable roommate problem with 4 students a b c d is de ned as follows Each student ranks the other three in strict order of preference A match ing is de ned as the separation of the students into two disjoint pairs A matching is stable if no two separated students prefer each other to their current roommates Does a stable matching always exist If yes give a proof Otherwise give an example roommate preference where no stable matching exists 6 Solve Kleinberg and Tardos Chapter 1 Exercise 3 7 Solve Kleinberg and Tardos Chapter 1 Exercise 4 8 N men and N women were participating in a stable matching process in a small town named Walnut Grove A stable matching was found after the matching process nished and everyone got engaged However a man named Almazo Wilder who is engaged with a woman named Nelly Oleson suddenly changes his mind by preferring another woman named Laura Ingles who was originally ranked right below Nelly in his preference list therefore Laura and Nelly swapped their positions in Almanzos preference list Your job now is to nd a new matching for all of these people and to take into account the new preference of Almanzo but you don t want to run the whole process from the beginning again and want to take advantage of the results you currently have from the previous matching Describe your algorithm for this problem Assume that no woman gets o ended if she got refused and then gets proposed by the same person again 1
View Full Document
Unlocking...