Algorithms Programming Assignment #1

EE360C Algorithms
 Programming Assignment #1

Programming Assignment #1

The goals of this lab are:
• Familiarize you with programming in Java
• Show an application of the stable matching problem
• Understand the difference between the two optimal stable matchings
Problem Description
In this project, you will implement a variation of the stable matching problem adapted from the textbook
Chapter 1, Exercise 4, and write a small report. We have provided Java code skeletons that you will fill in
with your own solution. Please read through this document and the documentation in the starter code
thoroughly before beginning.
Every year, hundreds of engineering students at UT apply for summer internship positions at a variety
of different companies. This process typically involves a stressful trip to the engineering EXPO, tedious
applications, and Zoom-based interviews. Your job is to devise and implement an algorithm to automate
this process based off of the Gale Shapley algorithm presented in class.
There are n prospective interns, each interested in working at one of m companies. Each company has a
set number of positions available, which can vary between companies. Every intern submits their preference list of companies, and every company creates a preference list of interns based on their submitted
resumes. We will assume that there are at least as many interns as the total positions available across all
m companies. This means that all positions will be filled, but some interns may be left unmatched to a
company. The interest lies in finding a way of assigning each intern to at most one company in such a
way that all available positions are filled.
We say that an assignment of interns to companies is stable if neither of the following situations arises:
• First type of instability: There are interns i and i
0
, and a company c, such that
– i is assigned to c, and
Programming Assignment #1: Sep 21, 2021 11:59 PM 2
– i
0
is assigned to no company, and
– c prefers i
0
to i
• Second type of instability: There are interns i and i
0
, and company c and c
0
, so that
– i is assigned to c, and
– i
0
is assigned to c
0
, and
– c prefers i
0
to i, and
– i
0 prefers c to c
0
.
So, we basically have the Stable Matching Problem as presented in class, except that (i) a company generally wants more than one intern, and (ii) there is potentially a surplus of interns. There are several parts
to this problem.
Part 1: Write a report [20 points]
Write a short report that includes the following information:
(a) Give an algorithm in pseudocode (either an outline or paragraph works) to find a stable assignment
that is company optimal.
(b) Give the runtime complexity of your algorithm in (a) in Big O notation and explain why. Note: Full
credit will be given to solutions that have a complexity of O(mn).
(c) Give an algorithm in pseudocode (either an outline or paragraph works) to find a stable assignment
that is intern optimal.
(d) Give the runtime complexity of your algorithm in (c) in Big O notation and explain why. Note:
Try to make your algorithm as efficient as you can, but you will get full credit even if it does
not match the runtime in (b) as long as you clearly explain your runtime and the difficulty of
optimizing it further.
For the programming assignment, you do not need to submit a proof that your algorithm returns a
stable matching, or of intern/company optimality.
Part 2: Implement a Checker to check stability of any given matching [20 points]
Given a Matching object problem, you should implement a boolean function to determine if the pairing of interns to companies (stored in the variable returned by problem.getInternMatching()) is stable or not. Your code will go inside a function called isStableMatching(Matching problem) inside
Program1.java. A file named Matching.java contains the data structure for a matching. Note that
you do not need to optimize the runtime of this function, a brute force approach is sufficient. See the
instructions section for more information on how to test this method.
Part 3: Implement Gale Shapley Algorithm [60 points]
Implement both algorithms from parts (a) (company optimal) and (c) (intern optimal) of your report.
Again, you are provided several files to work with. Implement the function that yields a intern optimal solution stableMatchingGaleShapley_internoptimal() and company optimal solution stableMatchingGaleShapleyinside of Program1.java.
Programming Assignment #1: Sep 21, 2021 11:59 PM 3
Of the files we have provided, please only modify Problem1.java, so that your solution remains compatible with ours. However, feel free to add any additional Java files (of your own authorship) as you see
fit.
Instructions
• Download and import the code into your favorite development environment. We will be grading
in Java 1.8. Therefore, we recommend you use Java 1.8 and NOT other versions of Java, as we can
not guarantee that other versions of Java will be compatible with our grading scripts. It is YOUR
responsibility to ensure that your solution compiles with Java 1.8. If you have doubts, email a TA
or post your question on Piazza.
• If you do not know how to download Java or are having trouble choosing and running an IDE, email
a TA, post your question on Piazza, or visit the TAs during Office Hours.
• Do not add any package statements to your code. Some IDEs will make a new package for you
automatically. If your IDE does this, make sure that you remove the package statements from your
source files before turning in the assignment.
• There are several .java files, but you only need to make modifications to Program1.java. Do
not modify the other files. However, you may add additional source files in your solution if you
so desire. Do not add extra imports to Program1.java; the included imports should be all you
need for your solution. There is a lot of starter code; carefully study the code provided for you,
and ensure that you understand it before starting to code your solution. The set of provided files
should compile and run successfully before you modify them.
• The main data structure for a matching is defined and documented in Matching.java. A Matching object includes:
– m: Number of companies
– n: Number of interns
– company_preference: An ArrayList of ArrayLists containing each of the company’s preferences of interns, in order from most preferred to least preferred. The companies are in order
from 0 to m −1. Each company has an ArrayList that ranks its preferences of interns who are
identified by numbers 0 through n −1.
– intern_preference: An ArrayList of ArrayLists containing each of the intern’s preferences for
companies, in order from most preferred to least preferred. The interns are in order from 0 to
n −1. Each intern has an ArrayList that ranks its preferences of companies who are identified
by numbers 0 to m −1.
– company_positions: An ArrayList that specifies how many positions each company has. The
index of the value corresponds to which company it represents.
– intern_matching: An ArrayList to hold the final matching. This ArrayList (should) hold
the number of the company each intern is assigned to. This field will be empty in the
Matching which is passed to your functions. The results of your algorithm should be stored
in this field either by calling setInternMatching(<your_solution>) or constructing a new
Programming Assignment #1: Sep 21, 2021 11:59 PM 4
Matching(data, <your_solution>), where data is the Matching we pass into the function. The index of this ArrayList corresponds to each intern. The value at that index indicates to which company they are matched. A value of -1 at that index indicates that the
intern is not matched up. For example, if intern 0 is matched to company 55, intern 1 is unmatched, and intern 2 is matched to company 3, the ArrayList should contain {55, -1, 3}. If
using the flag [-bf ], an input with an existing matching can be given to check correctness of
the isStableMatching() function.
• You must implement the methods
– isStableMatching()
– stableMatchingGaleShapley_internoptimal()
– stableMatchingGaleShapley_companyoptimal()
in the file Program1.java. You may add methods to this file if you feel it necessary or useful. You
may add additional source files if you so desire.
• Test cases take the format of text files, which either have the file extension of .in or .extended.in.
Here’s how to interpret each test case, line by line:
– Line 1: m n
– Line 2: m space separated integers, denoting the number of positions available in each company. The first integer represents the number of open positions in company 0, the next integer represents the number for company 1, and so on.
– The next m lines are the preference lists of the companies, where each space-separated integer
represents a intern. The list goes from left to right, from most to least desirable. The first of
these m lines is the preference list for company 0, the next line is for company 1, and so on.
– The next n lines are the preference lists of the interns, where each space-separated integer
represents a company. The list goes from left to right, from most to least desirable. The first
of these n lines is the preference list for intern 0, the next line is for intern 1, and so on.
– Last line (optional): n space separated integers representing a intern-company matching. If
the first integer is x, then the first intern is assigned to company x, the second intern to the
second integer, and so on. This is a way of hard coding in a matching to test your implementation of isStableMatching() in Part 2 before you complete Part 3. To see examples, see the
last lines of the test cases with the file extension .extended.in.
• Driver.java is the main driver program. Use command line arguments to choose between your
checker and your company optimal or intern optimal algorithms and to specify an input file. Use
-gc for company optimal, -gi for intern optimal, and -bf for importing an existing matching (to
check correctness of isStableMatching()). (i.e. java -classpath . Driver [-gc] [-gi]
[-bf] <filename> on a linux machine). As a test, the 3-10-3.in input file should output the
following for both a intern and company optimal solution:
– Intern 0 company -1
– Intern 1 company 1
Programming Assignment #1: Sep 21, 2021 11:59 PM 5
– Intern 2 company -1
– Intern 3 company -1
– Intern 4 company -1
– Intern 5 company -1
– Intern 6 company -1
– Intern 7 company 2
– Intern 8 company 0
– Intern 9 company -1
• When you run Driver.java, it will tell you if the results of your algorithm(s) pass the
isStableMatching() function that you coded for this particular set of data. When we grade your
program, however, we will use our implementation of isStableMatching() to verify the correctness of your solutions.
• Make sure your program compiles on the LRC machines before you submit it.
• We will be checking programming style. A penalty of up to 10 points will be given for poor programming practices (e.g. do not name your variables foo1, foo2, int1, and int2).
"NOTE: To avoid receiving a 0 for the coded portion of this assignment, you MUST ensure that your
code correctly compiles with the original, unmodified starter files on Java 1.8. Do not modify the
signatures of or remove existing methods of Program1.java. Do not add package statements. Do not
add extra imports. You must zip your code using the exact format described below with no spaces. We
recommend testing compilation of your code using the ECE LRC Linux machines (using “javac *.java”
and “java Driver inputfile.in”) after redownloading the starter files from Canvas. We will not be allowing
regrades on this assignment, so please be careful and double check that your final submission is correct.
What To Submit (please read carefully)
You should submit to Canvas a single ZIP file titled pa1_eid_lastname_firstname.zip that contains
Program1.java and any extra .java files you added. Do not submit AbstractProgram1.java,
Driver.java, or Matching.java. Do not put your .java files in a folder before you zip them (i.e.
the files should be in the root of the ZIP archive). Your ZIP file name MUST have the exact format:
pa1_eid_lastname_firstname.zip. Be certain that there are no spaces in your zip file name. Failure
to follow these instructions will result in a penalty of up to 10 points.
Your PDF report should be legibly scanned and submitted to Gradescope. Both your zipped code and
PDF report must be submitted BY 11:59 PM on Tuesday, September 21st, 2021. If you are unable to
complete the assignment by this time, you may submit the assignment late until Friday, September 24th
at 11:59 PM for a 20 point penalty.