Project #3: Oracle SOlution

Introduction




In this assignment, you will develop an oracle to test purported solutions to the Stable Marriage Problem.




You can learn more about the problem from Wikipedia , but a summary of the problem is as follows:




Assume you have two sets, A and B respectively, 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 order of members of the other set).




For this assignment, imagine matching companies with candidates. Each company will keep an internal ranking of all the candidates, based on who they would prefer to hire (we assume 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 n companies with n candidates. The program’s generated “hires” are stable if there are no two members, one from 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 only have partial information for making the assignment; etc.). Ultimately, however, this problem in its many guises has wide application.




Assignment Overview




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 a given solution and test the correctness of the output. In the past, you did this by comparing the output to a precomputed right 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 of these or both can 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 both a correct and incorrect solution of the stable marriage problem to help you write and test your oracle. You submit your oracle, and we will evaluate its performance in classifying various implementations as correct or incorrect.
















1






Input Output Specification




We have added a number of functions to Ocelot that you can use in this assignment. The first two are the two sample solutions mentioned. They are are wheat1(companies, candidates) and chaff1(companies, candidates) . wheat1 is a correct solution and chaff1 is an incorrect solution. companies and candidates are of type number[][] (i.e array of array of numbers) and represent the preference list of the companies and candidates. companies[i] (i.e. an arbitrary ith element of the companies array) is of type number[] with length n and represents the preference list for the ith company . companies[i][j] would be an integer between 0 and n-1 that refers to the ith company’s jth preference.




Let’s take a companies array of the form [[0, 1], [1, 0]] for example. The 0th element which is the 0th companies preference list, [0, 1] denotes that it prefers the 0th candidate best (because 0 is the first element of the array) and the 1st candidate second. The 1st element of the companies array, [1, 0] denotes that the 1st company prefers the 1st candidate best and 0th candidate second.




Similar to companies[i] , candidates[i] is a number[] of length n that represents the ith candidate’s preference list . candidates[i][j] would be an integer between 0 and n-1 that refers to the ith candidate’s jth preference for one company. Both wheat1 and chaff1 return an array of hires, created using the hire function which is the third function we have added to Ocelot. hire(comp, cand) takes as arguments two numbers, representing the indices of a candidate and a company, and produces an object that stores those indices. The object represents a pairing of one company with one candidate.







function hire(comp, cand) {




return {company: comp, candidate: cand};




}




wheat1 ,the correct solution, produces a set of hires (or in this case, an array of hire objects with a company and a candidate field.) that always obey the stability properties of the stable marriage problem while chaff1 does not necessarily do so. The set of hires returned are not required to be in any particular order. The solutions that we use to evaluate your autograder will follow the same format as these functions.







Programming Task




Write a function called generateInput(n) that generates a number[][] of size n by n that represents a randomly generated preference list, either for companies or candidates. The input generated will be used for testing a given solution. Above, we have described only the shapes of the inputs; you will have to infer the constraints we’ve left out. Make sure that your function always generates random values as it will be helpful to test a given solution with a broad spectrum of input.



Write a function oracle(matchmaker) that takes as input a sample solution to the stable marriage problem, matchmaker and executes a set of tests to evaluate the correctness of that implementation. Remember, an algorithm may sometimes produce a correct solution even if it is


an incorrect algorithm. At the same time, there are numerous ways for an algorithm to return an incorrect solution. A template for the oracle function is included below. 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.







function oracle(matchmaker) {




let numTests = 20; // Change this to some reasonably large value




for (let i = 0; i < numTests; ++i) {




let n = 6; // Change this to some reasonable size let companies = generateInput(n); let candidates = generateInput(n);




let hires = matchmaker(companies, candidates);




test('Hires length is correct', function() { assert(companies.length === hires.length);

});




// Write your tests here




}




}




You can then call oracle on the test inputs with either oracle(wheat1) or oracle(chaff1) .You can press on the “Test” button to run the tests in oracle .Note that this oracle function does not return anything. The goal of oracle is to have all its tests successfully pass when given a correct implementation and at least one test fail when given a faulty implementation.




Generating Random Numbers




This assignment requires you to generate random integers. This can be done using a combination of Math.random() and Math.floor() .







Returns a random int i where min <= i < max function randomInt(min, max) {



return Math.floor(Math.random() * (max - min)) + min;




}




Note: For this assignment and this assignment only, we will be providing full autograder results before the deadline .




Additional Note: Even though your goal for this assignment is to test different implementations of an algorithm, you should still test and verify any helper functions you call within your oracle.

































3