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., mw 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: mw' 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., mw 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: mw' 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 billiondollar 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 blackbox access to a function f: {0, 1}" {0, 1} such that f(x) = az, where a {0,1}" is unknown....

People with normal vision cannot focus their eyes underwater if they aren't wearing a face mask or goggles and there is water in contact with their eyes (see Discussion Question Q34.23). (a) Why not?...

A cylindrical tank in a chemical factory is to contain 2.000 m 3 of a corrosive liquid. Because of the cost of the material, it is desirable to minimize the area of the tank. Find the optimum radius...

A steam engine of \(100 \mathrm{~kW}\) runs at \(100 \mathrm{rpm}\). The speed of the engine is to be maintained within \(1 \%\) variation in mean speed. The flywheel has a mass of \(2000...

Noah and Joan Arc live with their family in Dayton, OH. Noahs Social Security number is 434113311. Noah was born on February 22, 1983, and Joan was born on July 1, 1984. Both enjoy good health and...

On the 30th September 2023, you can already an article about a proposed merger relating to ibibi bank. On 1t October you notice that shares of ibibi bank are currently selling at rs. 1000. A)...

BottleUp, Inc., was organized on January 8, 2010, and made its S election on January 24, 2010. The necessary consents to the election were filed in a timely manner. Its address is 1234 Hill Street,...

Find the Taylor series of the binomial function f(x) = (1+x)/2.

9/2/1 You learned in previous courses that the slope of a nonvertical straight line is or Ar 22 21 where (1.1) and (22, y2) are any two points on the line. Most functions we see in calculus have the...

Use a computer for this exercise. Let a system have the following state and output equation matrices: 1 0 8 02 A = 0 2 0 B = 3 0 C = [1 0 1] D = [00]. 0 0 3 00 For this system, answer the following

Find the root of the coupled equations x+2cosx+y1=0 2xsiny8=0 by the NewtonRalphson method. (a) Put the iteration formula in the matrix form Az = b, Ar where "i" is the iteration index, and Z= so...

Given f (9) = 5, f' (9) = 10, g (9)=1, and g' (9) = 8, find the values of the following. (a) (fg)' (9) Number (b) ()(9)  Number

Problem 3 (4 pts). A nonionic organic molecule "A" is dissolving and diffusing into a pure carrier solvent "B," which is flowing with a certain velocity across a flat surface of pure A. The...

On 1 July 2017, London Ltd acquired all of the shares of Whale Ltd, on a cumdiv . basis, for $2,700,000. At this date, the equity and liability sections of Whale Ltd.s statement of financial...

Express these numbers in standard notation. a. 2.87 108 b. 1.78 1011 c. 1.381 1023

Steve Jackson (age 51) is a single taxpayer living at 3215 Pacific Dr., Del Mar, CA 92014. His Social Security number is 465889415. 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 233) 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....

Which part of the brain controls posture, balance, and fine movements? (a) brainstem (b) cerebellum (c) cerebrum (d) thalamus

Which part of the brain is responsible for reasoning, language, and the control of voluntary movement? (a) brainstem (b) cerebellum (c) cerebrum (d) thalamus

Multiple tissues combine to make a(n)____, a structure in the body that has a specific function.
Study smarter with the SolutionInn App