Implement Gale-Shapley Algorithm for computing Stable Marriage Assignment

in any language, such as Python/Java only, using the approach

and data structures described in the first two Chapters of the Kleinberg and

Tardos text. The input file should include number of subjects, n, preference list

for men and women one line for each.

n

m1: w11, w12, ..., w1n

...

mn: wn1, wn2, ..., wnn

w1: m11, m12, ..., m1n

...

...

wn: mn1, mn2, ..., mnn

a) Write the output, explicitly checking to see that it is a stable match (It

requires a separate function to check). Turn in sample inputs and

corresponding outputs in separate files.

b) Write a function to create preference lists for men and women. Function

should take number of men (women), say n, create preferences and output

them.

c) Run the algorithm on several instances of the problem for n = 10 with

different input files and plot the variation in the running time.

d) Run the algorithm on several instances of the problem for n = 10 with the

same input file and plot the variation in the running time.

e) Run the algorithm on problem instances with n = 10, 15, 20, 50, 100, and

plot the average running time as a function of the problem input size (n).

NOTE: All questions are not answered in already existing chegg's same question.