CS代考 CS 70 Discrete Mathematics and Probability Theory Fall 2021 – cscodehelp代写

CS 70 Discrete Mathematics and Probability Theory Fall 2021
1 Stable Matching
Consider the set of jobs J = {1, 2, 3} and the set of candidates C = {A, B, C} with the following preferences.
Jobs Candidates
1 A>B>C 2 B>A>C 3 A>B>C
Candidates Jobs
A 2>1>3 B 1>3>2 C 1>2>3
Run the traditional propose-and-reject algorithm on this example. How many days does it take and what is the resulting pairing? (Show your work.)
Stable Matching III
1. True or False?
(a) If a candidate accidentally rejects a job she prefers on a given day, then the algorithm ends with a rogue couple.
(b) The Propose-and-Reject Algorithm never produces a candidate-optimal matching.
(c) If the same job is last on the preference list of every candidate, the job must end up with its least preferred candidate.
CS 70, Fall 2021, DIS 2A 1
Propose-and-Reject Proofs
Asyou¡¯veseenfromlecture,thejobs-proposingPropose-and-RejectAlgorithmproducesanemployer- optimal stable matching. Let¡¯s see if the candidate have any way of improving their standing. Suppose exactly one of the candidates has the power to arbitrarily reject one proposal, regardless of which job she has on her string (if any). Construct an example that illustrates the following: for any n ¡Ý 2, there exists a stable matching instance for which using this power helps every candidate, i.e. every candidate gets a better job than she would have gotten under the jobs-proposing Propose-and-Reject Algorithm.
Prove the following statements about the traditional propose-and-reject algorithm.
(a) In any execution of the algorithm, if a candidate receives a proposal on day i, then she receives some proposal on every day thereafter until termination.
(b) In any execution of the algorithm, if a candidate receives no proposal on day i, then she receives no proposal on any previous day j, 1 ¡Ü j < i. CS 70, Fall 2021, DIS 2A 2 (c) In any execution of the algorithm, there is at least one candidate who only receives a single proposal. (Hint: use the parts above!) 4 Be a Judge By stable matching instance we mean a set of jobs and candidates and their preference lists. For each of the following statements, indicate whether the statement is True or False and justify your answer with a short 2-3 line explanation: (a) There is a stable marriage instance for n jobs and n candidates for n > 1, such that in a stable matching algorithm with jobs proposing execution every job ends up with its least preferred candidate.
(b) In a stable matching instance, if job J and candidate C each put each other at the top of their respective preference lists, then J must be paired with C in every stable pairing.
(c) In a stable matching instance with at least two jobs and two candidates, if job J and candidate C each put each other at the bottom of their respective preference lists, then J cannot be paired with C in any stable pairing.
(d) For every n > 1, there is a stable matching instance for n jobs and n candidates which has a pairing in which every unmatched job-candidate pair is a rogue couple. Note that this pairing is not stable at all.
CS 70, Fall 2021, DIS 2A 3