JAVA IMPLEMENTATION OF GALE SHAPLEY ALGORITHM - USE HELPER CLASS PROVIDED BELOW (Preferences.java)

In this problem we will consider a version of the problem for professors and students and their fully ordered list of preferences. The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problem for professors and students and their fully ordered list of preferences. Note that ties in preference lists are not allowed. As before we have a set P of n professors and a set S of n students. Assume each professor and each student ranks the members of the opposite group.

Part 2: Implement Gale-Shapley Algorithm In order to solve this matching problem more efficiently, you need to implement Gale-Shapley Al- gorithm and give a solution for Professors Optimal Matching. For implementation, we provide you with again with Preferences.java and you will put your implementation to Assignment1.java file under stableMatchGaleShapley(). This function will again return ArrayList, described in previous part. Keep note that your algorithm should run in O(n2) time. Make sure that a student can compare between his current professor and another professor in constant time.

public static ArrayList stableMatchGaleShapley(Preferences preferences) {}

PREFERENCES.JAVA

import java.util.ArrayList;

/** * Class to provide input to Stable Matching algorithms */ public class Preferences { /** Number of professors. */ private int numberOfProfessors;

/** Number of students. */ private int numberOfStudents;

/** A list containing each professor's preference list. */ private ArrayList> professors_preference;

/** A list containing each student's preference list. */ private ArrayList> students_preference;

public Preferences(int numberOfProfessors, int numberOfStudents, ArrayList> professors_preference, ArrayList> students_preference) { this.numberOfProfessors = numberOfProfessors; this.numberOfStudents = numberOfStudents; this.professors_preference = professors_preference; this.students_preference = students_preference; }

public int getNumberOfProfessors() { return numberOfProfessors; }

public void setNumberOfProfessors(int numberOfProfessors) { this.numberOfProfessors = numberOfProfessors; }

public int getNumberOfStudents() { return numberOfStudents; }

public void setNumberOfStudents(int numberOfStudents) { this.numberOfStudents = numberOfStudents; }

public ArrayList> getProfessors_preference() { return professors_preference; }

public void setProfessors_preference(ArrayList> professors_preference) { this.professors_preference = professors_preference; }

public ArrayList> getStudents_preference() { return students_preference; }

public void setStudents_preference(ArrayList> students_preference) { this.students_preference = students_preference; } }