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....
-
The payoff matrix would now be as shown below, and the best choice, both individually and collectively, would be the risky job.
-
What are the four steps involved in ethical decision-making?
-
How does the development stage of the new-product process involve testing the product inside and outside the fi rm?
-
Mansker Station Corporation has declared an annual dividend of $0.80 per share. For the year just ended, earnings were %6.40 per share. a. What is Mansker Stations payout ratio? b. Suppose Mansker...
-
Henrich is a single taxpayer. In 2021, his taxable income is $450,500. What is his income tax and net investment income tax liability in each of the following alternative scenarios? Use Tax Rate...
-
Senior Home Living (SHL) is a Canadian-based corporation located in British Columbia. SHL provides senior living residences across Canada. The company was incorporated in 1975, and has been...
-
This case study research aims to create a master budget for Handle's Homemade ice cream and identify the sales budget, production budget, and direct materials budget for the first quarter of 2023....
-
Lennys Limousine Service (LLS) is considering the purchase of two Hummer limousines. Various information about the proposed investment follows: Required: Help LLS evaluate this project by calculating...
-
Lancer Corp. has the following information available about a potential capital investment Required: 1. Calculate the projects net present value. 2. Without making any calculations, determine whether...
-
Woodchuck Corp. is considering the possibility of outsourcing the production of upholstered chair pads included with some of its wooden chairs. The company has received a bid from Padalong Co. to...
-
Woodchuck Corp. is considering eliminating a product from its line of outdoor tables. Two products, the Oak-A and Fiesta tables, have impressive sales. However, sales for the Studio model have been...
-
Suppose that Flyaway Company also produces the Windy model fan, which currently has a net loss of \($40,000\) as follows: Eliminating the Windy product line would eliminate \($20,000\) of direct...
-
No need of explanation just give answer of all ASAP the systems manager the sales manager Question 10 (1 point) What represents the receipt of money generated by revenues less cash expenses? cash...
-
Express these numbers in standard notation. a. 2.87 10-8 b. 1.78 1011 c. 1.381 10-23
-
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....
-
Purchased debt instrument with impairment LO9, 11, 13, 14 On 1 January 2019, Biko Banking Ltd purchases a debt instrument with a 5-year term for its fair value of $1000 million (including...
-
Applying accounting theory LO6, 8, 13, 14 Tropical Tours Ltd needs to raise $500 000 to finance the acquisition of a new tour bus. It approached an investment bank that proposed the following...
-
Various financial assets and financial liabilities LO12, 13 Great Adventure Ltd has entered into a number of contracts that are financial instruments as follows. (a) On 1 July 2018, the company...
![Mobile App Logo](https://dsd5zvtm8ll6.cloudfront.net/includes/images/mobile/finalLogo.png)
Study smarter with the SolutionInn App