CS7200: Algorithm Design and Analysis Assignment 1 Help and Solution

Gale-Shapley Extension for Unequal Number of lists

Objective: Modify and analyze the Gale-Shapley Stable Marriage algorithm to handle cases with unequal number of men and women.

Part A: Implementation [ 60% Points]

Task: Implement the basic Gale-Shapley algorithm as discussed in the class and then extend it to handle cases where the number of men and women are unequal.

Input Format:

Your program must read one file at a time. You need to turn-in multiple files to demonstrate that you have tested your program thoroughly. The input files must be named input.txt, input1.txt, input2.txt, ..., inputN.txt, each structured as follows:

First line: Two integers M and W, the number of men and women respectively.

Next M lines: Each line consisting of a preference list of a man.

Following W lines: Each line consisting of a preference list of a woman.

Example Input (input1.txt):

3 2

m1 w1 w2

m2 w2 w1

m3 w1 w2

w1 m1 m2 m3

w2 m2 m1 m3

Output Format:

Output must be written to files named output.txt, output1.txt, output2.txt, ..., outputN.txt, respectively (whose name you can generate automatically) detailing the stable matches for the corresponding input file as shown below.

Example Output (output1.txt):

m1 w1

m2 w2

NAMING CONVENTIONS: You must name input file, output file, and the Python program file as follows: input.txt, output.txt, assignment1.py for one run. Specifically, make sure that your Python program receives only one argument, the input file (e.g., input.txt), from the command line and generates the output file (e.g., output.txt) 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.

Execution Format:

Your code must be executable with the following command with the appropriate input file (so generate the output file with the correct name): python3 assignment1.py input.txt

Part B: Theoretical Analysis [40% Points]

Task: Write a brief analysis of your extended algorithm, covering the following aspects:

1. Updated Pseudocode: Clearly show the changes made to the original Gale-Shapely algorithm for the “unequal number” case by bold-facing the changes.

2. Complexity Analysis: Analyze the time and space complexity of your extended algorithm, and state it in Big-Oh notation.

General Guidelines:

• Your assignment will be graded on correctness based on the test inputs we will provide, as well as on the documented source code.

• Your code should be well-documented and follow standard coding conventions.

• Reports should be concise, well-structured, and free of grammatical errors.

• Plagiarism in code or report will result in disqualification. (Refer to course policy on academic integrity violation.)

• We require that you submit earlier versions of just your source code assignment1.py as it evolves. So you are required to also submit your “checkpointed” version of the Source code to pilot on a regular basis --1st submission on February 2, 2nd on February 10 and final version on assignment due date February 17. 10% will be allotted for earlier timely submissions.

• Late submission of the final version will be penalized at the rate of 25% per day after the due date.

  
  

Delivery Instructions:

• Submit a ZIP file named Assignment1_GaleShapleyExtension.zip containing:

  • All source code and report PDF.

  • A Testing folder with paired inputn.txt and outputn.txt files (n is the test case number). To be clear, have one copy of input.txt at the top-level and additional test cases inside the Testing Folder.

  • A README.txt file with instructions to compile and run the program (at the top-level of zip-archive). Additionally, include names of all team members, and their email addresses in this document.

• Upload Assignment1_GaleShapleyExtension.zip to Pilot Dropbox folder for Assignment 1.

  
  

Please submit one ZIP file as instructed above per team of up to 3 members (teams can be of size 1, 2, or 3 as you deem fit – team of 4 is disallowed as you can split it into two teams of 2 members each).

[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.

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 until 3 days after the due date on Pilot.

Need Help and Solution?

Please contact for 100% Accurate and Plagiarism free Solution:

WhatsApp : +91 - 995 314 1035

Solution Includes: Plagiarism and AI report with 100% Accuracy.