Sometimes, a where block just isn’t enough. When you are testing complex functions, or perhaps even relations (as in the case of this assignment), you will need to put time and effort into building testing oracles.
In this assignment, you will develop oracles to test purported solutions to the Stable Marriage Problem. A summary of the problem is as follows:
Assume you have two sets, A and B, each with n members. Every member in A wants to be matched with exactly one member of B and vice versa. Every member of each set ranks its preference for being matched with each member of the other set by assigning each one a unique number between 0 and n-1 (i.e., providing a total ordering of members of the other set).
Our application of this of this problem consists of matching companies to candidates. Each company will keep an internal ranking of how much they would like to hire each candidate (we are assuming that only one candidate will be hired per company). Each candidate also has an opinion about where they want to work and therefore ranks each company as well. A programmer is asked to design and implement a program that generates n pairings of companies with candidates. The program’s generated “hires” are stable if there are no two members of each set that would prefer each other to their current match.
There are many problems of this nature. Consider assigning TAs to classes; matching residents with hospitals; pairing students for homeworks; and much more. Of course, some of these problems represent a slight variation on the theme (maybe the companies don’t rank every candidate, or are allowed to give some of them the same rank; maybe you have only partial information for making the assignment; etc.). Ultimately, however, this problem in its many guises has wide application.
Being confident that your software is correct involves more than just writing code you think is right. However, almost no software complex enough to be useful can be proved correct by hand in a reasonable amount of time. Naturally, a computer scientist’s solution to this problem is to write automated testing. Your job in this assignment is to build an automated testing oracle for a hypothetical solution to the stable marriage problem.
Your oracle’s job is to generate and feed test inputs to this solution, and test the correctness of the output. In the past, you did this by comparing the output to a precomputed correct answer. This assumes two things: that there is only one right answer, and that it is easy for you to find it. In the real world either or both of these can and will be false. (How do you know what the right answer to an arbitrary instance of the problem is if the original problem was to write a program to find it?)
You’ve got your work cut out for you: we give you a correct solution to the stable marriage problem to help you write and test your oracle. You submit your oracle, and we unleash hell’s own fury of incorrect solutions at it, each with its own subtle flaw.
You have access to Hire, hire, is-hire, and matchmaker from the support code:
| hire(company :: Number, candidate :: Number)
fun matchmaker(companies :: List<List<Number>>,
candidates :: List<List<Number>>)
Each purported solution will be a function like matchmaker that consumes two arguments, both of which are List<List<Number>> in which every list (both inner and outer, for both lists) is of the same size (call it n but n is naturally not fixed). The first list provides the companies’ preferences, the second one those for the candidates (though you should convince yourself it doesn’t matter which one is which). Each inner list corresponds to a specific candidate or company and contains a list of n numbers, index from 0 to n-1, where each number refers to the index of members of the other group, and the list is sorted in order of preference from greatest to least. The function generates a list of n hires, in which the numbers refer to the indices of the candidates and hires in the input lists.
To do well on this assignment, you will want to spend time considering all the different ways that output could be either invalid or inconsistent with the original problem statement. Be thorough! That’s the name of the game when testing.
Write a function named generate-input that generates input. Above, we have described only the shapes of the inputs; you will have to infer the constraints we’ve left out. Your function must generate a list of rankings for a specified number of candidates or companies.
fun generate-input(n :: Number) -> List<List<Number>>:
fun is-valid(companies :: List<List<Number>>,
candidates :: List<List<Number>>, m :: List<Hire>)
Using generate-input and is-valid, write a function named oracle that tests whether an algorithm is a valid solution to the stable marriage problem.
Remember, an algorithm may sometimes produce a correct solution even if it is an incorrect algorithm. Therefore, your oracle should try to only return true if an algorithm seems to always produce a stable set of hires (up to some value of “always”).
alg :: (List<List<Number>>, List<List<Number>>
This assignment has an extra initial submission step. By 11:59pm on Monday, you should submit a small set of test cases for the is-valid function.
For example, here is a test for an obviously incorrect match, where the candidates and companies both would prefer to switch:
companies = [list: [list: 0, 1], [list: 1, 0]]
candidates = [list: [list: 0, 1], [list: 1, 0]]
bad-hires = [list: hire(0, 1), hire(1, 0)]
is-valid(companies, candidates, bad-hires) is false
You will submit 5-10 interesting test cases for is-valid by the Monday deadline. After you submit, you will be given three other students’ tests to review, which you should complete by 11:59pm on Tuesday. (Note that you can submit both the tests and your reviews earlier than this, but the deadline makes sure that everyone gets feedback in time to use it before the assignment is due.)
To write the tests, start by copying the two template files below, and write your tests in oracle-sweep.arr. To submit them, first download just your tests by clicking "More / Download this file" from the menu at code.pyret.org, and save it as oracle-tests.arr. Then, visit:
and click on the oracle assignment. This will direct you to upload a file for tests. Select the oracle-tests.arr file you just saved. You will have just one chance to submit your tests, because when you do they will be sent out for review by other students.
Right after submitting, the page should say that the submission was successful, and give you a “Continue” link. Click “Continue” and complete the three reviews of other students’ code. You can complete reviews in any order (and view them all at the same time), but you must complete all three reviews before moving on to the next step.
When you receive reviews from your classmates, you will also be given the ability to submit feedback on the review. This feedback is only for the course staff and has no effect on your grade. We’re interested in hearing if the review was particularly helpful or unhelpful, or if you think it was wrong. Also, if you feel the review you receive is in any way inappropriate, you can flag it to bring the problem to our attention.
Note: Implementation dependent testing should be in the implementation file. The final tests file should contain your tests for the three procedures we had you implement.
Note that there are additional instructions for handing in your initial tests above.
To submit your implementation, return to the Captain Teach assignments page:
and click “Next Step” again. This time, save and then upload a zip file of
both oracle-tests.arr and oracle-code.arr. You can include as many
tests as you want (beyond 10) for this final submission, and you can include
tests you saw while reviewing (but copy with care!—
After you submit your implementation, you’ll have one further step to complete.
We want you to answer a quick two-question survey about what (if any) impact
the peer review process had on your final submission. The interface will look
similar to the review interface, and once you submit your answers to the two
questions there, you’re done. Again, this feedback will have no effect on your