Gale Shapley Algorithm

UNIVERSITY OF DAYTON Department of Computer Science

CPS 530 - Algorithm Design Fall 2021 Assignment 1 (100 pts)

Due: September 29, 2021 by 11:55pm (50 pts) 1. Implement Gale-Shapley Algorithm for computing Stable Marriage Assignment

in any language, such as Python, Java, C++ or MATLAB, 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 a function to create preference lists for men and women. Function

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

b) 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.

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

f) Run the algorithm on several instances of the problem for n = 10 with the same input file, let a different man start proposing and output the matches.

2. (20 pts) a. Run Gale-Shapley Algorithm and show your steps using the preference lists tables below. Are there any unstable pairs in the final match? b. Modify Gale-Shapley Algorithm such that women will propose instead of men. Show the final match. c. Compare and discuss the matches produced above in terms of men- optimality/women-pessimality and women-optimality/men-pessimality.

(15 pts) 3. Do Problem 3 in Chapter 2 on page 67 of the Kleinberg and Tardos text (given

below). Provide a “clear” explanation in each case.

(15 pts) 4. Do Problem 1 in Chapter 3 on page 107 of the Kleinberg and Tardos text (given

below). Look at solved exercise 1 on page 104 as an example.

You can write your answers for the questions 2 through 4 on paper, scan and create a pdf file.

TURNIN: Bundle your source code, sample inputs/results, timing plots and answers of each question as a single zip archive, name it using ”lastname- firstname” format, and submit to Isidore by the deadline.