代做CSE 2353程序、代写Java编程、C++, Python语言程序调试

日期：2020-12-07 10:09

CSE 2353 Project

Assigned Nov 4th

Due Dec 5th at 11:59pm

“Stable Marriage” Problem

A well-known problem in the field of Computer Science is known as the “Stable Marriage”

problem. As it was defined, the problem describes a scenario where a set of men and an equally

sized set of women are to be matched up for marriage while taking into account their

preference of partners. In a more general case, this problem can be defined as the following:

Suppose you have two distinct sets of elements, denoted A and B. Both sets have exactly n

elements. Each element in set A is to be paired with another element in set B. Prior to pairing,

all elements in A give high-to-low preference ranking showing which elements in B they want to

be paired with, and vice-versa. A “stable pairing” is a set (denoted S) in which the following

conditions hold true:

1. The set S must be a subset of A x B (cartesian product of A and B)

2. All elements in set A have a corresponding element in set B such that the pair (a, b) is an

element of S

3. All elements in set B have a corresponding element in set A such that the pair (a, b) is an

element of S

4. There are no two pairs (a, b) and (a’, b’) in S such that b’ is higher preference for a than

b, and a is higher preference for b’ than a’ (in this case, since a and b’ both prefer each

other to their assigned match, they will choose to break their match in favor of a match

(a, b’))

5. There are no two pairs (a, b) and (a’, b’) in S such that a’ is higher preference for b than

a, and b is higher preference for a’ than b’ (again, in this case b and a’ would break their

assigned match in favor of a match (a’, b)

For example, consider students in CS 3345 and CS 3353 as two distinct sets of people (assume

that you can’t enroll in both at the same time). Your sets may look like:

A = { “Alex”, “Bob”, “Charles” }

B = { “Devin”, “Erik”, “Frank” }

Where A = CS 3345 and B = CS 3353. A joint project between the two classes requires forming

pairs of students containing one student from each class. Prior to creating pairs, each student

was tasked with defining who they want to work with, in order of high to low preference:

Alex: Devin, Frank, Erik Devin: Charles, Bob, Alex

Bob: Frank, Erik, Devin Erik: Bob, Charles, Alex

Charles: Devin, Erik, Frank Frank: Bob, Alex, Charles

A stable pairing of the two sets of students may look like the following:

Alex & Erik

Bob & Frank

Charles & Devin

This satisfies each constraint. In particular, there are no sets of pairs wherein two people from

different pairs both prefer each other compared to their given partners. For example, while

both Alex and Erik are lowest in each other’s preferences, they are also lower in everyone else’s

preferences compared to their assigned partners. As such, no one will choose to leave their

groups and the pairing is deemed “stable” (perhaps not ideal, but stable nonetheless).

A generic solution to this problem has been defined in a seminal paper by David Gale and Lloyd

Shapley, appropriately named the Gale-Shapley algorithm. You will need to do outside

research on this algorithm in order to complete this project. The original paper is publicly

available and easily found online. Your task is to do some research and theoretical analysis on

how this algorithm works and demonstrate its correctness. Then, you will implement the

algorithm so that it works with some provided constraints.

Theory (40% of grade)

On page 1 of this handout, there are 5 conditions that must be satisfied in order for a set to be

considered a stable match. For each condition, convert it to formal logic. Be explicit and clear

when it comes to defining things like your domains, your predicates, etc. Hint: most of them

contain at least one kind of quantifier.

Then, use the method of proof by contradiction to prove the following:

• If both sets contain n elements, The Gale-Shapley algorithm always results in n pairs.

• The resulting pairs are stable; as in, there are no unstable pairs when the algorithm

finishes.

Additional research will be required to understand and answer the above bullet points. In

relation to the Implementation section below: outline an algorithm that can be used to verify

that a set of matches are in fact stable. Write this algorithm in pseudocode. You will eventually

convert this pseudocode into actual code in the next section.

Your answers must be grouped into a single PDF file. Neatly handwritten or typed responses

are accepted.

Implementation (60% of grade)

Your implementation of the Gale-Shapley algorithm can be done in any of the following

languages: Java, C++, Python, or JavaScript (node). You must implement the algorithms from

scratch.

The following defines some Java-esque pseudocode for building those sets:

class Element {

String name;

List<Element> preferences;

public Element(String name) { … }

public String getName() { … }

public void addPreference(Element pref) { … }

public List<Element> getPreferences() { … }

}

class SetOfElements {

List<Element> elementsInSet;

public SetOfElements() { … }

public void addElement(Element e) { … }

public List<Element> getElements { … }

}

class StableMatchSet {

List<Pair<Element>> matches;

public StableMatchSet() { … }

public void determineMatches(SetOfElements A, SetOfElements B) { … }

public void addMatch(Element a, Element b) { … }

public boolean matchesAreStable() { … }

}

You will likely need to add additional functions / data to complete this project. No matter what

language you choose, your code must have a similar structure, with data types appropriate to

that language. The implementation details are up to you to determine, but in general your

implementation must satisfy the following constraints:

• A Set contains a list / vector / array of Elements. The decision to use a list or vector or

array depends on your choice of programming language.

• An Element contains a string name and a list / vector / array of elements denoting their

hierarchy of preferences. preferences[0] represents the highest priority choice,

preferences[1] represents the second highest priority choice, etc.

• The result of your algorithm must be another Set type, which contains a list / vector /

array of pairs / tuples of elements, each denoting a match.

• That Set type must have a matchesAreStable() function that runs a verification function

to make sure your matches are in fact stable. It returns true if it is stable, false

otherwise. This should be based on the pseudocode you defined in the Theory section.

Your program will call that function after determining a stable match, and the results of

that function call will be printed (see expected output below).

Inputs

Your program will need to read two files, each with the same format. The first line will have a

number n representing the number of elements in the set. Each subsequent n lines will contain

a string, followed by a colon, followed by strings separated by commas. This represents an

element and their preferences ordered from highest to lowest preference. The string before

the colon represents that elements name. The strings separated by commas after the colon

represent the preference list for that element.

So for the example above you would read two files:

SetA.txt

3

Alex:Devin,Frank,Erik

Bob:Frank,Erik,Devin

Charles:Devin,Erik,Frank

SetB.txt

3

Devin:Charles,Bob,Alex

Erik:Bob,Charles,Alex

Frank:Bob,Alex,Charles

You can assume the following about these input files:

• Both files will be well formatted

• They will contain the same number of lines

• The first line will be a number n ³ 3 (no upper limit though)

• The preferences in file A exist as names in file B and vice-versa

• There are no spaces in the files (except for new line characters)

Outputs

Your program is expected to output the following:

• The elements in set A, with their preferences

• The elements in set B, with their preferences

• A stable pairing for those two sets

• The output of your matchesAreStable() function

Sample output is below. Match your output as closely as possible to this output.

Set A contains:

Alex: (Devin, Frank, Erik)

Bob: (Frank, Erik, Devin)

Charles: (Devin, Erik, Frank)

Set B contains:

Devin: (Charles, Bob, Alex)

Erik: (Bob, Alex, Charles)

Frank: (Bob, Alex, Charles)

Stable Pairing:

(Alex, Erik)

(Bob, Frank)

(Charles, Devin)

Result of verification function: true

Submission

In addition to your response for the Theory section and your code for the Implementation

section, you will need to create a README.md file defining how to run your program. If you are

using Java / C++, include instructions for both the compilation command (javac or g++, for

example) and the run command (java or ./a.out, for example). If you are using Python or

JavaScript, then include the appropriate run commands (node or python, for example). Lastly,

include instructions for where to place any additional input files and where in your code the

files are read.

I should be able to copy and paste your commands into a terminal and run your program.

Before you upload, make sure you can do the same. You can assume that I am running recent

versions of all 4 language compilers / runtimes.

You should use test files of various sizes as you develop your algorithm. I will be supplying my

own test files as I grade, which will contain a sizeable number of elements in each set. As such,

make sure you are appropriately stress testing your algorithm. In addition, I will be grading

based on whether or not your output is indeed “stable”.

On canvas, submit a single ZIP file. This zip file will contain the following:

- LastName, FirstName – Project (a single root folder)

o README.md (contains your instructions)

o LastName, FirstName – Theory.pdf (neatly handwritten or typed)

o LastName, FirstName – Implementation (this will be a folder)

Your Implementation folder will contain your source code as well as any input files that you

used in your tests.