CSCI 570 - Fall 2021 - HW 1Due: Sep 3rd, 11.59 PM PST1. 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 uniquestable matching if and only if the version of the Gale-Shapely algorithmwhere the male proposes and the version where the female proposes bothyield the exact same matching.5. A stable roommate problem with 4 students a, b, c, d is defined as follows.Each student ranks the other three in strict order of preference. A match-ing is defined as the separation of the students into two disjoint pairs. Amatching is stable if no two separated students prefer each other to theircurrent roommates. Does a stable matching always exist? If yes, give aproof. Otherwise give an example roommate preference where no stablematching 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 ina small town named Walnut Grove. A stable matching was found afterthe matching process finished and everyone got engaged. However, a mannamed Almazo Wilder, who is engaged with a woman named Nelly Oleson,suddenly changes his mind by preferring another woman named LauraIngles, who was originally ranked right below Nelly in his preference list,therefore Laura and Nelly swapped their positions in Almanzos preferencelist. Your job now is to find a new matching for all of these people andto take into account the new preference of Almanzo, but you don’t wantto run the whole process from the beginning again, and want to takeadvantage of the results you currently have from the previous matching.Describe your algorithm for this problem.Assume that no woman gets offended if she got refused and then getsproposed by the same person
View Full Document
Unlocking...