MIE250: Fundamentals of object oriented programming
Fundamentals of object oriented programming
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MIE250: Fundamentals of object oriented programming
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
[email protected]
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
[email protected]
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.