mkse150  Homework 3

Overview

Do these exercises from the E&K textbook: 8.4.1, 8.4.4, 10.7.1, 10.7.11, and 10.7.12. Two programming problems follow below. The paper problems should be handed in at the beginning of class on Mar 21, and the program should be submitted via turnin by midnight the same day.

Programming Background

In this assignment you will be working with two different marketplaces and finding Pareto-optimal assignments of

Your job is to implement these algorithms by editing the files OrganTrade.java, and Matching.java.

Setting up the Project

Download this eclipse project hw3.zip and Import it into Eclipse.
In the Package Explorer, open hw3/src/DefaultPackage.
Highlight DriverOT.java and run it. You should get two dozen lines, ending with this:
0 gets 0
1 gets 1
2 gets 2
3 gets 3
4 gets 4
Now highlight DriverSM.java and run it. You should 20ish lines, ending with this:
1 : X with A : 1
1 : Y with B : 1
1 : Z with C : 1
totals of lostprefs scores: 3 3  sum: 6
passed stability test
This means that you have succeeded to compile and run both provided programs. They are quite independent of each other.

Getting Oriented in the Organ Trade

The file DriverOT.java is simple. It generates three different examples of an organ-trading situation. (Two are currently commented out.) After constructing one of these objects, it will print out the full preference table, call POAssignments (which is what you will be writing), and then print out the assignments you generated.

Open the file OrganTrade.java. Inside the class, you will see these member fields:

	final int prefs[][];	// used to hold the total order of preferences for each patient.
	public final int size;	// number of patients in this exchange.
	enum stat {open,seen,removed}; // names the 3 different states each patient might be in.
	private stat status[];	// used to indicate a status value for each patient as algorithm proceeds.
The prefs double array holds all the preferences of all the players, but you won't have to use this directly. The size variable says how many players there are. The enum stat defines a convenient way of describing the 3 states that players enter as the algorithm proceeds. The status array holds one of those values associated with each of the players. You can find examples of the syntax for using this elsewhere in this file.

Finding the Optimal Assignment

Remember that there is a unique assignment from players to players that is Pareto optimal. Regardless of how you find it, the answers are necessarily the same as those found by the algorithm described in class.

Most of this task is done already. Your job is just to finish writing POAssignment. It has two arrays inside it:

		int assign[]= new int[size];	// will hold the final assignments that get returned
		status= new stat[size];		// holds one status field for each player
		for (int i=0; i<size; i++) status[i]= stat.open;	// initializes everyone to the open state
Next comes the main loop:
	while(true) { // This loop repeatedly searches for a cycle in the preference graph and removes it.
Inside that loop is another one that deals with what to do once a cycle has been found. Your only task is to write that inner loop. What is there now does something a bit wacky: it assigns everyone to herself. Technically that is a legal assignment, but it's not Pareto-optimal. You are to rewrite the innards of that loop to make it find something much better.

When you get your algorithm working, go back to DriverOT and uncomment those lines in main so that you get two more test cases.

Getting Oriented in the Stable Matching Market

The file DriverSM.java is simple. It generates 5 different examples of an organ-trading situation. (All but one are currently commented out.) Each market situation is defined by a set of players, each with a strict ordering on their preferences for players in a second set of players who each have a strict ordering on their preferences for players in the first set of players.

After constructing one of these objects, it will print out the full preference tables, call makeStableMatches (which is what you will be writing) print out the assignments you generated, and then score how well your assignment performs by counting how many of the top choices each player misses. It also runs a stability test on your assignment to determine if there is any pair of players who prefer each other over the matching that you chose for them.

It then calls your program again and this time it reverses the order of the arguments to the constructor. (Presumably, this reverses the role of the groups in your algorithm. If your algorithm is asymmetric in how it deals with the two groups, then you get to see how it performed in both cases.)

Open the file Matching.java. Inside the class, you will see these member fields:

	public final Player[] suitors,recvers;
	public final int size;	// how many player there are in both groups
	public final HashMap index; // a way to retrieve a Player given her name
The two groups of players are stored in arrays called suitors and recvers. The size just keeps the number of members there are in both groups you are given. The index is a useful table that will allow you to look up a Player object when all you have is a String that holds her name.

Finding a Stable Matching

There may be many matchings between players to players that are Pareto optimal. You just have to find any one of them.

Most of this task is done already. Your job is just to finish writing makeStableMatches. It has one line to initialize everyone's current fiancee:

		for (Player p : index.values()) p.fiancee= null;// initially, everyone has no fiancee
Next comes the main loop. What is there now does something arbitrary: it assigns everyone to a mate that has the same index number.
		for (int i=0; i<size; i++) {
			engage(suitors[i], recvers[i]);
		}
Technically that is a legal assignment, but in general it's not Pareto-optimal. You are to rewrite that loop to make it find something much better.

When you get your algorithm working, go back to DriverSM and uncomment the other lines in main so that you get some more test cases.

Finishing up

Use turnin to turn in both these files: OrganTrade.java and Matching.java.