Assignment 0 CSI2120

Assignment 0
CSI2120 Programming Paradigms


[12 marks]
Problem Description
This assignment asks you to implement solutions to the stable matching problem. We will consider the
problem of matching coop employers to coop students. In particular, we consider the problem of n
employers and n students where each employer will hire a single student. Each employer produces a
ranking of students who they prefer to hire for the coop term and each student rank all employers who
they prefer to work for. As input to the stable matching algorithm, we therefore have two preference
tables of size 𝑛 𝑥 𝑛: one for the employers and one for the students. This input will be stored as two csv
(comma-separated-values) files and a simple example for 𝑛 = 3 , i.e., for three employers and three
students in a very simple format.
Coop employer preferences:
Thales,Olivia,Jackson,Sophia
Canada Post,Sophia,Jackson,Olivia
Cisco,Olivia,Sophia,Jackson
Student preferences:
Olivia,Thales,Canada Post,Cisco
Jackson,Thales,Canada Post,Cisco
Sophia,Cisco,Thales,Canada Post
A stable matching solution for this problem is as follows
Pair: Canada Post - Jackson
Pair: Thales - Olivia
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 (in this order). 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 cannot use static methods (except main).
You must follow proper object-oriented design for full marks and hand-in your source tree in a single jar
file. Your jar file must include all source code (*.java).

CSI 2120 page 4
_________________________________________________________________________________________________
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
matches_go_nxn.csv where n is the size of in the problem. The file is to be saved in the current
directory.
Your solution must execute the function offer for different employers concurrently.
You must follow proper imperative and concurrent design for full marks including the creation and use
of packages. You must hand-in your source tree in a single zip file. Your zip file must not include any
executable code but only the source code in the proper directory structure.
Part 3: Logic solution (Prolog) [3 marks]
Create a Prolog predicate
stableMatching( L_employer_preference, L_student_preference, M )
that is true if the stable matching problem for coop employers and students is solved by the set of
matches M.
Your solution must include helper predicate called findStableMatch that takes as input the names
of two files containing the preference of coop employers and students as csv files. Your helper predicate
must save the stable matching to a csv file called matches_prolog_nxn.csv where n is the size
of in the problem. The file is to be saved in the current directory.
Your solution for the predicate stableMatching/3 must function as a predicate with all three
parameters instantiated but also find all stable matching results for full marks.
Part 4: Functional solution (Scheme) [3 marks]
Create a Scheme function stableMatching that solves the stable matching problem for coop
employers and students with the recursive McVitie-Wilson algorithm. With the above preference tables
of size 3, the function would be called as follows:
(stableMatching L_employer_preferences L_student_preferences)
CSI 2120 page 5
_________________________________________________________________________________________________
 (("Canada Post" "Jackson") ("Cisco" "Sophia") ("Thales"
"Olivia"))
Your solution must include helper functions for your function findStableMatch to be able to take
as input the names of two files containing the preference of coop employers and students as csv files.
Your helper predicate must save the stable matching to a csv file called
matches_scheme_nxn.csv where n is the size of in the problem. The file is to be saved in the
current directory.
Your solution must follow proper functional design for full marks.