写作CSE 2353程序、辅导Java编程

” 写作CSE 2353程序、辅导Java编程CSE 2353 ProjectAssigned Nov 4thDue Dec 5th at 11:59pmStable Marriage ProblemA well-known problem in the field of Computer Science is known as the Stable Marriageproblem. As it was defined, the problem describes a scenario where a set of men and an equallysized set of women are to be matched up for marriage while taking into account theirpreference 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 nelements. 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 tobe paired with, and vice-versa. A stable pairing is a set (denoted S) in which the followingconditions 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 anelement of S3. All elements in set B have a corresponding element in set A such that the pair (a, b) is anelement of S4. There are no two pairs (a, b) and (a, b) in S such that b is higher preference for a thanb, and a is higher preference for b than a (in this case, since a and b both prefer eachother 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 thana, and b is higher preference for a than b (again, in this case b and a would break theirassigned match in favor of a match (a, b)For example, consider Students in CS 3345 and CS 3353 as two distinct sets of people (assumethat you cant 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 formingpairs of students containing one student from each class. Prior to creating pairs, each studentwas tasked with Defining who they want to work with, in order of high to low preference:Alex: Devin, Frank, Erik Devin: Charles, Bob, AlexBob: Frank, Erik, Devin Erik: Bob, Charles, AlexCharles: Devin, Erik, Frank Frank: Bob, Alex, CharlesA stable pairing of the two sets of students may look like the following:Alex ErikBob FrankCharles DevinThis satisfies each constraint. In particular, there are no sets of pairs wherein two people fromdifferent pairs both prefer each other compared to their given partners. For example, whileboth Alex and Erik are lowest in each others preferences, they are also lower in everyone elsespreferences compared to their assigned partners. As such, no one will choose to leave theirgroups 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 LloydShapley, appropriately named the Gale-Shapley algorithm. You will need to do outsideresearch on this algorithm in order to complete this project. The original paper is publiclyavailable and easily found online. Your task is to do some research and theoretical analysis onhow this algorithm works and demonstrate its correctness. Then, you will implement thealgorithm 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 beconsidered a stable match. For each condition, convert it to formal logic. Be explicit and clearwhen it comes to defining things like your domains, your predicates, etc. Hint: most of themcontain 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 algorithmfinishes.Additional research will be required to understand and answer the above bullet points. Inrelation to the Implementation section below: outline an algorithm that can be used to verifythat a set of matches are in fact stable. Write this algorithm in pseudocode. You will eventuallyconvert this pseudocode into actual code in the next section.Your answers must be grouped into a single PDF file. Neatly handwritten or typed responsesare accepted.Implementation (60% of grade)Your implementation of the Gale-Shapley algorithm can be done in any of the followinglanguages: Java, C++, Python, or JavaScript (node). You must implement the algorithms fromscratch.The following defines some Java-esque pseudocode for building those sets:class Element {String name;ListElement Preferences;public Element(String name) { }public String getName() { }public void addPreference(Element pref) { }public ListElement getPreferences() { }}class SetOfElements {ListElement elementsInSet;public SetOfElements() { }public void addElement(Element e) { }public ListElement getElements { }}class StableMatchSet {ListPairElement 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 whatlanguage you choose, your code must have a similar structure, with data types appropriate tothat language. The implementation details are up to you to determine, but in general yourimplementation must satisfy the following constraints: A Set contains a list / Vector / array of Elements. The decision to use a list or vector orarray depends on your choice of programming language. An Element contains a string name and a list / vector / array of elements denoting theirhierarchy 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 functionto make sure your matches are in fact stable. It returns true if it is stable, falseotherwise. 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 ofthat function call will be printed (see expected output below).InputsYour program will need to read two files, each with the same format. The first line will have anumber n representing the number of elements in the set. Each subsequent n lines will containa string, followed by a colon, followed by strings separated by commas. This represents anelement and their preferences ordered from highest to lowest preference. The string beforethe colon represents that elements name. The strings separated by commas after the colonrepresent the preference list for that element.So for the example above you would read two files:SetA.txt3Alex:Devin,Frank,ErikBob:Frank,Erik,DevinCharles:Devin,Erik,FrankSetB.txt3Devin:Charles,Bob,AlexErik:Bob,Charles,AlexFrank:Bob,Alex,CharlesYou 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)OutputsYour 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() functionSample 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: trueSubmissionIn addition to your response for the Theory section and your code for the Implementationsection, you will need to create a README.md file defining how to run your program. If you areusing Java / C++, include instructions for both the compilation command (javac or g++, forexample) and the run command (java or ./a.out, for example). If you are using Python orJavaScript, 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 thefiles 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 recentversions of all 4 language compilers / runtimes.You should use test files of various sizes as you develop your algorithm. I will be supplying myown 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 gradingbased 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 youused in your tests.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com

“