Get CS 7200 Algorithm Design and Analysis Fall 2023 Assignment Help:
1) Study Stable Marriable Problem and its solution discussed in class. You are required to implement Gale-Shapley Algorithm in Python 3 using the approach and data structures described in the first two Chapters of Kleinberg and Tardos text and discussed in class/slides (no exceptions). (You may also watch the following video explaining the need to generalize the algorithm further to deal with the practical problem of matching Hospitals and Residency Applicants: https://www.youtube.com/watch?v=kvgfgGmemdA. Note that a hospital can have several slots and not all residency applicants will get a position.) In your solution, make sure:
(a) The input for an n-men-n-women problem is provided as a sequence of (2n+1)- lines (showing the value n on the first line, followed by the encodings of the preference lists – n lines for men and n lines for women) with each line containing spaces-separated list of n+1 totally ordered values formatted as follows:
n
MAN_1 WOMAN_i1 WOMAN_i2 …
…
MAN_n WOMAN_in1 WOMAN_in2 …
WOMAN_1 MAN_j1 MAN_j2 …
…
WOMAN_n MAN_jn1 MAN_jn2 …
For a sample example, consider:
3
Albert Diane Emily Fergie
Bradley Emily Diane Fergie
Charles Diane Emily Fergie
Diane Albert Bradley Charles
Emily Albert Bradley Charles
Fergie Albert Bradley Charles
For additional examples, consult the lecture slide deck.
(b) The format of the output file is as follows showing the matching of MEN to
WOMEN as:
MAN_1 WOMAN_k1
MAN_2 WOMAN_k2
…
MAN_n WOMAN_kn
For the above example, the solution is:
Albert Diane
Bradley Emily
Charles Fergie
(c) NAMING CONVENTIONS: You must name input file, output file, and the Python program file as follows: Input.txt, OutPut.txt, assignment1.py. Make sure that your Python program receives only one argument, the input file, from the command line and generates the output file in the current working directory. Note: The output file name can be automatically generated in accordance with this convention in the same directory. Points will be deducted if you do not follow these naming conventions and file extensions.
In addition to the above three files, you must also create a separate folder called Tests in the current working directory that contains adequate additional tests you have carried out to be convinced that your code works correctly.
Name these files Input1.txt, Output1.txt, Input2.txt, Output2.txt, Input3.txt, Output3.txt, …
In your program, include pseudo-code of the Gale Shapley algorithm as a comment to see the correspondence between the algorithm and the implementing code. As this is a team project, you must program in Python 3.
2) [Not to be turned in] Do Problem 4 in Chapter 2 on Pages 67-68 of the Kleinberg and Tardos text. Justify your ordering of the growth rate functions in each case. You are encouraged to try more exercises and discuss with your peers to improve your understanding.
TURNIN: Upload one zip archive per team of 1, 2 or 3 containing program files (with team member name(s) and email address(es) clearly given in the source code file(s) and any README.txt), Input.txt and Output.txt, as well as additional sample inputs and outputs (in the format shown above, organized in a separate Test directory/folder nested in the top-level directory), to Assignment 1 DropBox on Pilot. (Include only one submission per team called Assignment1.zip. Do not send redundant emails with your files beyond the Pilot submission.)
Grading Criteria: Your assignment will be graded on correctness based on the test inputs we will provide as well as on the documented source code and your tests. Late submissions will be penalized at the rate of 25% / day and no submissions will be accepted after 3 days on Pilot.
We will happy to assist You:
Please call at : +91-995 3141 035
OR Leave a WhatsApp message at : +91 - 995 3141 035 (For quick response)
Solution Includes: AI writing Detection and Plagiarism report with 100% Accuracy.
