CSS 549 – Algorithm Design and Analysis – Program 1 – Due January 16

 

Stable matching

 

1.       Post an introduction on the course message board in the “Introductions” thread.

 

2.       Implement the Gale-Shapley algorithm for stable matching with an O(n2) running time. In our version, people will be adopting pets. Each person will adopt exactly one pet and each pet will be adopted by exactly one person. Both people and pets have preference lists that you will read from a file. The file will  be formatted as follows:

 

Line 1: Number of people/pets (n)

Lines 2 to n+1: Names of people

Lines n+2 to 2n+1: Preference lists of people using indices, not names (n preferences per line)

Lines 2n+2 to 3n+1: Names of pets

Lines 3n+2 to 4n+1: Preference lists of pets using indices, not name (n preferences per line)

 

Your code should implement the algorithm to be people-optimal (each person is given their best valid match).

The file you read from must be named program1data.txt. Here is an example (also posted on the web site):

 

5

Anibel

Belinda

Clark

Delphina

Ernie

2 1 4 5 3

4 2 1 3 5

2 5 3 4 1

1 4 3 2 5

2 4 1 5 3

Dozer

Sassy

Betty

Tiger

Pippy

5 1 2 4 3

3 2 4 1 5

2 3 4 5 1

1 5 4 3 2

4 2 5 3 1

 

Your output should be pairs of names: person / pet (in the order the people are listed in the data file).

Anibel / Dozer

Belinda / Betty

Clark / Sassy

Delphina / Pippy

Ernie / Tiger

 

More details:

1.       You may use either Java or C++. I will be compiling C++ with Visual Studio 2017. Make sure that your code is compatible with this (if you use C++). You may use Java libraries and C++ STL for data structures such as stacks and queues, if you want.

2.       You may work in pairs, but you are not required to. Pairs must both be present when all work is done.

3.       Turn in your code at the assignment dropbox. Each pair should turn in only one set of code, but mark both members’ names clearly in the code. The partner who did not turn in code should submit a comment indicating who turned in the code they worked on.

4.       Your code should be able to handle at least 100 people/pets.

5.       See the posted grading rubric for details on how I grade.