CSI2120代做、代写Programming、Java语言代做、代做Java程序设计

日期：2020-04-01 10:23

CSI2120 Programming Paradigms

Winter 2020

Part 1 and 2 due on February 17th, 2020 before 11:00 pm in Virtual Campus

Part 3 and 4 due on April 4th, 2020 before 11:00 pm in Virtual Campus

[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)

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

if (employer is unmatched)

find most preferred student s on the list to whom

the employer has not yet offered a job.

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.

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.

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)

? (("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.