Programming Assignment 9 (20 points + 5 points extra credit)

Due at the beginning of class, Friday, April 20

One section of this assignment, a set of hand evaluation exercises
will be posted early next week.  Start early on the programming
portion of this assignment!

Description of the Problem 

When medical students graduate from medical school, they must apply to
hospitals for residency programs.  Obviously, the students want to get
into the hospital program that best suits their needs, and the
hospitals want to get the best students they can.

The problem, then, becomes how to assign students to hospitals in such
a way that the people/hospitals are as happy as they can be.  We call
this a "stable" relation: no hospital can find another student that it
prefers who also prefers that hospital (or equivalently, no student
can find another hospital that it prefers that also prefers that
student).

We are going to solve a simplied version of the residency matching
problem where we assume that each hospital has exactly one position
and the number of students and hospitals is equal.  (In fact,
most hopitals have several positions and there are more positions
than students.)

Let's look at an example: we'll assume that we have three hospitals
and three students.  Everybody makes a list of their preferences as
such:

Student1	{HospitalA, HospitalC, HospitalB}
Student2	{HospitalA, HospitalC, HospitalB}
Student3	{HospitalA, HospitalB, HospitalC}

HospitalA	{Student3, Student2, Student1}
HospitalB	{Student1, Student3, Student2}
HospitalC	{Student3, Student2, Student1}


An unstable pairing would be:

HospitalA   gets    Student1
HospitalB   gets    Student2
HospitalC   gets    Student3

...because HospitalA would rather have StudentC, and StudentC would
also rather have HospitalA.

A stable pairing would be:

HospitalA   gets    Student3
HospitalB   gets    Student1
HospitalC   gets    Student2

Check for yourself that this is stable.

An obvious question to ask from this is, "will there always be a
stable set of pairings?"  It turns out that the answer is yes, there
will always be an answer, as long as each student and each hospital's
preference list contains all of the possible choices.  A good way
to prove this fact is to formulate an algorithm to solve the problem
proving that that algorithm terminates.

There are several different ways to solve this problem, some more
efficient than others.  Given that we know a stable set of pairings
(relation) exists, we could simply try every
possible set of pairings and return the first one that is stable, much like
our solution to the missionaries and cannibals problem.

However, there is a more much direct and efficient way to solve the
problem that gives some insight about why a stable set of pairings
always exists.  The classic algorithm for solving this problem starts
with the first hospital and tentatively gives it its first pick.  The
algorithm proceeds to the second hospital and assigns it its first
pick.  If the first and second hospitals list the same student as
their top pick, then we need to decide which one gets that student.
Clearly, whichever of the two hospitals is more highly favored by the
student is the one that should get the student.  The algorithm sweeps
through all of the hospitals trying to match each hospital with its
first pick and uses the preferences of the students to settle any
conflicts.

After the initial round, there may be (and probably are) hospitals
that are not paired with a student because they lost their first pick
in a conflict with another hospital. All such hospital participate in
a second round conducted just like the first, except that each
unmatched hospital is tentatively paired with its second pick.  If
that pick is already matched (paired), student preferences are used to
settle the conflict.  Note that hospitals that were tentatively
matched in the first round may be "bumped" in the second round and
placed in the pool of unmatched hospitals.  After the second round,
the number of picks exhausted by each unassigned hospital can vary, so
you must keep track of this information for each hospital.

On each subsequent round, as long as there are unmatched hospitals,
each unmatched hospital tries to match its next unused pick.
The process terminates when there are no more unmatched hospitals.

What guarantees that the computation will reach this termination
condition?  After any hospital uses the kth pick on its list, at least
k students have been matched to hospitals.  Every student that is
"picked" by a particular hospital is matched either with that hospital
or a hospital higher on the students preference list.  Once a student
has been matched, it remains matched, although the assignment (choice
of hospital) may change.  Each such change gives the student an
assignment that he prefers to his former assignment.  If a hospital is
unmatched, the algorithm will keep exploring its choices until they
are exhausted.  When they are exhausted all students must be matched.
Hence the hospital itself must be matched.  (In fact, if a hospital
actually reaches its last pick, that student must be unassigned;
otherwise all students would already be matched!)

What guarantees that the resulting relation (set of pairings) is
stable?  Assume not. Then the relation includes the pairs (Hospital A,
Student 1) and (Hospital B, Student 2) such that Hospital A prefers
Student 2 and Hospital B prefers Student 1.  But Student 2 must appear
on Hospital A's preference list before Student 1.  Hence, Hospital A
"picked" Student 2 but lost that student in a conflict to another
hospital that Student 2 liked better.  Every subsequent change in
Student 2's assignment must be preferred by the student.  Hence,
Student 2 must like Hospital B better than Hospital A, which is a
contradiction.


This, then, is our algorithm:

While some hospitals have no match, peform the following:
  For each hospital H with no match:
  1.  Pair H with its next unused pick S, unless that pick is already 
      paired with a hospital that S preferers.
  2.  If H is paired with S and S was previously paired with another 
      hospital H', then place H' in the pool of unassigned hospitals
      for the next round.
  3.  If H is not paired with S, place H in the pool of unassigned
      hospitals for the next round.


Part A (10 points)

You must use the following data structures to represent the preference
and assignment infomation for hospitals and students:

; a student is a data structure
; (make-student name assignment preferences)
; where name is a symbol
;       assignment is a symbol or false
;	preferences is a vector of symbols

; a hospital is a data structure
; (make-hospital name assignee preferences)
; where name is a symbol
;       assignee is a symbol or false
;	preferences is a vector of symbols

For the "assignment" and "assignee" fields, a false value
indicates that the hospital or student does not yet
have a match.

In the original example, our data structures would look like:

(define list_of_students (vector
(make-student 'Student1	false (vector 'HospitalA, 'HospitalC, 'HospitalB))
(make-student 'Student2	false (vector 'HospitalA, 'HospitalC, 'HospitalB))
(make-student 'Student3	false (vector 'HospitalA, 'HospitalB, 'HospitalC))))

(define list_of_hospitals (vector
(make-hospital 'HospitalA false (vector 'Student3, 'Student2, 'Student1))
(make-hospital 'HospitalB false (vector 'Student1, 'Student3, 'Student2))
(make-hospital 'HospitalC false (vector 'Student3, 'Student2, 'Student1))))


One function we obviously will need is one that tells us the ordinal
position (rank) of a symbol in a student or hospital's list of
preferences -- so that we can answer the question, for example, "who
does 'Student1 prefer?"  Also, we will need some way to look up a name
in a list of students or hospitals and have that person's record
returned.


Your program must include the following two procedures:

; stable-picks: (vector-of student) (vector-of hospital) -> void 
;   (stable-picks los loh) returns void 
;   Effect: destructively modifies the assignment fields of los and
;   the assignee fields of loh to produce a stable pairing of students
;   and hospitals

; print-assignments: (vector-of hospital) -> void
;   (print-assignments loh) returns void
;   Effect: prints the pairings recorded in loh in a table as follows
;	   'HospitalA  gets   'Student1
;	   'HospitalB  gets   'Student2
;          ...etc.

In the stable-picks procedure and its helpers, you will make extensive
use of mutation operators namely set-struct!.  You may not create new
data objects to describe the current pairings of hospitals and
students; you must record this information by mutating the arguments
los and loh.  You may create new data structures to record auxiliary
information for the algorithm (such as how many picks each hospital
has used).

In the print-assignments procedure, use the printf procedure to
produce this listing.


Part B (4 points)

What happens if we let the students pick their assignments instead?
It turns out that with only three hospitals/residents, there's no
difference if one or the other picks first.

However, let's look at an example with _four_ players on
either side:

Ha	{ S4	S3	S2	S1 }
Hb	{ S3	S1	S2	S4 }
Hc	{ S4	S2	S3	S1 }
Hd	{ S1	S2	S4	S3 }

S1	{ Ha	Hc	Hd	Hb }
S2	{ Ha	Hc	Hd	Hb }
S3	{ Hd	Hb	Hc	Ha }
S4	{ Hd	Hb	Ha	Hc }


In this example, you get the following stable pairing if hospitals
picks students:

Ha 	gets	S4
Hb 	gets	S3
Hc 	gets	S2
Hd 	gets	S1

On the other hand, if you let the students pick their hospitals, you
get:

S1	gets	Hc
S2	gets	Ha
S3	gets	Hb
S4	gets	Hd

Write a revised version of your program from Part A where students
choose hospitals rather than vice versa.  

Try some experiments and determine the answer to the following question:
if you were a student, would you want to choose or be chosen, and why?

Part C (Hand Evaluation) (6 points)

Hand evaluate the following programs showing every step.  You may use
ellipsis where the omitted text is obvious.

1.
  (define (make-cons f r)
    (local [(define first f) (define rest r)]
      (lambda (msg)
	(cond [(symbol=? msg 'first)
	       (lambda () first)]
	      [(symbol=? msg 'rest)
	       (lambda () rest)]
	      [(symbol=? msg 'set-first!)
	       (lambda (v) (set! first v))]
	      [(symbol=? msg' set-rest!)
	       (lambda (v) (set! rest v))]))))
  (define (first c) ((c 'first)))
  (define (rest c) ((c' rest)))
  (define (set-cons-first! c v) ((c 'set-first!) v))
  (define (set-cons-rest! c v) ((c 'set-rest!) v))
  (define zeroes (make-cons 0 empty))
  (set-cons-rest! zeroes zeroes)
  (first (rest zeroes))

2. 
  (define-struct Cons (first rest))
  (define zeroes (make-Cons 0 empty))
  (set-Cons-rest! zeroes zeroes)
  (Cons-first (Cons-rest zeroes))

3.
  (define-struct Box (contents))
  (define (swap box1 box2)
    (local [(define temp (Box-contents box1))]
      (begin
	(set-Box-contents! box1 (Box-contents box2))
	(set-Box-contents! box2 temp))))
  (define a (make-Box 'A))
  (define b (make-Box 'B))
  (define c a)
  (begin (swap b c) (Box-contents a))


Part D (Extra Credit) (5 points)

Devise a more efficient representation for the database of students and
hospitals including the preference lists.  (Hint: avoid linear search
where possible.)  Re-implement the same functions that you implemented
in Part A and demonstrate the speed up on a large input.