You applied for a TAship in the summers and the RO office in all their algorithmic...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
You applied for a TAship in the summers and the RO office in all their algorithmic brilliance used the Gale Shapely algorithm to assign you your preferred course and you are now happily TAing Pakistan studies and have no real workload (this was actually the case for one of your TAS). But one fine day your instructor comes and tells you that you need to assign students partners for their upcom- ing pair presentation. Your class has exactly n male and n female students, and each pair needs to have one male and one female student. Normally you would have assigned random partners but today you feel a bit nice, and allow the students to send in their preference lists (of the opposite gender) so that you can form stable pairs using the stable matching algorithm you've studied in class. However, you're unable to choose a proposing party for the algorithm (will it be the group of males or the group of females that sends the proposals?). To keep things fair, you decide to start from a random perfect matching, and then check for instabilities randomly. If an instability is found, i.e., m-w and m'-w' are matched but m prefers w' to w and w' prefers m to m', then you break the current pairs and match them as follows: m-w' and m'-w. You continue to do this until no instabilities are left. Will this strategy always help you form a stable matching for the upcoming presentations? If yes, then provide a detailed proof that shows this strategy will always terminate and allow you to find a stable matching. If not, then provide a preference list (n = 3) and an initial perfect matching such that this strategy does not terminate with a stable matching. Particularly, dry run the algorithm using this preference list, such that you show a cycle in the matching state. You applied for a TAship in the summers and the RO office in all their algorithmic brilliance used the Gale Shapely algorithm to assign you your preferred course and you are now happily TAing Pakistan studies and have no real workload (this was actually the case for one of your TAS). But one fine day your instructor comes and tells you that you need to assign students partners for their upcom- ing pair presentation. Your class has exactly n male and n female students, and each pair needs to have one male and one female student. Normally you would have assigned random partners but today you feel a bit nice, and allow the students to send in their preference lists (of the opposite gender) so that you can form stable pairs using the stable matching algorithm you've studied in class. However, you're unable to choose a proposing party for the algorithm (will it be the group of males or the group of females that sends the proposals?). To keep things fair, you decide to start from a random perfect matching, and then check for instabilities randomly. If an instability is found, i.e., m-w and m'-w' are matched but m prefers w' to w and w' prefers m to m', then you break the current pairs and match them as follows: m-w' and m'-w. You continue to do this until no instabilities are left. Will this strategy always help you form a stable matching for the upcoming presentations? If yes, then provide a detailed proof that shows this strategy will always terminate and allow you to find a stable matching. If not, then provide a preference list (n = 3) and an initial perfect matching such that this strategy does not terminate with a stable matching. Particularly, dry run the algorithm using this preference list, such that you show a cycle in the matching state.
Expert Answer:
Related Book For
Income Tax Fundamentals 2013
ISBN: 9781285586618
31st Edition
Authors: Gerald E. Whittenburg, Martha Altus Buller, Steven L Gill
Posted Date:
Students also viewed these programming questions
-
when problem solving, your suppliers sort activities by answering three questions. They include what was different this time; why here and not there? What is another question that a supplier might...
-
The Crazy Eddie fraud may appear smaller and gentler than the massive billion-dollar frauds exposed in recent times, such as Bernie Madoffs Ponzi scheme, frauds in the subprime mortgage market, the...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
5. (8 points) (Determining a hidden "dot product vector") Consider the problem where one is given black-box access to a function f: {0, 1}" {0, 1} such that f(x) = a-z, where a {0,1}" is unknown....
-
Locate the centroid zc of the spherical segment. dz
-
DoorDash is planning an IPO for the 4th quarter of 2020. The company is currently valued at $16B and plans to issue 16 million shares as part of its IPO at this valuation. These shares will have a...
-
Calculate the interquartile range for each of the following sets of data: a. \(3,6,7,12,15,17,23,28\) b. \(8,4,1,6,13,10,12,5\) c. \(3,8,14,11,16,7,14,15,11,9,12,6\) d....
-
Castle Corporation prepares monthly cash budgets. Here are relevant data from operating budgets for 2014. All sales and purchases are on account. Budgeted collections and disbursement data are given...
-
PERCEPTUAL MAPPING EXERCISE FAST FOOD RESTAURANTS Learning Objectives Understand how consumer perceptions are studied and acted upon through the use of perceptual mapping Wide Choice Develop...
-
Examine the Apartment worksheet, and apply appropriate names to cells D17:D20. 2. Set up the structure of a one-variable data table on the Analysis worksheet that shows the apartment rental price,...
-
12. Write a program to draw a face of a clock that looks something like this:
-
Lisinipril is a drug designed to lower blood pressure. In a clinical trial of Lisinipril, blood pressure levels of subjects are measured before and after they have been treated with the drug....
-
Identifying the Population In a Gallup poll of 1010 adults in the United States, 55% of the respondents said that they used local TV stations daily as a source of news. Is the 1010 value a statistic...
-
According to the State of New York Unified Court System, names of potential jurors are selected from a variety of different sources. When a trial requires a jury, names from the list are randomly...
-
Years in which U.S. presidents were inaugurated. Determine which of the four levels of measurement (nominal, ordinal, interval, ratio) is most appropriate.
-
When collecting data from different sample locations in a lake, a researcher uses the line transect method by stretching a rope across the lake and collecting samples at every interval of 5 meters....
-
Problem 3.8 - Determine the moment about the line AB due to Force F. mmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmand Z 18 m A 10 m 20 m C B D 15 m F = 6 kN 12 m X
-
Consider the sections of two circuits illustrated above. Select True or False for all statements.After connecting a and b to a battery, the voltage across R1 always equals the voltage across R2.Rcd...
-
Steve Jackson (age 51) is a single taxpayer living at 3215 Pacific Dr., Del Mar, CA 92014. His Social Security number is 465-88-9415. In 2012, Steve's earnings and income tax withholding as the...
-
Sally and Charles Heck received the following dividends and interest during 2012: Assuming the Hecks file a joint tax return, complete Schedule B of Form 1040 (on page 2-33) for them for the 2012 tax...
-
Greg died on July 1, 2012, and left Lea, his wife, a $50,000 life insurance policy which she elects to receive at $5,000 per year plus interest for 10 years. In the current year, Lea receives $6,200....
-
Emily Stansbury is a licensed dentist. During the first month of the operation of her business, the following events and transactions occurred. Emily uses the following chart of accounts: No. 101...
-
Indicate how a journal is used in the recording process.
-
Transactions for Thorn Consulting for the month of June are presented below. Identify the accounts to be debited and credited for each transaction. June 1 2 Oleg Thorn invests 5,000 cash in a small...
The Young Chemist A Book Of Laboratory Work For Beginners 1st Edition - ISBN: 1437349137 - Free Book
Study smarter with the SolutionInn App