Programming Assignment 1 (15%) CSI2110/CSI2510 PART 2 (0.30*60 marks=18 marks=4.5%)
Due : November 8, 11:59PM
Politique de retard: Late assignment policy :
The Stable Matching problem
Supplementary questions
1. [4 points] Suppose that in a given stable matching problem, we have the following rankings:
company A: company B: company C: student X: student Y: student Z:
1. student Y 1. student Z 1. student X 1. company B 1. company C 1. company A
2. student X 2. student Y 2. student Z 2. company A 2. company B 2. company C
3. student Z 3. student X 3. student Y 3. company C 3. company A 3. company A
1min-24hres de retard -30% pénalité; devoirs non acceptés après 24hres.
1min-24hs late are accepted with 30%off; no assignments accepted after 24hs late.
In such situation, it is possible to give to either the companies or the students their first choice, as well as give both their second choice;
Solution 1: (A,Y), (B,Z), (C,X) Solution 2: (A,Z), (B,X), (C,Y) Solution 3: (A,X), (B,Y), (C,Z)
In the current implementation of the Gale-Shapley algorithm, which solution will be found?
2. [6 points] Estimate the Big-O running time complexity of your implementation of the Gale- Shapley algorithm (worst and best cases). Please, do not count the time for initialize() and only count the time for execute(). Justify your answer.
CSI 2110 page 2 _________________________________________________________________________________________________
3. To be valid, a matching solution must be stable as defined in the definition of the problem given in part 1.
In this example, the matching {(A,X), (B,Y), (C,Z)} is not stable because upon examining the
choices for company C and student Y, we
1) C prefers Y to current match Z
2) Y prefers C to current match B
have that both:
2. student Y 2. student Y 2. student Y 2. company B 2. company C 2. company A
company A: company B: company C: student X: student Y: student Z:
1. student X 1. student X 1. student X 1. company A 1. company A 1. company C
3. student Z 3. student Z 3. student Z 3. company C 3. company B 3. company B
On the other hand, solution {(A,X), (B,Z),(C,Y)} is stable, since there are no such pair of employer and student that would rather be matched to each other.
a) [4 points] Write an algorithm that returns a boolean value that indicates if a given matching is stable. The input for your algorithm is as below, with employers and students corresponding to numbers 0..n-1.
• Two arrays of length n: students and employers representing the match as in P1-part 1.
• Array A of size nxn with A[s][e]being the ranking score given by student s to eμployer
e, as used in P1-part 1.
• Array B of size nxn with B[e][s]being the ranking score given by employer e to student s.
Provide pseudocode or Java code.
b) [4 points] Estimate the Big-O worst-case running time complexity of your algorithm as a function of n.