University:
California State University, Northridge
Course:
COMP 482 | Algorithm Design and Analysis
Academic year:

2024
Views:

104

Pages:

2
Author:

Samuel K.

COMP 482 Quiz 1-1: Name Problem 1. (10 points) Run the Propose-Dispose algorithm on the instance of STABLEMARRIAGE below. Show enough work that I know you are running the algorithm and not just guessing, using brute force, copying off your neighbor, etc. M1: W1 W2 W3 W4 W5 W6 M2: W2 W1 W3 W4 W5 W6 M3: W3 W2 W1 W4 W5 W6 M4: W4 W3 W2 W1 W5 W6 M5: W5 W4 W3 W2 W1 W6 M6: W6 W5 W4 W3 W2 W1 W1: M1 M2 M3 M4 M5 M6 W2: M2 M1 M3 M4 M5 M6 W3: M3 M2 M1 M4 M5 M6 W4: M4 M3 M2 M1 M5 M6 W5: M5 M4 M3 M2 M1 M6 W6: M6 M5 M4 M3 M2 M1 Problem 2. (10 points) Give an instance of STABLEMARRIAGE with N = 4 where running Propose-Dispose results in no men and women being paired with their favorite. M1: 1 2 3 4 M2: 3 4 1 2 M3: 2 1 4 3 M4: 4 3 2 1 W1: 1 2 3 4 W2: 4 1 2 3 W3: 2 3 4 1 W4: 3 4 1 2 Problem 3. (10 points) Assume you have an instance of STABLEMARRIAGE and a matching where at least 1 man and 2 women (m, w1, and w2) are paired with their least favorite. Show that this matching cannot be stable. (Note: for this problem I am not asking for an instance which is an example/counterexample and I have not said anything about PROPOSE-DISPOSE.) M1: 1 - - - M2: - 2 - - M3: - - 3 - W1: 1 - - - W2: - 2 - - W3: - - 3 - Because the man who gets his least favorite is willing to be paired with any other women and there are two women who get their least favorite and willing to be paired with any other men. So, even if the man is paired with one of the women who get their least favorites, there's always at least 1 woman left who is willing to be paired with another man. So, the man and the woman who is left prefer each other and thus it is unstable.

COMP 482 Quiz 1

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock