讲解CSE 2353程序、辅导Java编程、C++, Python语言程序调试讲解R语言编程|辅导留学生 Statistics统计、回归、迭代

项目预算：开发周期：发布时间：要求地区：

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 preferences;
public Element(String name) { … }
public String getName() { … }
public void addPreference(Element pref) { … }
public List getPreferences() { … }
}
class SetOfElements {
List elementsInSet;
public SetOfElements() { … }
public void addElement(Element e) { … }
public List getElements { … }
}
class StableMatchSet {
List> 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.

讲解CSE 2353程序、辅导Java编程、C++, Python语言程序调试 讲解R语言编程|辅导留学生 Statistics统计、回归、迭代

讲解CSE 2353程序、辅导Java编程、C++, Python语言程序调试讲解R语言编程|辅导留学生 Statistics统计、回归、迭代