Programming with
Data Structures and Algorithms


As we have discussed in class, sometimes, check-expect 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 this:

Assume you have n men and n women. Each man wants to marry one woman, and each woman one man. Each woman ranks the men by assigning each one a unique number between 0 and n-1 (i.e., she provides a total ordering of the men). The men rank the women in the same way. A programmer is asked to design and implement a program that generates n pairings of men with women. The program's generated marriages are stable if there are no two people of the opposite sex who would prefer each other to their current partners.

Though the problem wording may make it sound frivolous, 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 women don't rank every man, 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.

The Assignment

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.

By downloading oracle-teachpack.rkt and putting (require "oracle-teachpack.rkt") at the top of your code, you will have access to the following struct and function:

(define-struct: marriage ([woman : Integer] [man : Integer]))

(: matchmaker ((Listof (Listof Integer)) (Listof (Listof Integer)) -> (Listof marriage)))
(define (matchmaker women men) ...)

Given a list of women's rankings and a list of men's rankings, produces a list of stable marriages.

Input-Output Specification

Each purported solution will be a function like matchmaker that consumes two arguments, both of which are (Listof (Listof Integer))s 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 womens' preferences, the second one those for the men (though you should convince yourself it doesn't matter which one is which). Each inner list corresponds to a specific man or woman and contains a list of n numbers, index from 0 to (- n 1), where each number refers to the index of the opposite-sex person in the other list, and the list is sorted in order of preference from greatest to least. The functions generate a list of n marriages, in which the numbers refer to the indices of the men and women in the input lists.

Your assignment has three tasks:

  1. Write a function named generate-input that (surprise, surprise!) 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 men or women. Here's the contract:

    (: generate-input (Integer -> (Listof (Listof Integer))))
  2. Write predicates that will verify the validity of an algorithm's output. Combine all of these into a single predicate:

    (: valid? ((Listof (Listof Integer)) (Listof (Listof Integer)) (Listof marriage) -> Boolean))
  3. Using generate-input and valid?, write a function named oracle that tests whether an algorithm is a valid solution to the stable marriage problem.

    (: oracle (((Listof (Listof Integer)) (Listof (Listof Integer)) -> (Listof marriage)) -> Boolean))

    Remember, an algorithm may sometimes produce a correct solution even if it is an incorrect algorithm. Therefore, your oracle should only return true if an algorithm always produces a stable set of marriages (it is up to you to determine the magnitude of "always").

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.

What to turn in:

A Racket file, oracle.rkt, containing your implementation of the functions described above.