Java代写 | CSI2120 Programming Paradigms

本次Java代写是完成一个雇佣匹配系统
CSI2120 Programming Paradigms
Pair: Cisco – Sophia
Why is this solution stable? We have to look at the definition of a stable match. A stable match is
defined such that neither party to the match have a preferred party that also prefers them over their
current match. E,g., Canada Post would prefer to hire Olivia over Jackson but Olivia is currently
CSI 2120 page 2
_________________________________________________________________________________________________
matched with Thales which she prefers over Canada Post. While Jackson would prefer to work for
Thales over Canada Post but Thales is matched with Olivia which Thales prefers over Jackson. As a
result, while neither Canada Post nor Jackson got their first choice, the match is stable as neither of them
have a way to improve their current match. The other pairs are also stable which is left as an exercise to
test. As a result, the solution provided is a stable matching and is also perfect. A perfect match is
actually a simpler criterion, just requiring each employer being matched to a student and each student
being matched to an employer.
In summary, in this assignment you will need to find a perfect and stable matching given preference
tables by coop employers and by students. There will always be the same number of employers and
students and every employer will only hire one student.
Algorithms:
The stable matching can be found with an iterative algorithm, the Gale-Shapley algorithm. The
corresponding pseudocode is given below. The input is a list of preferences from n employers




and a list of preferences from n students 

. The algorithm
calculates an output of n stable matches . In the algorithm the variable  stands for an employer and 
for a student.
Gale-Shapley ( 



, 

.)
Initialize  ∶= 
while ( some employer  is not matched to any student )
find most preferred student s on the list 


() to whom
the employer  has not yet offered a job.
if (student  is unmatched)
Add the pair to the set of matches (, ) → .
else if ( prefers  to employer ʹ of current match (’, ) )
Replace the match  → (′, ) with (, ) → 
else  rejects offer from 
return the set of stable matches 
While Gale-Shaley is an iterative solution, the recursive McVitie-Wilson will be easier to implement in
some paradigms. One can think of McVitie-Wilson as an alternating recursion of two functions: a
function offer and evaluate (see the pseudocode on the next page). These two recursive function
need to be called from a main loop which calls offer for each coop employer once.

CSI 2120 page 3
_________________________________________________________________________________________________
Initialize  ∶= 
offer ( employer  )
if (employer  is unmatched)
find most preferred student s on the list 


() to whom
the employer  has not yet offered a job.
if found evaluate match (, ) by calling evaluate((, ))
return
evaluate ( match (, ) )
if (student  is unmatched)
Add the pair to the set of matches (, ) → .
else if ( prefers  to employer ʹ of current match (’, ) )
Replace the match  → (′, ) with (, ) → 
offer(′)
else  rejects offer from 
offer()
return
Part 1: Object-oriented solution (Java) [3 marks]
Create the classes needed to solve the stable matching problem for coop employers and students with the
iterative Gale-Shapley algorithm. Your program must be a Java application called StableMatching
that takes as input the names of two files containing the preference of coop employers and students as
csv files. Your program must save the stable matching to a csv file called matches_java_nxn.csv
where n is the size of in the problem. The file is to be saved in the current directory.
In addition to the source code, you must also submit a UML class diagram showing all classes, their
attributes, methods, and associations. You can not use static methods (except main).
You must follow proper object-oriented design for full marks.
Part 2: Concurrent solution (Go) [3 marks]
Create a Go application that solve the stable matching problem for coop employers and students with the
recursive McVitie-Wilson algorithm. Your program must produce a Go executable called
stable_matching.exe that takes as input the names of two files containing the preference of coop
employers and students as csv files. Your program must save the stable matching to a csv file called
CSI 2120 page 4
_________________________________________________________________________________________________
matches_go_nxn.csv where n is the size of in the problem. The file is to be saved in the current
directory.