MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
Project 4: Stable marriage problem v2
Contents
1 Overview 1
1.1 The stable marriage problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Students, schools, and matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Program description 2
2.1 Reading students and schools from files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Gale-Shapley algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3 Menu options 4
4 Error messages 5
5 Required elements 5
5.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
5.2 Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
5.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
6 Helpful hints 9
New concepts: File I/O, time keeping, heuristic algorithms
1 Overview
This project builds upon the previous project, where a program was built to create and store students and
high schools to be matched together using principles from the stable marriage problem (SMP). This version
of the project will automate some of the more tedious aspects of the previous project, namely, student
and school data entry and matching. The remainder of this section provides an overview of SMP and the
student-school matching problem from the previous project.
1.1 The stable marriage problem
SMP is described as follows. Say you have a group of n men and n women, and they need to be matched
together in marriage.The men have ranked all the women in order of preference (1 is most preferred, n is
least preferred), and the women have similarly ranked all the men in order of preference. The matching
solution should make sure that each man is married to exactly one woman and vice versa, and that the
marriages are stable. A stable matching solution means that there is no one person who would rather be
with someone else who would also prefer to be with them. In other words, no two people would want to
have an affair with each other.
1.2 Students, schools, and matching
The program will store students’ names, grade point averages (GPAs), extracurricular scores, and ratings of
schools. GPAs are on a scale of 0-4 (4 being highest), and can be fractional. Extracurricular scores measure
how involved a student has been in extracurricular activities, and are integers on a scale 0-5 (with 5 being
most involved). Students’ rankings of school are provided by the user.
1
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
Palmetto High School,0.85
Coral Gables High School,0.72
Ransom High School,-0.33
Gulliver Preparatory School,0.65
(a) School data file
Jack O’Neill,3.1,3,2,1,3
Samantha Carter,4.0,5,1,2,3
Daniel Jackson,3.8,4,2,3
(b) Student data file
Figure 1: Data file structures. Note that each file must end with a single blank line.
The program will store schools’ names, GPA weights (α), and rankings of students. The GPA weight
is a value in [0, 1] that indicates how much a school emphasizes GPA score over extracurricular score.
For example, if α = 0.90, then the school puts 90% of its assessment of a student on GPA, and 10% on
extracurriculars. Each school creates a composite score for each student using the following formula:
composite score = αG+ (1 α)E
where G is the student’s GPA and E is the student’s extracurricular score. Each school has its own α, and
ranks the students according the composite scores (where higher scores are higher ranked). Thus, schools’
rankings of students are not entered manually, but are automatically calculated based on α. Ties are broken
in the same manner as in the previous project.
The following conditions must be satisfied in order to perform matching:
Students must be entered
Schools must be entered
The number of students and schools must be equal
Students and schools must have rankings for each other
These conditions are checked in order, and matching is aborted as soon as any condition is found to be
violated. The quality of matching is defined by whether or not the matching is stable and the total regret
of the participants. Regret is the difference in rank between a participant’s top choice and the match they
ended up with.
2 Program description
In this project, we will do two things:
1. Read student and school data from files
2. Use the famous Gale-Shapley algorithm [1] to automate the matching
2.1 Reading students and schools from files
Instead of receiving student and school information by hand, we will store the information in text files, and
our program will read those files to populate our students and schools. Schools will be stored in one file,
and students and their rankings of schools will be stored in another file. You may assume that all files are
correctly formatted (e.g., there will not be a string when you expect a number), but you will have to perform
error checks on the data.
A sample school file is shown in Figure 1a. Each line corresponds to a school. The lines are formatted
as the school name followed by its α weight, separated by a comma. A school can only be added to the
database if it has a valid α value. In this file example, Ransom High School would be rejected because it
has α < 0.
A sample student file is shown in Figure 1b. Each line corresponds to a student. The lines are formatted
as student name, GPA, and extracurricular score, followed by the student’s preferred order of schools. All
2
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
Algorithm 1 Gale-Shapley algorithm
Require: Set of suitors (men, M) and their rankings; set of receivers (women, W ) and their rankings
1: while free man m ∈M who still has a woman w ∈W to propose to do
2: w = m’s highest ranked woman to whom he has not yet proposed
3: if w is free then
4: (m,w) become engaged
5: else
6: Some pair (m′, w) already exists
7: if w prefers m to m′ then
8: (m,w) become engaged
9: m′ becomes free
10: end if
11: end if
12: end while
13: return Set of matchings
values are comma-separated. A student can only be added to the database if it has a valid GPA value, a
valid extracurricular score, and valid rankings. Valid rankings are defined as
The correct number of rankings (one per school)
All ranks are integers in the range [1, n]
Unique rankings (no repeated ranks)
Say there are three schools. In this file example, Daniel Jackson would be rejected because he only has
rankings for two schools.
Note that each file should end in a single blank line. Also note that in order to check ranking validity,
schools must be entered into the database first so that we know how many schools there are. Further,
each saved student and school will always have valid rankings, so you do not need to check for rank validity
elsewhere in the program. To maintain rank validity, if more schools are loaded, all existing students must be
cleared out since their rankings are no longer valid; it’s not the smoothest way of handling the situation, but
it is the easiest. However, since schools’ rankings of students are automatically calculated, if new students
are added, all schools’ rankings are just updated.
2.2 Gale-Shapley algorithm
The Gale-Shapley algorithm [1] was developed in 1962 by David Gale and Lloyd Shapley (who won the Nobel
Prize 50 years later) to solve SMP. Using the men-women marriage example, the Gale-Shapley algorithm
can be simply described as the following two steps:
1. Each free man proposes to the most preferred woman to whom he has not yet proposed.
2. Each woman accepts the proposal from the most preferred suitor, to whom she gets “engaged.”
If a free woman receives a proposal, she must accept.
If an engaged woman receives a proposal, she goes with whomever she prefers more (the new
suitor or her current fiance′). If she breaks up with her current fiance′, then that man is now free.
These two steps are repeated for every free man 1, . . . , n in order until everyone is engaged. Note that each
man makes at most one proposal per iteration (one proposal if not engaged, no proposals if already engaged).
The formal algorithm is shown in Algorithm 1.
The resulting solution is guaranteed to be stable and suitor-optimal, meaning that the suitors as a
group (though not necessarily individually) are optimally happy with the matching. So, if the men do the
proposing, they will be happy and the women will get what they get. If the women do the proposing, then
the roles are reversed. In this project, the students will be the suitors.
3
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
Women
A B C
M
en
1 2 1 3
2 3 1 2
3 1 2 3
(a) Men’s rankings of women
Men
1 2 3
W
o
m
en A 1 3 2
B 3 1 2
C 1 2 3
(b) Women’s rankings of men
Figure 2: SMP preference rankings. Elements are rows’ preferences for columns.
As an example, consider a set of three men M = {1, 2, 3} and a set of three women W = {A,B,C}. Each
group’s preferences are shown in Figure 2. The Gale-Shapley algorithm proceeds as follows:
1. Iteration 1
Man 1: Proposes to Woman B; Woman B must accept. Man 1 is now engaged to Woman B.
Man 2: Proposes to Woman B; Woman B dumps Man 1 because she prefers Man 2. Man 2 is
now engaged to Woman B. Man 1 is now free.
Man 3: Proposes to Woman A: Woman A must accept. Man 3 and Woman A are now engaged.
2. Iteration 2
Man 1: Proposes to Woman A; Woman A dumps Man 3 because she prefers Man 1. Man 1 is
now engaged to Woman A. Man 3 is now free.
Man 2: Already engaged
Man 3: Proposes to Woman B: Woman B rejects Man 3 because she prefers her current fiance′.
3. Iteration 3
Man 1: Already engaged
Man 2: Already engaged
Man 3: Proposes to Woman C: Woman C must accept. Man 3 is now engaged to Woman C.
Now that everyone is engaged, the algorithm is finished with the stable matching (1, A), (2, B), and (3, C).
3 Menu options
L - Load students and schools from file
Get file names from the user, then load the files.
E - Edit students and schools
Go to a sub-area with its own menu where students and schools can be edited.
P - Print students and schools
Print student and school information, including any existing matches and rankings.
M - Match students and schools using Gale-Shapley algorithm
Perform matching using the Gale-Shapley algorithm.
D - Display matches and statistics
Display the matches and statistics, which are whether or not the matching is stable, average regret for
students and schools, and average regret overall.
R - Reset database
Clear out the students and schools.
Q - Quit
Quit the program.
4
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
4 Error messages
ERROR: Invalid menu choice!
when the user enters an invalid menu choice.
ERROR: No students are loaded!
when the user attempts to edit students before students have been loaded.
ERROR: No schools are loaded!
when the user attempts to edit schools before schools have been loaded.
ERROR: No suitors are loaded!
when the user attempts to perform matching before suitors have been loaded into the solver.
ERROR: No receivers are loaded!
when the user attempts to perform matching before schools have been loaded into the solver.
ERROR: The number of suitors and receivers must be equal!
when the user attempts to perform matching, but the number of students are schools are not equal.
ERROR: No matches exist!
when the user attempts to display match statistics without performing matching.
ERROR: Choice must be ’y’ or ’n’!
when the user enters an invalid choice for editing a student’s ranking of schools.
ERROR: Rank already used!
when the user enters a rank that has already been used while editing a student’s ranking of schools.
ERROR: Input must be an integer in [, ]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of an int,
then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the negative
of the maximum storable value of an int, then “-infinity” is displayed instead of the actual LB
value.
ERROR: Input must be a real number in [, ]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of a
double, then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the
negative of the maximum storable value of a double, then “-infinity” is displayed instead of the
actual LB value.
5 Required elements
Your project must use the each of the elements described in this section. You can have more functions,
variables, and objects if you want, but you must at least use the elements described in this section.
Failure to correctly implement any of the elements in this section may result in a zero on
the project.
5.1 Variables
An array or ArrayList of Student objects, as defined in Section 5.2
An array or ArrayList of School objects, as defined in Section 5.2
A single SMPSolver object, as defined in Section 5.2
Global public static BufferedReader as the only BufferedReader object in the entire program
for reading user input
5
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
– Although your programs will compile and run just fine on your own computer with multiple
BufferedReader objects, they will not run correctly on a web server with multiple BufferedReader
objects. Since your programs will be graded on a web server, please don’t have more than one
BufferedReader for reading input from the console.
5.2 Classes
You are required to write three classes:
1. Student class to store student data
2. School class to store school data
3. SMPSolver class to run the Gale-Shapley algorithm and store matching results
You can write more classes, and you can add to these classes, but you must at least implement the classes
defined in this section.
1 public class Student {
2 private String name; // name
3 private double GPA; // GPA
4 private int ES; // extracurricular score
5 private int[] rankings; // rankings of schools
6 private int school; // index of matched school
7 private int regret; // regret
8
9 // constructors
10 public Student ()
11 public Student(String name , double GPA , int ES, int nSchools)
12
13 // getters
14 public String getName ()
15 public double getGPA ()
16 public int getES ()
17 public int getRanking(int i)
18 public int getSchool ()
19 public int getRegret ()
20
21 // setters
22 public void setName(String name)
23 public void setGPA(double GPA)
24 public void setES(int ES)
25 public void setRanking(int i, int r)
26 public void setSchool(int i)
27 public void setRegret(int r)
28 public void setNSchools(int n) // set rankings array size
29
30 public int findRankingByID(int ind) // find school ranking based on school ID
31 public void editInfo(ArrayList H, boolean canEditRankings) // user info
32 public void editRankings(ArrayList H, boolean rankingsSet) // edit ranks
33 public void print(ArrayList H) // print student row
34 public void printRankings(ArrayList H) // print the rankings in order
35 public boolean isValid () // check if this student has valid info
36 }
Student Template.java
1 public class School {
2 private String name; // name
6
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
3 private double alpha; // GPA weight
4 private int[] rankings; // rankings of students
5 private int student; // index of matched student
6 private int regret; // regret
7
8 // constructors
9 public School ()
10 public School(String name , double alpha , int nStudents)
11
12 // getters
13 public String getName ()
14 public double getAlpha ()
15 public int getRanking(int i)
16 public int getStudent ()
17 public int getRegret ()
18
19 // setters
20 public void setName(String name)
21 public void setAlpha(double alpha)
22 public void setRanking(int i, int r)
23 public void setStudent(int i)
24 public void setRegret(int r)
25 public void setNStudents(int n) // set rankings array size
26
27 public int findRankingByID(int ind) // find student ranking based on student ID
28 public void editInfo(ArrayList S, boolean canEditRankings) // user info
29 public void calcRankings(ArrayList S) // calculate rankings w/ alpha
30 public void print(ArrayList S, boolean rankingsSet) // print school row
31 public void printRankings(ArrayList S) // print the rankings in order
32 public boolean isValid () // check if this school has valid info
33 }
School Template.java
1 public class SMPSolver {
2 private ArrayList S = new ArrayList (); // suitors
3 private ArrayList R = new ArrayList (); // receivers
4 private double avgSuitorRegret; // average suitor regret
5 private double avgReceiverRegret; // average receiver regret
6 private double avgTotalRegret; // average total regret
7 private boolean matchesExist; // whether or not matches exist
8
9 // constructors
10 public SMPSolver ()
11 public SMPSolver(ArrayList S, ArrayList R)
12
13 // getters
14 public double getAvgSuitorRegret () { return this.avgSuitorRegret; }
15 public double getAvgReceiverRegret () { return this.avgReceiverRegret; }
16 public double getAvgTotalRegret () { return this.avgTotalRegret; }
17 public boolean matchesExist ()
18
19 // reset everything with new suitors and receivers
20 public void reset(ArrayList S, ArrayList R)
21
22 // methods for matching
23 public boolean match () // Gale -Shapley algorithm to match; students are suitors
24 private boolean makeProposal(int suitor , int receiver) // suitor proposes
25 private void makeEngagement(int suitor , int receiver) // make engagement
26 public boolean matchingCanProceed () // check that matching rules are satisfied
7
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
27 public void calcRegrets () // calculate regrets
28 public boolean isStable () // check if a matching is stable
29
30 // print methods
31 public void print () // print the matching results and statistics
32 public void printMatches () // print matches
33 public void printStats () // print matching statistics
34 }
SMPSolver Template.java
5.3 Functions
Function prototypes and short descriptions are provided below. It is your job to determine exactly what
should happen inside each function, though it should be clear from the function and argument names and
function descriptions. You can write more functions (and are strongly recommended to), but you must at
least implement the functions defined in this section.
Only ArrayLists are shown in the function prototypes, but you may always use an array instead of an
ArrayList. If you use arrays, you may pass extra arguments to and from the functions to act as counters.
public static void displayMenu()
Display the menu.
public static int loadStudents(ArrayList S, ArrayList H)
Load student information from a user-provided file and return the number of new students. New
students are added to the list of existing students.
public static int loadSchools(ArrayList H)
Load school information from a user-provided file and return the number of new schools. New schools
are added to the list of existing schools.
public static void editData(ArrayList S, ArrayList H)
Sub-area menu to edit students and schools.
public static void editStudents(ArrayList S, ArrayList H)
Sub-area to edit students. The edited student’s regret is updated if needed. Any existing school
rankings and regrets are re-calculated after editing a student.
public static void editSchools(ArrayList S, ArrayList H)
Sub-area to edit schools. Any existing rankings and regret for the edited school are updated.
public static void printStudents(ArrayList S, ArrayList H)
Print students to the screen, including matched school (if one exists).
public static void printSchools(ArrayList S, ArrayList H)
Print schools to the screen, including matched student (if one exists).
public static int getInteger(String prompt, int LB, int UB)
Get an integer in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value is
entered.
public static double getDouble(String prompt, double LB, double UB)
Get a real number in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value
is entered.
8
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
6 Helpful hints
All the hints from the previous project are still useful, however, the limit on the number of students and
schools is now raised to 2000 students and 2000 schools since the user’s job is now mostly automated.
Note that you can find the ranking of a participant’s match using the participant’s regret. For example,
if a school is with its third-ranked student, its regret is 2. In reverse, if a school has regret 2, it is with
its third-ranked student.
Try to keep your code in SMPSolver as generic as possible, that is, avoid writing code that specifically
requires that students be the suitors and schools be the receivers. It is good practice to be generic so
that you can re-use this solver for future matching problems.
When you provide a file name to read, Eclipse will look in the main project directory for the file
(e.g., if your project directory is /courses/MIE250/Pro4/, your file needs to be in that directory).
If you want to put the file somewhere else, you need to provide Eclipse with the full file path (e.g.,
/courses/MIE250/Pro4/input/myfile.txt) or relative file path (e.g., input/myfile.txt).
If you get tired of making up student-school examples, there is a .zip file of lots of randomly generated
files of students and schools on the main page of the chk pro site.
If you get tired of typing the same file name into your program over and over as you test and debug,
hard-code the full file name and path into your program instead of requiring the user (you) to type it
in. You will save yourself a lot time debugging. Just remember to go back to the user prompt for the
file name before running chk pro or submitting your project.
Here is an example of how to keep time in milliseconds (ms) in Java:
1 long start = System.currentTimeMillis (); // Get current time
2 // do something ...
3 long elapsedTime = System.currentTimeMillis ()-start; // Get elapsed time in ms
Don’t worry if your computation times are not exactly the same as the solution times. The
computation time is not only dependent on the algorithm, but also on the coding style: efficiency of
loops, efficiency of data structures, pre-processing, etc. If your algorithms run faster than the solution
program, Prof. Aleman wants to know, and wants to know if you are interested in doing research!
References
[1] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical
Monthly, 69(1):9–15, 1962.
9
already used!
when the user enters a rank that has already been used while editing a student’s ranking of schools.
ERROR: Input must be an integer in [, ]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of an int,
then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the negative
of the maximum storable value of an int, then “-infinity” is displayed instead of the actual LB
value.
ERROR: Input must be a real number in [, ]!
where LB and UB are lower and upper bounds. If UB is equal to the maximum storable value of a
double, then “infinity” is displayed instead of the actual UB value. Similarly, if LB is equal to the
negative of the maximum storable value of a double, then “-infinity” is displayed instead of the
actual LB value.
5 Required elements
Your project must use the each of the elements described in this section. You can have more functions,
variables, and objects if you want, but you must at least use the elements described in this section.
Failure to correctly implement any of the elements in this section may result in a zero on
the project.
5.1 Variables
An array or ArrayList of Student objects, as defined in Section 5.2
An array or ArrayList of School objects, as defined in Section 5.2
A single SMPSolver object, as defined in Section 5.2
Global public static BufferedReader as the only BufferedReader object in the entire program
for reading user input
5
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
– Although your programs will compile and run just fine on your own computer with multiple
BufferedReader objects, they will not run correctly on a web server with multiple BufferedReader
objects. Since your programs will be graded on a web server, please don’t have more than one
BufferedReader for reading input from the console.
5.2 Classes
You are required to write three classes:
1. Student class to store student data
2. School class to store school data
3. SMPSolver class to run the Gale-Shapley algorithm and store matching results
You can write more classes, and you can add to these classes, but you must at least implement the classes
defined in this section.
1 public class Student {
2 private String name; // name
3 private double GPA; // GPA
4 private int ES; // extracurricular score
5 private int[] rankings; // rankings of schools
6 private int school; // index of matched school
7 private int regret; // regret
8
9 // constructors
10 public Student ()
11 public Student(String name , double GPA , int ES, int nSchools)
12
13 // getters
14 public String getName ()
15 public double getGPA ()
16 public int getES ()
17 public int getRanking(int i)
18 public int getSchool ()
19 public int getRegret ()
20
21 // setters
22 public void setName(String name)
23 public void setGPA(double GPA)
24 public void setES(int ES)
25 public void setRanking(int i, int r)
26 public void setSchool(int i)
27 public void setRegret(int r)
28 public void setNSchools(int n) // set rankings array size
29
30 public int findRankingByID(int ind) // find school ranking based on school ID
31 public void editInfo(ArrayList H, boolean canEditRankings) // user info
32 public void editRankings(ArrayList H, boolean rankingsSet) // edit ranks
33 public void print(ArrayList H) // print student row
34 public void printRankings(ArrayList H) // print the rankings in order
35 public boolean isValid () // check if this student has valid info
36 }
Student Template.java
1 public class School {
2 private String name; // name
6
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
3 private double alpha; // GPA weight
4 private int[] rankings; // rankings of students
5 private int student; // index of matched student
6 private int regret; // regret
7
8 // constructors
9 public School ()
10 public School(String name , double alpha , int nStudents)
11
12 // getters
13 public String getName ()
14 public double getAlpha ()
15 public int getRanking(int i)
16 public int getStudent ()
17 public int getRegret ()
18
19 // setters
20 public void setName(String name)
21 public void setAlpha(double alpha)
22 public void setRanking(int i, int r)
23 public void setStudent(int i)
24 public void setRegret(int r)
25 public void setNStudents(int n) // set rankings array size
26
27 public int findRankingByID(int ind) // find student ranking based on student ID
28 public void editInfo(ArrayList S, boolean canEditRankings) // user info
29 public void calcRankings(ArrayList S) // calculate rankings w/ alpha
30 public void print(ArrayList S, boolean rankingsSet) // print school row
31 public void printRankings(ArrayList S) // print the rankings in order
32 public boolean isValid () // check if this school has valid info
33 }
School Template.java
1 public class SMPSolver {
2 private ArrayList S = new ArrayList (); // suitors
3 private ArrayList R = new ArrayList (); // receivers
4 private double avgSuitorRegret; // average suitor regret
5 private double avgReceiverRegret; // average receiver regret
6 private double avgTotalRegret; // average total regret
7 private boolean matchesExist; // whether or not matches exist
8
9 // constructors
10 public SMPSolver ()
11 public SMPSolver(ArrayList S, ArrayList R)
12
13 // getters
14 public double getAvgSuitorRegret () { return this.avgSuitorRegret; }
15 public double getAvgReceiverRegret () { return this.avgReceiverRegret; }
16 public double getAvgTotalRegret () { return this.avgTotalRegret; }
17 public boolean matchesExist ()
18
19 // reset everything with new suitors and receivers
20 public void reset(ArrayList S, ArrayList R)
21
22 // methods for matching
23 public boolean match () // Gale -Shapley algorithm to match; students are suitors
24 private boolean makeProposal(int suitor , int receiver) // suitor proposes
25 private void makeEngagement(int suitor , int receiver) // make engagement
26 public boolean matchingCanProceed () // check that matching rules are satisfied
7
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
27 public void calcRegrets () // calculate regrets
28 public boolean isStable () // check if a matching is stable
29
30 // print methods
31 public void print () // print the matching results and statistics
32 public void printMatches () // print matches
33 public void printStats () // print matching statistics
34 }
SMPSolver Template.java
5.3 Functions
Function prototypes and short descriptions are provided below. It is your job to determine exactly what
should happen inside each function, though it should be clear from the function and argument names and
function descriptions. You can write more functions (and are strongly recommended to), but you must at
least implement the functions defined in this section.
Only ArrayLists are shown in the function prototypes, but you may always use an array instead of an
ArrayList. If you use arrays, you may pass extra arguments to and from the functions to act as counters.
public static void displayMenu()
Display the menu.
public static int loadStudents(ArrayList S, ArrayList H)
Load student information from a user-provided file and return the number of new students. New
students are added to the list of existing students.
public static int loadSchools(ArrayList H)
Load school information from a user-provided file and return the number of new schools. New schools
are added to the list of existing schools.
public static void editData(ArrayList S, ArrayList H)
Sub-area menu to edit students and schools.
public static void editStudents(ArrayList S, ArrayList H)
Sub-area to edit students. The edited student’s regret is updated if needed. Any existing school
rankings and regrets are re-calculated after editing a student.
public static void editSchools(ArrayList S, ArrayList H)
Sub-area to edit schools. Any existing rankings and regret for the edited school are updated.
public static void printStudents(ArrayList S, ArrayList H)
Print students to the screen, including matched school (if one exists).
public static void printSchools(ArrayList S, ArrayList H)
Print schools to the screen, including matched student (if one exists).
public static int getInteger(String prompt, int LB, int UB)
Get an integer in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value is
entered.
public static double getDouble(String prompt, double LB, double UB)
Get a real number in the range [LB, UB] from the user. Prompt the user repeatedly until a valid value
is entered.
8
MIE250: Fundamentals of object oriented programming
University of Toronto
Prof. Aleman
aleman@mie.utoronto.ca
6 Helpful hints
All the hints from the previous project are still useful, however, the limit on the number of students and
schools is now raised to 2000 students and 2000 schools since the user’s job is now mostly automated.
Note that you can find the ranking of a participant’s match using the participant’s regret. For example,
if a school is with its third-ranked student, its regret is 2. In reverse, if a school has regret 2, it is with
its third-ranked student.
Try to keep your code in SMPSolver as generic as possible, that is,
